c# - 'Grokkable' algorithm to understand exponentiation where the exponent is floating point -

to clarify first:

• 2^3 = 8. that's equivalent 2*2*2. easy.
• 2^4 = 16. that's equivalent 2*2*2*2. easy.
• 2^3.5 = 11.313708... er, that's not easy grok.

want want simple algorithm shows how 2^3.5 = 11.313708. should preferably not use functions apart basic addition, subtract, multiply, or divide operators.

the code doesn't have fast, nor need short (though help). don't worry, can approximate given user-specified accuracy (which should part of algorithm). i'm hoping there binary chop/search type thing going on, that's pretty simple grok.

so far i've found this, top answer far simple understand on conceptual level.

the more answers merrier, can try understand different ways of attacking problem.

my language preference answer c#/c/c++/java, or pseudocode care.

ok, let's implement pow(x, y) using binary searches, addition , multiplication.

driving y below 1

first, take out of way:

pow(x, y) == pow(x*x, y/2) pow(x, y) == 1/pow(x, -y) 

this important handle negative exponents , drive y below 1, things start getting interesting. reduces problem finding pow(x, y) 0<y<1.

implementing sqrt

in answer assume know how perform sqrt. know sqrt(x) = x^(1/2), easy implement using binary search find y = sqrt(x) using y*y=x search function, e.g.:

#define eps 1e-8  double sqrt2(double x) {     double = 0, b = x>1 ? x : 1;      while(abs(a-b) > eps) {         double y = (a+b)/2;         if (y*y > x) b = y; else = y;     }     return a; } 

finding answer

the rationale every number below 1 can approximated sum of fractions 1/2^x:

0.875 = 1/2 + 1/4 + 1/8 0.333333... = 1/4 + 1/16 + 1/64 + 1/256 + ... 

if find fractions, find that:

x^0.875 = x^(1/2+1/4+1/8) = x^(1/2) * x^(1/4) * x^(1/8) 

that leads to

sqrt(x) * sqrt(sqrt(x)) * sqrt(sqrt(sqrt(x))) 

so, implementation (in c++)

#define eps 1e-8  double pow2(double x, double y){     if (x < 0 , abs(round(y)-y) < eps) {         return pow2(-x, y) * ((int)round(y)%2==1 ? -1 : 1);     } else if (y < 0) {         return 1/pow2(x, -y);     } else if(y > 1) {         return pow2(x * x, y / 2);     } else {         double fraction = 1;         double result = 1;          while(y > eps) {             if (y >= fraction) {                 y -= fraction;                 result *= x;             }              fraction /= 2;             x = sqrt2(x);         }         return result;     } }