Heater wrote:A scheme version of the collatz problem above would be great. Hint, hint...
A quick implementation. This is all tested on a mac, not on a Pi, under Chez scheme 9.4
Here's the trivial collatz step. Should be pretty readable, the only thing that might throw non-schemers is the use of `let name ....` which defines a named recursion point. so the `(let loop ((x x) (count 0)) …) block is actually a recursive function with two parameters, x and count. That explanation probably doesn't help, either :) This is tail recursive code, so no, it doesn't blow the stack. Performance-wise, though, it kinda blows chunks. 80 seconds on my machine for the 1-10M test (including compile time and function call overhead)
Code: Select all
(define (collatz x)
(let loop ((x x) (count 0))
(cond
((= 1 x) count)
((even? x) (loop (/ x 2) (+ count 1)))
((odd? x) (loop (+ (* x 3) 1) (+ count 1))))))
As we know we're dealing with integers, we can rewrite this in exactly the same form using the "fixnum" operators, as follows :
Code: Select all
(define (collatz-fx x)
(let loop ((x x) (count 0))
(cond
((fx=? 1 x) count)
((fxeven? x) (loop (fxdiv x 2) (fx+ count 1)))
((fxodd? x) (loop (fx+ (fx* x 3) 1) (fx+ count 1))))))
Basically looks the same, but significantly faster, 29 seconds for 10M, still including compile and function call overhead. I'm sure we can do better than that. fxdiv, for example, is number-theoretically correct. But as we're dividing an integer that is known to be positive and by a power of two, we can just bitshift it.
Code: Select all
(define (collatz-fxshift x)
(let loop ((x x) (count 0))
(cond
((fx=? 1 x) count)
((fxeven? x) (loop (fxarithmetic-shift-right x 1) (fx+ count 1)))
((fxodd? x) (loop (fx+ (fx* x 3) 1) (fx+ count 1))))))
And we're down to 8 seconds. The calling code, FWIW, looks like this, and uses fixnum operations throughout. It's ugly and I could do a lot better if I could be bothered.
Code: Select all
(define (collatz-test fn)
(let ((start-time (current-time)))
(let loop ((x 1) (max-x 0) (max-count 0))
(if (fx>? x 10000000)
(display (format "max : ~a, count: ~a, time ~a seconds\n" max-x max-count (time-difference (current-time) start-time)))
(let ((count (fn x)))
(if (fx>? count max-count)
(loop (fx+ x 1) x count)
(loop (fx+ x 1) max-x max-count)))))))
(display "Plain Collatz\n")
(collatz-test collatz)
(display "\nExplicitly fixnum\n")
(collatz-test collatz-fx)
(display "\nExplicitly fixnum with shifts for divide\n")
(collatz-test collatz-fxshift)
At this point, memoising could be a good next step. We have fixnum vectors, so why not? This will, of course, push a lot of overhead onto the vector manipulation code, it might not work. Unfortunately, I have a lot of stuff to do and only one day off, so it will have to wait.