On Sep 28, 2009, at 5:16 PM, David Rush wrote: > Please no. It is far simpler to just provide the O(1) limiting size. > If inexacts are good enough for overflow they're good enough for the > entire computation.
It's a mistake to assume that operations on fixnums are O(1). Your processor might actually take longer for a 32-bit multiply than it does for an addition, increment, compare, or any other operation. It might multiply 8-bit numbers faster than 32-bit numbers. I think there's a fair amount of incorrect assumptions about arithmetic complexity floating around. The bottom line is that multiplication is not O(1), nor is it O(n) in the number of bits in the number. Anyone who has implemented a hardware multiply should know this. You can throw resources at it to do it in parallel, but you could also certainly apply this to bignums using a GPGPU or other parallel processor. Arithmetic is fast on small numbers. Many algorithms are fast on small objects. This is no argument for or against anything. -- Brian Mastenbrook [email protected] http://brian.mastenbrook.net/ _______________________________________________ r6rs-discuss mailing list [email protected] http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
