From: Yukihiro Matsumoto Date: 2009-03-17T08:23:39+09:00 Subject: Re: BigNum optimizations Hi, In message "Re: BigNum optimizations" on Tue, 17 Mar 2009 07:49:20 +0900, Artem Voroztsov writes: |+1 for making it faster, i.e. N log N. | |It looks like BigNum will be faster in next release |(http://redmine.ruby-lang.org/search/index/ruby-19?q=Karatsuba), is it |true? True. % ruby -v a.rb ruby 1.8.7 (2008-08-11 patchlevel 72) [i486-linux] Rehearsal ---------------------------------------- 100 0.020000 0.000000 0.020000 ( 0.024290) 200 0.070000 0.000000 0.070000 ( 0.072934) 400 0.120000 0.000000 0.120000 ( 0.123551) 800 0.490000 0.000000 0.490000 ( 0.514302) 1600 1.900000 0.000000 1.900000 ( 1.971061) ------------------------------- total: 2.600000sec user system total real 100 0.010000 0.000000 0.010000 ( 0.015825) 200 0.030000 0.000000 0.030000 ( 0.048896) 400 0.120000 0.000000 0.120000 ( 0.124947) 800 0.480000 0.000000 0.480000 ( 0.490557) 1600 1.900000 0.000000 1.900000 ( 1.905196) % ruby1.9 -v a.rb ruby 1.9.2dev (2009-03-15 trunk 22972) [i686-linux] Rehearsal ---------------------------------------- 100 0.020000 0.000000 0.020000 ( 0.030905) 200 0.040000 0.000000 0.040000 ( 0.045328) 400 0.080000 0.000000 0.080000 ( 0.084670) 800 0.250000 0.000000 0.250000 ( 0.275130) 1600 0.770000 0.000000 0.770000 ( 0.796491) ------------------------------- total: 1.160000sec user system total real 100 0.010000 0.000000 0.010000 ( 0.007731) 200 0.020000 0.000000 0.020000 ( 0.026167) 400 0.070000 0.000000 0.070000 ( 0.092874) 800 0.260000 0.000000 0.260000 ( 0.256951) 1600 0.770000 0.000000 0.770000 ( 0.807816) |But why Karatsuba? It is only O(N**1.585) while Schönhage–Strassen is |O(N log N). It's matter of the resource we have. If some one would volunteer to implement it, we'd love to merge. matz.