[plt-scheme] DrScheme crash, and my bad programming

Do you have memory limits set on your program?

Robby

On Wed, May 21, 2008 at 3:25 PM, Joshua Zucker <joshua.zucker at gmail.com> wrote:
> I know that there's probably a more conventional way to write code
> like this -- this is just my dorky translation of a C for loop into a
> recursion.
>
> (define (solution6? a b c d n)
>  (let ([f (- (* 12 n (- n 2)) b (* 3 c) (* 2 d))])
>    (and (>= f 0)
>         (>= (* n n n) (+ a b c d (- (* 8 n) (* 2 a) b) f)))))
>
> (define (count-solutions a b c d n)
>  (cond
>    [(> a (* 4 n)) 0]
>    [(> b (- (* 8 n) (* 2 a))) (count-solutions (add1 a) 0 0 0 n)]
>    [(> c (- (* 4 n (- n 2)) b)) (count-solutions a (add1 b) 0 0 n)]
>    [(> d (quotient (- (* 12 n (- n 2))
>                       b
>                       (* 3 c))
>                    2)) (count-solutions a b (add1 c) 0 n)]
>    [(solution6? a b c d n) (add1 (count-solutions a b c (add1 d) n))]
>    [else (count-solutions a b c (add1 d) n)]))
>
> But if you run (count-solutions 0 0 0 0 10) or so,
> where the recursion is then going a couple hundred million layers deep,
> DrScheme crashes.
>
> If I break up the recursion into one function that recurses on c and d
> while another recurses on a and b, then it has no trouble.
>
> If you want me to be more specific about exactly what code I run to
> make DrScheme crash, let me know.  (By crash, I mean the application
> quits -- v372 on OS X 10.4)
>
> But I'm also writing because I figure there are more elegant ways to
> write for-loop-esque code like this -- maybe I should post that to
> plt-edu instead -- but I'd love to learn what the conventional way is
> to write this type of code.  Something with let loop?  I've seen that
> idiom but I don't really get it.
>
> Finally, the algorithm here is just brute-force counting of solutions
> to a system of three linear diophantine equations in seven variables,
> where all the variables have to be nonnegative.  So I pick 4 of them,
> look at all the possibilities, and check for whether the remaining
> values are positive (with a few shortcuts, since the limits of the
> loop guarantee some of them will be positive).  So maybe there are
> much much much more efficient ways of counting the number of solutions
> to a system like this?  (Equivalently, the number of lattice points in
> a 7-dimensional region bounded by a bunch of hyperplanes.)
>
> Thanks!
> --Joshua Zucker
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
>