defalg10_14(ms, f):
iflen(ms) == 1:
return [f]
else:
M = alg10_3(ms)
f0 = f % M[-2][0]
f1 = f % M[-2][1]
returnalg10_14(ms[:len(ms)//2], f0) + alg10_14(ms[len(ms)//2:], f1)
defalg10_14x(i_ms_s, i_ms_e, f, M, i_f0, j_f0):
if i_ms_e - i_ms_s == 1:
return [f]
else:
f0 = f % M[i_f0][j_f0]
f1 = f % M[i_f0][j_f0+1]
returnalg10_14x(i_ms_s, i_ms_s+(i_ms_e-i_ms_s)//2, f0, M, i_f0-1, 2*j_f0) \
+ alg10_14x(i_ms_s+(i_ms_e-i_ms_s)//2, i_ms_e, f1, M, i_f0-1, 2*j_f0+2)
ms = [2, 3, 5, 7, 11, 13, 17, 19]
f = 9699791res0 = [f % m form in ms]
res1 = alg10_14(ms=ms, f=f)
M = alg10_3(ms)
res2 = alg10_14x(0, len(ms), f, M, -2, 0)
assertall([x==y forx, y in zip(res0, res1)])
assertall([x==y forx, y in zip(res1, res2)])
res1
1
2
1
3
2
10
16
6
参考文献
Gathen, Joachim von zur, and Gerhard Jürgen. 2013. Modern computer algebra. 3rd ed. Cambridge: Cambridge University Press.
defalg10_14(ms, f):
iflen(ms) == 1:
return [f]
else:
M = alg10_3(ms)
f0 = f % M[-2][0]
f1 = f % M[-2][1]
returnalg10_14(ms[:len(ms)//2], f0) + alg10_14(ms[len(ms)//2:], f1)
defalg10_14x(i_ms_s, i_ms_e, f, M, i_f0, j_f0):
if i_ms_e - i_ms_s == 1:
return [f]
else:
f0 = f % M[i_f0][j_f0]
f1 = f % M[i_f0][j_f0+1]
returnalg10_14x(i_ms_s, i_ms_s+(i_ms_e-i_ms_s)//2, f0, M, i_f0-1, 2*j_f0) \
+ alg10_14x(i_ms_s+(i_ms_e-i_ms_s)//2, i_ms_e, f1, M, i_f0-1, 2*j_f0+2)
ms = [2, 3, 5, 7, 11, 13, 17, 19]
f = 9699791res0 = [f % m form in ms]
res1 = alg10_14(ms=ms, f=f)
M = alg10_3(ms)
res2 = alg10_14x(0, len(ms), f, M, -2, 0)
assertall([x==y forx, y in zip(res0, res1)])
assertall([x==y forx, y in zip(res1, res2)])
res1
1
2
1
3
2
10
16
6
参考文献
Gathen, Joachim von zur, and Gerhard Jürgen. 2013. Modern computer algebra. 3rd ed. Cambridge: Cambridge University Press.