這一題不是我獨(dú)立想出來(lái)的咯,比較遺憾，沒(méi)有認(rèn)真讀書(shū)中的注解，通過(guò)google解決的，一搜索才發(fā)現(xiàn)網(wǎng)上已經(jīng)有很多的scip習(xí)題的解答，我這個(gè)倒是畫(huà)蛇添足了!-_-。想一想還是有寫(xiě)下去的必要，盡管牛人多如牛毛，自己還是潛下心來(lái)一步一步向前。
來(lái)自http://dev.csdn.net/develop/article/64/64485.shtm
; ======================================================================
;
; Structure and Interpretation of Computer Programs
; (trial answer to excercises)
;
; 計(jì)算機(jī)程序的構(gòu)造和解釋(習(xí)題試解)
;
; created: code17 02/28/05
; modified:
; (保持內(nèi)容完整不變前提下，可以任意轉(zhuǎn)載)
; ======================================================================
;; SICP No.1.25
;; 本題為理解題
;; 直接定義(expmod base exp m)為base^exp基于m的模(modulo)
;; (define (expmod base exp m)
;; (remainder (fast-expt base exp) m))
;; 在理想情況下是正確的，在語(yǔ)義上與原定義是等價(jià)的，甚至遞歸層數(shù)
;; 都是一樣的，而且更加直觀。
;;
;; 但在實(shí)踐中，這樣的定義是不可行的，這也是為什么我們要采用原文中的定義
;; 的原因：因?yàn)閎ase^exp很可能是一個(gè)非常大的數(shù)。比如，當(dāng)我們?nèi)〉诙€(gè)
;; 測(cè)試?yán)又械膎=1000000時(shí)，base是[1,999999]區(qū)間中的任意
;; 隨機(jī)數(shù)，它的平均取值為50000，而exp=1000000。50000^1000000是一個(gè)大得
;; 驚人的數(shù)，無(wú)論是fast-expt的層層函數(shù)調(diào)用計(jì)算，還是用remainder對(duì)其取模，
;; 計(jì)算量都是很大的。
;;
;; 而相反，原始的expmod函數(shù)
;; (define (expmod base exp m)
;; (cond ((= exp 0) 1)
;; ((even? exp)
;; (remainder (square (expmod base (/ exp 2) m))
;; m))
;; (else
;; (remainder (* base (expmod base (- exp 1) m))
;; m))))
;; 通過(guò)分解(a*b mod n) 為 ((a mod n) * (b mod n) mod n)，使得每層遞歸
;; 調(diào)用的計(jì)算參數(shù)和返回值總是小于n (x mod n < n)，即便是計(jì)算過(guò)程中出現(xiàn)
;; 的最大數(shù)(a mod n) * (b mod n) 也依然是要小于n^2, 相對(duì)于前者n^n的數(shù)
;; 量級(jí)，實(shí)在是小得多，這樣就避免了大數(shù)的計(jì)算問(wèn)題。
;;
;; 比如經(jīng)測(cè)試，在使用新的expmod的情況下，1009的驗(yàn)證需要1.2ms的時(shí)間，
;; 1000003的驗(yàn)證需要 93680ms，遠(yuǎn)高于原來(lái)的expmod函數(shù)。
;;
;; 這也同時(shí)印證了我們?cè)?.24題中的分析，同樣的操作在不同字長(zhǎng)的數(shù)字上的
;; 代價(jià)是不同的。1000000的驗(yàn)證時(shí)間現(xiàn)在是1000的8000多倍，遠(yuǎn)不再是2倍左右
;; 的關(guān)系。在1.24中的，因?yàn)閑xpmod算法的控制，操作數(shù)最多是n^2級(jí)的，字長(zhǎng)
;; 所引起的差距并不明顯，只在10^6-10^12間產(chǎn)生了一點(diǎn)點(diǎn)階躍；而這里的算法
;; 中, 操作數(shù)可以達(dá)到n^n級(jí)，當(dāng)n=1000時(shí)，1000^1000的字長(zhǎng)大約在10000位(二
;; 進(jìn)制數(shù))左右，而n=1000000時(shí)1000000^1000000的字長(zhǎng)則達(dá)到在20000000位(二
;; 進(jìn)制數(shù))左右，這字長(zhǎng)的巨大差距導(dǎo)致了我們?cè)?.24中已經(jīng)發(fā)現(xiàn)的問(wèn)題更加明顯。
盡管兩個(gè)過(guò)程在語(yǔ)義和原理是相通的，但因?yàn)樵诓煌膱?chǎng)景中使用，所碰到的情況就截然不同了，算法在不同場(chǎng)景下的表現(xiàn)差異明顯，還需仔細(xì)斟酌。