Paul Rubin wrote: > [EMAIL PROTECTED] (Alex Martelli) writes: > > As the author of gmpy, I'd like to point out that the speed difference > > isn't all that large, if all you're doing is ordinary arithmetic -- a > > few times at most (it can be better if you need some of GMP's > > functionality which gmpy exposes, such as primality testing). > > For numbers of this size, won't gmpy use FFT-based multiplication? > That's potentially orders of magnitude faster than ordinary n**2 > multiplication.
Python's native longs use Karatsuba multiplication with is O(n^1.585). My early version of DecInt (BigDecimal) uses 4-way Toom-Cook multiplication which is O(n^1.4). My development version uses Nussbaumer convolution with is O(n ln(n)). For multiplicaiton of two 1,000,000 digits numbers and conversion to a decimal string, here are some times: GMPY multiplication: 0.96 seconds conversion to string: 712.7 seconds DecInt with GMPY multiplication: 1.33 seconds conversion to string: 0.83 seconds DecInt without GMPY multiplication: 2.84 seconds conversion to string: 0.45 seconds Python (using native long) multiplication: 8.47 seconds conversion to string: a really long time Case -- http://mail.python.org/mailman/listinfo/python-list
