递归迭代 - 计划到C

Question

能somewone帮我转换这个方案功能：

#lang racket 
(define (powmod2 x e m)  
    (define xsqrm (remainder (* x x) m))  
    (cond [(= e 0) 1]  
     [(even? e) (powmod2 xsqrm (/ e 2) m)]  
     [(odd? e) (remainder (* x (powmod2 xsqrm (/ (sub1 e) 2) m)) m)])) 

进入C中的函数，并且不使用递归即使用迭代。

我不知道'，困扰我的部分是当e很奇怪，然后递归调用在余数函数中。我不知道如何在一个while循环中传输它？任何提示或建议：

这是我迄今为止：因为代码已被写入尾递归

int powmod2(int x, int e, int m) { 
    int i = x; 
    int xsqrm = ((x * x) % m); 
    while (e != 0){ 
     if (e%2 == 0) { 
      x = xsqrm; 
      e = (e/2); 
      xsqrm = ((x * x) % m); 
     } 
     else { 
      i = x; 
      x = xsqrm; 
      e = (e - 1)/2; 
      xsqrm = ((x * x) % m); 

     } 
    } 
    e = 1; 
    return (i*e)%m; 

} 

Answer 1

偶数版本是直截了当这么(powmod2 xsqrm (/ e 2) m)呼叫可以通过更换Ë反复表达一半的e和x的平方m：

int powmod2(int x, int e, int m) { /* version for when e is a power of 2 */ 
    while ((e /= 2) != 0) 
    x = (x * x) % m; 
    return x; 
} 

但是奇数版本没有被递归写尾。一种方法是创建一个使用累加器的辅助方法。这个辅助方法可以被递归地写成尾和偶指数。然后，您可以将其转换为迭代。

Answer 2

由于原始方案代码不是尾递归，因此您无法进行转换。尝试向powmod2添加额外的参数，以便在调用递归函数后，您不需要在奇数情况下通过余数进行乘法运算。

为了说明这一点，它很难loopify以下功能

int fac(n){ 
    if(n == 0) { 
     return 1; 
    }else{ 
     return n * fac(n-1) 
    } 
} 

但是很容易与积累参数loopify版本

int fac(n, res){ 
    if(n == 0) { 
     return res; 
    }else{ 
     return fac(n-1, res*n) 
    } 
} 

int real_fac(n){ return fac(n, 1); } 

Answer 3

或许，如果你要运行一些算法值来查看结果的计算方式，它可以帮助您了解如何转换结果。让我们来看看x=5，e=5和m=7跑单：

1. x=5, e=5, m=7 
    xsqrm=4 
    e:odd => res = 5*...%7 
2. x=4, e=2, m=7 
    xsqrm=2 
    e:even => res = ...%7 
3. x=2, e=1, m=7 
    xsqrm=4 
    e:odd => res = 2*...%7 
4. x=4, e=0, m=7 
    e==0 => res = 1 

res = 5*2%7=3 

在步骤1中，我们得到的结果的部分计算：它是下一步国防部7的5倍，结果在第2步，因为它甚至结果与下一步的结果相同。在步骤3中，我们得到了类似于步骤1的结果。我们上楼的结果是通过将下一个结果乘以2（mod 7再次计算）来计算的。在终止时，我们得到了我们的结果来喂楼上：1.现在，随着我们上升，我们只知道如何计算res：步骤3的2*1%7，步骤2的2，步骤1的2*5%7。

实现它的一种方法是使用堆栈。在每个部分结果中，如果指数是奇数，我们可以将乘法因子推入堆栈，一旦我们终止，我们可以将它们全部乘以。这是转换的天真/欺骗方法。

当您查看上述步骤时，您应该能够看到更有效的方法。关于将所有东西都转换成尾递归的其他答案也是非常好的提示。

Answer 4

最简单的方法是推理什么是原始函数试图计算？这是x对电源e模块m的值。如果您以二进制表示e，则可以获得e = e0 * 1 + e1 * 2 + e2 * 4 + e3 * 8 + ...，其中en为0或1.并且x^n = x * e0 + x^2 * e1 + x^4 * e2 + x^8 * e3 + ...。

通过使用模运算符的数学属性，即。 (a + b) % m = ((a % m) + (b % m)) % m和(a * b) % m = ((a % m) * (b % m)) % m，我们就可以改写为函数：

int powmod2(int x, int e, int m) { 
    // This correspond to (= e 0) 
    int r = 1; 
    while (e != 0) { 
    if (e % 2) { 
     // This correspond to (odd? e) 
     r = (r * x) % m; 
    } 
    // This correspond to the recursive call 
    // that is done whatever the parity of e. 
    x = (x * x) % m; 
    e /= 2; 
    } 
    return r; 
} 

Answer 5

第一步将被写入原计划过程作为尾递归。请注意，这改写作品，因为模运算的性质：

(define (powmod2 x e m) 
    (define (iter x e acc) 
    (let ((xsqrm (remainder (* x x) m))) 
     (cond ((zero? e) acc) 
      ((even? e) (iter xsqrm (/ e 2) acc)) 
      (else (iter xsqrm (/ (sub1 e) 2) (remainder (* x acc) m)))))) 
    (iter x e 1)) 

上述过程的关键要素是，答案在acc参数传递。现在我们有一个尾递归，之后转换到完全迭代的解决方案是非常简单的：

int powmod2(int x, int e, int m) { 
    int acc = 1; 
    int xsqrm = 0; 
    while (e != 0) { 
     xsqrm = (x * x) % m; 
     if (e % 2 == 0) { 
      x = xsqrm; 
      e = e/2; 
     } 
     else { 
      acc = (x * acc) % m; 
      x = xsqrm; 
      e = (e - 1)/2; 
     } 
    } 
    return acc; 
} 

可以进一步优化，比如：

int powmod2(int x, int e, int m) { 
    int acc = 1; 
    while (e) { 
     if (e & 1) { 
      e--; 
      acc = (x * acc) % m; 
     } 
     x = (x * x) % m; 
     e >>= 1; 
    } 
    return acc; 
}