费马分解法极限

Question

我试图实现费马的因式分解(算法C在计算机编程艺术，第2卷)。不幸的是，在我的版本(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

没有必要进行(< limit y)检查，因为在最坏的情况下，算法最终会找到这个解决方案：

x=N+2

Y=N

然后它将返回1。

Answer 2

纵观算法C，问题似乎在于递归步骤，它在r < 0时有效地跳过了步骤C4，因为x没有增加，r仅由y递减。

使用1998年版(ISBN 0-201-89684-2)中的a、b和r表示法，方案版本如下：

(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时的变化。如果我们在上面的表达式中将b设置为b+2，这相当于将r简化为原来的b值，这就是为什么两者在算法的步骤C4中并行完成的原因。我鼓励你把上面的代数表达式展开，让你自己相信这是真的。

只要是r > 0，您就需要不断减少它以找到正确的b值，因此您可以继续重复步骤C4。然而，如果您超调，和r < 0，您需要增加它。您可以通过增加a来实现这一点，因为将a增加2等于按照a的旧值减少r，就像步骤C3中的那样。您将始终拥有a > b，因此在步骤C3中通过a增加r会自动使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，并且算法已经终止。