import java.applet.Applet;
import java.awt.*;
import java.awt.event.*;
import java.applet.*;
import java.awt.geom.*;
import java.math.*;
import java.io.*;


/*This class does basic real arithmetic in the ring Z[phi], where
  phi is the golden ratio.  The class has the form

       a[0]+ phi a[1]

*/


public class GoldenReal {
    long[] a=new long[2];



    
    /**constructors*/

    public GoldenReal() {
	a[0]=0;
	a[1]=0;
    } 

    public GoldenReal(int m,int n) {
	this.a[0]=m;
	this.a[1]=n;
    }

    public GoldenReal(long m,long n) {
	a[0]=m;
	a[1]=n;
    }

    public GoldenReal(GoldenReal x) {
	a[0]=x.a[0];
	a[1]=x.a[1];
    }

    public GoldenReal(double x,int depth) {
	int[] b=GoldenRatio.bestFit(x,depth);
	a[0]=b[0];
	a[1]=b[1];
    }

    public GoldenReal(double x,int depth,double tol) {
	int[] b=GoldenRatio.recognize(x,depth,tol);
	a[0]=b[0];
	a[1]=b[1];
    }


    public void print() {  
        String b=a[0]+" "+"+"+" "+a[1]+" "+"phi";
	System.out.println(b);
    }

    public void printNoLine() {  
        String b=a[0]+" "+"+"+" "+a[1]+" "+"phi";
	System.out.print(b);
    }

    public String toString() {
        Integer Q0=new Integer((int)(a[0]));
        Integer Q1=new Integer((int)(a[1]));
	String a0=Q0.toString();
	String a1=Q1.toString();
        String b=a0+" "+"+"+" "+a1+" "+"\u03A6";
	return(b);
    }

    public void print2() {  
	System.out.println(this.toDouble());
    }

    public static boolean equals(GoldenReal r,GoldenReal s) {
	if(r.a[0]!=s.a[0]) return(false);
	if(r.a[1]!=s.a[1]) return(false);
	return(true);
    }

    public double toDouble() {
	double x=a[0]+GoldenRatio.phi(1)*a[1];
	return(x);
    }

    /**These routines are safeguards to make sure we
       are never doing operations on integers that
       are too large.  It avoids overflow error.**/

    public static void failMessage(GoldenReal x,GoldenReal y) {
	x.print();
	y.print();
	throw(new ProofException("too big"));
    }

    public static boolean tooBig(long k,int exp) {
        long k0=k;
	if(k<0) k0=-k;
	if(k>=Math.pow(2,exp)) return(true);
	return(false);
    }

    public static boolean tooBig(GoldenReal x,int exp) {
	if(tooBig(x.a[0],exp)==true) return(true);
	if(tooBig(x.a[1],exp)==true) return(true);
	return(false);
    }

    public static boolean tooBigPlus(GoldenReal x,GoldenReal y) {
	if(tooBig(x,60)==true) return(true);
	if(tooBig(y,60)==true) return(true);
	return(false);
    }

    public static boolean tooBigTimes(GoldenReal x,GoldenReal y) {
	if(tooBig(x,30)==true) return(true);
	if(tooBig(y,30)==true) return(true);
	return(false);
    }

    public static boolean tooBigUnary(GoldenReal x) {
	if(tooBig(x,30)==true) return(true);
	return(false);
    }



    /***BASIC ARITHMETIC OPERATIONS**/

    /**To run the rigorous proofs with the overflow checks,
       you need to uncomment the lines that have tooBig in 
       them and then recompile the program.**/

    public static GoldenReal plus(GoldenReal x,GoldenReal y) {
	GoldenReal z=new GoldenReal(x.a[0]+y.a[0],x.a[1]+y.a[1]);
	//if(tooBigPlus(x,y)==true) failMessage(x,y);
	return(z);
    }

    public static GoldenReal minus(GoldenReal x,GoldenReal y) {
	GoldenReal z=new GoldenReal(x.a[0]-y.a[0],x.a[1]-y.a[1]);
	//if(tooBigPlus(x,y)==true) failMessage(x,y);
	return(z);
    }

    public GoldenReal negate() {
	//if(tooBigUnary(this)==true) failMessage(this,this);
	return(new GoldenReal(-a[0],-a[1]));
    }


    public static GoldenReal times(GoldenReal x,GoldenReal y) {
	long c0=x.a[0]*y.a[0]+x.a[1]*y.a[1];
	long c1=x.a[1]*y.a[1]+x.a[0]*y.a[1]+x.a[1]*y.a[0];
	GoldenReal z=new GoldenReal(c0,c1);
  	//if(tooBigTimes(x,y)==true) failMessage(x,y);
	return(z);
    }


    public GoldenReal conjugate() {
	//if(tooBigUnary(this)==true) failMessage(this,this);
	return(new GoldenReal(a[0]+a[1],-a[1]));
    }

    /**This routine is only used when the quotient lies in Z[phi].*/

    public static GoldenReal specialDivide(GoldenReal x,GoldenReal y) {
	GoldenReal r1=times(x,y.conjugate());
	GoldenReal r2=times(y,y.conjugate());
	GoldenReal r3=new GoldenReal(r1.a[0]/r2.a[0],r1.a[1]/r2.a[0]);
	GoldenReal xx=times(r3,y);
	//if(tooBigTimes(x,xx)==true) failMessage(x,xx);
	if(equals(x,xx)==true) return(r3);
	return(null);
    }

    /************************************************************/





    /**This routine only returns a true value if the
       number is positive.  However, if might return a false
       value for numbers extremely close to zero.  Such
       exceptions do not arise in our calculations.**/


    public boolean isPositive() {
	BigInteger f1=new BigInteger("354224848179261915075");  //100th fibonacci
	BigInteger f2=new BigInteger("573147844013817084101");  //101st fibonacci
	BigInteger f3=new BigInteger("927372692193078999176");  //102nd fibonacci
	Long a0=new Long(a[0]);
	Long a1=new Long(a[1]);
	BigInteger A0=new BigInteger(a0.toString());
	BigInteger A1=new BigInteger(a1.toString());
	BigInteger B0=f1.multiply(A0);
	B0=B0.add(f2.multiply(A1));
	BigInteger B1=f2.multiply(A0);
	B1=B1.add(f3.multiply(A1));
	BigInteger ZERO=new BigInteger("0");
	if(B0.compareTo(ZERO)!=1) return(false);
	if(B1.compareTo(ZERO)!=1) return(false);
	return(true);
    }

    public boolean isZero() {
	if((a[0]==0)&&(a[1]==0)) return(true);
	return(false);
    }
    public boolean isPositiveOrZero() {
	if(isPositive()==true) return(true);
	if(isZero()==true) return(true);
	return(false);
    }


    /**checks if the first one is less than the second one.**/

    public static boolean isLess(GoldenReal t1,GoldenReal t2) {
	GoldenReal u=minus(t2,t1);
	if(u.isPositive()==true) return(true);
	return(false);
    }



    /**This routine computes integer in kZ less or equal to the
       given goldenreal.  We use floating point arithmetic only
       as a guide for where to begin the search.*/


    public GoldenReal floor(int k) {
	double t=this.toDouble();
	t=k*Math.floor(t/k);
	int LIM=(int)(t);

	for(int i=LIM-k;i<LIM+k;i=i+k) {  
            GoldenReal g=new GoldenReal(i,0);
	    GoldenReal g1=GoldenReal.minus(this,g);
	    GoldenReal g2=GoldenReal.minus(g1,new GoldenReal(k,0));
	    boolean test1=g1.isPositive();
	    boolean test2=g2.isPositive();
	    boolean test3=equals(g1,new GoldenReal(0,0));
	    if(test3==true) {
                return(g);
	    }
	    if((test1==true)&&(test2==false)) {	
               return(g);
	    }
	}
	return(null);
    }



    public GoldenReal dec(int k) {
	GoldenReal r=this.floor(k);
	r=GoldenReal.minus(this,r);
	return(r);
    }

    /**picks a random golden real with both coeffs between -N and N**/

    public static GoldenReal random(int N) {
	int a0=(int)(2*N*Math.random()-N);
	int a1=(int)(2*N*Math.random()-N);
	GoldenReal x=new GoldenReal(a0,a1);
	return(x);
    }


    /**gets a GoldenReal between the two given**/

    public static GoldenReal interpolate(GoldenReal a,GoldenReal b) {
	GoldenReal c=times(a,new GoldenReal(-1,1));
	c=plus(c,times(b,new GoldenReal(2,-1)));
	return(c);
    }

    /**given a list of N+1 GoldenReals, this produces a list of N GoldenReals
       that completely interlace the original list.**/

    public static GoldenReal[] interlace(GoldenReal[] LIST) {
	GoldenReal[] LIST2=new GoldenReal[LIST.length-1];
	for(int i=0;i<LIST2.length;++i) {
	    LIST2[i]=interpolate(LIST[i],LIST[i+1]);
	}
	return(LIST2);
    }

}