SICP: итеративное возведение в степень

Долго думал, как сделать итеративный процесс возведения в степень (SICP, упражнение 1.16). Я сразу догадался, что брать за основу надо число в двоичной системе счисления, но мне было непонятно, как переводить это число в алгоритм.

Вот например, как выглядели алгоритмы и двоичная запись для некоторых чисел:

7 *+*+ 111
8 *** 1000
9 ***+ 1001
10 **+* 1010

В итоге оказалось всё просто. Надо отбрасывать самый первый знак, а дальше трактовать единицу как "возвести в квадрат и умножить", а ноль — как "просто возвести в квадрат".

Также я впервые использовал здесь функцию cons, которая объединяет first и rest.

; Возвести число b в степень p (p должно быть больше 1)
(define (pow-hm b p)
  (apply (fn (x y) (if (= y) (* x x) (* x x b)))
         (cons b (map int (1 (explode (bits p)))))
         2))

А вот то же самое, только по "итеративному алгоритму" предложенному в SICP:

; Возвести b в степень n
(define (pow-sicp-1 b n)
  (cond ((= n 1) b)
        ((= (% n 2)) (pow-sicp-1 (* b b) (/ n 2)))
        (true (* (pow-sicp-1 (* b b) (/ n 2)) b))))

Вроде бы как, ошибиться тут просто негде. Однако… цитирую SICP:

«Храните, помимо значения степени n и основания b, дополнительную переменную состояния a, и определите переход между состояниями так, чтобы произведение abⁿ от шага к шагу не менялось».

Спрашивается, зачем козе баян? Разве что, перехерачить алгоритм вот так:

; То же самое, но с инвариантом
(define (pow-sicp-2 b n (a 1))
  (if (= n 1)
    (* b a)
    (* a (pow-sicp-2 (* b b) (/ n 2) (if (= (% n 2)) 1 b)))))

Согласно тестам, кстати, самый быстрый алгоритм — это рекурсия без инварианта. Алгоритмы с инвариантом и с разложением на биты немного медленнее. Впрочем, скорости там одного порядка, существенной разницы нет.

Дополнение.

Блджад. Только перейдя к упражнению 1.17 я понял, в чём была соль. По условиям задачи, у нас есть вот такие функции:

(define (double x) (* x 2))
(define (halve x) (/ x 2))
(define (even? x) (if (= (% x 2))))

Из них надо склепать умножение. Вот труе итеративный вариант:

; Умножить а на b
(define (mul-sicp-i a b (p 0))
  (let (p 0)
    (until (= b 1)
      (set 'p (+ p (if (even? b) 0 a)))
      (set 'a (double a))
      (set 'b (halve b)))
    (+ a p)))

А вот то же самое, но через жопу концевую рекурсию:

; Умножить a на b
(define (mul-sicp-t a b (p 0))
  (if (= b 1)
    (+ a p)
    (mul-sicp-t (double a) (halve b) (+ p (if (even? b) 0 a)))))