5 ms·
Hi Bernard. Can you shed some light on why Rivest's prediction that this puzzle would take 35 years of computation was so wildly off? In the paper he predicts t
by spuz 8y ago
Hi Bernard. Can you shed some light on why Rivest's prediction that this puzzle would take 35 years of computation was so wildly off? In the paper he predicts that clock speeds would reach 10Ghz by 2012, he also predicts another 5 fold speed improvement by 2034. I am not sure what the actual technological improvements have been since 1999 but it seems our processors are way below his predictions of where we would be in 2012, let alone 2034. He states:
> "We estimate that the puzzle will require 35 years of continuous
computation to solve, with the computer being replaced every year by
the next fastest model available. Most of the work will really be
done in the last few years, however."
So how were you able to perform a calculation that should take 35 years in just 4? Where did Rivest get his assumptions wrong?
- CodeArtisan 8y agoYou still need the same amount of iterations (79 685 186 856 218)[1] to resolve the problem but it's now faster because SIMD instructions[2] lowered the amount of cpu cycles needed per operation. Novel algorithms[3] lowered the amount of operations needed per iteration. [1] https://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt https://people.csail.mit.edu/rivest/lcs35-puzzle-description... (short description at the bottom). [2] https://en.wikipedia.org/wiki/SIMD https://en.wikipedia.org/wiki/SIMD [3] https://gmplib.org/manual/Algorithms.html https://gmplib.org/manual/Algorithms.html
- vlovich123 8y agoThe problem appears to be sequential so how would SIMD help? Also what advances in squatting algorithms have there been specifically? None of the links you have provided appear relevant
- eru 8y agoThe numbers involved are quite large. They don't fit into a single computer word. The problem is designed so that iterations have to be sequential, but a single iteration can use parallelism.