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.

Overture - To walk a less harmful path
===============================================================================

It is a well known phenomenon that all great fields of science and higher
thought at a particular point in history reflect the unique nuances and aspects
of culture of their host civilizations. When it comes to the perilous state of
the field of ``Computer Science'' and the software development community at
large, it is no different. One simply has to look at the culture and direction
of the present civilizations that currently hold grip over computing
to understand the source of our predicament.

When a cycle of civilization is reaching its end, it is difficult to achieve
anything by resisting it and by directly opposing the forces in motion. The
``current'' is too strong; one would be overwhelmed. The essential thing is
to not let oneself be impressed by the omnipotence and apparent triumph of the
forces of the epoch. These forces, devoid of connection to any higher princ-
iple, are in fact on a short chain. One should not become fixated on the
present and on things at hand, but keep in view the conditions that may come
about in the future. Thus the principle to follow could be that of letting
the forces and processes of this epoch take their own course, while keeping
oneself firm and ready to intervene when the great behemoths of the software
and computing world--and their supporting base of ignorant users--finally
succumb to irrelevance.

The old Christian saying ``resist not evil'' may have a similar meaning, if
taken in a very particular way. One abandons direct action and retreats to a
more internal position. The perspective offered by the doctrine of cyclical
laws is implicit here. When one cycle closes, another begins, and the point
at which a given process reaches its extreme is also the point at which it
turns in the opposite direction.

But there is still the problem of continuity between the two cycles. To use
an image from the poet Hofmannsthal, the positive solution would be that of a
meeting between those who have been able to stay awake through the long night,
and those who may appear the next morning. But one cannot be sure of this
happening. It is impossible to foresee with certainty how, and on what plane,
there can be any continuity between the cycle that is nearing its end and the
next one.

My assertion that today there is no political system, no software development
community, and no computing methodology whatsoever worth devoting oneself to,
and that everything existing must be denied, likely disconcerts many. However,
this denial and non-commitment do not derive from a lack of principles, but
from the possession of principles, which are precise, solid and not subject to
compromise. In the life of today it can be appropriate, for many, to withdraw
in order to settle in a more interior line of trenches, so that which we cannot
do anything about cannot do anything against us.

However, it should not be encouraged that people let themselves go, but
precisely the contrary: a strict discipline of life and of computing brought
to the highest point should be the foremost aspiration. On this inner,
spiritual plane of the individual, what is required is the opposite of non-
involvement. To draw your attention to the possibility that, before thinking
of outer actions, often dictated by momentary enthusiasms, one should think of
the formation of oneself, the action on oneself, against everything that is
formless, temporary, mediocre and borgeois.

We must thus pay attention to the particular plane of problems that are
oriented inward from the anterior, and moreover, realise that not every
individual we come across can expect to identify himself with modernity.
Perhaps he too is alienated from the present and desires only lucidity and
realism in how he conducts his life and carries out computing. Therein a
common ground can be found. And if there are men willing to fight in spite
of all, even on lost positions, one should be most grateful to them.