代码之家 › 专栏 › 技术社区 › Fakrudeen

费马分解法极限

scheme algorithm

Fakrudeen · 技术社区 · 16 年前

我在尝试实现fermat的因子分解( 算法C 在里面 计算机程序设计艺术 ,第2卷)。不幸的是,在我的版本(ISBN81-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))))))

2 回复 | 直到 16 年前

Jason Orendorff Oliver 16 年前

这个 (< limit y) 不需要检查,因为在最坏的情况下,算法最终会找到此解决方案:

X = n + 2

Y = n

然后返回1。

Pillsy 16 年前

看穿 算法C ,看起来问题在于递归步骤,它在任何时候都有效地跳过步骤c4。 r < 0 ,因为 x 不是递增的 r 只有 y .

使用符号 a , b 和 R 从1998年版第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 当我们增加 一 或 乙 . 如果我们准备 乙 到 b+2 在表达式中 R 上面,它相当于减少 R 根据 乙 ,这就是为什么在算法的步骤c4中两者并行完成的原因。我鼓励你展开上面的代数表达式,并说服自己这是真的。

只要 r > 0 ,您希望继续减小它以找到 乙 ,所以你继续重复步骤c4。但是,如果你超调,并且 R<0 ,你需要增加它。你通过增加 一 ,因为 一 2等于减少 R 根据 一 ,如步骤c3所示。你将永远拥有 a > b ,所以越来越多 R 通过 一 在步骤c3中自动生成 R 再次肯定,所以你直接进入步骤C4。

也很容易证明 A & B . 我们从 一 明显大于 乙 ,如果我们增加 乙 以至于 b = a - 2 我们有

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

这意味着 N 是质数,因为它的最大因子小于 sqrt(N) 为1,并且算法已终止。