for review: big ints

[Bert Thompson]

Thomas Charles CONWAY <conway at cs.mu.OZ.AU> writes:

|Bert Thompson, you write:
| > Gday peoples,
| > 
| > Could someone please review this addition to the library.
| > 
| > Thanks,
| > Bert
| > P.S. The answer to your first question is "because it was there".
| > --------------------

|I wrote an equivalent module quite some time ago, but I never
|included it because multiplication was O(N^2) (as yours is).
|For it to be useful, it really needs the O(NlogN) version which
|is considerably harder to implement.

I disagree. The O(n log n) algorithm is useful only for *huge*
numbers, on the order of hundreds of thousands of digits. (I assume
you mean the Fourier techniques.) Such algorithms are useful
for things like extracting pi to a gadzillion places using
A-G recurrences (such as the Ramanujan-inspired recurrences
used by Borwein a few years ago), but are rarely used otherwise.
(I'm willing to stand corrected on this if anyone knows an
alternative useful application.)

On the other hand, the O(n^(3/2)) Karatsuba(?) algorithm is both useful and
dirt-simple to implement. I didn't do it since I don't want to spend
more time on this module than is strictly necessary.

Bert