[racket] Mutable state vs RAM on fire

This reminded me that I had a similar kind of recursion issue when I
wrote some code for generating integer partitions. In the end I
abandoned the stack+tail recursion form and accumulated a list of
things to do when I thought I was done, which made all calls tail
calls. It significantly sped up the generation of partitions.

I happen to have the same code at home here at work and did a quick
check. The timing for the previous calculation is included here
because my work laptop is significantly better than my laptop at home,
just for comparison purposes.

> (define-syntax-rule (my-time exp)
    (begin
      (displayln (quote exp))
      (display #\tab)
      (collect-garbage)(collect-garbage)(collect-garbage)
      (time exp)))
  (let ((big-one (my-time (poly-expt '(1 1 1 1 1 1 0) 300)))
        (big-one-again (my-time (poly-expt-tail '(1 1 1 1 1 1 0) 300)))
        (a (my-time (poly-expt '(1 0 1 0 1) 300)))
        (b (my-time (poly-expt-tail '(1 0 1 0 1) 300))))
    (and (equal? big-one big-one-again)
         (equal? a b)))
(poly-expt '(1 1 1 1 1 1 0) 300)
	cpu time: 2091 real time: 2090 gc time: 425
(poly-expt-tail '(1 1 1 1 1 1 0) 300)
	cpu time: 921 real time: 920 gc time: 173
(poly-expt '(1 0 1 0 1) 300)
	cpu time: 717 real time: 718 gc time: 172
(poly-expt-tail '(1 0 1 0 1) 300)
	cpu time: 234 real time: 234 gc time: 31
#t
>

Seems like a pretty worthwhile optimization. Here are the two
procedures for comparison:
;;;;;;;;;;;;;;;;;;;
(define (poly-expt poly expt)
    (if (zero? expt)
        (list 1)
        (let loop ((expt expt))
          (cond ((= 1 expt) poly)
                ((even? expt)
                 (poly-expt (poly* poly poly) (/ expt 2)))
                (else
                 (poly* poly (loop (sub1 expt))))))))

  (define (poly-expt-tail poly expt)
    (if (zero? expt)
        (list 1)
        (let loop ((poly poly)
                   (expt expt)
                   (todo (list 1))) ; leftover multiplications
          (cond ((= 1 expt)
                 (poly* poly todo))
                ((even? expt)
                 (loop (poly* poly poly) (/ expt 2) todo))
                (else
                 (loop poly (sub1 expt) (poly* poly todo)))))))
;;;;;;;;;;;;;;;;;;;;

Deren

On Thu, May 3, 2012 at 10:34 AM, Stephen Bloch <bloch at adelphi.edu> wrote:
> On May 3, 2012, at 7:45 AM, Rüdiger Asche <rac at ruediger-asche.de> wrote:
>
>> uhm... am I mistaken, or is there one recursive call to fast-expt in a non tail recursive position?
>
> Yes, there is.
>
>> Schouldn't that be unwound?
>
> Assuming you want correct answers :-) , it can't be unless you start adding extra parameters to fast-expt, making it harder to understand.  And, as somebody else pointed out, the recursion depth is only log_2(n) so it's really not a concern.
>
> Stephen Bloch
> sbloch at adelphi.edu
>>
>
> ____________________
>  Racket Users list:
>  http://lists.racket-lang.org/users