From: Robert Feldt <feldt@...>
Date: 2003-05-23T01:25:23+09:00
Subject: Re: Speed Kata: pure-Ruby powmod

On Thu, 22 May 2003, Robert Feldt wrote:

> > Additionally, this enabled the Modulo instances to speedup calculation by
> > caching results.
> >
> On a second note maybe it can have an effect since the "pattern" of
> recursive calls for the version above only depends on p and thus could be
> precomputed in some way. Hmm, I'll investigate, thx.
>
I tried with an iterative version:

  class IterativeBinExpPowMod
    def initialize(p, m)
      @p, @m = p, m
      @msb_pos = (Math.log(p)/Log2).floor
      @mask = 1 << (@msb_pos-1)
    end

    def calc(b)
      return ((m == 1) ? 0 : 1) if p == 0
      mask = @mask
      t = b % m
      while mask > 0
	t = (t * t) % m
	t = ((b * t) % m) if (p & mask) > 0
	mask >>= 1
      end
      t
    end
  end

and it seems to gain a couple of percent in speed vs. the recursive one I
used previously on relevant test data. This one is better though since the
recursive one can cause too deep stack nesting errors with large exponents.

Regards,

Robert