|
|
- '''
- 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()
|