| From: Brian Mastenbrook <[email protected]> | Date: Wed, 23 Sep 2009 11:05:35 -0500 | | On Sep 22, 2009, at 4:48 PM, Aubrey Jaffer wrote: | | > My solution was to limit the number of bits in a bignum, in SCM's | > case 16000. Why this limit? Bignum operations have widely varying | > asymptotic time requirements. SCM's multiplication is O(N^2). So | > repeated doubling of a bignum value can quickly generate numbers | > which would outlast anyone's patience to multiply. To the extent | > possible, I want SCM's primitive operations to take bounded time and | > space. | | Maybe this is a counterpoint to the idea that it's possible to | usefully implement bignums in pure Scheme. Of the implementations I | tested with homegrown bignum implementations (in C), most handle | multiplication of bignums up to 2^20 = 1048576 bits without too much | trouble. GMP-based implementations will of course handle much larger | numbers.
In uncontrived programs which use bignums, small integers are used much more than bignums. So although you can improve the time performance of huge multiplications with an external MP package, overall performance will suffer unless the MP package is only used for large numbers. See: "The Distribution of Integer Magnitudes in Polynomial Arithmetic" <http://people.csail.mit.edu/jaffer/CNS/DIMPA> | > 1600 bits is adequate to do any cryptographic calculation for | > the next several years. | | I'm assuming that this was a typo, and you meant 16000 again. Yes, 16000. _______________________________________________ r6rs-discuss mailing list [email protected] http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
