-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 06-03-12 12:03, Pierpaolo Bernardi wrote: > Hello, > > I was expecting the procedure 'fa' below to run in constant > memory, as, in my understanding, It doesn't use any non-tail > recursive loops, it does not build any data structure, and only > performs arithmetic operations on small integers. > > But some of my assumptions must be wrong, as the calls to next-z > accumulate and eventually fill the available memory. > > Can someone explain me where's my mistake? > > (A secondary note: the debugger shows the value of the squares > vector as a 100 element vector, with no hint that the value is > abbreviated. Pretty confusing, IMHO). > > Thanks. > > Pierpaolo > > ================ #lang racket > > (define (perfect-square? n) (= n (sqr (integer-sqrt n)))) > > (define (fa) (let ((squares (for/vector ((i (in-range 1 10000))) (* > i i)))) (let/ec return (let next-sum ((sum 3)) (let ((limit-z > (quotient sum 3))) (let next-z ((z 1)) (if (= z limit-z) (next-sum > (add1 sum)) (for ((y+z (in-vector squares)))
This loop is a fiction as all paths in the body go to either next-sum or next-z and leave the rest of the iteration for whenever. Thus you never iterate over your vector of squares, but you do build up stack-frames that promise to do that in a future which never happens. > (let ((y (- y+z z))) (if (> (+ y z) sum) (next-sum (add1 sum)) (let > ((x (- sum z y))) (if (and (perfect-square? (+ x y)) > (perfect-square? (- x y)) (perfect-square? (+ x z)) > (perfect-square? (- x z))) (return (list x y z sum)) (next-z (add1 > z)))))))))))))) Marijn -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.18 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAk9WD9UACgkQp/VmCx0OL2y8+gCgiXhLP4pkO5/Iv6d0JKNdpv+A 9zMAn33IqJqdEvVczELg+Y3XgYPIECgY =3QeK -----END PGP SIGNATURE----- ____________________ Racket Users list: http://lists.racket-lang.org/users
