Rosetta Code

Chinese remainder theorem: Difference between revisions

← Older editNewer edit →
Content deleted Content added
Mihailp (talk | contribs)
298 edits
add picolisp
Hansoft (talk | contribs)
374 edits
Line 929:
@(100) = 2 : @(101) = 3 : @(102) = 2
 
Print Func (_Chinese_Remainder (3))
Push 3 : GoSub _Chinese_Remainder
Print Pop()
 
' -------------------------------------
Line 937 ⟶ 936:
@(100) = 10 : @(101) = 04 : @(102) = 12
 
Print Func (_Chinese_Remainder (3))
Push 3 : GoSub _Chinese_Remainder
Print Pop()
 
' -------------------------------------
Line 945 ⟶ 943:
 
' returns x where (a * x) % b == 1
_Mul_Inv Param (2) ' ( a b -- n)
Local (64)
 
b@ = Pop()
a@ = Pop()
 
c@ = b@
Line 955 ⟶ 950:
e@ = 1
 
If b@ = 1 Then Return (1)
Push 1
Return
EndIf
 
Do While a@ > 1
Line 968 ⟶ 960:
If e@ < 0 Then e@ = e@ + c@
 
Return (e@)▼
Push e@
▲Return
 
 
_Chinese_Remainder Param (1) ' ( len -- n)
Local (5)
 
a@ = Pop()
b@ = 1
c@ = 0
Line 985 ⟶ 975:
For d@ = 0 Step 1 While d@ < a@
e@ = b@ / @(d@)
Pushc@ e= c@, + (@(100 + d@) :* GoSubFunc (_Mul_Inv (e@, @(d@))) * e@)
c@ = c@ + (@(100 + d@) * Pop() * e@)
Next
 
PushReturn (c@ % b@)
Return
</lang>
{{out}}
Line 997 ⟶ 985:
1000
 
0 OK, 0:10541034
</pre>
 
Retrieved from "https://rosettacode.org/wiki/Chinese_remainder_theorem"