- Notifications
You must be signed in to change notification settings - Fork20.8k
Added FastPower#731
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
Added FastPower#731
Uh oh!
There was an error while loading.Please reload this page.
Conversation
Added FastPower
havanagrawal left a comment
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
This looks like the same functionality asmodPow, so the tests should use this as the "expected" value.
| public class FastPowerTest { | ||
| @Test | ||
| public void test() { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
This should haveassert* statements, notprintlns.
| BigInteger ans = BigInteger.ONE; | ||
| while (!k.equals(BigInteger.ZERO)) { | ||
| int odd = k.mod(new BigInteger("2")).compareTo(BigInteger.ZERO); | ||
| if(odd == 1){ |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
The result ofcompareTo should only be compared with 0, there is no guarantee that it will be 1, only that it may be negative, 0 or positive.
| if(odd == 1){ | ||
| ans = ans.multiply(n).mod(mod); | ||
| } | ||
| k = k.divide(new BigInteger("2")); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Instead of usingnew BigInteger("2") in a loop, we could declare it as a constant outside:
publicstaticfinalBigIntegerTWO =newBigInteger("2");
DDullahan commentedMay 3, 2019
Thanks for your review@havanagrawal , I have fixed these problems. |
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Added FastPower
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.