@bintou
2018-10-15T21:23:03.000000Z
字数 1916
阅读 1905
代码
以下代码用于CINTA的学习,建议大家自己敲代码,不要Ctrl c+ Ctrl v 。
# Simple mul
# Input unsigned integers a and b
# Output a * b
def multiply(a, b):
result = 0
#terminate when b == 0
while (b != 0):
# check if b is even or odd
if (b % 2):
result += a
# b / 2
b = b >> 1
# a *= 2
a = a << 1
return result
# Fast power
# Input: integer a, b
# Output a^b
def power(a, b):
result = 1
while (b != 0):
# check if b is even or odd
if(b % 2):
# b is odd
result *= a
b = b / 2
a *= a
return result
# Input: integers a and b, with a > b .
# Output: d=gcd(a,b), and
# r and s s.t. d = a*r + b*s
def egcd(a, b):
r0, r1, s0, s1 = 1, 0, 0, 1
while(b):
q, a, b = a/b, b, a%b
r0, r1 = r1, r0 - q*r1
s0, s1 = s1, s0 - q*s1
return a, r0, s0
# Function to implement Stein's Algorithm
# Input: positive integers a and b, with a > b .
# Output: the greatest common divisor of a and b.
def binary_gcd( a, b):
# Finding 'k', which is the greatest power of 2
# that divides both 'a' and 'b'.
k = 0
while(((a | b) & 1) == 0) :
a = a >> 1
b = b >> 1
k = k + 1
# Dividing 'a' by 2 until 'a' becomes odd
while ((a & 1) == 0) :
a = a >> 1
# From here on, 'a' is always odd.
while(b != 0) :
# If 'b' is even, remove all factor of 2 in 'b'
while ((b & 1) == 0) :
b = b >> 1
# Now 'a' and 'b' are both odd.
#Swap if necessary so a <= b
if (a > b) :
a, b = b, a # Swap 'a' and 'b'.
b = (b - a) # b = b - a (which is even).
# restore common factors of 2
return (a << k)
对比以下两个数列求积算法,说明并验证它们的效率。
第一个算法逐个元素相乘;第二个算法使用递归,把元素分成两组分别进行相乘。除了理论分析,最好有实验数据。
# Input: Given a sequence of number X
# Output: The product of all the numbers in X
def product1(X):
res = 1
for i in range(len(X)):
res *= X[i]
return res
# Input: Given a sequence of number X
# Output: The product of all the numbers in X
def product2(X):
if len(X) == 0: return 1
if len(X) == 1: return X[0]
if len(X) == 2: return X[0]*X[1]
l = len(X)
return product2(X[0:(l+1)//2]) * product2(X[(l+1)//2: l])
def producttree(X):
result = [X]
while len(X) > 1:
#prod is a build-in function in Sage.
X = [prod(X[i*2:(i+1)*2]) for i in range((len(X)+1)/2)]
result.append(X)
return result
#Input: a, b, n
#Output: x, s.t. ax \equiv b (mod n)
def modular_linear_equation_Solver(a, b, n):
res = []
(d, x, y) = xgcd(a, n) #egcd in Sage.
if d.divides(b):
x0 = (x*(b//d)) % n
for i in range(d): #i from 0 to d - 1
res = res + [(x0 + i*(n//d)) % n]
else:
print("no solutions...")
return res