@bintou 2018-10-15T13:23:03.000000Z 字数 1916 阅读 832

# CINTA相关代码

代码

### Multiplication and Power

# Simple mul# Input unsigned integers a and b# Output a * bdef 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^bdef 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*sdef 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 Xdef 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       if len(X) == 2: return X*X       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  • 私有
• 公开
• 删除