FilesExpand file tree

master

/

binary_exponentiation_2.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

50 lines (39 loc) · 1.24 KB

master

/

binary_exponentiation_2.py

Copy path

Top

File metadata and controls

• Code
• Blame

50 lines (39 loc) · 1.24 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

"""

* Binary Exponentiation with Multiplication

* This is a method to find a*b in a time complexity of O(log b)

* This is one of the most commonly used methods of finding result of multiplication.

* Also useful in cases where solution to (a*b)%c is required,

* where a,b,c can be numbers over the computers calculation limits.

* Done using iteration, can also be done using recursion

* @author chinmoy159

* @version 1.0 dated 10/08/2017

"""

def b_expo(a, b):

res = 0

while b > 0:

if b & 1:

res += a

a += a

b >>= 1

return res

def b_expo_mod(a, b, c):

res = 0

while b > 0:

if b & 1:

res = ((res % c) + (a % c)) % c

a += a

b >>= 1

return res

"""

* Wondering how this method works !

* It's pretty simple.

* Let's say you need to calculate a ^ b

* RULE 1 : a * b = (a+a) * (b/2) ---- example : 4 * 4 = (4+4) * (4/2) = 8 * 2

* RULE 2 : IF b is ODD, then ---- a * b = a + (a * (b - 1)) :: where (b - 1) is even.

* Once b is even, repeat the process to get a * b

* Repeat the process till b = 1 OR b = 0, because a*1 = a AND a*0 = 0

*

* As far as the modulo is concerned,

* the fact : (a+b) % c = ((a%c) + (b%c)) % c

* Now apply RULE 1 OR 2, whichever is required.

"""