Optimizing a Bignum Library for Fun

1. oils

   1 272 3,144 9.1 Python

   Oils is our upgrade path from bash to a better language and runtime. It's also for Python and JavaScript users who avoid shell!

   

2. Stream

   getstream.io featured

   Stream - Scalable APIs for Chat, Feeds, Moderation, & Video. Stream helps developers build engaging apps that scale to millions with performant and flexible Chat, Feeds, Moderation, and Video APIs and SDKs powered by a global edge network and enterprise-grade infrastructure.

   

3. LibTomMath

   2 4 729 6.7 C

   LibTomMath is a free open source portable number theoretic multiple-precision integer library written entirely in C.

   

   If you're interested in even more details you could also have a look at Tom's book about bignum arithmetics. C.f. third paragraph of https://github.com/libtom/libtommath#summary

   The library evolved since then, so the algorithm documentation only exists in code nowadays.

   FTR I'm involved in the project as maintainer.

4. bigint

   3 1 33 2.3 C

   Arbitrary precision integer library for C and C++ (by 983)

   

   For maximum efficiency, you should work in binary instead of base 10. Handling carries becomes more straightforward with the right primitives, for example __builtin_addc with GCC: https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins...

   You can also implement it in C if you want a more portable solution: https://github.com/983/bigint/blob/ee0834c65a27d18fa628e6c52...

   If you scroll around, you can also find my implementations for multiplication and such.

5. bignums

   4 1 1 - C

   A project for fun to teach me x86 and ARM

   

   Funny, I did this myself 10 years ago. Shit, it's been that long..?

   For my undergrad project I wrote a computer algebra system to do symbolic integration. The supervisor was a hardcore, old school C guy, so naturally I was going to just C and no libraries. He told me I'd need bignums first, so I got to work (this is because many algorithms like polynomial GCD create massive numbers as they go, even if the inputs and final outputs are generally very small).

   I just couldn't figure out how to better than the largest power of 10 per digit at the time. Working with non base 10 arithmetic was a mind fuck for me at the time. So I did it with digits holding 10^9 and the classical algorithms from Knuth. Division is the hardest!

   At some point I discovered the GNU multiple precision library (GMP) and made my program work with that instead of mine. I was shocked at how much faster GMP was! I finished my project with my own code, but I knew I had to come back to do it better.

   The breakthrough came when I got a copy of Hacker's Delight. It has stuff like how to detect overflow after it's happened (in C). Something twigged and then I just understood how to fill each word completely rather than use a power of 10. I don't know what confused me before.

   But, of course, the real way to do it is to use assembly. You can't get close to high performance in C alone. In assembly you get the overflow bit. It's actually easier in a way! So you write tiny platform specific bits for the digits and build on that in C. My add and subtract were then as fast as GMP. I lost interest when it came to implement faster multiplication algorithms.

   Code in case anyone is interested: https://github.com/georgek/bignums

Suggest a related project