Kodama's home / tips.
Multiply big integers(ruby module)
The module BIG_TIMES is based on Karatsuba's algorithm
and more efficient than standard a*b for big integer.
Download big_times.rb
Example
# sample.rb
require "big_times"
require "elapse"
a=9**100000
Elapse::time{ x=a*a }.print
Elapse::time{ x=BIG_TIMES::times(a,a) }.print
See also elapse.rb to display elapsed time.
Result
% ruby sample.rb
Elapsed_time: 3.620000 # with a * a
Elapsed_time: 0.670000 # with BIG_TIMES::times(a,a)
Followings are Japanese explanations.
Karatsuba のアルゴリズムだが Ruby で記述しているのでかなり遅くなってしまった.
1000 桁程度よりも大きい Integer について, 組み込みの 積 よりも速い.
C でちゃんと記述すると 数百桁程度で効果があるはず.
数千桁以上では, FFT を使う積の方が速いと思われる.
Kodama's home / tips.