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

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

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25