lineaire-combinatie-en-greatest-common-divisor

Gesponsorde koppelingen

PHP script bestanden

  1. lineaire-combinatie-en-greatest-common-divisor

« Lees de omschrijving en reacties

Code (php)
PHP script in nieuw venster Selecteer het PHP script
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
<?php

/**    Getting the lineair combination and the greatest common divider  of 2 integers
*    @description Used to get the modulo inverse of some integer
*    @author Ruud Verbij
*    @date April the 8th 2008
*/


class LineairCombination {

    /**    @var            Integer
        @description    For counting the total steps used for the algorithm
    */

    private $steps = 0;
    
    /**    @var            Array
        @description    These 2 Arrays are used in this way:
                    a[0] = q[0]*a[1] + a[2]
                    a[1] = q[1]*a[2] + a[3]
                    etc.
    */

    private $A = Array();
    private $Q = Array();
    
    /**    @var            Array
        @description     This array is used to get the lineair combination of a[0] (table[i][0]) and a[1] (table[i][1]) for every i > 1
                    Offcourse most valuable at table[count(table)+1] (the last A, the greatest common divider  of a[0] and a[1])
                    So, table[i][0]*a[0] + table[i][1]*a[1] = a[i], this means that table[i] stores the lineair combination of a[0] and a[1] for a[i]
    */

    private $table = Array();
    
    /**    @var            Array
        @description    The same as table[count(table)+1], so, used to store the information on a more easy way to find
    */

    private $lineairCombination = Array();
    
    /**    @var            Integer
        @description    Used to store the greatest common divider , the same as a[count(a)-1]
    */

    private $gcd = -1;
    
    /**     Constructor
        @param        Integer
        @param        Integer
        @description    Inputs the 2 integers for which the greatest common divider  and the lineair combination must be calculated
        @require        $a != $b && is_integer($a) && is_integer($b) && $a > 0 && $b > 0
    */

    public function __construct($a,$b) {
        // make sure that a[0] > a[1]
        $this->A[0] = ($a < $b) ? $b : $a;
        $this->A[1] = ($a > $b) ? $b : $a;
    }

    
    /**    Returns the greatest common divider
        @require        called AFTER run method has been called
        @return        Integer, containing the greatest common divider  of A[0] and A[1]
    */

    public function getGcd() {
        return $this->gcd;
    }

    
    /**    Returns the lineair combination
        @require        called AFTER run method has been called
        @return        Array, containing the lineair combination of A[0] and A[1] --> return[0]*A[0] + return[1]*A[1] = returnGcd()
    */

    public function getLinComb() {
        return $this->lineairCombination;
    }
    
    
    /**    Return the module inverse of A[1] in module A[0], only exists whenever getGcd() == 1, otherwhise the return is false
        @require        called AFTER run method has been called && getGcd() == 1, otherwhise a[1] has no modulo-inverse in modulo a[0]
        @return        Integer, 0 < return < A[0] OR false if getGcd != 1
        @ensure        return * A[1] mod A[0] = 1 OR return is false
    */

    public function getModuloInverse() {
        return ($this->getGcd == 1) ? (($this->lineairCombination[1] < 0) ? $this->lineairCombination[1] + $this->A[0] : $this->lineairCombination[1]) : false;
    }

    
    /**    Some sort of reset function
        @ensure        Object == new LineairCombination($a,$b);
    */

    public function setAandB($a, $b) {
        // reset all variables
        $this->steps                 = 0;
        $this->A                     = Array();
        $this->Q                    = Array();
        $this->table                = Array();
        $this->lineairCombination     = Array();
        $this->gcd                     = -1;
        
        // make sure that a[0] > a[1]
        $this->A[0] = ($a < $b) ? $b : $a;
        $this->A[1] = ($a > $b) ? $b : $a;
    }

    
    /**    Run the class
        @description    Used to run the class and find the greatest common divider  and lineair combination
    */

    public function run() {
        // call both the gcd and lineair combination functions
        $this->recursiveGcd();
        $this->recursiveLineairCombination();
        
        // store the found variables in a logically named variable
        $this->gcd = $this->A[count($this->A)-1];
        $this->lineairCombination = $this->table[count($this->table)+1];
        
        // example echo
        echo "So, the lineair combination of (".$this->A[0].",".$this->A[1].") is:<br />";
        echo $this->gcd." = ".$this->lineairCombination[0]." x ".$this->A[0]." + ".$this->lineairCombination[1]." x ".$this->A[1];
        echo "<br />Calculated in ".$this->steps." steps";
        
        return;
    }

    
    /**    Find the greatest common divider  */
    private function recursiveGcd() {
        // call recursive function
        $this->gcd($this->A[0],$this->A[1],0);
        
        return;
    }

    
    /**    Recursive function gcd
        @description    Find the lineair combination of $a and $b and store it at $this->A[$n+2]
        @require        $a > $b && is_integer($a) && is_integer($b) && $a != 0 && $b != 0
        @ensure        $this->A[$n+2] = gcd($a,$b) && $this->A[$n+2] + $this->Q[$n]*$b = $a
    */

    private function gcd($a,$b,$n) {    
        // increase steps
        $this->steps++;
        
        // the probably new A and Q values
        $new_A = $a % $b;
        $new_Q = floor($a/$b);
        
        // though, the new A cannot be 0, otherwhise we have already found the greatest common divider  ($b)
        if($new_A != 0) {
            // store the new A and Q
            $this->A[$n+2] = $new_A;
            $this->Q[$n] = $new_Q;
            
            // call the function recursively to find the gcd of A[$n+1] and A[$n+2] ($b and $new_A)
            $this->gcd($this->A[$n+1],$this->A[$n+2],$n+1);
        }

        return;
    }

    
    /**    Find the lineair combination
        @require        Called AFTER the getGcd method is called, therefore made private, and only called from the run method
    */

    private function recursiveLineairCombination() {
        // first fill the second position of the table (pre-made)
        $this->table[2] = Array(1, -1 * $this->Q[0]);
        
        // if there will be a theird position ($a[0] != m * $a[1])
        if(count($this->Q) > 1)
            // fill it
            $this->table[3] = Array(-1*$this->Q[1],$this->Q[0]*$this->Q[1] + 1);
            
        // find the lineair combination recursively, by starting at the last A and working back
        // using the equation: A[n] = -1 * Q[n-2] * A[n-1] + A[n-2]

        $this->lineairCombination(count($this->A)-1);
        
        return;
    }

    
    /**    Find the lineair combination
        @description    Find the lineair combination of A[0] and A[1] to make A[$n], started at A[count(A)-1] and working back, filling the table
        @param        Integer, for which to find the lineair combination of A[0] and A[1]
        @require        Called AFTER the getGcd method is called, therefor made private, and only called from the getLineairCombination method, which has the same requirement
        @ensure        table[n][0]*a[0] + table[n][1]*a[1] = a[n]
    */

    private function lineairCombination($n) {
        // increase the number of steps made
        $this->steps++;
        
        // if $n <= 3 --> table[n-2] is not defined AND all necessary $n <= 3 are already in the table
        if($n <= 3) return;
        
        // to make the code a little smaller, fill table[i][0] and table[i][1] with this for-loop
        $temp = Array();
        for($i = 1; $i <= 2; $i++) {
            // if not already in the table, find it recursively
            if(!$this->table[$n-$i][0])
                $this->lineairCombination($n-$i);
            $temp[$i-1] = $this->table[$n - $i];
        }

        
        // Fill the table with the equation: A[n] = -1 * Q[n-2] * A[n-1] + A[n-2]
        $this->table[$n] = Array(-1 * $this->Q[$n-2] * $temp[0][0] + $temp[1][0],
                                 -
1 * $this->Q[$n-2] * $temp[0][1] + $temp[1][1]);
        return;
    }

}


// Example (and testing)
$a = (isset($_GET['a'])) ? $_GET['a'] : 91;
$b = (isset($_GET['b'])) ? $_GET['b'] : 17;

$linComb = new LineairCombination($a,$b);
$linComb->run();

?>

 
 

Om de gebruiksvriendelijkheid van onze website en diensten te optimaliseren maken wij gebruik van cookies. Deze cookies gebruiken wij voor functionaliteiten, analytische gegevens en marketing doeleinden. U vindt meer informatie in onze privacy statement.