费马分解的方案代码

Question

我正在尝试通过实现一些算法来学习方案。

FermatFactor(N): // N should be odd

    a ← ceil(sqrt(N))
    b2 ← a*a - N
    while b2 isn't a square:

            a ← a + 1 // equivalently: b2 ← b2 + 2*a + 1
            b2 ← a*a - N // a ← a + 1

    endwhile
    return a - sqrt(b2) // or a + sqrt(b2)

我正在尝试在方案中实现上述算法。我被困在 while 循环中。任何帮助，将不胜感激。谢谢

Answer 1

与其使用 while 循环，不如在 Scheme 中使用递归。 Scheme 具有尾递归，因此递归与其他语言中的循环结构一样高效。

具体来说，在这种情况下，您可能会使用名为 "named let" 的东西，这使得创建内联递归变得容易。将上述代码直接转换为 Scheme 将导致：

(define (fermat-factor n)
  (let* ((a (ceiling (sqrt n)))
         (b (- (* a a) n)))
    (let loop ()
      (cond
        ((not (integer? (sqrt b)))
         (set! a (+ a 1))
         (set! b (- (* a a) n))
         (loop))))
    (- a (sqrt b))))

不过，这确实不是很地道，因为它使用了突变（对 set! 的调用），这在该算法中是完全没有必要的。更惯用的方法如下所示：

(define (fermat-factor* n)
  (let* ((a0 (ceiling (sqrt n)))
         (b0 (- (* a0 a0) n)))
    (let loop ((a a0)
               (b b0))
      (if (integer? (sqrt b))
          (- a (sqrt b))
          (loop (+ a 1)
                (- (* a a) n))))))

（使用开头的 let* 是必要的，因为命名 let 不允许 let* 样式中的顺序绑定，并且 let* 不支持命名 let 模式。 )

另见

费马分解的方案代码

Scheme code for fermat's Factorization

scheme