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.

>>101
Yes, you can do that. The idea of using LLVM IR or SPIR-V is that the multi-precision arithmetic instructions, vector types, and loop unrolling/vectorization attributes are part of the spec. Doing the equivalent in C would mean using compiler specific extensions. I'd only be bother with supporting GCC and Clang, which isn't a problem for most people, but might be for some.

>>102
I have multiplication and division working where one addend is single word-sized value. Can do roundtrip conversions between strings and bignums now.

https://github.com/suiginsoft/hebimath/blob/master/src/packet/x86_64/mulp_u.S
https://github.com/suiginsoft/hebimath/blob/master/test/unit/get_set.c

I haven't benchmarked anything, there's a lot of room for optimization in how the conversions are done. For example, using shifting for power of two bases, and fixed-point multiplication for the division.

I will try to get to Karatsuba by this weekend (I'm working during the days).

>>103
If you're going to be compiling from source, you'll be able to spend the 5 minutes configuring it to strip out the unneeded kernel variants.