FilesExpand file tree

 Development

/

FastPower.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

36 lines (33 loc) · 1.02 KB

 Development

/

FastPower.java

Copy path

Top

File metadata and controls

• Code
• Blame

36 lines (33 loc) · 1.02 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

package com.others;

import java.math.BigInteger;

/**

* We may calculate power with loops, but what if the index is too large ?

* FastPower aims to calculate quickly in this circumstances with time complexity O(log k),

* where k is the index.

*

*/

public class FastPower {

public static BigInteger calculate(BigInteger n, BigInteger k, BigInteger mod) {

BigInteger ans = BigInteger.ONE;

while (!k.equals(BigInteger.ZERO)) {

int odd = k.mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO);

if (odd > 0) {

ans = ans.multiply(n).mod(mod);

}

k = k.divide(BigInteger.valueOf(2));

n = n.multiply(n).mod(mod);

}

return ans.mod(mod);

}

public static long calculate(long n, long k, long mod) {

long ans = 1;

while (k != 0) {

if (k % 2 == 1) {

ans = (ans * n) % mod;

}

k >>= 1;

n = (n * n) % mod;

}

return ans % mod;

}

}