[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
| From: Bradley Lucier <lucier@xxxxxxxxxxxxxxx>
| 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
So yes; you can do number theory with simple arithmetic algorithms if
you are very, very patient. Is that practical?