Commit1b82826

authored

Added Binary Exponentiation Fixes:TheAlgorithms#1943 (TheAlgorithms#1945)

* Added Binary Exponentiation Fixes:TheAlgorithms#1943* tests added in Binary ExponentationTheAlgorithms#1945* Assertion Added

1 parent9c8ad9c commit1b82826Copy full SHA for 1b82826

File tree

+46

-0

lines changed

+46

-0

lines changed

Lines changed: 46 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,46 @@`
	`1`	`+packageMaths;`
	`2`	`+`
	`3`	`+publicclassBinaryPow {`
	`4`	`+/**`
	`5`	`+ * Calculate a^p using binary exponentiation`
	`6`	`+ * [Binary-Exponentiation](https://cp-algorithms.com/algebra/binary-exp.html)`
	`7`	`+ *`
	`8`	`+ * @param a the base for exponentiation`
	`9`	`+ * @param p the exponent - must be greater than 0`
	`10`	`+ * @return a^p`
	`11`	`+ */`
	`12`	`+publicstaticintbinPow(inta,intp) {`
	`13`	`+intres =1;`
	`14`	`+while (p >0) {`
	`15`	`+if ((p &1) ==1) {`
	`16`	`+res =res *a;`
	`17`	`+ }`
	`18`	`+a =a *a;`
	`19`	`+p >>>=1;`
	`20`	`+ }`
	`21`	`+returnres;`
	`22`	`+ }`
	`23`	`+`
	`24`	`+/**`
	`25`	`+ * Function for testing binary exponentiation`
	`26`	`+ * @param a the base`
	`27`	`+ * @param p the exponent`
	`28`	`+ */`
	`29`	`+publicstaticvoidtest(inta,intp) {`
	`30`	`+intres =binPow(a,p);`
	`31`	`+assertres == (int)Math.pow(a,p) :"Incorrect Implementation";`
	`32`	`+System.out.println(a +"^" +p +": " +res);`
	`33`	`+ }`
	`34`	`+`
	`35`	`+/** Main Function to call tests`
	`36`	`+ *`
	`37`	`+ * @param args System Line Arguments`
	`38`	`+ */`
	`39`	`+publicstaticvoidmain(String[]args) {`
	`40`	`+// prints 2^15: 32768`
	`41`	`+test(2,15);`
	`42`	`+`
	`43`	`+// prints 3^9: 19683`
	`44`	`+test(3,9);`
	`45`	`+ }`
	`46`	`+}`

Comments

(0)