Chinese remainder theorem: Difference between revisions
add RPL
(add RPL) |
|||
Line 3,137:
say 'no solution found.' /*oops, announce that solution ¬ found.*/</syntaxhighlight>
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}} <br><br>
=={{header|RPL}}==
{{trans|Python}}
{{works with|Halcyon Calc|4.2.9}}
{| class="wikitable" ≪
! RPL code
! Comment
|-
|
≪
DUP ROT 1 R→C ROT 0 R→C
'''WHILE''' DUP RE '''REPEAT'''
OVER RE OVER RE / FLOOR
OVER * NEG ROT +
'''END'''
DROP C→R ROT MOD
SWAP 1 == SWAP 0 IFTE
≫ ‘<span style="color:blue">MODINV</span>’ STO
≪ → n a
≪ 0
1 1 n SIZE '''FOR''' j n j GET * '''NEXT'''
1 n SIZE '''FOR''' j
DUP n j GET / FLOOR
ROT OVER n j GET <span style="color:blue">MODINV</span> a j GET * ROT * +
SWAP '''NEXT'''
MOD
≫ ≫ ‘<span style="color:blue">NCHREM</span>’ STO
|
<span style="color:blue">MODINV</span> ''( a b → x ) with ax = 1 mod b''
3:b 2:(r,u) ← (a,1) 1:(r',u') ← (b,0)
While r' ≠ 0
q ← r // r'
(r - q*r', u - q*u')
Forget (r',u') and calculate u mod b
Test r and return zero if a and b are not co-prime
<span style="color:blue">NCHREM</span> ''( n a → remainder )''
sum = 0
prod = reduce(lambda a, b: a*b, n)
for n_i, a_i in zip(n, a):
p = prod / n_i
sum += a_i * mul_inv(p, n_i) * p
// reorder stack for next iteration
return sum % prod
|}
'''RPL 2003 version'''
{{works with|HP|49}}
≪ → a n
≪ a 1 GET n 1 GET →V2
2 a SIZE '''FOR''' j
a j GET n j GET →V2 ICHINREM
'''NEXT'''
V→ MOD
≫ ≫ '<span style="color:blue">NCHREM</span>' STO
{ 2 3 2 } { 3 5 7 } <span style="color:blue">NCHREM</span>
{{out}}
<pre>
1: 23.
</pre>
=={{header|Ruby}}==
Brute-force.
Line 3,180 ⟶ 3,244:
p chinese_remainder([10,4,9], [11,22,19]) #=> nil
</syntaxhighlight>
=={{header|Rust}}==
<syntaxhighlight lang="rust">fn egcd(a: i64, b: i64) -> (i64, i64, i64) {
| |||