Exercise 1.25

Tue, Dec 1, 2020

This is the 25th question from Sicp. I personally find that this question is really interesting.

The Question

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.

My thoughts

This Question’s meaning is simple - Is this new expmod more efficient than the other ?

To answer this, We are gonna do two things:

Write a procedure to time expmod to prove it again.
Prove this using Order of Growth (Well I’ll try. I suck at Order of Growth)

The Answer

Here’s a procedure that I cooked up in a hurry (I know its not the greatest, but I didn’t have time to work on that):

(define (fast-expt b n)
  (cond ((= n 0) 1)
	((even? n) (square (fast-expt b (/ n 2))))
	(else (* b (fast-expt b (- n 1))))))

(define (expmod2 base exp m)
  (remainder (fast-expt base exp) m))

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

(define (beautify base exp m)
  (newline)
  (display base)
  (display "^")
  (display exp)
  (display " % ")
  (display m)
  (display " = "))

(define (report-expmod elasped-time new-expmod)
  (newline)
  (display "    ")
  (if new-expmod
      (display "new expmod *** ")
      (display "expmod *** "))
  (display elasped-time))

(define (start-expmod-test base exp m new-expmod startime)
  (if new-expmod
      (and (expmod2 base exp m) (report-expmod (- (runtime) startime) #t))
      (and (expmod base exp m)(report-expmod (- (runtime) startime) #f))))

(define (timed-test base exp m)
  (beautify base exp m)
  (display (expmod base exp m))
  (start-expmod-test base exp m #f (runtime))
  (start-expmod-test base exp m #t (runtime)))

Let’s try to use timed-test with some random numbers:

(timed-test 16789 780 17)

16789^780 % 17 = 13
    expmod *** 0.
    new expmod *** 0.
;Unspecified return value

1 (user) => (timed-test 167899823475 7800 17)

167899823475^7800 % 17 = 16
    expmod *** 0.
    new expmod *** 9.999999999990905e-3
;Unspecified return value

1 (user) => (timed-test 1234567890123 123456 123)

1234567890123^123456 % 123 = 42
    expmod *** 0.
    new expmod *** 5.969999999999999
;Unspecified return value

As you can see, it is much slower than expmod. The Question is why ?

Let’s try to do expmod2 manually. First compute fast-expt and then the remainder of the that:

(fast-expt 16789 780)

;Value:
33064861288562614120408180449607187874831671437096310549477846141231603536143246895711002284065407352100347902473705165271152260422378975496230870395606782767815230491701406944014463562084126867429559109443930020395583955324104284165962105889907999323847287423859382428823445171352881381514587825849428659744826672200183280362406797716862159350884691674662515596789371134548566881638974774852287803691115572990780381050798892032305898609992185893867721279499976018935890529735322945813408475833007439541821175059264158036996190277227037999753677784629625690904213184842818788603262922540634564330105512966792332721848517080249191800772933902983580931576195894811771671640609376520215700268189291197389208310928173476946319444430521262726444407235253157010019527410659541429857938367260385215632628708720728158798034268948803139963563146534896321522613601246915894786012185854087799674865366010139140499520892308521118418280572361634151584293912526943680847515198552094836864038647926513350498717859824743980212328568882405704343520410576464101939261495432215272597053707907786499163317403315462954974681569801402430394399237622568141622174742021566306625786114543133218563692376665576692400300152222984851027505011281662659195834670804798711589241303935088352780754080383011557090424963998054646491404444797472530395476058460369168594577147300132492667417197006566047923143327447120850377779761709663854926871881668330977145542829806571608034830281479993905154550841483814099372535206430521423010776603702840837343421302709787487523800106360569846831303776539114624375427605049554780332548125305941870813820111400631411452093653570620588987404684910581005197577551316615948024434730288294054196264726440618004818819383523575109909580798464469087102708911286053202709124144988466127626479332608244159371510453407920888392352900287505779030344035910589710103445213806866936293639202045790395190835891398056896887821934060985531750004583378446051184194531676998236751876953548652548750437699565038164288987486222853906012174291788247047231584932892417853068185224912772992302001997959314343205903524697323357113352689224369124237311423183592841247082845289504392311479880424705968590869083211043449137611334638086479604283283956519625358601629614434937155115289853243706269997748517244433456081001754419159130334698106953215624426891037168227444805069722017512757487701671669244836583537909517090783436694071034789744393274152608470713690731699583792760066626370051166795022087064869738628711913639481715376427012443806449241353350997616746140074026287588954403901100224414193491500320866237259879536430848979074417600899553189555111407845320003378027745339007194469110315521210741508689069676341418166217805956903966383916068040105966921264697417804097939610820508644850177225020705930984526757026141227411913170919551999465739976304267813739196825068073736150691639681127063659944486665500747825226945772850061644720308407435744593079947016590316522951183174922205108588283760823906475232599191776239948766010731845227526639936602625038849718826865192686004460849034740755992987904291703879325634477640420029735173398325311541619991664052179651383458709058400715237439119152351908674157726328165417840945249531249515221788482380933284278613068141418624900851105167811338281229427211767666185334801

Well, that’s a huge number ! And quite obviously finding the remainder of that is not a easy job.

Let’s look at the description of expmod from the 46th foothnote:

The reduction steps in the cases where the exponent e is greater than 1 are based on the fact that, for any integers x , y , and m , we can find the remainder of x times y modulo m by computing separately the remainders of x modulo m and y modulo m , multiplying these, and then taking the remainder of the result modulo m . For instance, in the case where e is even, we compute the remainder of b e/ 2 modulo m , square this, and take the remainder modulo m . This technique is useful because it means we can perform our computation without ever having to deal with numbers much larger than m .

The summary of that is we deal with smaller numbers. Because we compute the remainder every call, we end up with much smaller numbers. This allows for less Memory being taken by the interpreter.

And about the Order of Growth - I have no idea how to explain that using Order of Growth (atleast a way that won’t take all my free time from work)