Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
#46 (Primality Testing)
#1
Quote:46. What is the drawback of the following implementation with respect to primality testing:

Code:
   (define (expmod base exp m)
       (% (fast-expt base exp) m))

  1. fast-expt may overflow in systems with fixed-sized integers
  2. fast-expt is slow for systems with fixed-sized integers
  3. the mod operation should happen before the call to fast-expt
  4. fast-expt already performs the mod operation

I know d is incorrect, as fast-epxt merely calculates an exponential in O(logn) time.

I'm guessing expmod is used in primality testing to calculate what (a^n)%n is. It seems as though the modulo is in the correct place (it's the same in normal notation as "fast-expt(base,exp) % m"). So c seems incorrect.

Fast-expt is just a way of calculating the exponent faster than by repetitive multiplication by using squares efficiently- I'm don't know how fixed-sized integers would play into this.

Help?
UA ACM Vice President
ACM has bi-weekly meetings Tuesdays at 5:15pm
We're UA's best organization for CS majors (website)
Join us on Slack for all kinds of discussion channels (including one for CS403)
Reply
#2
Try it! See how it behaves versus the book's final version of expmod.
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)