>
I was recently chatting with someone about algorithms, and we were talking about efficient algorithm for implementing integer division with modulus, and how to make it efficient for large integers.
The following code snippet shows a class that implements two division methods, linear and binary. I wonder if there is a more elegant way to implement binary, please feel free to post to comments if there are. Also, any other faster methods are welcome.
# divide.rb
# Integer Divider Class that implements two algorithms for finding the
# division result and modulus of two integers.
class IntegerDivider
def self.linear n, d
raise 'Cant divide by zero!' if (d == 0)
multiplier = n * d = n)
i -= 1 if (i*d > n)
return multiplier * i, n - i*d, i
end
def self.binary n, d
raise 'Cant divide by zero!' if (d == 0)
multiplier = n * d = n)
return multiplier * i, 0 if (i*d == n)
i /= 2; j = i; cnt = 0
begin
j /= 2; cnt += 1
sign = ((i + j)*d > n) ? 0 : 1
i = i + sign * j
end until (i*d n)
return multiplier * i, n - i*d, cnt
end
def self.divide(how, numerator, denominator)
before = Time.now.to_f
(result, remainder, iterations) = self.send(how, numerator, denominator)
after = Time.now.to_f
puts "#{sprintf('%8.3f',(after - before)*1000)}ms #{how}" +
" (#{sprintf '%10d', iterations} iterations): #{numerator} / " +
" #{denominator} = #{result}, mod #{remainder}"
return [result, remainder]
end
end
[:linear, :binary].each do |method|
ARGV.each do |numerator|
IntegerDivider.divide(method, numerator.to_i, 3)
end
end
And some results of running it. Of course for large number like 100000000, binary search takes 24 iterations to get the answer, while linear … well 100000000. The total speed difference at such large number is big: 1524ms/0.012ms = 127,000.
> ruby divide.rb 10 100 1000 20000 100000000 0.006ms linear ( 3 iterations): 10 / 3 = 3, mod 1 0.003ms binary ( 1 iterations): 10 / 3 = 3, mod 1 0.003ms linear ( 33 iterations): 100 / 3 = 33, mod 1 0.003ms binary ( 5 iterations): 100 / 3 = 33, mod 1 0.017ms linear ( 333 iterations): 1000 / 3 = 333, mod 1 0.004ms binary ( 8 iterations): 1000 / 3 = 333, mod 1 0.411ms linear ( 6666 iterations): 20000 / 3 = 6666, mod 2 0.006ms binary ( 11 iterations): 20000 / 3 = 6666, mod 2 1524.712ms linear ( 33333333 iterations): 100000000 / 3 = 33333333, mod 1 0.012ms binary ( 24 iterations): 100000000 / 3 = 33333333, mod 1
