遞歸迭代 - 計劃到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; 
}