Problem 67 Fibonacci sequence
Back to General discussions forum
Hi all, I believe I have worked out an algorithm which would solve this. However, problem seems to be that the numbers to be checked are just too big to work in java, even using the "long" type. Is there anything I am missing here? Any little hint to get me on right track would be appreciated :-)
I've got the same trouble. And this hint about pen and paper doesn't help at all. The main problem: how to enter these immense numbers to the program.
There are multiple ways of solving this problem. This is one way.
If you have two enormous numbers, each containing many thousands of digits, one way of adding them is to do one digit at a time, e.g. say the numbers end with "...9483" and "...6271"
If you add 3+1=4 you know that the last digit of the answer is 4.
If you then add 8+7=15 you know that the last but one digit of the answer is 5 and there's 1 to carry.
Then, by adding 4+2+1=7 (the 1 is the carry) you know that the next digit of the answer is 7 (and nothing to carry).
You now know that the answer ends with the digits "754".
If you continue until you reach the start of the two enormous numbers you'll have added them together.
Try reading up on modular arithmetic.
http://www.codeabbey.com/index/wiki/modular-arithmetic
That's the method I used to solve the problem.
-- Christopher P. Matthews