09-03-2017, 10:08 PM

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

- fast-expt may overflow in systems with fixed-sized integers

- fast-expt is slow for systems with fixed-sized integers

- the mod operation should happen before the call to fast-expt

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

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)