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.

>>24

So we should implement a ``suckless'' bignum library in LISP? But anon, LISP already has bignums. What's the point?

If you feel like creating a better bignum implementation, what better place to play with it than a language which supports bignums? Why dick around with calling library functions instead of directly using immediate built-in syntax?

Besides, C compiler intrinsics are no different than LISP forms that are builtin to the LISP compiler or interpreter, instead of implemented with macros on top of more elementary forms.

Lol, do you even Lisp, bro?

You don't do this with regular macros, you do it with compiler macros and defining new transforms in the intermediate compiler definitions. You can add CPU-specific AVX instructions or whatever as a general toolkit for the compiler to use without having to code entire routines in asm. Lisp lets you hone Lisp to your problem, instead of fighting against the C compiler's fixed assumptions.

In order to get an optimal mapping from a form to machine instructions, the LISP implementer often has to do the job himself, or use some form of brute-force search or genetic algorithm combined with runtime profiling to arrive at the optimal solution.

Bullshit. Type inference carries a long way, and the language passes a higher level of abstraction to the compiler for optimization than C, with a billion times less undefined behavior keeping it cleaner. And if you're talking about high-level human optimization of algorithms and style, that's the same in every single language.