trekhleb / trekhleb/javascript-algorithms

Should approach fastPowering this way?

Open
#299 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
JavaScript
Stars
197k
Forks
31k
PR merge metrics
No merged PRs in 30d

Description

While learning about Fast Powering Algorithm, I notice that a minor tweak can be made to the fastPowering.js file.

In both of the cases whether the power is odd or event, calculated multiplier will be the same. So, we can calculate multiplier before the if clause and return the multiplication based on the nature of power.

export default function fastPowering(base, power) {
  if (power === 0) {
    // Anything that is raised to the power of zero is 1.
    return 1;
  }

  // multiplier will be same whether power is even or odd
  const multiplier = fastPowering(base, Math.floor(power / 2)); 
  if (power % 2 === 0) {
    // If the power is even...
    // we may recursively redefine the result via twice smaller powers:
    // x^8 = x^4 * x^4.
    return multiplier * multiplier;
  }

  // If the power is odd...
  // we may recursively redefine the result via twice smaller powers:
  // x^9 = x^4 * x^4 * x.
  return multiplier * multiplier * base;
}

@trekhleb Let me know your thoughts. And if you're okay with this implementation I can raise a PR.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Read fastPowering.js and compare its odd and even branches with the proposed shared multiplier calculation. Verify that the refactor preserves results for zero, even, and odd powers; done means the approach is accepted and the issue is closed.

Written by the indexing model from the issue text.

Assessment

Tech stack
javascript
Domain
tooling
Issue type
Refactor
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.