Рекурсия к итерации - схема на C

Question

Может ли кто-нибудь помочь мне преобразовать эту схему функции:

#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 нечетно, а затем рекурсивный вызов находится в функции остатка. Я не знаю, как передать это в то время как цикл? любые советы или предложения:

Вот что у меня есть:

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 на половину 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, чтобы вам не нужно было выполнять умножение на остаток в нечетном случае после вызова рекурсивной функции.

Для иллюстрации трудно зацикливать следующую функцию

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

Но версию цикла легко зациклить с параметром накопления

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

Первым шагом будет написание оригинальной процедуры Scheme в виде хвостовой рекурсии. Обратите внимание, что эта перезапись работает из-за свойств модульной арифметики:

(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;
}

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

Возможно, если вы запустите алгоритм с некоторыми значениями, чтобы увидеть, как рассчитывается результат, он может помочь вам понять, как его преобразовать.Давайте посмотрим один прогон для 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 мы получаем частичный расчет для результата: это в 5 раз больше результата следующего шага мод7. На шаге 2, поскольку это даже результат, совпадает с результатом следующего шага.На шаге 3 мы получили что-то похожее на шаг 1. Результат, который мы передадим наверх, рассчитывается путем умножения следующего результата на 2 (снова мод 7).И в конце у нас есть наш результат, чтобы подать наверх: 1. Теперь, когда мы идем вверх, мы просто знаем, как вычислить res: 2*1%7 для шага 3, 2 для шага 2 и 2*5%7 дляШаг 1.

Один из способов реализовать это - использовать стек.При каждом частичном результате, если показатель степени нечетен, мы можем поместить коэффициент умножения в стек, а после завершения мы можем просто умножить их все.Это наивный / читерский метод для конвертации.

Есть более эффективный способ, который вы сможете увидеть, если взгляните на шаги выше.Также другие ответы о преобразовании всего в хвостовую рекурсию - очень хороший совет.