Quick Exponentiation

So the problem comes from Daily Coding Problem:

This problem was asked by Google.
Implement integer exponentiation. That is, implement the pow(x, y) function, where x and y are integers and returns x^y.
Do this faster than the naive method of repeated multiplication.
For example, pow(2, 10) should return 1024.

So the secret here is to decompose the exponent (say 10) in its power of 2. So 10 = 8 + 2. Each of these parts can be computed in Log(N) time, which makes the overall execution time for exponentiation some constant * Log(y). Faster than the repeated multiplication. Code is down below, or on GitHub: https://github.com/BorisVasilenko/dailycodingproblem/blob/master/DailyCodingProblem11142018.cs

Thanks, Boris
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DailyCodingProblem
{
 class DailyCodingProblem11142018
 {
  public long Exponentiation(long x, long y)
  {
   long result = 1;

   while (y > 0)
   {
    long exp = x;
    long count = 1;
    while (count * 2 <= y)
    {
     exp *= exp;
     count *= 2;
    }
    y -= count;
    result *= exp;
   }

   return result;
  }
 }
}

Comments

  1. This looks like a special case of https://leetcode.com/problems/powx-n My solution is slightly more efficient as it uses fewer variables and as such involves fewer memory copies, but the idea is similar:

    class Solution {
    public:
    double myPow(double x, long n) {
    if (n < 0) return 1 / myPow(x, -n);
    double result = 1;
    for (; n > 0; n /= 2) {
    if (n % 2 == 1) result *= x;
    x *= x;
    }
    return result;
    }
    };

    which can be simplified in for the provided problem statement to:

    class Solution {
    public:
    long myPow(long x, long n) {
    long result = 1;
    for (; n > 0; n /= 2, x *= x) {
    if (n % 2 == 1) result *= x;
    }
    return result;
    }
    };

    which interestingly looks like a valid C# :)

    ReplyDelete
  2. Love the dual-purpose for-loop: control (n) and production (x). Clever!

    ReplyDelete
    Replies
    1. it does not always help, but since I often use guard conditions to avoid deep nesting (interestingly I didn't use it in this case) and using for-loop is a great way to make sure that all post-iteration changes do actually happen. In other words I do this because I'm a very sloppy and it's one of the ways to avoid some common pitfalls :)

      Delete

Post a Comment

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons