//Viswanath.java
//Fibonacci but subtract if coin flip is tails, add if heads.
//absolute value of sequence converges to 1.13198824^n
//i.e. Nth root of |Fn| converges to 1.13198824
//i.e. exponential growth rate of random Fibonacci sequence is 1.13198824
//cf. exponential growth rate of Fibonacci sequence is phi golden ratio (1+sqrt(5))/2 =1.61803...

import javax.swing.*;

public class Viswanath  {   

    public static void main (String[] args) {
        int trials, maxF;
        long Fn, Fn1, Fn2;
        double sum=0, sumAbs=0;
        String input;
        double vis= 1.13198824;

        input = JOptionPane.showInputDialog("Number of trials","100");
        trials = Integer.parseInt(input);
 
        input = JOptionPane.showInputDialog("n","100");
        maxF = Integer.parseInt(input);
        maxF++;
        System.out.printf("   Fn            |Fn|       |Fn|^(1/n) \n");
        
        for (int i=0; i<trials; i++) {  

            Fn=0;
            Fn1=1;
            Fn2=1;
 	    //System.out.printf("%2d %6d   \n",1,Fn2);
 	    //System.out.printf("%2d %6d   \n",2,Fn1);
	
 	    for (int n=3; n<=maxF; n++) {
 	        if (Math.random() < 0.5)
 	            Fn = Fn1 + Fn2;
 	        else
 	    	    Fn = Fn2 - Fn1;
 	        //System.out.printf("%2d %6d   %6d    %12.4f\n",
 	            //          n,Fn,Math.abs(Fn),Math.pow(vis,n));
 	        Fn2 = Fn1;
 	        Fn1 = Fn;
 	    }
 	    System.out.printf("%9d   %9d   %12.4f\n",
 	                       Fn,Math.abs(Fn),Math.pow(Math.abs(Fn),1.0/maxF));
 	    sumAbs += Math.abs(Fn);
 	    sum += Fn;
        }
        System.out.printf("\nAvg |Fn|: %12.4f   (Avg |Fn|)^(1/n): %8.4f \n",(sumAbs/trials),Math.pow((sumAbs/trials),1.0/maxF));
        System.out.printf("Avg Fn:   %12.4f   (Avg Fn)^(1/n): %8.4f \n",(sum/trials),Math.pow((sum/trials),1.0/maxF));
        System.out.printf("\n1.13198824^N= %12.4f\n",Math.pow(vis,maxF));
  }
    
}