package transcend;
//© Stephen Lee www.chronon.org

import java.util.*;
import java.text.*;
import java.awt.*;
import java.awt.event.*;
import java.applet.*;
import java.lang.*;
import java.math.*;

public class transa extends Applet
  implements Runnable,MouseListener{

final int Hlim=32;
final int dwid=50;

Interval curp,alt;
String v1;
long p[],dp[];
TextArea TA=new TextArea();
Thread t1=null;
String newline;
Label lab1=new Label();
Label lab2=new Label();
long s[],r[],rh[][];
int H,n,posn,ns,nr,DPs,sfree,sfact,instk;
BigDecimal eps;
BigDecimal TWO=BigDecimal.valueOf(2);
Interval[] in=new Interval[5];
Checkbox PauseB= new Checkbox("Pause");



void trans(long q[],int qn,long t){
int i,j;
for (i=0;i<qn;i++)rh[i][0]=q[qn];
for (j=1;j<qn;j++)rh[0][j]=rh[0][j-1]*t+q[qn-j];
q[0]=rh[0][qn-1]*t+q[0];
for (i=1;i<qn;i++){
  for (j=1;j<qn-i;j++)rh[i][j]=t*rh[i][j-1]+rh[i-1][j];
  q[i]=t*rh[i][qn-i-1]+rh[i-1][qn-i];}
}

void trans1(long q[],int qn){trans(q,qn,1);}

void invert(long q[],int qn){
int i;long t;
for (i=0;i<=qn/2;i++){t=q[i];q[i]=q[n-i];q[n-i]=t;}}

int lbd(long p[],int n){
int k,l;
double min,x;
l=0;min=10000000.0;
for (k=1;k<=n;k++)if ((p[k]<0)==(p[0]>0))l++;
for (k=1;k<=n;k++)if ((p[k]<0)==(p[0]>0)){
  x=Math.pow(Math.abs((double)p[0]/(p[k]*l)),1.0/k);
  if (x<min)min=x;}
return (int)Math.floor(min);
}

int ubd(long p[],int n){
int k,l;
double max,x;
l=0;max=0.0;
for (k=0;k<n;k++)if ((p[k]<0)==(p[n]>0))l++;
for (k=0;k<n;k++)if ((p[k]<0)==(p[n]>0)){
  x=Math.pow(Math.abs((double)(p[k]*l)/p[n]),1.0/(n-k));
  if (x>max)max=x;}
return (int)Math.ceil(max);
}

char differ(char c){
char r;
if (c=='0')return'5';
else return (char)(c-1);}

void putdigit(BigDecimal num){
lab1.setText("Decimal Place: "+DPs);
try {Thread.sleep(10);} catch (InterruptedException e){}
posn++;
//There's a bug with text area which means that mouse dragging may delete some text
//even when non-editable.  Setting
//TA.setEnabled(false);
//at this point seems to prevent it, but also makes the text flicker slightly
if (posn>=dwid){TA.append(newline);posn=0;}
TA.append(String.valueOf(differ(num.toString().charAt(DPs))));
//TA.setEnabled(true);
}

void xroot(long x,long y){
BigDecimal num,den;
DPs++;
num=BigDecimal.valueOf(x);
den=BigDecimal.valueOf(y);
num=num.divide(den,DPs,BigDecimal.ROUND_HALF_DOWN);
putdigit(num);
}

BigDecimal eval(long p[],int n,BigDecimal x){
BigDecimal res;
String vr;
int i;
res=BigDecimal.valueOf(p[n]);vr=res.toString();
for (i=n-1;i>=0;i--){
  res=res.multiply(x).add(BigDecimal.valueOf(p[i]));
  vr=res.toString();}
return res;}

void root(Interval in){
BigDecimal x,y,t1,t2,del;
boolean zd;
int acc=DPs+5;
DPs++;
if (in.d==0){in.b=ubd(p,n);in.d=1;}
if (in.c==0){in.a=ubd(p,n);in.c=1;}
eps=new BigDecimal(BigInteger.valueOf(1),acc);
x=BigDecimal.valueOf(in.b*in.c+in.a*in.d);
y=BigDecimal.valueOf(2*in.c*in.d);
del=BigDecimal.valueOf(Math.abs(in.b*in.c-in.a*in.d)).divide(y,acc,BigDecimal.ROUND_HALF_DOWN);
x=x.divide(y,acc,BigDecimal.ROUND_HALF_DOWN);
v1=x.toString();
do{
do{
  t2=eval(dp,n-1,x);v1=t2.toString();
  zd=t2.signum()==0;
  if (zd){del=del.divide(TWO,acc,BigDecimal.ROUND_HALF_DOWN);x=x.add(del);}
  }while (zd);
t1=eval(p,n,x);v1=t1.toString();
del=t1.divide(t2,acc,BigDecimal.ROUND_HALF_DOWN);v1=del.toString();
x=x.subtract(del);
v1=x.toString();
}while (del.abs().compareTo(eps)>0);
putdigit(x);
}

//-------------Interval------------------

class Interval{
long a,b,c,d;long q[];int n,s;
Interval(int n){q=new long[n];}

public void setvals(long a1,long b1,long c1,long d1,long q1[],int n1,int s1){
int i;
if (q1!=null)
  for (i=0;i<=n1;i++)
    q[i]=q1[i];
a=a1;b=b1;c=c1;d=d1;s=s1;n=n1;
}

public void setvals(Interval in){
setvals(in.a,in.b,in.c,in.d,in.q,in.n,in.s);}

public Interval copy(){
Interval on=new Interval(n+1);
on.setvals(a,b,c,d,q,n,s);
return on;}

int zchk(){
int i;
if (q[0]==0){xroot(b,d);
  for (i=0;i<n;i++)q[i]=q[i+1];n--;
  return 1;}
return 0;
}

void rootsloop(){
int m,al,i,j,r;
do{
al=lbd(q,n);
if (al>16) {
  a=al*a;c=al*c;m=1;
  for (i=0;i<n;i++){q[i]*=m;m*=al;}
  al=1;}
if (al>=1) {trans(q,n,al);b=al*a+b;c=al*c;}
zchk();
s=sgc(q,n);
if (s<2) {
  if (s==1)
    root(curp);
  return;}
for (i=0;i<=n;i++)alt.q[i]=q[i];
alt.setvals(a,a+b,c,c+d,q,n,s);
trans1(alt.q,n);r=alt.zchk();alt.s=sgc(alt.q,alt.n);
setvals(b,a+b,d,c+d,null,n,s-alt.s-r);
if (alt.s==1){
  root(alt);alt.s--;}
if (s>=2){
  invert(q,n);
  trans1(q,n);
  s=sgc(q,n);}
if (s<2){
  if (s==1)
    root(curp);
  if (alt.s==0)return;
  setvals(alt);}
else if (alt.s>=2)in[instk++].setvals(alt);
}while (true);}
}//-------------------------------------------Interval


public void init() {
newline = System.getProperty("line.separator");
setLayout(null);
setBackground(new Color(230,240,240));
add(TA);
TA.setBounds(20,30,400,350);
TA.append(newline);
TA.setBackground(Color.white);
add(PauseB);
PauseB.setBounds(350,10,100,20);
add(lab1);
lab1.setBounds(20,10,120,20);
add(lab2);
lab2.setBounds(150,10,180,20);}

public void start(){
TA.setEditable(false);
TA.setText("0.");
t1=new Thread(this);
t1.start();
}
public void stop() {t1.stop();}
//public void paint(Graphics g){}

public int sgc(long p[],int n){
int i,ct;boolean pos;
ct=0;pos=p[n]>0;
for(i=n-1;i>=0;i--)
  if (pos){if (p[i]<0){pos=false;ct++;}}else if (p[i]>0){pos=true;ct++;}
return ct;}


public String showpoly(long a[],int n)
{
int i;long v;
String p;
p=new String();
for (i=n;i>=0;i--){
  if (a[i]!=0){v=Math.abs(a[i]);
    if (i<n)
      if (v>0)p=p+((a[i]<0)?"-":"+");
    if (v>1|i==0) p=p+v;
    if (i>0){p=p+"x";
      if (i>1){p=p+"^"+i;}}}}
return p;
}

public void showroots(){
int s;
s=sgc(p,n);
in[0].setvals(1,0,0,1,p,n,s);
if (s<2){
  if (s==1) root(in[0]);
  return;}
instk=1;
do{curp=in[--instk].copy();
curp.rootsloop();
}while (instk>0);
}

public void sdigs(){
}

public void psimp(long r[],int nr){
long g;int i;
g=r[nr];for (i=nr-1;i>=0;i--)if (r[i]!=0)g=gcd(g,r[i]);
if (r[nr]<0)g=-g;
for (i=0;i<=nr;i++)r[i]=r[i]/g;}

public long gcd(long a,long b){
long t,g;
g=1;a=Math.abs(a);b=Math.abs(b);
while ((a&1)==0&(b&1)==0) {a=a/2;b=b/2;g=g*2;}
while (b!=0) {
  if ((a&1)==0) a=a/2;
  else if ((b&1)==0) b=b/2;
  else if (a>b) a=(a-b)/2;
  else b=(b-a)/2;}
return a*g;}

public boolean pgcd(){
long rm,sm,gc;
int i,dn;
ns=n-1;if (ns==0) return false;
for (i=0;i<n;i++)s[i]=dp[i];
sm=s[ns]/(long)p[n];rm=1;
for (i=1;i<=n-1;i++) r[i]=sm*p[i]-rm*s[i-1];
r[0]=sm*p[0];
nr=-1;for (i=0;i<n;i++)if (r[i]!=0) nr=i;
while (true) {
if (nr<=ns){dn=ns-nr;
  psimp(s,ns);
  if (nr==-1) {nr=ns;for (i=0;i<=nr;i++) r[i]=s[i];
    return true;}
  if (nr==0) return false; //no common factor
  gc=gcd(s[ns],r[nr]);sm=s[ns]/gc;rm=r[nr]/gc;
  for (i=dn;i<ns;i++) s[i]=(rm*s[i]-sm*r[i-dn]);
  for (i=0;i<dn;i++) s[i]=rm*s[i];
  dn=-1;for (i=0;i<ns;i++)if (s[i]!=0)dn=i;
  ns=dn;}
else{dn=nr-ns;
  psimp(r,nr);
  if (ns==-1)
   return true;//r is common factor
  if (ns==0) return false; //no common factor
  gc=gcd(s[ns],r[nr]);sm=s[ns]/gc;rm=r[nr]/gc;
  for (i=dn;i<nr;i++) r[i]=(sm*r[i]-rm*s[i-dn]);
  for (i=0;i<dn;i++) r[i]=sm*r[i];
  dn=-1;for (i=0;i<nr;i++)if (r[i]!=0) dn=i;
  nr=dn;}}
}

public void dopoly(){
int count;
if (pgcd()){sfact++;return;}
while (PauseB.getState())
  try {Thread.sleep(10);} catch (InterruptedException e){}
sfree++;
count=sfact+sfree;
lab2.setText("Polynomial: "+showpoly(p,n));
showroots();
}

public void dopolys(int r,int j){
int l;
if (j==0){
  p[0]=r;dopoly();
  p[0]=-r;dopoly();}
else for (l=-r+1;l<=+r-1;l++){
  p[j]=l;dp[j-1]=j*l;
  dopolys(r-Math.abs(l),j-1);
}}

public void run() {
int i,j,an;
posn=1;
j=0;
H=0;DPs=1;sfree=0;sfact=0;
for (H=3;H<Hlim;H++){
  for (i=0;i<5;i++)in[i]=new Interval(H);
  for (n=1;n<H-2;n++){
    p=new long[n+1];dp=new long[n];
    r=new long[n];s=new long[n];
    rh=new long[n][];
    curp=new Interval(n+1);alt=new Interval(n+1);
    for (i = 0; i < rh.length; i++) rh[i] = new long[n-i];
    for (an=1;an<=H-n-1;an++){
      p[n]=an;dp[n-1]=n*an;
      dopolys(H-n-Math.abs(an),n-1);}}}
}

public void paint(Graphics g){super.paint(g);}

public void mouseClicked(MouseEvent e){Toolkit.getDefaultToolkit().beep();}
public void mousePressed(MouseEvent e){};
public void mouseReleased(MouseEvent e){};
public void mouseEntered(MouseEvent e){};
public void mouseExited(MouseEvent e){};

public String getAppletInfo() {return "Transcendental Number";}
}