Chinese remainder theorem: Difference between revisions
Content added Content deleted
(Added XPL0 example.) |
(Fortran version) |
||
Line 1,375: | Line 1,375: | ||
10 11 4 22 9 19 3 >>>crt<<< . |
10 11 4 22 9 19 3 >>>crt<<< . |
||
</pre> |
</pre> |
||
=={{header|Fortran}}== |
|||
Written in Fortran-77 style (fixed form, GO TO), directly translated from the problem description. |
|||
<syntaxhighlight lang="Fortran"> |
|||
* RC task: use the Chinese Remainder Theorem to solve a system of congruences. |
|||
FUNCTION crt(n, residues, moduli) |
|||
IMPLICIT INTEGER (A-Z) |
|||
DIMENSION residues(n), moduli(n) |
|||
p = product(moduli) |
|||
crt = 0 |
|||
DO 10 i = 1, n |
|||
m = p/moduli(i) |
|||
CALL egcd(moduli(i), m, r, s, gcd) |
|||
IF (gcd .ne. 1) GO TO 20 ! error exit |
|||
10 crt = crt + residues(i)*s*m |
|||
crt = modulo(crt, p) |
|||
RETURN |
|||
20 crt = -1 ! will never be negative, so flag an error |
|||
END |
|||
* Compute egcd(a, b), returning x, y, g s.t. |
|||
* g = gcd(a, b) and a*x + b*y = g |
|||
* |
|||
SUBROUTINE egcd(a, b, x, y, g) |
|||
IMPLICIT INTEGER (A-Z) |
|||
g = a |
|||
u = 0 |
|||
v = 1 |
|||
w = b |
|||
x = 1 |
|||
y = 0 |
|||
1 IF (w .eq. 0) RETURN |
|||
q = g/w |
|||
u next = x - q*u |
|||
v next = y - q*v |
|||
w next = g - q*w |
|||
x = u |
|||
y = v |
|||
g = w |
|||
u = u next |
|||
v = v next |
|||
w = w next |
|||
GO TO 1 |
|||
END |
|||
PROGRAM Chinese Remainder |
|||
IMPLICIT INTEGER (A-Z) |
|||
n = crt(3, [2, 3, 2], [3, 5, 7]) |
|||
PRINT *, n |
|||
n = crt(3, [2, 3, 2], [3, 6, 7]) |
|||
PRINT *, n ! no solution |
|||
END |
|||
</syntaxhighlight> |
|||
{{Out}} |
|||
<pre> |
|||
23 |
|||
-1 |
|||
</pre> |
|||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
Partial {{trans|C}}. Uses the code from [[Greatest_common_divisor#Recursive_solution]] as an include. |
Partial {{trans|C}}. Uses the code from [[Greatest_common_divisor#Recursive_solution]] as an include. |
||
Line 1,412: | Line 1,480: | ||
print chinese_remainder(n(), a())</syntaxhighlight> |
print chinese_remainder(n(), a())</syntaxhighlight> |
||
{{out}}<pre>23</pre> |
{{out}}<pre>23</pre> |
||
=={{header|Frink}}== |
=={{header|Frink}}== |
||
This example solves an extended version of the Chinese Remainder theorem by allowing an optional third parameter <CODE>d</CODE> which defaults to 0 and is an integer. The solution returned is the smallest solution >= d. (This optional parameter is common in many/most real-world applications of the Chinese Remainder Theorem.) |
This example solves an extended version of the Chinese Remainder theorem by allowing an optional third parameter <CODE>d</CODE> which defaults to 0 and is an integer. The solution returned is the smallest solution >= d. (This optional parameter is common in many/most real-world applications of the Chinese Remainder Theorem.) |