Commit64bd1a1

authored

Merge pull requestTheAlgorithms#731 from DDullahan/Development

Added FastPower

2 parents184f644 +c85caf5 commit64bd1a1Copy full SHA for 64bd1a1

File tree

+69

-0

lines changed

+69

-0

lines changed

Lines changed: 37 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,37 @@`
	`1`	`+packagesrc.main.java.com.Others;`
	`2`	`+`
	`3`	`+importjava.math.BigInteger;`
	`4`	`+`
	`5`	`+/**`
	`6`	`+ * We may calculate power with loops, but what if the index is too large ?`
	`7`	`+ * FastPower aims to calculate quickly in this circumstances with time complexity O(log k),`
	`8`	`+ * where k is the index.`
	`9`	`+ *`
	`10`	`+ * @author DDullahan`
	`11`	`+ */`
	`12`	`+publicclassFastPower {`
	`13`	`+publicstaticBigIntegercalculate(BigIntegern,BigIntegerk,BigIntegermod) {`
	`14`	`+BigIntegerans =BigInteger.ONE;`
	`15`	`+while (!k.equals(BigInteger.ZERO)) {`
	`16`	`+intodd =k.mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO);`
	`17`	`+if(odd >0){`
	`18`	`+ans =ans.multiply(n).mod(mod);`
	`19`	`+ }`
	`20`	`+k =k.divide(BigInteger.valueOf(2));`
	`21`	`+n =n.multiply(n).mod(mod);`
	`22`	`+ }`
	`23`	`+returnans.mod(mod);`
	`24`	`+ }`
	`25`	`+`
	`26`	`+publicstaticlongcalculate(longn,longk,longmod) {`
	`27`	`+longans =1;`
	`28`	`+while (k !=0) {`
	`29`	`+if (k %2 ==1) {`
	`30`	`+ans = (ans *n) %mod;`
	`31`	`+ }`
	`32`	`+k >>=1;`
	`33`	`+n = (n *n) %mod;`
	`34`	`+ }`
	`35`	`+returnans %mod;`
	`36`	`+ }`
	`37`	`+}`

Lines changed: 32 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,32 @@`
	`1`	`+packagesrc.main.java.com.Others;`
	`2`	`+`
	`3`	`+importorg.junit.*;`
	`4`	`+`
	`5`	`+importjava.math.BigInteger;`
	`6`	`+`
	`7`	`+importstaticorg.junit.Assert.*;`
	`8`	`+`
	`9`	`+publicclassFastPowerTest {`
	`10`	`+`
	`11`	`+voidtestLong(longn,longk,longm){`
	`12`	`+longresult =FastPower.calculate(n,k,m);`
	`13`	`+assertEquals(result,BigInteger.valueOf(n).modPow(BigInteger.valueOf(k),BigInteger.valueOf(m)).longValue());`
	`14`	`+ }`
	`15`	`+`
	`16`	`+voidtestBigInteger(BigIntegern,BigIntegerk,BigIntegerm){`
	`17`	`+BigIntegerresult =FastPower.calculate(n,k,m);`
	`18`	`+assertEquals(result,n.modPow(k,m));`
	`19`	`+ }`
	`20`	`+`
	`21`	`+@Test`
	`22`	`+publicvoidtest() {`
	`23`	`+testLong(2,2,10);`
	`24`	`+testLong(100,1000,20);`
	`25`	`+testLong(123456,123456789,234);`
	`26`	`+`
	`27`	`+testBigInteger(BigInteger.TEN,BigInteger.TEN,BigInteger.valueOf(4));`
	`28`	`+testBigInteger(newBigInteger("123456"),newBigInteger("123456789"),newBigInteger("234"));`
	`29`	`+testBigInteger(newBigInteger("123456789101112"),newBigInteger("12345678910111213"),newBigInteger("567890"));`
	`30`	`+`
	`31`	`+ }`
	`32`	`+}`

Comments

(0)