Python/maths/binary_exponentiation.py at master · gio-puter/Python · GitHub

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
"""Binary Exponentiation."""

# Author : Junth Basnet
# Time Complexity : O(logn)


defbinary_exponentiation(a: int, n: int) ->int:
"""
 Compute a number raised by some quantity
 >>> binary_exponentiation(-1, 3)
 -1
 >>> binary_exponentiation(-1, 4)
 1
 >>> binary_exponentiation(2, 2)
 4
 >>> binary_exponentiation(3, 5)
 243
 >>> binary_exponentiation(10, 3)
 1000
 >>> binary_exponentiation(5e3, 1)
 5000.0
 >>> binary_exponentiation(-5e3, 1)
 -5000.0
 """
ifn==0:
return1

elifn%2==1:
returnbinary_exponentiation(a, n-1) *a

else:
b=binary_exponentiation(a, n//2)
returnb*b


if__name__=="__main__":
importdoctest

doctest.testmod()

try:
BASE=int(float(input("Enter Base : ").strip()))
POWER=int(input("Enter Power : ").strip())
exceptValueError:
print("Invalid literal for integer")

RESULT=binary_exponentiation(BASE, POWER)
print(f"{BASE}^({POWER}) : {RESULT}")
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
"""Binary Exponentiation."""

# Author : Junth Basnet
# Time Complexity : O(logn)


defbinary_exponentiation(a: int, n: int) ->int:
"""
 Compute a number raised by some quantity
 >>> binary_exponentiation(-1, 3)
 -1
 >>> binary_exponentiation(-1, 4)
 1
 >>> binary_exponentiation(2, 2)
 4
 >>> binary_exponentiation(3, 5)
 243
 >>> binary_exponentiation(10, 3)
 1000
 >>> binary_exponentiation(5e3, 1)
 5000.0
 >>> binary_exponentiation(-5e3, 1)
 -5000.0
 """
ifn==0:
return1

elifn%2==1:
returnbinary_exponentiation(a, n-1) *a

else:
b=binary_exponentiation(a, n//2)
returnb*b


if__name__=="__main__":
importdoctest

doctest.testmod()

try:
BASE=int(float(input("Enter Base : ").strip()))
POWER=int(input("Enter Power : ").strip())
exceptValueError:
print("Invalid literal for integer")

RESULT=binary_exponentiation(BASE, POWER)
print(f"{BASE}^({POWER}) : {RESULT}")
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
"""Binary Exponentiation."""

# Author : Junth Basnet
# Time Complexity : O(logn)


defbinary_exponentiation(a: int, n: int) ->int:
"""
 Compute a number raised by some quantity
 >>> binary_exponentiation(-1, 3)
 -1
 >>> binary_exponentiation(-1, 4)
 1
 >>> binary_exponentiation(2, 2)
 4
 >>> binary_exponentiation(3, 5)
 243
 >>> binary_exponentiation(10, 3)
 1000
 >>> binary_exponentiation(5e3, 1)
 5000.0
 >>> binary_exponentiation(-5e3, 1)
 -5000.0
 """
ifn==0:
return1

elifn%2==1:
returnbinary_exponentiation(a, n-1) *a

else:
b=binary_exponentiation(a, n//2)
returnb*b


if__name__=="__main__":
importdoctest

doctest.testmod()

try:
BASE=int(float(input("Enter Base : ").strip()))
POWER=int(input("Enter Power : ").strip())
exceptValueError:
print("Invalid literal for integer")

RESULT=binary_exponentiation(BASE, POWER)
print(f"{BASE}^({POWER}) : {RESULT}")
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
"""Binary Exponentiation."""

# Author : Junth Basnet
# Time Complexity : O(logn)


defbinary_exponentiation(a: int, n: int) ->int:
"""
 Compute a number raised by some quantity
 >>> binary_exponentiation(-1, 3)
 -1
 >>> binary_exponentiation(-1, 4)
 1
 >>> binary_exponentiation(2, 2)
 4
 >>> binary_exponentiation(3, 5)
 243
 >>> binary_exponentiation(10, 3)
 1000
 >>> binary_exponentiation(5e3, 1)
 5000.0
 >>> binary_exponentiation(-5e3, 1)
 -5000.0
 """
ifn==0:
return1

elifn%2==1:
returnbinary_exponentiation(a, n-1) *a

else:
b=binary_exponentiation(a, n//2)
returnb*b


if__name__=="__main__":
importdoctest

doctest.testmod()

try:
BASE=int(float(input("Enter Base : ").strip()))
POWER=int(input("Enter Power : ").strip())
exceptValueError:
print("Invalid literal for integer")

RESULT=binary_exponentiation(BASE, POWER)
print(f"{BASE}^({POWER}) : {RESULT}")
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
"""Binary Exponentiation."""

# Author : Junth Basnet
# Time Complexity : O(logn)


defbinary_exponentiation(a: int, n: int) ->int:
"""
 Compute a number raised by some quantity
 >>> binary_exponentiation(-1, 3)
 -1
 >>> binary_exponentiation(-1, 4)
 1
 >>> binary_exponentiation(2, 2)
 4
 >>> binary_exponentiation(3, 5)
 243
 >>> binary_exponentiation(10, 3)
 1000
 >>> binary_exponentiation(5e3, 1)
 5000.0
 >>> binary_exponentiation(-5e3, 1)
 -5000.0
 """
ifn==0:
return1

elifn%2==1:
returnbinary_exponentiation(a, n-1) *a

else:
b=binary_exponentiation(a, n//2)
returnb*b


if__name__=="__main__":
importdoctest

doctest.testmod()

try:
BASE=int(float(input("Enter Base : ").strip()))
POWER=int(input("Enter Power : ").strip())
exceptValueError:
print("Invalid literal for integer")

RESULT=binary_exponentiation(BASE, POWER)
print(f"{BASE}^({POWER}) : {RESULT}")
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
"""Binary Exponentiation."""

# Author : Junth Basnet
# Time Complexity : O(logn)


defbinary_exponentiation(a: int, n: int) ->int:
"""
 Compute a number raised by some quantity
 >>> binary_exponentiation(-1, 3)
 -1
 >>> binary_exponentiation(-1, 4)
 1
 >>> binary_exponentiation(2, 2)
 4
 >>> binary_exponentiation(3, 5)
 243
 >>> binary_exponentiation(10, 3)
 1000
 >>> binary_exponentiation(5e3, 1)
 5000.0
 >>> binary_exponentiation(-5e3, 1)
 -5000.0
 """
ifn==0:
return1

elifn%2==1:
returnbinary_exponentiation(a, n-1) *a

else:
b=binary_exponentiation(a, n//2)
returnb*b


if__name__=="__main__":
importdoctest

doctest.testmod()

try:
BASE=int(float(input("Enter Base : ").strip()))
POWER=int(input("Enter Power : ").strip())
exceptValueError:
print("Invalid literal for integer")

RESULT=binary_exponentiation(BASE, POWER)
print(f"{BASE}^({POWER}) : {RESULT}")
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
"""Binary Exponentiation."""

# Author : Junth Basnet
# Time Complexity : O(logn)


defbinary_exponentiation(a: int, n: int) ->int:
"""
 Compute a number raised by some quantity
 >>> binary_exponentiation(-1, 3)
 -1
 >>> binary_exponentiation(-1, 4)
 1
 >>> binary_exponentiation(2, 2)
 4
 >>> binary_exponentiation(3, 5)
 243
 >>> binary_exponentiation(10, 3)
 1000
 >>> binary_exponentiation(5e3, 1)
 5000.0
 >>> binary_exponentiation(-5e3, 1)
 -5000.0
 """
ifn==0:
return1

elifn%2==1:
returnbinary_exponentiation(a, n-1) *a

else:
b=binary_exponentiation(a, n//2)
returnb*b


if__name__=="__main__":
importdoctest

doctest.testmod()

try:
BASE=int(float(input("Enter Base : ").strip()))
POWER=int(input("Enter Power : ").strip())
exceptValueError:
print("Invalid literal for integer")

RESULT=binary_exponentiation(BASE, POWER)
print(f"{BASE}^({POWER}) : {RESULT}")
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
"""Binary Exponentiation."""

# Author : Junth Basnet
# Time Complexity : O(logn)


defbinary_exponentiation(a: int, n: int) ->int:
"""
 Compute a number raised by some quantity
 >>> binary_exponentiation(-1, 3)
 -1
 >>> binary_exponentiation(-1, 4)
 1
 >>> binary_exponentiation(2, 2)
 4
 >>> binary_exponentiation(3, 5)
 243
 >>> binary_exponentiation(10, 3)
 1000
 >>> binary_exponentiation(5e3, 1)
 5000.0
 >>> binary_exponentiation(-5e3, 1)
 -5000.0
 """
ifn==0:
return1

elifn%2==1:
returnbinary_exponentiation(a, n-1) *a

else:
b=binary_exponentiation(a, n//2)
returnb*b


if__name__=="__main__":
importdoctest

doctest.testmod()

try:
BASE=int(float(input("Enter Base : ").strip()))
POWER=int(input("Enter Power : ").strip())
exceptValueError:
print("Invalid literal for integer")

RESULT=binary_exponentiation(BASE, POWER)
print(f"{BASE}^({POWER}) : {RESULT}")