CINTA相关代码

代码

以下代码用于CINTA的学习，建议大家自己敲代码，不要Ctrl c+ Ctrl v 。

Multiplication and Power

# 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

EGCD

# 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

The Binary Euclidean Algorithm.

# 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)

Pruduct tree

对比以下两个数列求积算法，说明并验证它们的效率。
第一个算法逐个元素相乘；第二个算法使用递归，把元素分成两组分别进行相乘。除了理论分析，最好有实验数据。

# 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