for review: big ints
Bert Thompson
aet at hydra.cs.mu.oz.au
Sat Apr 4 18:52:19 AEST 1998
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
More information about the developers
mailing list