[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Really bignums



 | 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
FFT-multiplication.

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