SICP exercise 1.17 issue

Question

I'm doing exercise 1.18 in SICP and I face some trouble. The goal is to make a procedure based on 2 previous exercises. This procedure implements so-called Russian peasant method (or Ancient Egyptian multiplication). I wrote a code, but one procedure just doesn't want to execute. Here's my code:

#lang sicp
(define (double a) (+ a a)) 
(define (halve a) (/ a 2)) 

(define (r_m a b)
  (iter a b 0))
  
(define (iter a b n)
    (cond ((= b 0) 0)
          ((even? a) (iter (halve a) (double b) (+ n b)))
          (else (iter (halve a) (double b) n))))

So, when I call my procedure (r_m) with such arguments (r_m 13 19) it stops after 1st iteration. (iter (halve a) (double b) (+ n b) (with arguments 13 and 19) gives this result: iter (13/2) 38 19

After that, program tries to check if 13/2 is odd. But it can't check such number (13/2), because odd? expects an integer, not this undone division.

For some reason, the halve procedure doesn't work when called. I don't really understand why, because other procedures (double and simple + n b) work fine.

Thank you in advance and I hope my grammar doesn't hurt you too much.

Unknown Unknown · Accepted Answer · 2020-08-31T16:39:13

There are several things wrong with your program. Apart from anything else, even if halve worked the way you want it to work, how would b become zero? This is not the only problem!

However the particular case of halve happens because you are assuming programming languages to do what they normally do: incorrect arithmetic which is convenient for the machine, rather than correct arithmetic which is convenient for humans. Scheme tries hard to do correct arithmetic. What, mathematically, is 13/2? It's not 6, or 7, or 3, it's 13/2, or 6 + 1/2: it's a rational number, not an integer.

If you want the next integer below 13/2, the way you want to get it is by subtracting 1 before you divide: (halve (- 13 1)) is 6, exactly. So if you change that cond clause to have (halve (- a 1)) your program will be closer to working (but, in fact it will then fail to terminate, so in a sense it will be further from working...).

SICP exercise 1.17 issue

1 Answers