Problem 42937. Project Euler: Problem 14, Longest Collatz sequence
Brilliant. Power in simplicity. An order of magnitude faster than my attempt.
Thanks. Don't know why mod(a,m) is slower than a-floor(a/m)*m.
Probably internal input/output argument checks. Multiply it via millions of iterations and you get significant difference. Your algorithm saves tons of time (in comparison) because you didn't bother to store all the steps, therefore you didn't fell into "dynamic indexing" trap which saves some steps, but drastically slows down the process during saving values to the main array.
I guess this is one of those times where saving the intermediate steps doesn't help your computation time. Nicely done. As a comparison, using mod(b,2) takes about two-thirds longer than 2*floor(b/2) on my machine; 18.8 sec vs 11.3 sec for n=1e8, and 38 sec vs 23 sec for 2e8. That's good to know for speeding things up in other codes I need to run millions of times!
mod(b,k) takes about 10x longer than b-k*floor(b/k) on my machine (2016b win64):
a = randi(1e7,1e8,1); m = 37;
tic, b = mod(a,m); toc;
tic, c = a - floor(a/m)*m; toc;
norm(b - c)
Elapsed time is 3.131306 seconds.
Elapsed time is 0.253768 seconds.
I did the same thing, minus the uint64. My Project Euler code timed out on the 1e7 and 1e8 test cases.
That's right. My code would pass the test suite if last test were changed from 1e8 to 2e7, but that's all. 1e8 would take approx 110 seconds on Cody servers.
Problem Recent Solvers18
Find a subset that divides the vector into equal halves
Output any real number that is neither positive nor negative
More from this Author2
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!