3 ms·
I know is it is not the point of the question, but that problem would benefit greatly from memoization. Calculate it recursively and memoize the result of every
by bjoli 9y ago
I know is it is not the point of the question, but that problem would benefit greatly from memoization. Calculate it recursively and memoize the result of every step. With all the neat trickery that they are doing with assembly they could easily go sub 10ms.
I whipped together a short poc in chezscheme, and it clocks in at about 50ms on my 4 yo laptop.
- Veedrac 9y agoWhen everything is in cache and you're calculating sequentially, definitely, but equally why not just precompute the whole range and do a binary search? Once you're looking for better algorithms the whole problem just falls away! That said, I do think it's neat that the fastest brute-force variant is a rough factor-2 from your naïve memoized version. It might even win if it was fighting a hyperthread for cache space! Just shows how much throughput modern CPUs have... if only they were used this well all the time ;).
- bjoli 9y ago> That said, I do think it's neat that the fastest brute-force variant is a rough factor-2 from your naïve memoized version. My naive memoized version in a GCd language that is consistently 4-5x slower than my own (pretty bad) C versions of the same project Euler problems without any of the tricks the fastest C++ version is doing. Still pretty impressive considering most solutions in the project euler forums take more than 1s.
- shoo 9y ago> but equally why not just precompute the whole range and do a binary search? what do you mean?
- Veedrac 9y agoThe code finds the longest Collatz sequence below N, where N is a 32-bit integer. There are only ~1k longest sequences possible, so just list them all. Given N, search for the largest N below that and return its corresponding iteration count.