[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

BigNum optimizations

Artem Voroztsov

3/16/2009 10:49:00 PM

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 =3D 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=3...), is it
true?
But why Karatsuba? It is only O(N**1.585) while Sch=F6nhage=96Strassen is
O(N log N).

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

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

Artem Voroztsov