英文:
How does the Fast Modular Exponentiation Algorithm handle recursive calls?
问题
以下是翻译好的部分：
我已经学习了下面显示的快速模指数算法。
FastExponentiation(a, p, n):
if p = 0 then
return 1
if p is even then
t <- FastExponentiation(a, p/2, n)
return t^2 mod n
t <- FastExponentiation(a, (p-1)/2, n)
return a(t^2 mod n) mod n
第二和第三个return语句如何在运行这个程序时被执行？在这两个语句之前有一个递归调用，所以程序肯定会进入递归循环吗？
英文:
I have been taught the Fast Modular Exponentiation Algorithm as shown below.
FastExponentiation(a, p, n):
if p = 0 then
return 1
if p is even then
t <- FastExponentiation(a, p/2, n)
return t^2 mod n
t <- FastExponentiation(a, (p-1)/2, n)
return a(t^2 mod n) mod n
How do the second and third return statements ever get reached when running this program? There is a recursive call before these two statements so surely the program would just enter a recursive loop?
答案1
得分: 2
以下是翻译好的部分：
这个片段可以说明当进一步进入递归时，p 如何减小，直到变为 1。在下一次递归调用中，它变为零：(1-1)/2 → 0。
function fastExp (a, p, n, level = 0, pExpr = '') {
if (level == 0) {
console.log(`快速幂运算: ${a} ^ ${p} mod ${n}`);
}
console.log(`${' '.repeat(level)}> p = ${pExpr}${p}`);
let res;
if (p == 0) {
res = 1;
}
else if ((p & 1) == 0) {
let t = fastExp(a, p/2, n, level+1, `${p}/2 = `);
res = (t*t) % n;
}
else {
let t = fastExp(a, (p-1)/2, n, level+1, `(${p}-1)/2 = `);
res = (a * ((t*t) % n)) % n;
}
console.log(`${' '.repeat(level)}> ${a} ^ ${p} mod ${n} = ${res}`);
return res;
}
function rand () { return Math.floor(Math.random() * 50) + 50; }
fastExp(rand(), rand(), rand());
英文:
The snippet below can illustrate you how p decreases while going deeper into the recursion, until it becomes 1. On the next recursive call it becomes zero: (1-1)/2 → 0.
<!-- begin snippet: js hide: false console: true babel: false -->
<!-- language: lang-js -->
function fastExp (a, p, n, level = 0, pExpr = '') {
if (level == 0) {
console.log(`Fast exponentiation: ${a} ^ ${p} mod ${n}`);
}
console.log(`${' '.repeat(level)}> p = ${pExpr}${p}`);
let res;
if (p == 0) {
res = 1;
}
else if ((p & 1) == 0) {
let t = fastExp(a, p/2, n, level+1, `${p}/2 = `);
res = (t*t) % n;
}
else {
let t = fastExp(a, (p-1)/2, n, level+1, `(${p}-1)/2 = `);
res = (a * ((t*t) % n)) % n;
}
console.log(`${' '.repeat(level)}> ${a} ^ ${p} mod ${n} = ${res}`);
return res;
}
function rand () { return Math.floor(Math.random() * 50) + 50; }
fastExp(rand(), rand(), rand());
<!-- end snippet -->
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论