Updates to my BC number theory programs

• 10th January 2008. Added nicf_pqa0(d,t,p,q,e) to nipell. Bugs fixed subsequently.
• 8th January 2008. I now convert the input surd (u +t√d)/v to standard form in files nipell and nscf_pell. ie. (U +√D)/V, where gcd(U, V, (D - V²)/V) = 1.
  
• 1st December 2007. Removed auto variables t1 and t2 in nscf_pell(d,e). Apparently 26 is the maximum number of auto variables allowed in a BC function! Also tightened the logic in the definition of the partial numerators a[i].
• 15th November 2007. Added gcd3(a,b,c).
• Altered the code for the nearest square algorithm so as to agree with lines 5-6, page 25, of the A.A.K. Ayyangar paper, when |Q'| = |Q"|.
• 2nd November 2007. Added nscf_pqa(d,t,p,q,e) to nscf_pell.
• 1st November 2007.Made some small improvements and corrections (regarding the period length) to nscf_pell and nipell.
• 31st October 2007. Added nscf_pell.
• 22nd October 2007. Added nicf_pqa(d,t,u,v,e) to nipell.
• 18th October 2007. Added nicf(m,n) to lra.
• 12th October 2007. Corrected output about period in nipell.
• 11th October 2007. Added nipell.
• 12th February 2007. Added sqrtd_period.
• 9th February 2007. Added decimal2rational.
• 8th February 2007. Removed the restriction gcd(b,n)=1 from the decimal program.
• 15th November 2006. Small improvement to reducepos.
• 13th June 2006. Fixed a serious error in nprimeap.
• 8th August 2004. Added binary to patz.
• 4th August 2004. Added quadratic to squareroot.
• 16th July 2004. Added patz.
• 14th July 2004. squareroot continues to haunt me.
  • I fixed a bug in relation to solving x² 0 (mod 2).
  • Also had an incorrect construction for extending the solutions to original modulus n, so as to list them in the form ±P (mod n), with 0 ≤ P ≤ n/2.
  • Replaced if(qglobal[i]==2 && number==1) by if(number==1). This error was giving the wrong answer in x² 0 (mod 6).
• 14th May 2004. Added forster_log.
• 13th May 2004. Noticed that I'd omitted a restriction that in discrete_log, we must have p < 2³²-2¹⁶ in order to satisy BC array upper bound length of 2¹⁶-1.
• 27th April 2004. Fixed a small global variable problem arising when calculating Ramanujan's tau function tau_composite(n). Having factored n and obtained global variables representing the prime factors q[i] and their exponents k[i], I inadvertently changed these on subsequent factorisations involved in calculating tau(q[i]).
• 21st April 2004. Added sigmak(k,n) and tau to phi.
• 15th April 2004. Added squareroot, which is a cleaner version of sqroot. The new program contains cornacchia(a,b,m).
• 7th April 2004. Improved factor and phi by incorporating pollard.
• 24th March 2004. Changed name of cfrace to davison.
• 23rd March 2004. Added cfrace.
• 22nd March 2004. Added raney.
• 19th March 2004. Inserted a sign term in function padic.
• 17th March 2004. Changed name of 2adic to p-adic. Also added padic(a,p,n).
• 10th March 2004. Added 2adic.
• 27th February 2004. Added factorial.
• 26th February 2004. Added binomial.
• 22nd May 2003. Added unimodular.
• 15th May 2003. Added the solution of equations x²-d*y²=±3 and ±4 to pell.
• 14th May 2003. Added table(m,n) to classnopos.
• 14th May 2003. Added table(m,n) to classnoneg.
• 12th May 2003. Fixed a small error in the function period. It was supposed to be returning the cycle-length, not global_count!
• 12th May 2003. Added class_number0(d) to classnopos.
• 7th May 2003. Fixed an error on lines 58-60 of classnoneg.
• 5th May 2003. Added classnopos.
• 1st May 2003. Added reduceneg.
• 29th April 2003. Added classnoneg.
• 28th April 2003. Changed the output of surd to allow choice of printing complete quotients.
• 27th April 2003. Added reducepos.
• 20th April 2003. Fixed a trivial printing error at the end of unit.
• 19th February 2003. Added program john.
• 23rd September 2002. Fixed errors on lines 104 and 112 of lagrange, where I had 2 instead of n.
• 18th September 2002. lagrange now needs sturm. gcdpi and sturm now have an extra parameter e, where e=0 suppresses printing. lagrange has also been tightened up. We now check that the input polynomial satisfies the appropriate restrictions. Also the program now handles the case when the root above 1 is in fact rational.
• 16th September 2002. Improved printp in sturm.
• 15th September 2002. Added sturm.
• 11th September 2002. Interchanged lines 43 and 44 in decimal to fix a printing error.
• 9th September 2002. Added nprime and nprimeap.
• 3rd September 2002. primes now generates more primes.
• 3rd September 2002. Made a small improvement to primes when m=2.
• 2nd September 2002. Added missing else b=0 at line 214 of proth.
• 27th August 2002. Rewrote leastqnr so that it ony needs mpower as in gcd.
• 25th August 2002. Improved the output of surd.
• 22nd August 2002. Improved the output of pell.
• 9th August 2002. Added base and perfect_power.
• 31st July 2002. Replaced "<=" by "<" on line 11 of mthrootr() in gcd.
• 25th June 2002. Replaced all log programs by log.
• 14th June 2002. Added another log program - log2.
• 8th March 2002. I removed the line j=2 from gcd1 in gcd and sqroot. (Kindly pointed out by Kjell Wooding.)
• 10th August 2001. I reinstated log1.
• 24th July 2001. I replaced the above log program by the one that is currently in my manuscript log.pdf.
• 14th June 2001. Today I noticed problems with degenerate cases arising from small r in my log algorithm.
• 23rd February 2001. Added tomas2.
• 13th February 2001. Added tomas1.
• 20th October 2000. Altered unit so that when d=5 it returned the correct answer.
• 7th August 2000. Altered log(a,b,r,e) to log(a,b,d,r,e)
• 29th July 2000. Improved the printing in log.
• 6th May 2000. Fixed a bug in surd.
• 1st May 2000. Corrected printing of output in thue: changed s to t at appropriate places.
• 26th April 2000. surd now prints P_n and Q_n, where the nth complete quotient is (P_n+sqrt(d))/Q_n.
• 11th April 2000. Realised sqroot still had some bugs. Hopefully these are now fixed.
• 7th April 2000. Replaced sqroot by an improved version which solves the general congruence x²d (mod n). Any bug reports are gratefully received.
• 6th April 2000. Realised sqroot has some bugs.
• 5th April 2000. Changed thue(d,p) to thue(d,u,p).
• 4th April 2000. Added sqroot. This finds all solutions of x²d (mod n) where gcd(d,n)=1.
• 3rd April 2000. Changed name of chineseab() to chineseb(). Rewrote chinesea() and chineseb().
• 2nd April 2000. Added printing of partial quotients and truncated decimal expansion to log. Removed printing of A[i]. Also added thue. Here d>1, is not a square, p an odd prime not dividing d-1. Then thue(d,p) finds x,y such that x²-dy²=kp, with small k.
• 1st April 2000. jacobi now does not need gcd and is a stand-alone program.
  
• 28th March 2000. Discovered that the old version of log did not always give the correct partial quotients. The current version seems to be more reliable. Type log(3,2,2,10,0) to output roughly 20 partial quotients of log₂(3), whereas typing log(3,2,2,10,1) prints the A[i] of algorithm 1 of manuscript log.pdf. The number of partial quotients is returned in both cases.
• 13th March 2000. Made some improvements to the output of log.
• 4th March 2000. Added rootd_modn. This is a crude program for solving x²d (mod n) with 0 ≤ x ≤ n/2 for small n.
• Added log. This is a discrete variant of Shank's algorithm for computing the simple continued fraction for log_bn, (Math. Tables and Aids to Computation. 8, 1954, 60-64), originally written by Alan Offer and recently improved by vacation scholar Sean Seefried and myself. It should currently be treated with caution. For while we believe that log(n,b,z,e) computes approximately 2z partial quotients of log_bn, we cannot guarantee the correctness of output!.
• lagrange was improved by Sean Seefried, using the binary search method in page 261 of Number Theory with Computer Applications, by R. Kumanduri and C. Romero, 17th December 1999.
• Improved the euclid program. It now prints the s[k] and t[k] associated with Euclid's algorithm.
• Forgot to test possibility n_p=2 in leastqnr(p). Fixed 28th September 1999.
• Cosmetic alterations to the tonelli program, 24th August 1999.
• Added leastqnr, 13th August 1999. Also removed dependence of proth on phi and gcd.
  
• Removed dependence of lucas on phi.
  
• Tightened up the discrete_log program, 11th August 1999.
• Added the discrete_log program, 12th July 1999.
• Added the tonelli program, 29th June 1999.
• Fixed bug in gcd in lcma(m[ ],n) (should have returned b[n-1], not b[n]) 11th November 1998.
• Added some functions to phi that are normally in gcd, 9th October 1998.
• Added recursion, 3rd May 1998.
• Added the lupei program. 24th March 1998.
• Added to lra. 21st December 1997.
• Added the lagrange program. 17th December 1997.
• Added the convergents program. 15th December 1997.
• Added the lra program. 24th January 1997.
• Added the venturini1 program. 1st April 1996.
• Added a missing case at line 27 in unit(n). 5th November 1995.
• Added the mordell program. 26th September 1995.
• Added the challenge program. 27th August 1995.
• Added the 3branch program. 26th August 1995. Fixed a bug there on 27th August 1995
• 15th June 95. Deleted the for loop in function b(n) on line 253 of factors.

Email
http://www.numbertheory.org/keith.html

Last modified 31st October 2007