[关闭]
@bintou 2018-10-15T13:23:03.000000Z 字数 1916 阅读 840

CINTA相关代码

代码


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

Multiplication and Power

  1. # Simple mul
  2. # Input unsigned integers a and b
  3. # Output a * b
  4. def multiply(a, b):
  5. result = 0
  6. #terminate when b == 0
  7. while (b != 0):
  8. # check if b is even or odd
  9. if (b % 2):
  10. result += a
  11. # b / 2
  12. b = b >> 1
  13. # a *= 2
  14. a = a << 1
  15. return result
  16. # Fast power
  17. # Input: integer a, b
  18. # Output a^b
  19. def power(a, b):
  20. result = 1
  21. while (b != 0):
  22. # check if b is even or odd
  23. if(b % 2):
  24. # b is odd
  25. result *= a
  26. b = b / 2
  27. a *= a
  28. return result

EGCD

  1. # Input: integers a and b, with a > b .
  2. # Output: d=gcd(a,b), and
  3. # r and s s.t. d = a*r + b*s
  4. def egcd(a, b):
  5. r0, r1, s0, s1 = 1, 0, 0, 1
  6. while(b):
  7. q, a, b = a/b, b, a%b
  8. r0, r1 = r1, r0 - q*r1
  9. s0, s1 = s1, s0 - q*s1
  10. return a, r0, s0

The Binary Euclidean Algorithm.

  1. # Function to implement Stein's Algorithm
  2. # Input: positive integers a and b, with a > b .
  3. # Output: the greatest common divisor of a and b.
  4. def binary_gcd( a, b):
  5. # Finding 'k', which is the greatest power of 2
  6. # that divides both 'a' and 'b'.
  7. k = 0
  8. while(((a | b) & 1) == 0) :
  9. a = a >> 1
  10. b = b >> 1
  11. k = k + 1
  12. # Dividing 'a' by 2 until 'a' becomes odd
  13. while ((a & 1) == 0) :
  14. a = a >> 1
  15. # From here on, 'a' is always odd.
  16. while(b != 0) :
  17. # If 'b' is even, remove all factor of 2 in 'b'
  18. while ((b & 1) == 0) :
  19. b = b >> 1
  20. # Now 'a' and 'b' are both odd.
  21. #Swap if necessary so a <= b
  22. if (a > b) :
  23. a, b = b, a # Swap 'a' and 'b'.
  24. b = (b - a) # b = b - a (which is even).
  25. # restore common factors of 2
  26. return (a << k)

Pruduct tree

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

  1. # Input: Given a sequence of number X
  2. # Output: The product of all the numbers in X
  3. def product1(X):
  4. res = 1
  5. for i in range(len(X)):
  6. res *= X[i]
  7. return res
  1. # Input: Given a sequence of number X
  2. # Output: The product of all the numbers in X
  3. def product2(X):
  4. if len(X) == 0: return 1
  5. if len(X) == 1: return X[0]
  6. if len(X) == 2: return X[0]*X[1]
  7. l = len(X)
  8. return product2(X[0:(l+1)//2]) * product2(X[(l+1)//2: l])
  1. def producttree(X):
  2. result = [X]
  3. while len(X) > 1:
  4. #prod is a build-in function in Sage.
  5. X = [prod(X[i*2:(i+1)*2]) for i in range((len(X)+1)/2)]
  6. result.append(X)
  7. return result
  1. #Input: a, b, n
  2. #Output: x, s.t. ax \equiv b (mod n)
  3. def modular_linear_equation_Solver(a, b, n):
  4. res = []
  5. (d, x, y) = xgcd(a, n) #egcd in Sage.
  6. if d.divides(b):
  7. x0 = (x*(b//d)) % n
  8. for i in range(d): #i from 0 to d - 1
  9. res = res + [(x0 + i*(n//d)) % n]
  10. else:
  11. print("no solutions...")
  12. return res
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注