Chinese remainder theorem: Difference between revisions
Fortran version
(Added XPL0 example.) |
(Fortran version) |
||
Line 1,375:
10 11 4 22 9 19 3 >>>crt<<< .
</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}}==
Partial {{trans|C}}. Uses the code from [[Greatest_common_divisor#Recursive_solution]] as an include.
Line 1,412 ⟶ 1,480:
print chinese_remainder(n(), a())</syntaxhighlight>
{{out}}<pre>23</pre>
=={{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.)
| |||