Итеративный модуль с повторным вычитанием?

Question

Я пытаюсь написать итеративную процедуру для выполнения арифметики по модулю в схеме без с использованием встроенных процедур по модулю, остатку или /. Однако я столкнулся с несколькими проблемами при попытке написать код, который выглядит, как это до сих пор:

(define (mod a b) 
    (define (mod-iter a b) 
     (cond ((= b 0) 0) 
       ((< b 0) (+ old_b new_b)))) 
    (mod-iter a (- a b))) 

Как вы можете видеть, я столкнулся с проблемой необходимости добавить исходное значение б току значение b. Я не знаю, как это сделать. Кроме того, когда я оставил ответ второго условного выражения примитивными данными (просто чтобы убедиться, что процедура enitre сработала), я получаю ошибку «неопределенное возвращаемое значение», и я не уверен, почему это происходит, потому что остальная часть моего кода (или так кажется?) Заранее благодарю вас за понимание.

Answer 1

Когда вы определяете функцию mod-iter с аргументами (a b), вы затеняете аргументы, определенные в mod. Для того, чтобы избежать затенения, используйте разные идентификаторы, такие, как:

(define (mod a b) 
    (define (mod-iter ax bx) 
    (cond ((= bx 0) 0) 
      ((< bx 0) (+ b bx)))) 
    (mod-iter a (- a b))) 

Заметим, что это не выглядит как правильного алгоритма (не рекурсивный вызов). Как вы обрабатываете общий случай (> bx 0)? Вам нужно что-то вроде:

(define (mod a b) 
    (define (mod-iter ax bx) 
    (cond ((= bx 0) 0) 
      ((< bx 0) (+ b bx)) 
      ((> bx 0) ...)))  ;; <- something here with mod-iter? 
    (mod-iter a (- a b))) 

Answer 2

Прежде всего, если вы не хотите захватывать имя переменной, используйте внутренние имена переменных во внутренней функции. Во-вторых, я считаю, что аргументы неправильны по сравнению со встроенной версией. (по модулю 5 6) равно 5 и (по модулю 6 5) равно 1. В любом случае здесь есть вариация в logrirthmic time. То, что основано на генерации списка степеней b (2 4 8 16 32 ...), равно b, равно 2, вплоть до значения a. Затем оппортунистически вычитая эти обратные значения. Таким образом, проблемы, подобные (mod (expt 267 34) 85), возвращают ответ очень быстро. (несколько сотен примитивных вызовов функций против нескольких миллионов)

(define (mod a-in b-in) 
(letrec ((a (abs a-in)) 
      (sign (if (< 0 b-in) - +)) 
      (b (abs b-in)) 
     (powers-list-calc 
     (lambda (next-exponent) 
      (cond ((> b a) '()) 
      ((= next-exponent 0) 
      (error "Number 0 passed as the second argument to mod 
       is not in the correct range")) 
        (else (cons next-exponent (powers-list (* b next-exponent)))))))) 
    (let ((powers-list (reverse (powers-list-calc b)))) 
     (sign 
    (let loop ((a a) (powers-L powers-list)) 
      (cond ((null? powers-L) a) 
       ((> a (car powers-L)) 
      (loop (- a (car powers-L)) powers-L)) 
       (else (loop a (cdr powers-L)))))))))