Big Integers in Zig | Hacker News Reader

Big Integers in Zig

tiehuis.github.io

72 pointsAndyKelley11 comments

Open articleView on HN

Zig is really interesting, and the explicit allocators is a feature I miss in many other system languages (like Rust).

Presentation by the Zig author is a good introduction to the concept https://youtu.be/Z4oYSByyRak

Custom allocators are coming in Rust: https://github.com/rust-lang/rfcs/pull/1398

While I haven’t had a need for this myself, I believe you can use that feature on nightly today.

Excellent, thanks for the direct link to RFC!

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.

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/

Karatsuba I'd not that hard to implement, and Toom-3 and then Schönhage-Strassen will also give a huge boost for huge bigints.

Anyone interested in using a big integer library, but unwilling to subject themselves to GMP's viral licence, check out LibTomMath (no affiliation): https://www.libtom.net/

Copyright is viral and copyleft is the cure. But these are just religious issues these days and as such I couldn't convince you to think otherwise.

GMP is available under the LGPL.

> GMP is available under the LGPL.

GMP is not a common system API like POSIX, so if you rely on it, you actually have to bundle GMP, or otherwise handle the dependency.

LGPL is fine for things like standard C and POSIX, because your program is not tied to that LGPL-ed implementation. The GPL itself recognizes "system library" as a special status. It is permissible for GNU programs to depend on proprietary libraries if they are system libraries. Under very similar reasoning, depending on LGPL-ed libraries is okay in an otherwise completely free program if those LGPL-ed libraries are system libraries.

LGPL limits you to dynamic linking, which is gross for this kind of thing. (Have you looked at a dynamic library function call lately?)

If you make a language depend on a LGPL library for numbers, that turns into GPL if you have to build a static image for an embedded system.

This is not a problem with malloc or printf which you just get from that system, rather than by carrying the GNU C Library into your program.

Legally you may be able to get away with adding a LGPLed library to a MIT or BSD program; in practice, licensing is not purely about "what can I legally get away with". What kind of hassles and restrictions will there be factors into it. Also philosophy factors into it: it's ideologically inappropriate for a liberally licensed (BSD, MIT) program to depend on special-purpose, non-system GNU libraries.

You can statically link a LGPL'd library without releasing the whole under the LGPL, but you need to provide a way for the user to modify the library and re-link it. See: https://www.gnu.org/licenses/gpl-faq.html#LGPLStaticVsDynami...

LibTomMath is based on Michael Fromberger's "MPI".

I chose MPI for TXR; LibTomMath, though providing some optimizations like Karatsuba multiplication, just brings in too much cruft.

Quite a few bugs in MPI, but I have a handle on it.

I extended it with bit operations, a faster square root, more conversion routines and such.

http://www.kylheku.com/cgit/txr/log/mpi

I'm familiar with LibTomMath. Tom St. Denis used to post to the comp.lang.c newsgroup years ago. Some 15 years ago I used it (or rather LibTomCrypt, which is based on it) in a commercial project to do some RSA-based authentication on some configuration packets sent to mobile devices.

Reply on news.ycombinator.com