import java.applet.Applet; import java.awt.event.*; import java.awt.*; public class MathRational { public int p; //numerator public int q; //denominator public int code; public int level; public MathRational(int p,int q) { this.p=p; this.q=q; this.code=0; this.level=0; } public MathRational() {} /*The first part of this file deals with the approximation of real numbers by rationals.*/ public static MathRational reduce(MathRational F) { int k=GCD(F.p,F.q); MathRational G=new MathRational(F.p/k,F.q/k); return(G); } public static int[] reduce(int a,int b) { int c=GCD(a,b); int[] d={a/c,b/c}; return(d); } public static MathRational average(MathRational F1,MathRational F2) { MathRational G1=reduce(F1); MathRational G2=reduce(F2); MathRational H=new MathRational(G1.p+G2.p,G1.q+G2.q); H=reduce(H); return(H); } /* 1 means (nearly) equals left endpoint 2 means inside 3 means (nearly) equals right endpoint 0 means outside */ public static int isInside(double x,MathRational[] F) { double f0=1.0*F[0].p/F[0].q; double f1=1.0*F[1].p/F[1].q; double cutoff=0.000000000000001; if(xf1+cutoff) return(0); if(Math.abs(x-f0)<=cutoff) return(1); if(Math.abs(x-f1)<=cutoff) return(3); return(2); } public static MathRational[] subdivide0(int k,MathRational[] F) { MathRational[] G=new MathRational[2]; G[0]=new MathRational(0,1); G[1]=new MathRational(1,1); if(k==0) { G[0]=new MathRational(F[0].p,F[0].q); G[1]=average(F[0],F[1]); } if(k==1) { G[0]=average(F[0],F[1]); G[1]=new MathRational(F[1].p,F[1].q); } G[0].code=k; return(G); } public static MathRational[] subdivide(double x,MathRational[] F) { MathRational[] G1=subdivide0(0,F); MathRational[] G2=subdivide0(1,F); int test=isInside(x,G2); if(test!=0) return(G2); return(G1); } /**the double should be between 0 and 1*/ public static MathRational approximate0(double x,double tol) { MathRational[] F=new MathRational[2]; int code=0; F[0]=new MathRational(0,1); F[1]=new MathRational(1,1); int count=0; double test=1.0; while((count<500)&&(test>tol)) { ++count; F=subdivide(x,F); double f0=1.0*F[0].p/F[0].q; double f1=1.0*F[1].p/F[1].q; test=Math.abs(f0-f1); } MathRational G=average(F[0],F[1]); double d1=1.0*G.p/G.q-x; if(d1>0) return(F[0]); return(F[1]); } public static int[] approximate(double x,double tol) { double x1=Math.floor(x); double x2=x-x1; int[] I=new int[2]; if(Math.abs(x2)<.00000001) { I[0]=(int)(x1); I[1]=1; return(I); } if(Math.abs(x2)>1-.00000001) { I[0]=(int)(x1+1); I[1]=1; return(I); } MathRational F=approximate0(x2,tol); I[0]=(int)(x1*F.q+F.p); I[1]=F.q; return(I); } /*This part of the file deals with the inferior and superior sequences constructed in the monograph*/ /*This first routine implements the extended Euclidean algorithm. This is to say that program takes integers a,b and finds not only g=gcd(a,b) but also integers c,d such that ac+bd=g. I originally had programmed my own version of the Euclidean algorithm, but I lifted this algorithm from the internet. The algorithm is taken from Donald Knuth's book of algorithms.*/ public static int[] GCDe(int a,int b) { int u,v,g; int u1,v1,g1; int t1,t2,t3; int q; u = 1; v = 0; g = a; u1 = 0; v1 = 1; g1 = b; while (g1 != 0) { q = g/g1; t1 = u - q*u1; t2 = v - q*v1; t3 = g - q*g1; u = u1; v = v1; g = g1; u1 = t1; v1 = t2; g1 = t3; } int[] x={u,v,g}; return(x); } /*This just computes the greatest common divisor, without the coefficients.*/ public static int GCD(int a,int b) { int[] x=GCDe(a,b); return(x[2]); } /*In the notation of the monograph, these routines compute A+ and A-, the two simpler rationals that are Farey related to A=a/b.*/ public static int[] RMINUS(int a,int b) { if(a==1) { int[] x={0,1}; return(x); } int[] d=GCDe(a,b); d[1]=-d[1]; int t=(int)(Math.floor(1.0*d[0]/b)); d[0]=d[0]-t*b; d[1]=d[1]-t*a; int[] e={d[1],d[0]}; return(e); } public static int[] RPLUS(int a,int b) { int[] x = RMINUS(a,b); int[] y={a-x[0],b-x[1]}; return(y); } /*Here are the inferior and superior predecessor functions from the monograph */ public static int[] inferiorPredecessor(int a,int b) { int[] d1=RMINUS(a,b); int[] d2={a-d1[0],b-d1[1]}; int[] e=new int[2]; e[0]=d1[0]-d2[0]; e[1]=d1[1]-d2[1]; if(e[0]<0) e[0]=-e[0]; if(e[1]<0) e[1]=-e[1]; return(e); } public static int[] superiorPredecessor(int a,int b) { if(a==1) { int[] x={1,1}; return(x); } int test=0; int[] c=new int[2]; c[0]=a; c[1]=b; while(test==0) { int k=diophantine(c[0],c[1]); if(k>1) test=1; if(b==1) test=1; c=inferiorPredecessor(c[0],c[1]); } return(c); } /* In the notation of the monograph, this computes the renormalization constant between a rational and its inferior predecessor*/ public static int diophantine(int a,int b) { int[] c=inferiorPredecessor(a,b); double A1=1.0*a/b; double A0=1.0*c[0]/c[1]; double k=2.0/(c[1]*c[1]*Math.abs(A0-A1)); int kk=(int)(Math.floor(k)); return(kk); } /*This routine generates more complicated rationals from simpler ones. Given the rational aa/bb, the rational produced has aa/bb as an inferior predecessor, at least when p/q=1/2. When p/q != 1/2, the relation between aa/bb and the output is more subtle.*/ public static int[] computeModular(int aa,int bb,int p,int q,int n) { int a=aa; int b=bb; if(a>b) a=a%b; int[] dd=RPLUS(a,b); int c=dd[0]; int d=dd[1]; int[] u=new int[2]; u[0]=a*p+c*q+a*n*q; u[1]=b*p+d*q+b*n*q; int div=MathRational.GCD(u[0],u[1]); u[0]=u[0]/div; u[1]=u[1]/div; return(u); } //for even rationals public static int[] oddPredecessor(int a,int b) { int[] d1=RPLUS(a,b); int[] d2=RMINUS(a,b); int test=(d1[0]*d1[1])%2; if(test==1) return(d1); return(d2); } public static int[] evenPredecessor(int a,int b) { int[] d1=RPLUS(a,b); int[] d2=RMINUS(a,b); int test=(d1[0]*d1[1])%2; if(test==1) return(d2); return(d1); } public static int[] oddSuccessor(int a,int b) { int[] x=oddPredecessor(a,b); int c=2*a-x[0]; int d=2*b-x[1]; int[] aa={c,d}; return(aa); } public static int[] oppositeType(int a,int b) { System.out.println("test1 "+a+" "+b); int test1=(a*b)%2; int[] d1=RPLUS(a,b); int[] d2=RMINUS(a,b); int test2=(d1[0]*d1[1])%2; if(test2==test1) return(d2); return(d1); } /*pivot points: answer is returned as (left_x,left_y,right_x,right_y)*/ public static int[] pivot(int p,int q) { int test=(p+q)%2; int pp=p; int qq=q; if(test==1) { int[] x=oddSuccessor(p,q); pp=x[0]; qq=x[1]; } return(oddPivot(pp,qq)); } public static int[] oddPivot(int p,int q) { int[][] x=new int[100][2]; int[] d=new int[100]; int[] e=new int[100]; int test=0; int count=0; x[0][0]=p; x[0][1]=q; while(test==0) { x[count+1]=inferiorPredecessor(x[count][0],x[count][1]); d[count+1]=x[count][1]/(2*x[count+1][1]); double y0=1.0*x[count+0][0]/x[count+0][1]; double y1=1.0*x[count+1][0]/x[count+1][1]; e[count+1]=1; if(y00) a2=a2+x[i][1]*d[i]; if(e[i]>0) b2=b2-x[i][0]*d[i]; } int[] aa={a1,b1,a2,b2}; return(aa); } }