| From: Bradley Lucier <xxxxxx@math.purdue.edu>
 | Date: Sun, 7 Aug 2005 22:34:31 -0500
 |
 | On Aug 7, 2005, at 12:21 PM, Aubrey Jaffer wrote:
 |
 | > There is a third way: report a violation of an implementation
 | > restriction when trying to return numbers with more than, say,
 | > 16000 bits.  Practical calculation on numbers larger than that
 | > would need FFT multiplication and other number-theoretic
 | > algorithms, which is a lot of hair to support execution of simple
 | > programming errors.
 |
 | If you're saying that any computations that need more than 16,000
 | bits are simple programming errors, then I'd point you to
 | computational number theorists and others who use much bigger
 | numbers.  It would be good if these problems could be done
 | practically in Scheme.

FFT-multiplication time is O(n*log(n)) while regular multiplication
time is O(n^2).  If I understand big-O notation, for some k > 1000,
products with k or more (base 65536) digits will take hundreds of
times longer to compute using the n^2 algorithm than with
FFT-multiplication.

So yes; you can do number theory with simple arithmetic algorithms if
you are very, very patient.  Is that practical?