The lengths method from question 2 will usually take a long time to calculate the sum of lengths when its input value n is greater than 500 000. To make it faster we can take advantage of the fact that there is considerable overlap between many sequences. For example: if we have already calculated lengths(3) then we must have computed the sequence:
3 10 5 16 8 4 2 1
and would, threfore, also have had access to answers to lengths(10),lengths(5), lengths(16),lengths(8),lengths(4),lengths(2), and lengths(1). If we can store at least some of these temporary solutions as we go, and then use them, when possible, then the speed of lengths is greatly increased.
In a file called SyraLengthsEfficient.java write a new version of lengths that behaves the same way as the lengths from question two above, but is able to work much faster for large numbers by memorising some partial solutions.
This new syraLength and it's encapsulating class must contain the code necessary to remember and recall the values of some intermediate lengths.
Campbell Ritchie wrote:Please write down the algorithm you are using for the Syracuse sequence, because most people here are not familiar with it.
You will have to work out whether you are putting things on the stack and whether you are taking them off, but you can only do that when you know how the algorithm works.
And welcome to the Ranch