BigMath

We interviewed a guy at work last week. In addition to an interview we often either provide a small homework coding assignment or ask to see some sample code. More frequently than I would have guessed, the candidates do not have any sample code to provide. All of their work was proprietary for an employer. No personal projects, I guess. That's hard for me to imagine.

The code I provided for my interview was BigMath (now 4th on Google when searching for BigMath). I originally wrote it as a consequence of wanting to implement some crypto stuff for a software registration key system. Later on I ripped it out of that and set it free.

int
main (int argc, char *argv[])
{
  srandomdev();
  
  bignum_t * num_a = bignum_alloc();
  bignum_t * num_b = bignum_alloc();
  
  while (1)
  {
    int op = rand() % 4;
    
    u_int64_t oofm_a = rand() % 1000;
    u_int64_t oofm_b = rand() % 1000;
    
    bignum_rnd_mag(num_a, oofm_a);
    bignum_rnd_mag(num_b, oofm_b);
    
    switch (op) {
      case 0: test_bignum_add(num_a, num_b); break;
      case 1: test_bignum_sub(num_a, num_b); break;
      case 2: test_bignum_mul(num_a, num_b); break;
      case 3: test_bignum_div(num_a, num_b); break;
    };
  }
  
  bignum_free(num_a);
  bignum_free(num_b);
  
  return EXIT_SUCCESS;
}

I was inspired today to finish up my radix conversion code and add some automated and randomized testing. The test code looks like this:

In short, for each test two random numbers are chosen each of which is less than (4.2x10^9)^1000 (BigMath uses an unsigned 32-bit data type for the radix internally) and then randomly chooses one basic arithmetic operation to test. Each test is verified by using the "opposite" operation. Thus to test a + b = c verification is performed by c - b = a. Similarly, a / b = c rmdr d with c * b + d = a. The result of each test is then printed.

The T indicates true because the verification succeeded. The xxx.xxx number that follows indicates the time that the operation took to execute (in milliseconds). The text that follows is the test and the verification. While the operations themselves are quite precise, when printing the numbers in scientific notation, obviously a lot of precision is lost, so very frequently in the case of addition or subtraction, the sum and difference each appear identical to one of the input values. Yeah, I wasted about an hour of my life trying to figure out what was going on with that.

[T | 000.106] 6.88028x10^403 + 6.9579x10^9506 = 6.9579x10^9506 and 6.9579x10^9506 - 6.9579x10^9506 = 6.88028x10^403

[T | 000.081] 1.0509x10^6828 - 6.5092x10^1511 = 1.0509x10^6828 and 1.0509x10^6828 + 6.5092x10^1511 = 1.0509x10^6828

[T | 044.231] 5.7084x10^7859 * 3.4298x10^3226 = 1.957x10^11086 and 1.957x10^11086 / 3.4298x10^3226 = 5.7084x10^7859 r 0

[T | 044.042] 1.8904x10^7802 / 9.6678x10^6096 = 1.9554x10^1705 r7.9791x10^6096 and 1.9554x10^1705 * 9.6678x10^6096 + 7.9791x10^6096 = 1.8904x10^7802

The operation times above should probably be ignored since I'm only showing a single result for each of the tests - and this is running on my MacBook Air. So, I decided to run each operation numerous times and find out where it averages to. Drum roll:

ADD 000.079ms average for 10,000 operations
SUB 000.084ms average for 10,000 operations
MUL 030.067ms average for 100 operations
DIV 052.050ms average for 100 operations

My radix conversion code isn't very quick (results aren't shown here). Or maybe it is and the numbers are just stupid big. I'll post about that later.

You can get the source code here.