You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
111 lines
2.1 KiB
111 lines
2.1 KiB
'''
|
|
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
|
|
|
|
#TEST functions
|
|
|
|
def test_is_perfect_square():
|
|
print("Testing is_perfect_square")
|
|
testsuit = [4, 0, 15, 25, 18, 901, 1000, 1024]
|
|
|
|
for n in testsuit:
|
|
print("Is ", n, " a perfect square?")
|
|
if is_perfect_square(n)!= -1:
|
|
print("Yes!")
|
|
else:
|
|
print("Nope")
|
|
|
|
if __name__ == "__main__":
|
|
test_is_perfect_square()
|