php_libraries/php_lib_uculib_com/int_string_algorithms.inc

<?php
//********************************************************************************
//Copyright (C) 2007 David T. Ashley
//********************************************************************************
//This program or source file is free software; you can redistribute it and/or
//modify it under the terms of the GNU Lesser General Public License as published
//by the Free Software Foundation; either version 2 of the License, or (at your
//option) any later version.
//
//This program or source file is distributed in the hope that it will
//be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//GNU General Public License for more details.
//
//You may have received a copy of the GNU Lesser General Public License
//along with this program; if not, write to the Free Software
//Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//********************************************************************************
//This file implements algorithms on integers (typically large integers) 
//represented as strings.
//--------------------------------------------------------------------------------
//Notes on canonical form:  for use with the numerical functions in this
//library, the following conventions apply:
//   a)Zero has one representation, "0".
//   b)On non-zero numbers, no leading 0's are allowed.
//   c)Positive numbers have no leading "+", but negative numbers have a
//     leading "-".
//   d)No commas, spaces, or extraneous characters are allowed.
//
//The notes above apply only to the form used for calculation.  For presentation
//in human-readable form, commas are allowed.
//--------------------------------------------------------------------------------
require_once("int_string_arithmetic.inc");
//--------------------------------------------------------------------------------
//
//Calculates the GCD of the two integers n1 and n2, using Euclid's classic
//algorithm.
//
//Results returned:
//  out_gcd:     The gcd, as a string.  FALSE is returned if there is an
//               error condition and the out_icalcs value is undefined.
//
//  out_icalcs:  The calculation intermediate results, as an array.  Each
//               subscripted element of the array has these fields:
//                  dividend  : The dividend in that round.
//                  divisor   : The divisor in that round.
//                  quotient  : The quotient in that round.
//                  remainder : The remainder in that round.
//
function ISALG_gcd($in_n1, $in_n2, &$out_gcd, &$out_icalcs)
   {
   if ((ISARITH_cmp(1, $in_n1) > 0) || (ISARITH_cmp(1, $in_n2) > 0))
      {
      //Input parameter(s) illegal.  Must return FALSE.
      $out_gcd    = FALSE;
      $out_icalcs = FALSE;
      }
   else
      {
      $i = -1;
      $out_icalcs[0]['dividend'] = $in_n1;
      $out_icalcs[0]['divisor']  = $in_n2;
      do
         {
         $i++;

         $out_icalcs[$i]['quotient']  = ISARITH_div($out_icalcs[$i]['dividend'], $out_icalcs[$i]['divisor']);
         $out_icalcs[$i]['remainder'] = ISARITH_mod($out_icalcs[$i]['dividend'], $out_icalcs[$i]['divisor']);
         if (ISARITH_cmp($out_icalcs[$i]['remainder'], 0) > 0)
            {
            $out_icalcs[$i+1]['dividend']  = $out_icalcs[$i]['divisor'];
            $out_icalcs[$i+1]['divisor']   = $out_icalcs[$i]['remainder'];
            }
         } while(ISARITH_cmp($out_icalcs[$i]['remainder'], 0) > 0);

      //Unless we completed in a single round, GCD is the last non-zero remainder.
      //Since the last remainder is zero to terminate the loop, this must be it.
      if ($i <= 0)
         $out_gcd = $out_icalcs[0]['divisor'];
      else
         $out_gcd = $out_icalcs[$i-1]['remainder'];
      }
   }
?>
1	<?php
2	//********************************************************************************
3	//Copyright (C) 2007 David T. Ashley
4	//********************************************************************************
5	//This program or source file is free software; you can redistribute it and/or
6	//modify it under the terms of the GNU Lesser General Public License as published
7	//by the Free Software Foundation; either version 2 of the License, or (at your
8	//option) any later version.
9	//
10	//This program or source file is distributed in the hope that it will
11	//be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
12	//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13	//GNU General Public License for more details.
14	//
15	//You may have received a copy of the GNU Lesser General Public License
16	//along with this program; if not, write to the Free Software
17	//Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18	//********************************************************************************
19	//This file implements algorithms on integers (typically large integers)
20	//represented as strings.
21	//--------------------------------------------------------------------------------
22	//Notes on canonical form: for use with the numerical functions in this
23	//library, the following conventions apply:
24	// a)Zero has one representation, "0".
25	// b)On non-zero numbers, no leading 0's are allowed.
26	// c)Positive numbers have no leading "+", but negative numbers have a
27	// leading "-".
28	// d)No commas, spaces, or extraneous characters are allowed.
29	//
30	//The notes above apply only to the form used for calculation. For presentation
31	//in human-readable form, commas are allowed.
32	//--------------------------------------------------------------------------------
33	require_once("int_string_arithmetic.inc");
34	//--------------------------------------------------------------------------------
35	//
36	//Calculates the GCD of the two integers n1 and n2, using Euclid's classic
37	//algorithm.
38	//
39	//Results returned:
40	// out_gcd: The gcd, as a string. FALSE is returned if there is an
41	// error condition and the out_icalcs value is undefined.
42	//
43	// out_icalcs: The calculation intermediate results, as an array. Each
44	// subscripted element of the array has these fields:
45	// dividend : The dividend in that round.
46	// divisor : The divisor in that round.
47	// quotient : The quotient in that round.
48	// remainder : The remainder in that round.
49	//
50	function ISALG_gcd($in_n1, $in_n2, &$out_gcd, &$out_icalcs)
51	{
52	if ((ISARITH_cmp(1, $in_n1) > 0) \|\| (ISARITH_cmp(1, $in_n2) > 0))
53	{
54	//Input parameter(s) illegal. Must return FALSE.
55	$out_gcd = FALSE;
56	$out_icalcs = FALSE;
57	}
58	else
59	{
60	$i = -1;
61	$out_icalcs[0]['dividend'] = $in_n1;
62	$out_icalcs[0]['divisor'] = $in_n2;
63	do
64	{
65	$i++;
66
67	$out_icalcs[$i]['quotient'] = ISARITH_div($out_icalcs[$i]['dividend'], $out_icalcs[$i]['divisor']);
68	$out_icalcs[$i]['remainder'] = ISARITH_mod($out_icalcs[$i]['dividend'], $out_icalcs[$i]['divisor']);
69	if (ISARITH_cmp($out_icalcs[$i]['remainder'], 0) > 0)
70	{
71	$out_icalcs[$i+1]['dividend'] = $out_icalcs[$i]['divisor'];
72	$out_icalcs[$i+1]['divisor'] = $out_icalcs[$i]['remainder'];
73	}
74	} while(ISARITH_cmp($out_icalcs[$i]['remainder'], 0) > 0);
75
76	//Unless we completed in a single round, GCD is the last non-zero remainder.
77	//Since the last remainder is zero to terminate the loop, this must be it.
78	if ($i <= 0)
79	$out_gcd = $out_icalcs[0]['divisor'];
80	else
81	$out_gcd = $out_icalcs[$i-1]['remainder'];
82	}
83	}
84	?>