16 hours ago

my attempt to do the exercises in sicp.

## Saturday, June 28, 2008

### sicp exercise 1.25

; Exercise 1.25. Alyssa P. Hacker complains that we went to a lot of extra work in writing expmod.

; After all, she says, since we already know how to compute exponentials, we could have simply written

;

; (define (expmod base exp m)

; (remainder (fast-expt base exp) m))

;

; Is she correct? Would this procedure serve as well for our fast prime tester? Explain.

; Answer: She is ofcourse wrong. We are not calculating exponentials, we want to calculate the mod

; of a^n by reducing it in terms of mod of a^(n/2).

; Here i want to present my derivation for the procedure expmod

;----------------------------------------------------------------

;

; Question: find a^n mod m

;

; Answer:

; let us begin by finding x*y mod n

; reduce x*y mod n in simpler terms

; assume x,y > n , we can write x and y as follows

; x = Xn + a, where a < n

; y = Yn + b, where b < n

;

; then x*y = XY*n^2 + (aY + bX)n + ab

;

; then,

;

; x*y mod n is equiv to a*b mod n because other terms have a n factor

;

; if y=x then,

;

; x^2 mod n is equiv to a^2 mod n

;

; similarily,

;

; x^m mod n is equiv to a^m mod n is equiv to ((a^m/2 mod n)^2 mod n)

;

; (define (square num) (* num num))

;

; (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))))

;

; (display (expmod 6 7 7))(newline)

;

;----------------------------------------------------------------

Subscribe to:
Post Comments (Atom)

## No comments:

Post a Comment