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 FFT-multiplication. So yes; you can do number theory with simple arithmetic algorithms if you are very, very patient. Is that practical?