>>128
I've been doing some other things the past few days so I haven't progressed on the higher-order implementation, other than making a brief note about it. I did take the time to remove the egregious code duplication in my first-order implementation though. It's probably still not as clear as making the run-length encoding explicit as was done in >>18 but it's certainly more readable than my the last version. I also just before posting this realized how smart of a move it was in the sequence implementation >>123,130,136 to instead of computing the triangular number bounded by the values of R[n-1] and R[n] for every recursion to compute the triangular number of R[n] + (- n i) and then subtract the values of R that have been seen. Something like half of my computation was spent on computing these triangular numbers, and it explained almost the complete difference between our implementations, so I've blatantly stolen this brilliant move, and integrated it into my own implementation.
(define (hofstadter n)
(let ((r0 (list 1))
(m (inexact->exact (ceiling (* 1.5 (sqrt n)))))
(T (lambda (a) (quotient (* a (+ a 1)) 2))))
(let H ((i 1) (r r0) (R r0) (R2 0) (S 1))
(let* ((skip (= (car R) S))
(S (if skip (+ S 1) S))
(rh (car r))
(rt (if (<= rh m)
(begin (set-cdr! r (list (+ rh S))) (cdr r))
(list (+ rh S)))))
(if (> (+ i S) n)
(- (T (+ rh (- n i))) (+ (- R2 1) rh))
(H (+ i (- S 1)) rt (if skip (cdr R) R)
(+ R2 rh) (+ S 1)))))))I "compressed" the unused S values. Not much improvement in terms of order of growth though.
sequence.scm
R(10^12) 500000941936492050650505 2.782sec
R(10^13) 50000029798618763894670256 8.979secThis is a significant improvement, you pretty much halved the runtime on my machine (in Chicken). This makes sense considering your implementation is memory/GC bound, and you just dramatically reduced the amount of values you are creating/deleting in `ss'. In contrast almost the entirety the time my implementation takes is in computing `T' on each iteration, which makes me wonder if I could copy your... [see the start of the reply :)]
It seems the gmpy2.mpz advantage isn't nearly as dramatic as I expected.
That's really too bad, I wish I could help understand why.