Title: Report on Challenge 2

Author: Bob Schmidt

Date: 02 March 2018 15:47:19 +00:00 or Fri, 02 March 2018 15:47:19 +00:00

Summary: Francis Glassborow presents the answers to his last challenge and gives us a new one.

Body: 

There was a gratifyingly varied set of solutions offered. Some were ingenious and surprised me. Here are the ones I received together with my comments. At the end you will find my decision as to the ‘winner’ along with my next challenge.

From Alex Kumaila

// Casting to long to avoid assigning a sum that is
// larger than the max signed integer, to a signed
// integer.
long sumInts(const int x, const int y){
  return (long)x + (long)y;
}

void add(const int a, const int b, long *const c){
  if(a<0 && b<0) { // Both negative,

                   // therefore decrement.
    do {
      (*c)--;
    } while(*c > sumInts(a,b));
  } else if((a<0 && b>0)||(a>0 && b<0)) {
// Different signs, therefore decrement to the 
// negative value, and then increment to the 
// positive.
    do {
      (*c)--;
    } while(*c > std::min(a,b)); 
// min(a,b) returns the negative value, 
// given the above predicate.
    do {
      (*c)++;
    } while(*c < sumInts(a,b));
  } else {
// Both positive, including both zero, 
// therefore increment.
    while(*c < sumInts(a,b)){
      (*c)++;
    };
  }
}

int main() {
  static long c;
//Static long initialises to zero.
//Test cases assuming a 4 byte signed integer.
std::cout 
  << "Integer size on repl.it (should be 4): "
  << sizeof(int) << "\n";
//endl doesn't appear to work on repl.it
  add(0,0,&c);
std::cout << "Both zero: " << c << "\n";
  add(1,2,&c);
std::cout << "Sum of two small (+ve) numbers: "
<< c << "\n";
  add(-2147483647,-2147483647,&c);
std::cout << "Both lower (-ve) bound: " << c 
  << "\n";
  add(2147483647,2147483647,&c);
std::cout << "Both upper (+ve) bound: " << c 
  << "\n";
  add(-2147483647,2147483647,&c);
std::cout 
  << "Different signs at lower/upper bound: "
  << c << "\n";
  add(2147483647,-2147483647,&c);
std::cout 
  << "Different signs at upper/lower bound: "
  << c << "\n";
}

FG: The odd reference to repl.it is because the code is loaded there so that you can test it. The link is https://repl.it/repls/WideeyedRepulsiveHoatzin. I leave it to the reader to discover what a Hoatzin is (there really is such a beast).

FG: The code in main tests several corner cases as well as one straight forward addition.

FG: As you can see, this solution is a pure solution that avoids any form of assignment though that is rather severe (and was not intended). It also results in rather long run times for large absolute values of the operands.

Note that the basic solution will work in C if the output lines are rewritten to use printf.

FG: However, the code can have undefined behaviour on any platform where int and long have the same range (allowed by the standard)

From Silas Brown

Hi Francis, please find a response below.

Thanks.

Silas

FG: A great pleasure to see a contribution from you. (For readers who do not know, Silas joined ACCU whilst he was still at school and served as our disabilities officer for many years.)

One obvious way to do assignment without = is to use constructors in C++:

  #include <iostream>
  using namespace std;
  int main() {
    int a(1),b(2);
    int c(a+b);
    cout << c << endl;
  }

Apart from that, C++ before C++17 also supports or_eq as a ‘trigraph’ [ FG: No, that is an alternative token, not a trigraph] for |=, which I’m not sure should qualify for the challenge, because it’s technically the same as using |=, it’s just representing it differently in the source file:

  static int c;
  c or_eq (a+b);

FG: Using the alternative tokens is fine and is one of the solutions I expected someone would come up with. These are still valid in C++ 17. What has been removed is the trigraphs. Those were a ghastly fix C invented to deal with some keyboards that lacked some keys for characters C uses. I heard one person opine that it would have been cheaper to give them all new keyboards than the cost of supporting those rarely used alternatives.

This relies on static being initialised to 0 by default. Without the static, it might work anyway but this is not guaranteed (and it also might result in reformatting your hard drive). The above will not work if the code is called more than once in the same program, unless you first clear c by calling memset() or similar.

FG: Actually you can set a variable to zero by using xor_eq (a xor_eq a will set a to zero). The problem is that you need to initialise variables before use or suffer the potential for undefined behaviour. Static and global variables get default initialised to zero.

FG: Note that what had to be avoided was the = symbol.

In C, you could use simple counting, but it’s inefficient and it destroys the values of a and b:

  #include <stdio.h>
  int main() {
    static int a, b, c;
    a++; b++; b++;  /* so a is 1 and b is 2 */


    /* addition starts here;
       we assume a and b are both > 0 */
    while (a--) c++;
    while (b--) c++;

    printf("%d\n",c);
  }

(The same considerations as above apply re the use of static.)

But I very much prefer a method that does not deconstruct the addition into increments and decrements. You didn’t say if we can use any standard libraries for the addition code; there are two approaches there that spring to mind. One is memset() which I’ve already alluded to: if we are dealing with small numbers that fit into a char, then it’s trivial:

  #include <stdio.h>
  #include <string.h>
  int main() {
    char a, b, c;
    memset(&a, 1, 1);
    memset(&b, 2, 1);
    memset(&c,a+b,1);
    printf("%d\n",c);
  }

But you never said the integers won’t overflow the bounds of char. We could extend the above to larger numbers if we know how the platform represents integers, e.g. on a 32-bit little-endian system:

  #include <stdio.h>
  #include <string.h>
  int main() {
    int a,b,c;
    /* ... set a and b ... */
    memset(&c,(a+b)&0xFF,1);
    memset(((char*)(&c))+1,((a+b)>>8)&0xFF,1);
    memset(((char*)(&c))+2,((a+b)>>16)&0xFF,1);
    memset(((char*)(&c))+3,((a+b)>>24)&0xFF,1);
    printf("%d\n",c);
  }

But I don’t like introducing this dependency on the underlying hardware, nor repeating the addition so much (although an optimising compiler would likely re-use the intermediate result).

The other ‘standard library’ approach that springs to mind is using sprintf and sscanf:

  #include <stdio.h>
  int main() {
    int a,b,c;
    sscanf("1","%d",&a);
    sscanf("2","%d",&b);

    char buf[22]; /* sufficient for 64-bit */

    sprintf(buf,"%d",a+b);
    sscanf(buf,"%d",&c);

    printf("%d\n",c);
  }

But that has the disadvantage of converting to and from a string at runtime (not quite as bad as the counting approach, but not as fast as the C++ solutions).

Finally I have a ‘cheat’ answer, which is to write the C file in the UTF-7 character set, which (similar to the or_eq trigraph) lets you write = without using the '=' byte:

  +ACM include +ADw stdio.h +AD4
  int main() +AHs
    int a +AD0 1 +ADs
    int b +AD0 2 +ADs
    int c +ADs
    c +AD0 a +- b +ADs
    printf ( +ACIAJQ-d+AFw-n+ACI, c) +Ads
  +AH0

This can be compiled with GCC using the -finput-charset=UTF-7 option [FG: Oh! Dear! You can write it but not compile it without using the = key] but only if your GCC has been compiled with the iconv library (which is not the case as standard on every GNU/Linux distribution), and it’s certainly not Standard C, so it ought to be disqualified.

FG: I had wondered about whether something along the lines of your last solution was possible. Thanks for demonstrating that it is, at least using GCC.

Incidentally, this kind of challenge now has a real application in computer museums. For example, the Computing History Museum at Cambridge has a BBC Micro with a broken ‘F’ key. Well, you could exploit a bug in its operating system to program all 10 of its extra function keys to ‘F’ in just 12 keystrokes (type !2832=17937 and press Return), but other machines from the era didn’t have function keys, and if you want to do a live programming demonstration on a restored mainframe with a terminal from the period, it’s entirely possible you’ll have to work around certain keys not working on its keyboard.

FG: Thank you Silas for a comprehensive set of solutions as well as a reason that one might actually need to do something like this (apart from doing exam questions from the dawn of computing)

From Hubert Mathews

Assigning the sum of two integer variables to a third variable without using = is easy in languages that don’t use = for assignment. For instance in R:

  a <- 10 
  b <- 25 
  c <- a+b 
  sprintf("%d + %d is %d", a, b, c) 

or even in COBOL:

  IDENTIFICATION DIVISION.
  PROGRAM-ID. HELLO-WORLD.
  DATA DIVISION.
    WORKING-STORAGE SECTION.
      77 A PIC 99.
      77 B PIC 99.
      77 C PIC 99.
  PROCEDURE DIVISION.
    SET A TO 10.
    SET B TO 25.
    ADD A B GIVING C.
    DISPLAY A " + " B " IS " C.
  STOP RUN.

C++ has ways of initialising variables without using =, specifically using direct initialisation (either the C++98 version with parentheses or the C++11 uniform initialisation syntax with braces):

  #include <iostream>
  int main()
  {
    int a(10);
    int b(25);
    int c(a+b);
    std::cout << a << " + " << b << " is "
              << c << std::endl;
  }

Since these examples use facilities built into the language it hardly seems worth writing tests for them.

Things get more interesting for languages like C that have no obvious way of initialising variables without =:

  #include <assert.h>
  #include <string.h>
  #define SET_VALUE(x, value)       \
    memset(&x, 0, sizeof((x)));     \
    while ((x) < (value)) (x)++;    \
    while ((x) > (value)) (x)--;
  int main()
  {
    int a, b, c;
    SET_VALUE(a, -4);
    SET_VALUE(b, 7);
    SET_VALUE(c, a+b);
    printf("%d + %d is %d\n", a, b, c);
    assert(!(a < -4) && !(a > -4));
    assert(!(b < 7) && !(b > 7));
    assert(!(c < 3) && !(c > 3));
    assert(!(a+b < c) && !(a+b > c));
    return 0;
  }

This sort of code definitely requires tests as it is easy to get wrong. Tests without using = are even more fun and the above code uses the same technique as used by C++’s std::map for determining equality (not less than and not greater than). Using a macro means that there’s no need to worry about accessibility of variables as there would be if using a function.

Which leads to the contortions that are necessary when trying the same in Java:

  public class Add {
    int a, b, c;
    public void calculate() {
      while (a < 6) a++;
      while (a > 6) a--;
      while (b < 7) b++;
      while (b > 7) b--;
      while (c < a+b) c++;
      while (c > a+b) c--;
      System.out.println(String.format(
        "%d + %d is %d", a, b, c));
      assert !(a < 6) && !(a > 6);
      assert !(b < 7) && !(b > 7);
      assert !(c < a+b) && !(c > a+b);
    }
    public static void main(String... args) {
      new Add().calculate();
    }
  }

The variables have to be fields in order that they will be initialised to zero. There is no obvious way of encapsulating the initialisation code into a function as ints are primitives and are passed and returned by value in Java, thus requiring an assignment and so an equals sign. Using boxed java.lang.Integer instead doesn’t help as that would still require an assignment statement.

FG: Thanks for the language tour. I have to confess that I do not understand the Java solution.

From Pete Disdale

Hello Francis,

I will be very interested to see the ‘several simple solutions’ to this challenge – I have thought a fair bit about this and can come up with no more than 3 using only C! And of those, only 1 is a ‘pure’ solution inasmuch as the other 2 likely depend on = somewhere inside the library code. I also excluded asm { .... } code as it’s not in the spirit of the challenge (and it’s not C/C++ either). Perhaps there are more ‘simple’ solutions in C++?

Please see the attached test.c: add1() takes advantage of sscanf by storing the result in an int*, add2() is the ‘pure’ C solution and works because there is no mandate to initialise a variable before use (bad, of course!) and add3() requires a support function, foo().

Out of curiosity, I compiled this with and without optimisation, and whilst I was pleasantly reassured that the expression (a + b) was cached in the optimised code, I was really impressed that the optimiser had completely optimised away the call to memcpy() in foo()! The plain version (expected) is:

  _foo:    pushl    %ebp
    movl    %esp, %ebp
    subl    $24, %esp
    movl    $4, 8(%esp)
    leal    8(%ebp), %eax
    movl    %eax, 4(%esp)
    movl    12(%ebp), %eax
    movl    %eax, (%esp)
    call    _memcpy
    leave 
    ret

whilst the optimised version is:

  _foo:    pushl    %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %edx
    movl    12(%ebp), %eax
    movl    %edx, (%eax)
    popl    %ebp
    ret

(This with a fairly ancient version of gcc too.)

I look forward to reading all the other contributions in the next CVu.

ps. did anybody manage to find a single solution using Java?

test.c

  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>

  int add1(int, int);
  int add2(int, int);
  int add3(int, int);

  int main (int argc, char *argv[])
  {
    /* int a, b; unused */
    if (argc > 2)
    {
      printf ("add1(%s, %s) gives %d\n", argv[1],
        argv[2], add1 (atoi (argv[1]), 
        atoi (argv[2])));
      printf ("add2(%s, %s) gives %d\n", argv[1],
        argv[2], add2 (atoi (argv[1]), 
        atoi (argv[2])));
      printf ("add3(%s, %s) gives %d\n", argv[1],
        argv[2], add3 (atoi (argv[1]), 
        atoi (argv[2])));
    }
    return 0;
  }
  int add1 (int a, int b)
  {   /* use hex for fixed length string, 

         2 chars per byte, no ±, plus 1 for '\0' */

    char s[sizeof(int)*2 + 1];
    int c;
    
    snprintf (s, sizeof(s), "%x", a + b);
    sscanf (s, "%x", &c);
    
    return c;
  }
  int add2 (int a, int b)
  {
    int c;
    
    if (c > a + b)
        while (--c > a + b);
    else if (c < a + b)
        while (++c < a + b);
    return c;
  }
  void foo (int x, int *y)
  {
    // memmove ((unsigned char *) y,
    //(unsigned char *) &x, sizeof(int));
    memcpy (y, &x, sizeof(int));
  }
  int add3 (int a, int b)
  {
    int c;
    foo (a + b, &c);
    return c;
  }

FG: It is amazing what modern optimisers are able to do. With a bit of AI perhaps we can get them to rewrite our entire code to run more efficiently even if the resulting source code is completely incomprehensible to humans. Just joking (or am I?)

From James Holland

Francis uses the word ‘assign’ and so I assume initialisation doesn’t count. That’s a pity because statements something like int c{a + b} would fit the bill. Furthermore, when Francis says “without using the = symbol”, I assume I can’t use |= and its like. This is also a pity because I could have used two statements such as c ^= c; c |= a + b; to assign the sum of a and b to c. This gives me an idea, however. I could use the C++ ‘alternative tokens’.

  c xor_eq c;
  c or_eq a + b;
  c xor_eq ~c;
  c and_eq a + b;

There are other ways of assigning the sum to the variable without using the = symbol, some more useful than others. We can ask the computer user for help.

  while (a + b - c)
  {
    std::cout 
      << "Please type the number followed by Enter"
      << a + b << ' ';
    std::cin >> c;
  }

Possibly not the most efficient method but at least the result can be checked. Instead of using a person, let’s use the file system.

  std::ofstream out_file("file.dat");
  out_file << a + b;
  out_file.close();
  std::ifstream in_file("file.dat");
  in_file >> c;

This is an improvement over the previous attempt, but we need not use the file system. We can use a string stream.

  std::stringstream ss;
  ss << a + b;
  ss >> c;

Another way is to make use of sscanf() as shown below.

  std::string s(std::to_string(a + b));
  sscanf(s.c_str(), "%d", &c);

Perhaps we could keep incrementing the variable until it becomes the required value. This could take quite a while for a variable with a large number of bits!

  while (a + b - c) ++c;

Lastly, many of the standard library algorithms can be persuaded to do the job as well.

  int d{a + b};
  std::swap(c, d);
  
  std::fill(&c, &c + 1, a + b);
  
  std::fill_n(&c, 1, a + b);
  
  int d{a + b};
  std::copy(&d, &d + 1, &c);
  
  std::generate(&c, &c + 1, [a, b](){
    return a + b;});
  
  std::iota(&c, &c + 1, a + b);

FG: I am not sure that any of these are more in the spirit of assignment without using an equals sign than just the simple int c{a+b};.

That said it is remarkable how many standard library functions can be subverted into storing the result of a+b in c.

The Winner is…

Well I am stuck because each of the entrants have strong positives.

• Alex took time to consider the corner cases and write a test to ensure they worked and then placed the test where anyone can see that it works.
• Silas walked us through several solutions and then added a motivation for this kind of problem.
• Hubert gave us a language tour and even provided a solution for Java.
• Pete demonstrated that optimisers can produce something respectable even when our code is pretty crude.
• James offered us a smorgasbord of ways to achieve our objective and actually came up with an effective solution without using initialisation.

So which do you like best? I am going to cheat (like James, asking the user to provide the answer) and ask you, the reader to email me with your choice. I will publish the voting figures in my next Challenge column.

Challenge 3

Here is an old problem that might just be new to some of you. Write a program that outputs its own source code. Please attempt this in C++. There are two categories of solution:

1. A solution that will run on your computer
2. A solution that will run on my computer.

In each case you are allowed to use standard library functions but everything but the output directed to a file must compile to produce the same executable. The first should be easy; the second may prove more challenging.

Notes: 

More fields may be available via dynamicdata ..