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).
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/
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.
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.
12 comments
[ 3.3 ms ] story [ 33.5 ms ] threadPresentation by the Zig author is a good introduction to the concept https://youtu.be/Z4oYSByyRak
While I haven’t had a need for this myself, I believe you can use that feature on nightly today.
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 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/
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.
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.