SICP

Question

我正在使用 SICP 这本书并试图解决这个练习：

1.2.4 Exponentiation

Exercise 1.18. Using the results of exercises 1.16 and 1.17, devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps

我正在尝试使用以下代码解决此问题：

(define (double x) 
  (+ x x))

(define (halve x) 
  (floor (/ x 2)))

(define (* a b)
  (define (iter count accumulate)
    (cond ((= count 1) accumulate)
          ((even? a) (iter (halve count) (+ accumulate (double b))))
          (else empty)))
  (iter a 0))

如您所见，我正在尝试先处理偶数。我正在使用 SICP wiki as my solutions-guide。他们建议进行一些测试以查看代码是否有效：

 (* 2 4) 
 (* 4 0)

我没有得到的是我的代码通过了这两个最初的测试，只处理偶数。

但是，当我尝试一些大数（2 的倍数）时，代码失败了。我使用 Python 检查了结果。例如，

(IN PYTHON)

2**100  
>> 1267650600228229401496703205376  
2**98
>> 316912650057057350374175801344
a = 2**100
b = 2**98
a*b
>> 401734511064747568885490523085290650630550748445698208825344

当我在 Dr. Racket 中使用我的函数和这些值时，我得到了不同的结果：

(* 1267650600228229401496703205376 316912650057057350374175801344)

我的结果是：63382530011411470074835160268800，这是错误的，正如 Python 内置函数所建议的那样。

为什么会这样？

Answer 1

递归步骤似乎不对，empty 在那里做什么？另外，如果 b 为负数会怎样？此解决方案应该有效：

(define (mul a b)
  (define (iter a b acc)
    (cond ((zero? b) acc)
          ((even? b) (iter (double a) (halve b) acc))
          (else (iter a (- b 1) (+ a acc)))))
  (if (< b 0)
      (- (iter a (- b) 0))
      (iter a b 0)))

例如：

(mul 1267650600228229401496703205376 316912650057057350374175801344)
=> 401734511064747568885490523085290650630550748445698208825344

SICP - 通过加法乘法

SICP - Multiplication through addition

lisp

racket

1.2.4 Exponentiation