Changes and additions to Keith Matthews' BCMATH programs

28th April 2008. Added an algorithm for converting the RCF, up to the end of the first period, into the NICF.
21st April 2008. I realised that the Selenius singularization algorithm does not necessarily convert an RCF period directly into an NSCF period. (It does if ξ₀=√D.) So now I only output the NSCF expansion until the end of the first RCF period, without determining the NSCF period.
18th April 2008. Added Selenius' algorithm for converting the RCF up to the end of the first period to the NSCF.
4th April 2008. Added the optimal continued fraction algorithm for rationals.
2nd April 2008. Added the choice of not printing the b_k and u_k/v_k in the optimal continued fraction algorithm.
1st April 2008. Fixed a logical error in my coding of the optimal continued fraction algorithm.
14th February 2008. Added the optimal continued fraction algorithm of Wieb Bosma.
10th January 2008. I improved the output for NICF program. Currently (11.30am Brisbane time), I have a resulting tricky bold font problem to fix. (This was fixed at 2.40pm Brisbane time.)
7th January 2007. I now convert the input surd (u +t√d)/v to standard form in various continued fraction programs. ie. (U +√D)/V, where gcd(U, V, (D - V²)/V) = 1.
20th November 2007. Fixed a bug in [1].
13th November 2007. Altered the code in [1] and [2] 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"|.
Also added to the description of [1].
2nd November 2007. Added nearest square continued fraction expansion of a quadratic rational.
2nd November 2007. Added nearest square Pell equation algorithm .
21st October 2007. Removed the restriction v divides d - u² in nearest integer continued fraction and now allow quadratic irrationals of the form (u + t√d)/v.
19th October 2007. Added nearest integer continued fraction expansion of a quadratic rational
18th October 2007. Added a second NICF expansion of m/n to nearest integer Euclidean algorithm.
11th October 2007. Added nearest integer Pell equation algorithm .
5th October 2007. Added nearest integer Euclidean algorithm .
13th September 2007. Made improvements to binary.html for b even.
13th February 2007. Added computing the period of the continued fraction expansion of √d.
9th February 2007. Added decimal to rational program.
8th February 2007. Removed the restriction gcd(b,n)=1 from the decimal program.
7th February 2007. Added calculating the power of a quadratic irrational.
7th December 2006. Replaced continued fraction-based reduction algorithm for indefinite binary quadratic forms by Henri Cohen's reduction algorithm.
6th December 2006. I had a sign change in the wrong places twice in the reduction algorithm for indefinite binary quadratic forms.
5th December 2006. Cleared up some remaining confusion regarding the reduction algorithm for indefinite binary quadratic forms. We now expand 1/τ and consequently make changes F_i = (-1)ⁱt/f_i and the unimodular transformation becomes x = Y, y = -X + (-1)ⁱtg_iY.
Cleared up some underlying confusion regarding the reduction algorithm for indefinite binary quadratic forms. We now find a unimodular matrix that transforms (a,b,c) to reduced form.
Added the word "primitive" to classnopos0.html.
24th October 2006. Corrected and improved the paper linked in negative_pell.html.
16th October 2006. Corrected an error in the output of classnopos0.html regarding the solubility of the equation x² - dy² = -4.
4th October 2006. Improved the output for surd.html.
29th September 2006. Added testing the solubility of the negative Pell equation.
29th September 2006. Added the Grytczuk, Luca, Wojtowicz construction of non-square d such that the continued fraction of √d has odd length period, testing over ranges for u and v.
19th September 2006. Added finding the gcd of n positive integers.
19th September 2006. Added Calculating the quadratic irrationality whose simple continued fraction is given.
13th September 2006. Fixed a small bug in Aubry-Thue which affected the printing of the solution.
6th September 2006. Added the constructive version of the Aubry-Thue theorem.
28th August 2006. Added the Grytczuk, Luca, Wojtowicz construction of non-square d such that the continued fraction of √d has odd length period.
16th August 2006. Added &sigma_k(n) and λ(n).
20th July 2006. Added finding the continued fraction of the unique positive root of a trinomial axⁿ+bx^n-1+c.
20th July 2006. Added finding the continued fraction of the unique positive root of a trinomial axⁿ+bx+c.
26th June 2006. Fixed a typo in a print statement in the code for the continued fraction of a quadratic irrational.
13th June 2006. Fixed a serious error in nprimeap.html.
5th June 2006. Added perfect-power testing.
2nd June 2006. Added finding the simple continued fraction of the n-th root of a positive rational.
31st May 2006. Made lots of trivial changes to == etc and carelessly destroyed some code which took me 4 hours to reinstate. There could also be some annoying bugs because of my absentmindedness in making those changes.
27th May 2006. Notice that the following BCMATH program shows that one has to use the bccomp() function in conditionals:
```
<?php
$test1="100000000000001415402032694799700273500898";
$test2="100000000000001421659378396209449729633403";
if($test1 > $test2){
   echo "$test1 > $test2";
}
if($test1 == $test2){
   echo "$test1 = $test2";
}
if($test1 < $test2){
   echo "$test1 < $test2";
}
?>
```
The program produces output
100000000000001415402032694799700273500898 = 100000000000001421659378396209449729633403
I will now have to start the tedious task of changing back to using bccomp().
26th May 2006. Added Representing an integer by a positive definite binary quadratic form.
20th May 2006. Added the option of printing the convergents in Calculating the simple continued fraction of a quadratic irrational.
3rd May 2006. Noticed that the Fox-Landi program is exiting prematurely and doesn't declare state 3 to be transient for the matrix.

1 0 0

0 1 0

1 1 1

This was due to double-counting and was easily fixed.
The bug was also present in Generalized 3x+1 functions and Markov matrices.
29th April 2006. Added finding the cyclic classes and cyclic form to the periodic matrix program.
10th March 2006. Fixed the error in Fox-Landi. It was due to my confusion in only adjoining elements i_k+1,..,i_r to S_{i_k}, instead of taking the unions of S_{i_k+1},..,S_{i_r} with S_{i_k}.
9th March 2006. Fox-Landi is playing up again in relation to analysing Q(m)! eg. The program hangs when d=2,m=8,m[0]=1,m[1]=3,x[0]=0,x[1]=1.
25th February 2006. Added option of viewing transitions between classes in George Leigh's program.
25th February 2006. Added cycle-finding program for generalized 3x+1 functions.
24th February 2006. Added Example 7 of G. Venturini.
23rd February 2006. Added Example 1 of G. Venturini.
23rd February 2006. 3pm. I believe I have fixed the flaws in Fox-Landi. The error affected both programs for processing Q(m). There still remains an inefficiency due to my initial confusion about communicating transient states.
22nd February 2006. Found an error in Fox-Landi. I am currently working on it.
22nd February 2006. Added a program for finding the transition matrix of George Leigh's Markov chain Y_n(x).
9th January 2006. Added finding the canonical form of the Markov matrix Q(m) arising from generalized 3x+1 functions.
6th January 2006. Added a verbose option to Fox_Landi program.
4th January 2006. Fixed an error in the construction of the permutation of rows and columns which gives the canonical form in the Fox-Landi program.
29th December 2005. Added the Fox-Landi algorithm. I'm still learning about _REQUEST, _SESSION etc. so there may be some bugs in the front end of this program.
14th June 2005. After an email from a user of binary.html, I realised I had absent-mindedly forgotten to print " no solution" in the case that an examinaton of the relevant cfracs revealed this to be the case in binary.html.
25th January 2005. Added padiclog.html. (Coded August 2004)
9th September 2004. Added the option of printing the complete quotients in surd.html.
8th August 2004. Added binary.html.
5th August 2004. Found a transcription error in squareroot_.php. Also wrote a better version of quadratic.html.
16th July 2004. Added patz.html.
15th July 2004. Fixed some bugs in squareroot_.php, which corresponded to bugs in BC program squareroot. These would have affected cornacchia.
21st May 2004. Added discrete_log.
21st May 2004. While adding cong and cong1 to library.php, I noticed a bug in finding squareroots (mod m). It was in a call to cong() instead of cong1 in sqroot1 in the file squareroot_.php.
21st May 2004. Adding more functions to library.php. This requires care to avoid clashes with other include files.
20th May 2004. More carelessness. Changed name of include file mpower.php to library.php in arithmeticm.php.
28th April 2004. Improved my use of include files by creating a large include file called library.php.
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]).
22nd April 2004. Hopefully I've fixed problems concerning multiple declarations in include files.
22nd April 2004. Fixed a small printing bug in square roots (mod n), when omega(n)=1.
22nd April 2004. Started introducing some order in the way I used include files. This has been causing some errors.
21st April 2004. Added calculating Ramanujan's tau function.
16th April 2004. Added solving ax²+by²=m.
16th April 2004. Added finding square roots (mod n).
7th April 2004. Added Pollard p-1 to factoring program.
6th April 2004. Added ord_ma.
6th April 2004. Added least primitive root (mod p).
6th April 2004. Added factoring and computing omega(n), phi(n), d(n), sigma(n) and mu(n).
24th March 2004. Added finding partial quotients of e^l/m.
22nd March 2004. Added factorising a non-negative non-singular matrix.
19th March 2004. Inserted a missing sign term in p-adic_.php.
17th March 2004. Added p-adic square root.
11th March 2004. Added 2adic square root.
27th February 2004. Added prime-power factorization of n!
17th July 2003. Improved the output of the log program when log_ba is rational.
27th February 2004. Added prime-power factorization of binomial coefficients.
17th July 2003. Improved the output of the log program when log_ba is rational.
13th June 2003. Fixed similar error to below in calculating classnumbers of binary quadratic forms of positive discriminant.
11th June 2003. Fixed an error in calculating classnumbers of real quadratic fields.

Return to BCMATH page