4 ms·

Big Integers in Zig

72 points by AndyKelley 8y ago

Boulth 8y ago
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 https://youtu.be/Z4oYSByyRak
- bluejekyll 8y ago
  Custom allocators are coming in Rust: https://github.com/rust-lang/rfcs/pull/1398 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.
  - Boulth 8y ago
    Excellent, thanks for the direct link to RFC!
cup-of-tea 8y ago
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.
- tiehuis 8y ago
  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/ https://gmplib.org/devel/thres/
tomp 8y ago
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/ https://www.libtom.net/
- cup-of-tea 8y ago
  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.
  - kazinator 8y ago
    > 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.
    - librexpr 8y ago
      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#LGPLStaticVsDynamic https://www.gnu.org/licenses/gpl-faq.html#LGPLStaticVsDynami...
rurban 8y ago
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.
deleted 8y ago
[deleted]

72 points by AndyKelley 8y ago

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 https://youtu.be/Z4oYSByyRak

bluejekyll 8y ago
Custom allocators are coming in Rust: https://github.com/rust-lang/rfcs/pull/1398 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.
- Boulth 8y ago
  Excellent, thanks for the direct link to RFC!

cup-of-tea 8y ago

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.

tiehuis 8y ago
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/ https://gmplib.org/devel/thres/

tomp 8y ago

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/ https://www.libtom.net/

cup-of-tea 8y ago
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.
- kazinator 8y ago
  > 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.
  - librexpr 8y ago
    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#LGPLStaticVsDynamic https://www.gnu.org/licenses/gpl-faq.html#LGPLStaticVsDynami...

rurban 8y ago

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.

deleted 8y ago

[deleted]