Problem when computing the power of huge numbers

[Diego Alexander Rojas]

Hi,

I've been recently following the book Structure and Interpretation of computer
programs and I found something very strange. I currently have this two
functions to compute an exponential function:

(define (even? n)
(= (remainder n 2) 0))

(define (square x) (* x x))

(define (fast-exp b n)
(cond ((= n 0) 1)
((even? n) (square (fast-exp b (/ n 2))))
(else (* b (fast-exp b (- n 1))))))

(define (exp-iter b n sol)
(cond ((= n 0) sol)
((even? n) (exp-iter (square b) (/ n 2) sol))
(else (exp-iter b (- n 1) (* b sol)))))
(define (myfast-exp b n)
(exp-iter b n 1))

both give different results both non are the correct one (I checked
with python,
octave and calc). However this functions just start to fail when computing
very big exponentials, because it didn't fail with numbers such as
123 ^ 331

Any Suggestions?

[Faried Nawaz]

Post by Diego Alexander Rojas
both give different results both non are the correct one (I checked
with python, octave and calc). However this functions just start to
fail when computing very big exponentials, because it didn't fail with
numbers such as 123 ^ 331

Can you provide an example of a failure? For me, (fast-exp 123 331) or
(myfast-exp 123 331) return the same value in guile 1.8.7, scheme48 1.8,
and, when translated, in sbcl 1.0.29.11 and python 2.6.5. I also tried
(myfast-exp 2048 2048) and (myfast-exp 1048578 23456).

This is on a 64 bit Linux desktop, with vendor-provided
interpreters/compilers (Ubuntu 10.04).


Faried.

[Michael Sperber]

Post by Diego Alexander Rojas
Hi,
I've been recently following the book Structure and Interpretation of computer
programs and I found something very strange. I currently have this two
(define (even? n)
(= (remainder n 2) 0))
(define (square x) (* x x))
(define (fast-exp b n)
(cond ((= n 0) 1)
((even? n) (square (fast-exp b (/ n 2))))
(else (* b (fast-exp b (- n 1))))))
(define (exp-iter b n sol)
(cond ((= n 0) sol)
((even? n) (exp-iter (square b) (/ n 2) sol))
(else (exp-iter b (- n 1) (* b sol)))))
(define (myfast-exp b n)
(exp-iter b n 1))
both give different results both non are the correct one (I checked
with python,
octave and calc). However this functions just start to fail when computing
very big exponentials, because it didn't fail with numbers such as
123 ^ 331

Could you give a few more details, like an example of where it does
fail?