Given: // This pseudocode tries to recursively calculate x^n mod m, // by using

Question

Given:
// This pseudocode tries to recursively calculate x^n mod m,
// by using formula: x^n mod m = (x^(n-1) mod m * x mod m ) mod m
procedure finds(n, x, m: positive integers) {
if x^n < m then
finds(n, x, m) =: x^n
else
finds(n, x, m) =: (x^(n-1) mod m * x mod m ) mod m

}

a) Write out a trace of calls for the following algorithm starting with finds(4,2,5)
b) What do you think this algorithm does? Please summarize input, output, and the function it is calculating. Note that the algorithm may have bugs.
c) Does the algorithm need fixing? If so please enter a fixed version here

Explanation / Answer

(a) 1) finds(4,2,5)--->n=4, x=2, m=5, x^n>m, call finds(n-1,x,m) which is finds(3,2,5) finds(4,2,5)=(finds(3,2,5)*2 mod 5) mod 5 2) call finds(3,2,5)---->n=3,x=2,m=5, x^n>m, call finds(n-1,x,m) which is finds(2,2,5) finds(3,2,5)=(finds(2,2,5)*2 mod 5) mod 5 3) call finds(2,2,5)----> n=2,x=2,m=5, x^n

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---