冪乗のバイナリ法による演算

知りませんでした。
これはすごい。すごいと書いてるけど納得はしてない。
指数を 2 で割りながら反復する、同時にそのときの底を二乗する。
指数が 2 の冪乗でないときは、余った分の最初の底を乗じる。
これは素敵すぎるな。
冪乗 - Wikipedia
プログラマーに数学は必須 ? | スラド サイエンス
Good Programmers learn Mathematics

;; 10進数を2進数に
(define (dec2bin n)
  (define (iter x l)
    (cond ((= 0 x)
           (reverse l))
          ((= 0 (remainder x 2))
           (iter (quotient x 2) (append l '(0))))
          (else
           (iter (quotient x 2) (append l '(1))))))
  (iter n '()))

;; 下位桁から
(define (powerexponential a n)
  (define (iter p n v)
    (display (format "~a ~a ~a" p n v))
    (newline)
    (if (= n 0)
        v
        (iter (* p p)
              (quotient n 2)
              (if (= 1 (remainder n 2))
                  (* v p)
                  v))))
  (iter a n 1))

;; 上位桁から
(define (powerexponential a n)
  (define (iter n v)
    (display (format "~a ~a" n v))
    (newline)
    (if (null? n)
        v
        (iter (cdr n) (* v v (if (= 1 (car n)) a 1)))))
  (iter (dec2bin n) 1))

# 下位桁バージョン
gosh> (powerexponential 2 43)
2 43 1
4 21 2
16 10 8
256 5 8
65536 2 2048
4294967296 1 2048
18446744073709551616 0 8796093022208
8796093022208
# 上位桁バージョン
gosh> (powerexponential 2 43)
(1 0 1 0 1 1) 1
(0 1 0 1 1) 2
(1 0 1 1) 4
(0 1 1) 32
(1 1) 1024
(1) 2097152
() 8796093022208
8796093022208