68 lines
1.2 KiB
Text
68 lines
1.2 KiB
Text
//
|
|
// Chinese Remainder Theorem
|
|
//
|
|
// Using FutureBasic 7.0.34
|
|
// August 25, R.W
|
|
|
|
|
|
Int n(2) = { 3, 5, 7 } // Rosetta's test data
|
|
Int a(2) = { 2, 3, 2 }
|
|
|
|
//Int n(2) = { 11, 12, 13 } // Expecting 1000
|
|
//Int a(2) = { 10, 4, 12 }
|
|
|
|
//Int n(2) = { 11, 22, 19 } // Failure test
|
|
//Int a(2) = { 10, 4, 9 }
|
|
|
|
//
|
|
// Greatest Common Factor
|
|
|
|
local fn GCF(x As UInt64, y As UInt64) As UInt64
|
|
UInt64 t
|
|
While y
|
|
t = y
|
|
y = x Mod y
|
|
x = t
|
|
Wend
|
|
end fn = x
|
|
|
|
// x = (ax) MOD b == 1
|
|
local fn ModularMultiplicativeInverse( a1 as Int, b1 as Int ) as Int
|
|
Int i
|
|
if b1 == 1 then return 1
|
|
for i = 1 to b1
|
|
if (a1 * i) % b1 == 1 then return i
|
|
next i
|
|
end fn = 0
|
|
|
|
local fn chinese_remainder(ln as int ) as int
|
|
int i,j,p,prod,sum,ni,ai
|
|
prod = 1
|
|
sum = 0
|
|
for i = 0 to ln-1
|
|
for j = i+1 to ln-1
|
|
if fn GCF( n(i), n(j) ) > 1
|
|
print "N relative prime with no GCF"
|
|
end if
|
|
next
|
|
next
|
|
for i = 0 to ln-1
|
|
prod *= n(i)
|
|
next
|
|
for i = 0 to ln-1
|
|
ni = n(i)
|
|
ai = a(i)
|
|
p = prod / ni
|
|
sum += ai * fn ModularMultiplicativeInverse(p,ni) * p
|
|
next
|
|
|
|
end fn = sum mod prod
|
|
|
|
//
|
|
// main
|
|
|
|
window 1
|
|
|
|
print fn chinese_remainder(3)
|
|
|
|
HandleEvents
|