3 ms·
When 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 yo
by Veedrac 9y ago
When 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.