Google Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
Isn't it just doing multiplication of x for n times? The important thing here I think is how you handle double/integer overflow.
/*
A complete pow(x,y) implementation supporting fraction powers as well.
*/
#include <iostream>
#include <stdio.h>
using namespace std;
typedef unsigned long long UINT64;
int gcd(int a, int b) {
if(b == 0) return a;
return gcd(b, a%b);
}
double powI(double x, int n){
if(x==0 && n) return 0;
if(n==0) return 1;
double powTable[100];
powTable[0] = 1;
powTable[1] = x;
for(int i=2; i<=n;i++) powTable[i] = 0;
int i=1;
double result = 1;
while(i<n){
if(2*i <= n){
if(!powTable[2*i]) powTable[2*i] = powTable[i] * powTable[i];
result = powTable[2*i];
i *= 2;
continue;
}
int j = n - i;
while(!powTable[j]) j--;
result *= powTable[j];
i = i+j;
}
return result;
}
void ExtractFraction(double P, int& m, int& n){
int x=1;
while(P != (int)P){
P *= 10;
x *= 10;
}
int d=gcd(P, x);
m=P/d;
n=x/d;
}
// Using Newton–Raphson method
double CalculateNRoot(int x, int n) {
double y=1;
double delta = 1;
while(true){
double yn = powI(y,n);
double FX = yn-x;
double FDX = n*(yn/y);
double m = y - FX/FDX;
delta = (m>y)? (m-y) : (y-m);
y=m;
if(delta < .000000001) break;
}
return y;
}
// calculate x^y
double pow(double x, double y){
if(x<0) return -1; // -ve x not supported
if(x==0 && y==0) return -1;
if(x==0) return 0;
if(y==0) return 1;
double Y = y>=0 ? y : -y;
double result=0;
if(Y == (int)Y){ // Y is an integer
result = powI(x,Y);
} else { // fraction Y
int m,n;
ExtractFraction(Y, m, n);
result = powI(x, m);
result = CalculateNRoot(result, n);
}
return y>=0 ? result : (1/result);
}
int main() {
cout << pow(2, 16) << endl;
cout << pow(2, -16) << endl;
cout << pow(2, 1.6) << endl;
return 0;
}
power by squaring:
pow(x, exp) = {
if x is even (x^2)(x^(2/n))
if x is odd x((x^2)^(n-1/2)
}
base cases:
if exp == 0 then return 1
if exp == 1 then return x itself
float powe(float x, int exp)
{
printf("%f %d\n", x, exp);
if (exp < 0)
return powe(1/x, -exp);
if (exp == 0)
return 1;
if (exp == 1)
return x;
if (((int)exp)%2==0)
return powe(x*x, exp/2);
else
return x*powe(x*x, (exp-1)/2);
}
float powe(float x, int exp)
{
if (exp < 0)
return powe(1/x, -exp);
if (exp == 0)
return 1;
if (exp == 1)
return x;
if (((int)exp)%2==0)
return powe(x*x, exp/2);
else
return x*powe(x*x, (exp-1)/2);
}
Corrected the negative exponents. However, the more difficult part is the fractional exponents.
#include <iostream>
#include <cmath>
#include <ctime>
float powe(float x, int exp)
{
printf("%f %d\n", x, exp);
if (exp < 0)
return powe(1 / x, -exp);
if (exp == 0)
return 1;
if (exp == 1)
return x;
if (((int)exp) % 2 == 0)
return powe(x*x, exp / 2);
else
return x*powe(x*x, (exp - 1) / 2);
}
int main() {
std::cout << pow(5, 1.7);
std::cout << std::endl;
std::cout << powe(5, 1.7);
}
pow(5, 1.7) outputs 15.4258.
powe(5, 1.7) outputs 5.00001.
Think about a^4.3 = a^4 * a^.3
Where a^.3 = a^.5^.5 * a^.05
Where a^.05 = a^.5^.5^.5^.5^.5 * a^.01875
Of course you'll never end this descent but you can get as close as desired. (6 decimals of precision)
It's not the fastest(you can do better with taylor series expansion and logarithms) but using repeating square roots is a quick and dirty way to handle fractional(or irrational) exponents.
Disclaimer: Not my code - Square Root Method
#include <iostream>
// Not My Code, edited to be more effecient
double sqr(double x) { return x * x; }
// meaning of 'precision': the returned answer should be base^x, where
// x is in [power-precision/2,power+precision/2]
double mypow(double base, double power, double precision)
{
if (power < 0) return 1 / mypow(base, -power, precision);
if (power >= 1) return base * mypow(base, power - 1, precision);
if (precision >= 1) return sqrt(base);
return sqrt(mypow(base, power * 2, precision * 2));
}
// End not my code
// My code
double mypowfast(double base, int power) {
if (power == 0) return 1;
if (power == 1) return base;
if (power % 2 == 0) return mypowfast(base * base, power / 2);
else return base * mypowfast(base*base, (power - 1) / 2);
}
// My code
double mypow(double base, double power) {
if (power < 0) {
power = -power;
base = 1 / base;
}
int intpower = (int)power;
double t = mypowfast(base, intpower);
power -= intpower;
return t*mypow(base, power, .000001);
}
int main() {
std::cout << mypow(5, 1.734) << std::endl;
std::cout << pow(5, 1.734) << std::endl;
}
Yeah, for a^b where b is a real number. I find a^(integer portion of b) then multiply by a^(floating point portion of b).
To find the floating point portion we use the following observation:
a^b = sqrt(a^2b)
a^b = sqrt(sqrt(a^4b)
a^b = sqrt(sqrt(sqrt(a^8b)))
As an example lets say 4b < 1 <= 8b
then a^b = sqrt(sqrt(sqrt(a * a^(8b-1))))
.
.
Notice that this could continue infinitely, or at least way past the precision that we care about, which is why we keep a precision counter. (if you plug in a giant number like 2000000 for precision in the ideone code below you'll notice that for 1.7, the power actually converges to 1 around 40-60 iterations so it stops on it's own.)
For example, 5^1.7
5^1 * 5^.7
5^.7 = sqrt(5^1.4)
= sqrt(5^1*5^.4)
5^.4 = sqrt(5^.8) = sqrt(sqrt(5^1.6)) = sqrt(sqrt(5^1*5^.6)
Continue until you reach the level of precision desired at which point you just estimate with sqrt(5).
Unwinding gives us 5^1.7 = 5*sqrt(5*sqrt(sqrt(5*sqrt(5))))
The precision number could be replaced by a counter that counts down. For example, the log_2(1/0.00001) = 16.609... so I picked 20 in the ideone code below to be safe.
Here is edited C++11 code that, instead of outputing the answer, outputs the closed form 5*sqrt(5*sqrt(sqrt(....
Feel free to mess around with it:
(If you haven't used ideone before, just hit edit and under input type two numbers seperated by a space, base exponent. I have it default to 5 1.7)
Note that the actual algorithm gives you NaN, just like the std::pow function, for negative bases to fractional exponents but the string version will most likely just spit out the positive version with negatives in front of everything incorrectly.
http://ideone.com/2mcE5h
I hope that helps.
@SycohphantEve: we can also do this way which is how i think standard pow is implemented
x^y = e^(y . log(x))
and exponentiation is calculated with pre-calculated tables.
I don't believe they actually use a table, as a precalculated table for all possible numbers between [0, maxDouble] up to 6 digits of precision would take a gigantic amount of memory. A square root table maybe, as shown below, but you still need to know how to convert that to an actual power.
I personally believe they use an optimized, base 2, approximation algorithm similar to fast square root.
All Credit goes to Spektre on Stack Overflow, this was posted in the link I posted below.
I am using fixed point long arithmetics and my pow is log2/exp2 based. Numbers consist of:
int sig = { -1; +1 } signum
DWORD a[A+B] number
A is num of DWORDs for integer part of number
B is num of DWORDs for fractional part
My simplified solution is this:
//---------------------------------------------------------------------------
longnum exp2 (const longnum &x)
{
int i,j;
longnum c,d;
c.one();
if (x.iszero()) return c;
i=x.bits()-1;
for(d=2,j=_longnum_bits_b;j<=i;j++,d*=d)
if (x.bitget(j))
c*=d;
for(i=0,j=_longnum_bits_b-1;i<_longnum_bits_b;j--,i++)
if (x.bitget(j))
c*=_longnum_log2[i];
if (x.sig<0) {d.one(); c=d/c;}
return c;
}
//---------------------------------------------------------------------------
longnum log2 (const longnum &x)
{
int i,j;
longnum c,d,dd,e,xx;
c.zero(); d.one(); e.zero(); xx=x;
if (xx.iszero()) return c; //**** error: log2(0) = infinity
if (xx.sig<0) return c; //**** error: log2(negative x) ... no result possible
if (d.geq(x,d)==0) {xx=d/xx; xx.sig=-1;}
i=xx.bits()-1;
e.bitset(i); i-=_longnum_bits_b;
for (;i>0;i--,e>>=1) // integer part
{
dd=d*e;
j=dd.geq(dd,xx);
if (j==1) continue; // dd> xx
c+=i; d=dd;
if (j==2) break; // dd==xx
}
for (i=0;i<_longnum_bits_b;i++) // fractional part
{
dd=d*_longnum_log2[i];
j=dd.geq(dd,xx);
if (j==1) continue; // dd> xx
c.bitset(_longnum_bits_b-i-1); d=dd;
if (j==2) break; // dd==xx
}
c.sig=xx.sig;
c.iszero();
return c;
}
//---------------------------------------------------------------------------
longnum pow (const longnum &x,const longnum &y)
{
//x^y = exp2(y*log2(x))
int ssig=+1; longnum c; c=x;
if (y.iszero()) {c.one(); return c;} // ?^0=1
if (c.iszero()) return c; // 0^?=0
if (c.sig<0)
{
c.overflow(); c.sig=+1;
if (y.isreal()) {c.zero(); return c;} //**** error: negative x ^ noninteger y
if (y.bitget(_longnum_bits_b)) ssig=-1;
}
c=exp2(log2(c)*y); c.sig=ssig; c.iszero();
return c;
}
//---------------------------------------------------------------------------
where:
_longnum_bits_a = A*32
_longnum_bits_b = B*32
_longnum_log2[i] = 2 ^ (1/(2^i)) ... precomputed sqrt table
_longnum_log2[0]=sqrt(2)
_longnum_log2[1]=sqrt[tab[0])
_longnum_log2[i]=sqrt(tab[i-1])
longnum::zero() sets *this=0
longnum::one() sets *this=+1
bool longnum::iszero() returns (*this==0)
bool longnum::isnonzero() returns (*this!=0)
bool longnum::isreal() returns (true if fractional part !=0)
bool longnum::isinteger() returns (true if fractional part ==0)
int longnum::bits() return num of used bits in number counted from LSB
longnum::bitget()/bitset()/bitres()/bitxor() are bit access
longnum.overflow() rounds number if there was a overflow
X.FFFFFFFFFF...FFFFFFFFF??h -> (X+1).0000000000000...000000000h
int longnum::geq(x,y) is comparition |x|,|y| returns 0,1,2 for (<,>,==)
All you need to understand this code is that numbers in binary form consists of sum of powers of 2, when you need to compute 2^num then it can be rewritten as this
2^(b(-n)*2^(-n) + ... + b(+m)*2^(+m)) where n are fractional bits and m are integer bits multiplication/division by 2 in binary form is simple bit shifting so if you put it all together you get code for exp2 similar to my. log2 is based on changing the result bits from MSB to LSB until it matches searched value (very similar algorithm as for fast sqrt computation). hope this helps clarify things...
Note that the sqrt is quick and dirty as it's about 3 lines of code. (6-7 if you have to write your own sqrt function, and it'll be slower).
Take a look here: http://stackoverflow.com/questions/2882706/how-can-i-write-a-power-function-myself
For different methods including the Square Root method, the logarithm/taylor series methods, and the code I posted above.
This can be done with brute force multiply the base N-times giving a O(n)
X^N = X*X*X*...X // N-time Brut force O(N)
But can be done in O(logN) if we use a math trick, we can split the pow operation
X^N = X^(N/2) * X^(N/2) //If exponent is even
X^N = X^(N/2) * X^(N/2) * X //If exponent is odd
We just need to compute one call from the recursión
- hnatsu June 22, 2015public double Pow(double x, int n) { if (x == 0 && n == 0) throw new InvalidOperationException(); if (n == 0) return 1; double result = InternalPow(x, Math.Abs(n)); // If exponent is negative if (n < 0) result = 1 / result; return result; } private double InternalPow(double x, int n) { if (n == 1) return x; else if (n == 2) return x * x; double pow = InternalPow(x, n / 2); pow *= pow; // If N is even extra multiply X^N = X^(N/2) * X^(N/2) * N if (n % 2 != 0) pow *= x; return pow; }