/* BC program wildberger1. * This solves Pell's equation using Norman Wildberger's algorithm. * See http://www.numbertheory.org/php/wildberger.html * e=1 is verbose. */ define wild(d,e){ auto a,b,c,t,i,u,v,r,s,lr[],j,count,temp,flag,negv,negs a=1 b=0 c=-d u=1 v=0 r=0 s=1 i=0 flag=0 if(e){ print "(a[0[,b[0],c[0])=(1,0,",-d,")\n" } while(1){ t=a+2*b+c if(t>0){ a=t b=b+c u=u+v r=r+s if(e){ print"L:" } lr[i]=-1 }else{ b=a+b c=t v=u+v s=r+s if(e){ print"R:" } lr[i]=1 } temp=i+1 if(e){ print "N[",temp,"]=(",u,",",v,",",r,",",s,")\n" print "(a[",temp,"],b[",temp,"],c[",temp,"])=(",a,",",b,",",c,")\n" } if(a==d && b==0 && c==-1){ negv=v negs=s flag=1 } if(a==1 && b==0 && c=-d){ if(flag){ print "The negative Pell equation has least positive solution (",negv,",",negs ,")\n" } print "The Pell equation has least positive solution (",u,",",r ,")\n" count=i+1 if(e){ print "N[",temp,"]=" for(k=i;k>=0;k--){ if(lr[k]==1){ print "R" }else{ print "L" } } print "\n" print "=" while(i>=0){ if(lr[i]==1){ j=0 print "R" while(i>=0 && lr[i]==1){ i=i-1 j=j+1 } } if(j>1){ print j } if(i>0){ print"." } if(i==-1){ break } if(lr[i]==-1 && i>=0){ j=0 print "L" while(lr[i]==-1){ i=i-1 j=j+1 } } if(j>1){ print j } print"." } print "\n" print "number of matrices R and L in N[",temp,"] = " } return(count) } i=i+1 } }