Expand description
§Spinlock
There are two insights that speed up part two.
The first is that we don’t need a buffer. We only need to preserve the last value inserted whenever the index becomes zero. Once 50 million values have been inserted then this value is the final result.
The second trick is realizing that we can insert multiple values at a time before the index
wraps around. For example if the index is 1, the current value 10,000 and the step 300,
then we can insert 34 values at once. The div_ceil method is perfect for this computation.
This reduces the number of loops needed to approximately √50000000 = 7071.