-
Notifications
You must be signed in to change notification settings - Fork 125
/
Arithmetic.py
95 lines (80 loc) · 1.78 KB
/
Arithmetic.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
'''
Created on Dec 22, 2011
@author: pablocelayes
'''
def egcd(a,b):
'''
Extended Euclidean Algorithm
returns x, y, gcd(a,b) such that ax + by = gcd(a,b)
'''
u, u1 = 1, 0
v, v1 = 0, 1
while b:
q = a // b
u, u1 = u1, u - q * u1
v, v1 = v1, v - q * v1
a, b = b, a - q * b
return u, v, a
def gcd(a,b):
'''
2.8 times faster than egcd(a,b)[2]
'''
a,b=(b,a) if a<b else (a,b)
while b:
a,b=b,a%b
return a
def modInverse(e,n):
'''
d such that de = 1 (mod n)
e must be coprime to n
this is assumed to be true
'''
return egcd(e,n)[0]%n
def totient(p,q):
'''
Calculates the totient of pq
'''
return (p-1)*(q-1)
def bitlength(x):
'''
Calculates the bitlength of x
'''
assert x >= 0
n = 0
while x > 0:
n = n+1
x = x>>1
return n
def isqrt(n):
'''
Calculates the integer square root
for arbitrary large nonnegative integers
'''
if n < 0:
raise ValueError('square root not defined for negative numbers')
if n == 0:
return 0
a, b = divmod(bitlength(n), 2)
x = 2**(a+b)
while True:
y = (x + n//x)//2
if y >= x:
return x
x = y
def is_perfect_square(n):
'''
If n is a perfect square it returns sqrt(n),
otherwise returns -1
'''
h = n & 0xF; #last hexadecimal "digit"
if h > 9:
return -1 # return immediately in 6 cases out of 16.
# Take advantage of Boolean short-circuit evaluation
if ( h != 2 and h != 3 and h != 5 and h != 6 and h != 7 and h != 8 ):
# take square root if you must
t = isqrt(n)
if t*t == n:
return t
else:
return -1
return -1