莊周夢蝶

    這一題不是我獨立想出來的咯,比較遺憾，沒有認真讀書中的注解，通過google解決的，一搜索才發現網上已經有很多的scip習題的解答，我這個倒是畫蛇添足了!-_-。想一想還是有寫下去的必要，盡管牛人多如牛毛，自己還是潛下心來一步一步向前。
   來自http://dev.csdn.net/develop/article/64/64485.shtm

; ======================================================================
;
;          Structure and Interpretation of Computer Programs
;                  (trial answer to excercises)
;
;                  計算機程序的構造和解釋(習題試解)
;
;                                             created: code17 02/28/05
;                                             modified:
; (保持內容完整不變前提下，可以任意轉載)
; ======================================================================

;; SICP No.1.25
;; 本題為理解題

;; 直接定義(expmod base exp m)為base^exp基于m的模(modulo)
;; (define (expmod base exp m)
;;   (remainder (fast-expt base exp) m))
;; 在理想情況下是正確的，在語義上與原定義是等價的，甚至遞歸層數
;; 都是一樣的，而且更加直觀。
;;
;; 但在實踐中，這樣的定義是不可行的，這也是為什么我們要采用原文中的定義
;; 的原因：因為base^exp很可能是一個非常大的數。比如，當我們取第二個
;; 測試例子中的n=1000000時，base是[1,999999]區間中的任意
;; 隨機數，它的平均取值為50000，而exp=1000000。50000^1000000是一個大得
;; 驚人的數，無論是fast-expt的層層函數調用計算，還是用remainder對其取模，
;; 計算量都是很大的。
;;
;; 而相反，原始的expmod函數
;; (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))))
;; 通過分解(a*b mod n) 為 ((a mod n) * (b mod n) mod n)，使得每層遞歸
;; 調用的計算參數和返回值總是小于n (x mod n < n)，即便是計算過程中出現
;; 的最大數(a mod n) * (b mod n) 也依然是要小于n^2, 相對于前者n^n的數
;; 量級，實在是小得多，這樣就避免了大數的計算問題。
;;
;; 比如經測試，在使用新的expmod的情況下，1009的驗證需要1.2ms的時間，
;; 1000003的驗證需要 93680ms，遠高于原來的expmod函數。
;;
;; 這也同時印證了我們在1.24題中的分析，同樣的操作在不同字長的數字上的
;; 代價是不同的。1000000的驗證時間現在是1000的8000多倍，遠不再是2倍左右
;; 的關系。在1.24中的，因為expmod算法的控制，操作數最多是n^2級的，字長
;; 所引起的差距并不明顯，只在10^6-10^12間產生了一點點階躍；而這里的算法
;; 中, 操作數可以達到n^n級，當n=1000時，1000^1000的字長大約在10000位(二
;; 進制數)左右，而n=1000000時1000000^1000000的字長則達到在20000000位(二
;; 進制數)左右，這字長的巨大差距導致了我們在1.24中已經發現的問題更加明顯。

    盡管兩個過程在語義和原理是相通的，但因為在不同的場景中使用，所碰到的情況就截然不同了，算法在不同場景下的表現差異明顯，還需仔細斟酌。