News for hackers. Stuff that matters.
Re:Big Integers in Zig by cup-of-tea on Sunday May 13, 2018 @05:00AM (#17057992)
I had good fun writing my own bignum library many years ago. I initially did it because I was writing a computer algebra system to do symbolic integration and didn't want to include (or maybe didn't know about) libraries like GMP.

On my first attempt I just couldn't figure out how to use the full word for each "big digit". So I ended up using the highest power of ten I could fit in a word as my big digit radix. It took me a while to free myself from decimal notation of numbers. I remember being absolutely blown away by the performance of GMP compared to my implementation.

I revisited it later and that time I could figure out how to use full words (the key I think is knowing how to check for overflows without having access to the overflow flag). I actually started to get closer to GMP performance for addition and subtraction. I then did the core routines in x86-64 assembly which got me so close I was just a constant time off. As this article mentions, though, you need to change the algorithms to get close for multiplication and division, though.

Re:Big Integers in Zig by tiehuis on Sunday May 13, 2018 @05:56AM (#17058141)
It certainly isn't out of reach to get a fairly close speed to GMP implementation-wise if you are willing to optimize the low-level loops in assembly. I think the simple cases are rather straight-forward to reach parity but once you start needing to optimize your algorithm thresholds, it requires much more testing to find the optimal values [1].

It is also easy to overlook how well optimized GMP is across a wide range of less common architectures and chips and I wouldn't be surprised if my particular implementation lost a bit of ground on other architectures like ARM (would be a good thing to test).

[1] https://gmplib.org/devel/thres/