designing a suckless bignum library

Let's design a suckless bignum library. (I'm not part of suckless though, just curious about replacing GMP).

I researched a bit into algorithms and the rundown is this:
* long multiplication: O(n^2)
* karatsuba O(n^1.5)
* Toom-Cook, fourier transform based methods - even faster but only used for numbers 10k digits+ long. Much more complex.

So we should probably use karatsuba for all multiplications. Squaring can be done a bit faster than multiplying two different numbers sometimes.

Now I suggest programming it in assembly, that gives you access to the carry bit (C doesn't get you that). Of course we will use libc and the normal C calling conventions so that it's a regular C library.

What to do about memory management? e.g. if you want to add two numbers do we need to allocate a new 'number' as long as the largest to write the result into or do it destructively "x <- x + y"? Maybe the library should support both - then a calculator program would figure out the best primitives to use for a given computation.

It might be nice to also support things like (big modulus) modular arithmetic and polynomials. stuff like exponentiation and modular inverses have interesting algorithms.

What other integer operations would we want? I don't really want to do anything with arb. prec. real numbers - arithmetic with rationals could be done though.

>>96
Right.

So consider an optimizing JIT capable of targetting numerous, modern CPU architecture families and variants, with the ability to auto-vectorize code and generate machine instructions approaching equivalent hand-optimized code, and without requiring a garbage collector or a huge managed-code runtime.

There's only one existing project that I know of that meets that requirement: LLVM. But LLVM is quite a huge dependency, and not everyone likes polluting their system with something that's written in C++. Embedding LLVM as a JIT compiler is going to add 30MB or so to your executable size.

One thing I was thinking of, however, was writing reference implementations of the bignum kernels in LLVM IR or SPIR-V, then use the LLVM compiler to generate GNU assembly files for the different kernel variants. LLVM IR/SPIR-V have bignum and SIMD instructions, so this would get us perhaps 90% of the way there. A little sed/awk magic to glue it all altogether, and maybe a final pass of hand optimizing of the target assembly code for where LLVM is lacking to take things toward perfection.

The final GNU assembler files would then be all that is required to build the library. The LLVM IR/SPIR-V is just there to aid in adding support for a new architecture, and LLVM isn't required as a dependency. You would still ship all of the kernel variants together in the library and do runtime dispatching based on what your CPU supports.