Monday, December 24, 2012

Large integer primitive improvements

Recently we had to go through the large integer primitives because the C type "long" does not mean the same thing in all our 64 bit platforms.  This type was used by the GCD primitives, so we had to go audit that code. Right, that code...

  • The code uses a hybrid of two different multiprecision GCD algorithms from Knuth.
  • Although it seems to work, the code comments do not have a proof for the correctness of the code.
That was an interesting bit of code audit.  The implementation uses Algorithm L, except that the multiprecision division is replaced with a customized implementation of Algorithm B.  It's quite complex because Knuth glosses over what happens when you use signed types to implement these algorithms.  So... why does all this stuff work, exactly?...

In any case, we deleted the usual few hundred LOC, wrote a new ultra paranoid set of tests, and we also produced a proof that says the code should work.  We didn't stop there either: we also threw out a bunch of big endian related code, and we also improved the performance for some of our big endian platforms (up to 25-30% speedup, depending on the use).

Moving along in this department, too...

Update: now up to 37% faster.

No comments: