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.

If it's already in L1, it's not extra work

You forgot the fact that L1 is shared by all the code running on the CPU, and if your code is taking up some portion of it, it got there by forcing some other code out. Not realising this is why microbenchmarking is stupid. Faster in this small part makes everything else slower.

No, you're wasting everyone's time by forcing them to make sure they pick the correct locale at install time and never change it afterward.

Waiting a lot longer (it adds up really quickly if everyone does this) for each download, along with extracting and installing shit I don't need and probably never will, or an extra second or two of nearly no thought?

l18n string tables are fucking tiny compared to the available space on most systems

"The amount of chemicals we dump into the ocean is fucking tiny compared to the amount of water in there". That didn't turn out so well, did it? It's not just YOU who will be doing it, if you're saying everyone should be.

http://i.stack.imgur.com/yDd8C.png

Look at the size of all the Windows language packs. That's not even all of them and it's 1GB+ already. Do you want to wait for another hour or two, paying for the power and bandwidth, downloading data which is absolutely useless to you?