/[dtapublic]/to_be_filed/webprojs/php_libraries/php_lib_uculib_com/int_string_algorithms.inc
ViewVC logotype

Contents of /to_be_filed/webprojs/php_libraries/php_lib_uculib_com/int_string_algorithms.inc

Parent Directory Parent Directory | Revision Log Revision Log


Revision 35 - (show annotations) (download)
Sat Oct 8 23:35:33 2016 UTC (6 years, 3 months ago) by dashley
File size: 3909 byte(s)
Initial commit.
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 ?>

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25