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

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.

*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):