From: Artem Voroztsov <artem.voroztsov@...>
Date: 2009-03-17T07:49:20+09:00
Subject: BigNum optimizations

Time for multiplication of BigNums grows quadratically with number of
digits (ruby 1.8.7). And in ruby 1.9 is lower than in ruby 1.8:

require 'benchmark'

Benchmark.bmbm do |b|
  [100, 200, 400, 800, 1600].each do |n|
    num = 1123 ** n
    b.report "#{n}" do
      1000.times{num*num}
    end
  end
end

>ruby -v a.rb
ruby 1.8.7 (2008-08-11 patchlevel 72) [i486-linux]
Rehearsal ----------------------------------------
100    0.010000   0.000000   0.010000 (  0.010418)
200    0.030000   0.000000   0.030000 (  0.036871)
400    0.130000   0.000000   0.130000 (  0.125760)
800    0.460000   0.000000   0.460000 (  0.482740)
1600   1.810000   0.000000   1.810000 (  1.903963)
------------------------------- total: 2.440000sec

           user     system      total        real
100    0.020000   0.000000   0.020000 (  0.008206)
200    0.020000   0.000000   0.020000 (  0.029941)
400    0.120000   0.000000   0.120000 (  0.115787)
800    0.460000   0.000000   0.460000 (  0.459517)
1600   1.770000   0.020000   1.790000 (  1.807655)
>Exit code: 0


$ ruby1.9 -v a.rb
ruby 1.9.0 (2008-06-20 revision 17482) [i486-linux]
Rehearsal ----------------------------------------
100    0.020000   0.000000   0.020000 (  0.013167)
200    0.040000   0.000000   0.040000 (  0.046076)
400    0.150000   0.000000   0.150000 (  0.150487)
800    0.540000   0.010000   0.550000 (  0.589719)
1600   2.200000   0.000000   2.200000 (  2.258581)
------------------------------- total: 2.960000sec

           user     system      total        real
100    0.000000   0.000000   0.000000 (  0.009808)
200    0.040000   0.000000   0.040000 (  0.037194)
400    0.140000   0.000000   0.140000 (  0.144723)
800    0.560000   0.000000   0.560000 (  0.587338)
1600   2.210000   0.000000   2.210000 (  2.254998)
>Exit code: 0


+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?
But why Karatsuba? It is only O(N**1.585)  while Schönhage–Strassen is
O(N log N).

I guess it is more reasonable to implement
http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm
or take use of any GPL soft

See also talk http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/77470
dated 30 Jul 2003

Artem Voroztsov