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 arithmetic in the ring Z[phi], where
   phi is the golden ratio.**/


public class GoldenRatio {



    /**This routine recognizes numbers of the form
       A+B phi, where A and B are integers.
       The most common uses for this routine are k=1,2.*/

    public static int[] recognize(double d,int depth) {
	double phi=(1+Math.sqrt(5))/2;
	double min=1000.0;
	double test=0;
	int ii=0;
	int jj=0;

	for(int j=-depth;j<=depth;++j) {
	    int lim1=(int)(Math.floor(d-1-j*phi));
	    int lim2=(int)(Math.floor(d+1-j*phi))+1;
	    for(int i=lim1;i<lim2;++i) {
		test=Math.abs(1.0*i+j*phi-d);
		if(min>test) {ii=i;jj=j;min=test;}
	    }
	}
	int[] ans={ii,jj};
	if(min<.00000001) return(ans);
	ans[0]=9999;
	ans[1]=9999;
	return(ans);
    }


    /**This is a similar program with a tolerance you can specify**/

    public static int[] recognize(double d,int depth,double tol) {
	double phi=GoldenRatio.phi(1);
	double test=0;
	int ii=0;
	int jj=0;
	boolean used=false;
	int q=0;
	while((used==false)&&(q<depth)) {
	    ++q;
	    int L=(int)(Math.pow(2,q)); 

	    for(int j=0;j<L;++j) {
	       int lim1=(int)(Math.floor(d-1-j*phi));
	       int lim2=(int)(Math.floor(d+1-j*phi))+1;
	       for(int i=lim1;i<lim2;++i) {
		  test=Math.abs(1.0*i+j*phi-d);
		  if((used==false)&&(test<tol)) {
                       ii=i;
                       jj=j;
                       used=true;
		  }
	       }

	         lim1=(int)(Math.floor(d-1+j*phi));
	         lim2=(int)(Math.floor(d+1+j*phi))+1;
	         for(int i=lim1;i<lim2;++i) {
		  test=Math.abs(1.0*i-j*phi-d);
		  if((used==false)&&(test<tol)) {
                       ii=i;
                       jj=-j;
                       used=true;
		  }
		 }
	    }
	}
	if(used==false) return(null);
	int[] ans={ii,jj};
	return(ans);
    }




    /**This routine is similar to the previous one, but it
       simply chooses the best fit amongst all the values, whether or
       not one of them is the "right" fit."*/


    public static int[] bestFit(double d,int depth) {
	double phi=(1+Math.sqrt(5))/2;
	double min=1000.0;
	double test=0;
	int ii=0;
	int jj=0;

	for(int j=-depth;j<=depth;++j) {
	    int lim1=(int)(Math.floor(d-1-j*phi));
	    int lim2=(int)(Math.floor(d+1-j*phi))+1;
	    for(int i=lim1;i<lim2;++i) {
		test=Math.abs(1.0*i+j*phi-d);
		if(min>test) {ii=i;jj=j;min=test;}
	    }
	}
 	int[] ans={ii,jj};
 	return(ans);
    }



    /**This starts with a number of the form k*phi and adds integers until the result lies in [0,2].**/

    public static double completeParameter(int k) {

	double phi=(1+Math.sqrt(5))/2;
	for(int i=-999;i<1000;i=i+2) {
	    double y=k*phi+i;
	    if((y>=0)&&(y<=2)) return(y);
	}
	return(1);
    }


    public static double phi(int k) {
	double phi=(1+Math.sqrt(5))/2;
	return(Math.pow(phi,k));
    }



}