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

Really bignums

This page is part of the web mail archives of SRFI 70 from before July 7th, 2015. The new archives for SRFI 70 contain all messages, not just those from before July 7th, 2015.

 | 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?