1 |
dashley |
35 |
<?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 |
|
|
?>
|