Friday 2 January 2015

Fibonacci Sequence (Part 1)

Our younger son was given a Raspberry Pi for Christmas. He loaded Python onto it and started to work out terms in the Fibonacci sequence. To my surprise, the number of significant figures provided by integer addition in Python is limited only by the amount of available memory. He was therefore able to work out the millionth term of the series and tell me that it is over 200,000 digits long. I wondered if there was any way I could check this in Java. First I wrote a simple program to calculate up to the 100th term:

andrew@UBUNTU:~/Java$ cat prog64.java
public class prog64
{
public static void main (String args[])
  {
  int x = 1;
  int y = 1;
  int term;
  for (int z=1; z<=50; z++)
    {
    term = 2*z-1;
    System.out.println("Term " + term + " = " + x);
    term++;
    System.out.println("Term " + term + " = " + y);
    x = x + y;
    y = x + y;
    }
  }
}
andrew@UBUNTU:~/Java$ javac prog64.java
andrew@UBUNTU:~/Java$ java prog64
Term 1 = 1
Term 2 = 1
Term 3 = 2
Term 4 = 3
Term 5 = 5
Term 6 = 8
Term 7 = 13
Term 8 = 21
Term 9 = 34
Term 10 = 55
Term 11 = 89
Term 12 = 144
Term 13 = 233
Term 14 = 377
Term 15 = 610
Term 16 = 987
Term 17 = 1597
Term 18 = 2584
Term 19 = 4181
Term 20 = 6765
etc

etc

It calculated the first few terms without any difficulty but ran out of significant figures while working out term 47. To make matters worse, it then gave incorrect values and did not tell me it had gone wrong:

etc
etc
Term 45 = 1134903170
Term 46 = 1836311903
Term 47 = -1323752223
Term 48 = 512559680
Term 49 = -811192543
Term 50 = -298632863
Term 51 = -1109825406
Term 52 = -1408458269
Term 53 = 1776683621
Term 54 = 368225352
etc

etc

Time for some research, I think (more to follow).