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

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

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)
Try it! See how it behaves versus the book's final version of expmod.

Forum Jump:

Users browsing this thread: 1 Guest(s)