乐正

Actions speak louder than words.

Sicp-ex1-25

问题

Alyssa P. Hacker 提出,在写expmod的时我们做了过多的额外工作。她说,毕竟我们已 经知道怎么样计算乘幂,因此只需要简单地写:

1
2
(define (expmod base exp m)
  (remainder (fast-expt base exp) m))

她说的对吗?这一过程能很好地用于我们的快速检查程序吗?请解释这些问题。

解答

她说的是不对的。费马检查中的expmod对于指数值$e$大于1的情况,所采用的归约方式是 基于以下事实:对任意的$x$、$y$和$m$,我们总可以通过分别计算$x$取模$m$和$y$取模$m$ ,而后将它们乘起来之后取模$m$,得到$x$乘$y$取模的余数。例如,在$e$是偶数的时,我 们计算$b^{\frac {e} {2}}$取模$m$的余数,求它的平方,而后再求它取模$m$的余数。这 种技术非常有用,因为它意味着我们的计算中不需要处理比$m$大很多的数。

而使用Alyssa的expmod进行费马检查在针对一个很大的素数的检测的时候,可能需要计算 一个很大的乘幂,这种非常大的数值计算的速度非常慢,而且很容易因为超出实现的限制而 造成溢出。

测试

1
2
3
4
5
6
7
;;; (load alyssa-expmod)

(expmod-alyssa 1000000000 1000000000 3) ; 解释器停止响应

;;; (load expmod)
(expmod 1000000000 1000000000 3) ; 立即返回
;Value: 1

draft

« sicp-ex1-24 sicp-ex1-26 »

Comments