From: "Florian G. Pflug" <fgp@...>
Date: 2003-05-22T09:56:46+09:00
Subject: Re: Speed Kata: pure-Ruby powmod

On Thu, May 22, 2003 at 08:09:33AM +0900, Robert Feldt wrote:
> Anyway I currently use the simple, recursive and pretty fast
> 
>   # Calculate ((b**p) % m) assuming that b and m are large integers.
>   def Math.power_modulo(b, p, m)
>     if p == 1
>       b % m
>     elsif (p & 0x1) == 0 # p.even?
>       t = power_modulo(b, p >> 1, m)
>       (t * t) % m
>     else
>       (b * power_modulo(b, p-1, m)) % m
>     end
>   end

Wouldn't it be better to define some classes for calculating modulo some
integer?

like

my_ring = Modulo::new(5)
a = my_ring.convert(2)
b = my_ring.convert(3)
c = Modulo::new(4).convert(2)

puts a*b #yields "1 mod 5"
puts a+b #yields "0 mod 5"
puts my_ring.unit / a #yields "3 mod 5"
puts my_ring.unit / b #yields "2 mod 5"
puts Modulo::new(4).unit / c #throws Modulo::InverseDoesNotExist
puts a*c #throws "Modulo::ElementsFromDifferentRings.

The interface can probably be improved... But this seems more like the ruby
way for me.
Additionally, this enabled the Modulo instances to speedup calculation by
caching results.

Finally, there could be class methods in Modulo, like
power_module(a,b,n)
with the semantik you described.

What do you think?

greetings, Florian Pflug