费马分解方法极限

Question

我正在尝试实现 Fermat 分解（计算机编程艺术，第 2 卷中的算法 C）。不幸的是，在我的版本（ISBN 81-7758-335-2）中，该算法打印不正确。下面的因子内循环的条件应该是什么？我正在运行循环，直到 y <= n [作为限制传入]。

(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

( 检查是不必要的，因为在最坏的情况下，算法最终会找到这个解决方案：

x = N + 2

y = N

然后它将返回 1。

Answer 2

纵观算法C，问题似乎出在递归步骤上，每当r <<时，递归步骤就会有效地跳过步骤C4。 0，因为x不递增，而r仅递减y。

使用 1998 年版 Vol 中的 a、b 和 r 表示法。 2（ISBN 0-201-89684-2），Scheme 版本如下：

(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 的技巧，我们正在做通过简单地跟踪当我们增加 a 或 b 时 r 如何变化即可。如果我们在上面的 r 表达式中将 b 设置为 b+2，则相当于减少 r由 b 的旧值决定，这就是为什么两者在算法的步骤 C4 中并行完成的原因。我鼓励您扩展上面的代数表达式并说服自己这是正确的。

只要 r > 0，你想不断减少它来找到正确的b值，所以你不断重复步骤C4。但是，如果超出范围，并且 r 0，你需要增加它。您可以通过增加 a 来实现此目的，因为将 a 增加 2 相当于将 r 减少 a 的旧值>，如步骤 C3 中所示。你总会有 a >; b，因此在步骤 C3 中将 r 增加 a 会自动使 r 再次为正值，因此您只需直接进入步骤 C4 。

证明 a > 也很容易。 b。我们从明显大于 b 的 a 开始，如果我们将 b 增加到 b = a - 2 code>，我们有

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

这意味着 N 是素数，因为它小于 sqrt(N) 的最大因子是 1，算法终止。