lineaire-combinatie-en-greatest-common-divisor
Gesponsorde koppelingen
PHP script bestanden
Code (php)
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
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();
?>
/** 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();
?>