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

*To*: lucier@xxxxxxxxxxxxxxx*Subject*: Really bignums*From*: Aubrey Jaffer <agj@xxxxxxxxxxxx>*Date*: Mon, 8 Aug 2005 13:09:20 -0400 (EDT)*Cc*: bear@xxxxxxxxx, will@xxxxxxxxxxx, srfi-70@xxxxxxxxxxxxxxxxx*Delivered-to*: srfi-70@xxxxxxxxxxxxxxxxx*In-reply-to*: <9f18b20841165beed91bac5cb29c3817@xxxxxxxxxxxxxxx> (message from Bradley Lucier on Sun, 7 Aug 2005 22:34:31 -0500)*References*: <y9ly87s4ud7.fsf@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx> <20050731023754.BBC9F1B77B4@xxxxxxxxxxxxxxxx> <Pine.LNX.4.58.0507302308240.6586@xxxxxxxxxxxxxx> <20050807172151.7647E1B77B4@xxxxxxxxxxxxxxxx> <9f18b20841165beed91bac5cb29c3817@xxxxxxxxxxxxxxx>

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

**References**:**Re: inexactness vs. exactness***From:*William D Clinger

**Re: inexactness vs. exactness***From:*Aubrey Jaffer

**Re: inexactness vs. exactness***From:*bear

**Re: inexactness vs. exactness***From:*Aubrey Jaffer

**Re: inexactness vs. exactness***From:*Bradley Lucier

- Prev by Date:
**Re: inexactness vs. exactness** - Next by Date:
**Re: inexactness vs. exactness** - Previous by thread:
**Re: inexactness vs. exactness** - Next by thread:
**Re: inexactness vs. exactness** - Index(es):