1

The following program is designed to calculate base^expo mod m.

(define (expmod base expo m)
  (define (square n)
    (* n n))
  (define (even? n)
    (= (remainder n 2) 0))
  (define (expmod-iter base expo m result)
    (cond ((= expo 0) result)
          ((even? expo)
           (expmod-iter base
                        (/ expo 2)
                        m
                        (remainder (square result) m)))
          (else
            (expmod-iter base
                         (- expo 1)
                         m
                         (remainder (* base result) m)))))
  (expmod-iter base expo m 1))

In fact, I'm trying to convert a tail-recursive program from SICP to its iterative equivalent. Here is the original program:

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

The result of (expmod 42 1000000007 1000000007) is 270001056, but according to Fermat's Little Theorem, since 1000000007 is prime, the result should be 42.

What am I doing wrong?

nalzok
  • 14,965
  • 21
  • 72
  • 139
  • Your `base` needs to be squared in the even case. Also, BTW, Scheme provides a built-in `even?` predicate and you don't need to define your own. – C. K. Young Nov 23 '16 at 04:56
  • @ChrisJester-Young After I squared `base` in the even case, things seem to go wrong even in the simplest cases. For example, `(expmod 3 5 8)` would compute to `1`, while `3^5 = 243 = 30*8+3` – nalzok Nov 23 '16 at 05:07
  • 2
    The original recursive function is *not* tail-recursive. –  Nov 23 '16 at 07:25
  • @tfb What's the difference between a tail-recursive process and a iterative process? I think, in [SICP](https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1)'s terminology, the `tailrecsum` function in [this answer](http://stackoverflow.com/a/37010/5399734) is iterative, rather than (tail-)recursive. – nalzok Nov 23 '16 at 07:54
  • @SunQingyao I'm not the right person to ask as I get the terminology wrong, but I think that a tail-recursive function generates an iterative process (in Scheme, anyway, not in Python, say). A tail call is a call whose value is immediately returned as the value of the function making the call. You can see that the calls `expmod` makes to itself above are not tail calls. It's possible to rewrite it so they are, but not in this comment... –  Nov 23 '16 at 10:45
  • Remove the "modulus" parameter so your procedure computes the plain power of `base` and test it. You'll notice that it's incorrect. Fix that first, then reintroduce the modulus. – molbdnilo Nov 24 '16 at 15:22
  • 1
    Clarification: The accumulation of values is "reversed" relative to the original, non tail-recursive version; you have `expmod 2 4 -> expmod-iter 2 4 1 -> expmod-iter 2 2 (square 1) -> expmod-iter 2 1 (square 1)`... – molbdnilo Nov 24 '16 at 15:23
  • @molbdnilo So I have no choice but to square `base` in the even case? I don't really want to do so, because squaring large numbers can be very time-consuming... – nalzok Nov 24 '16 at 16:48

1 Answers1

1

This is my implementation of an iterative expmod:

(define (expmod base exp mod)
  (let loop ((base base)
             (exp exp)
             (result 1))
    (cond ((zero? exp) result)
          ((odd? exp) (loop base (sub1 exp) (modulo (* result base) mod)))
          (else (loop (modulo (sqr base) mod) (quotient exp 2) result)))))

Tested in Racket with your sample input. You'll need to replace sub1 and sqr with suitable implementations if you're not using Racket.

Note that, while you do have to square the base for an even exponent, you can actually mod the result of that, as you can see in my code. So it doesn't get too massive.

C. K. Young
  • 219,335
  • 46
  • 382
  • 435