Предел метода факторизации Ферма

Question

Я пытаюсь реализовать факторизацию Ферма ( Алгоритм C в Искусство компьютерного программирования , том 2). К сожалению, в моем издании (ISBN 81-7758-335-2) этот алгоритм напечатан неправильно. какое должно быть условие на фактор-внутренний цикл ниже? Я запускаю цикл до тех пор, пока y <= n [передается как предел]. </p>

(if (< limit y) 0 (factor-inner x (+ y 2) (- r y) limit))

Есть ли способ вообще избежать этого условия, так как оно удвоит скорость цикла?

(define (factor n) 
  (let ((square-root (inexact->exact (floor (sqrt n))))) 
    (factor-inner (+ (* 2 square-root) 1)
                  1 
                  (- (* square-root square-root) n)
                  n)))

(define (factor-inner x y r limit)
  (if (= r 0)
    (/ (- x y) 2)
    (begin 
      (display x) (display " ") (display y) (display " ") (display r) (newline)
      ;;(sleep-current-thread 1)
      (if (< r 0)
        (factor-inner (+ x 2) y (+  r x) limit)
        (if (< limit y)
          0
          (factor-inner x (+ y 2) (- r y) limit))))))

Answer 1

Проверка (< limit y) не требуется, поскольку в худшем случае алгоритм в конечном итоге найдет следующее решение:

x = N + 2

y = N

Затем вернется 1.

Answer 2

Рассматривая Алгоритм C , похоже, что проблема связана с этапом рекурсии, который фактически пропускает этап C4 всякий раз, когда r < 0, поскольку x не увеличивается, а r уменьшается только y.

Используя обозначения a, b и r из издания 1998 года Vol. 2 (ISBN 0-201-89684-2), версия Схемы будет выглядеть следующим образом:

(define (factor n) 
  (let ((x (inexact->exact (floor (sqrt n)))))
    (factor-inner (+ (* x 2) 1)
                  1
                  (- (* x x) n))))

(define (factor-inner a b r)
  (cond ((= r 0) (/ (- a b) 2))
        ((< 0 r) (factor-inner a       (+ b 2) (- r b)))
        (else    (factor-inner (+ a 2) (+ b 2) (- r (- a b))))))

РЕДАКТИРОВАТЬ добавить: в основном, мы делаем трюк, который неоднократно проверяет, является ли

r <- ((a - b) / 2)*((a + b - 2)/2) - N

равен 0, и мы делаем это, просто отслеживая, как r изменяется при увеличении a или b. Если в выражении для r установить b на b+2, это эквивалентно уменьшению r на старое значение b, поэтому оба шага выполняются параллельно на шаге C4 алгоритм. Я призываю вас расширить приведенное выше алгебраическое выражение и убедить себя в том, что это правда.

Пока r > 0, вы хотите продолжать уменьшать его, чтобы найти правильное значение b, поэтому вы продолжаете повторять шаг C4. Тем не менее, если вы превышаете значение r < 0, вам нужно его увеличить. Вы делаете это, увеличивая a, потому что увеличение a на 2 эквивалентно уменьшению r на старое значение a, как на этапе C3. У вас всегда будет a > b, поэтому увеличение r на a на шаге C3 автоматически делает r положительным снова, поэтому вы просто переходите непосредственно к шагу C4.

Также легко доказать это a > b. Мы начинаем с a, явно превышающего b, и если мы когда-либо увеличим b до точки, где b = a - 2, мы получим

N = (a - (a - 2))/2 * ((a + (a - 2) - 2)/2 = 1 * (a - 2)

Это означает, что N является простым, так как наибольший коэффициент, который меньше, чем sqrt(N), равен 1, и алгоритм завершен.