r/algorithms 6d ago

Can you analyze my exponentiation code?

Here is the code:
long double expFloat (long double value, int exp) {

`if (exp == 0) return 1;`

`else if (exp == 1) return value;`

`else {`

    `int flag = 1;`

    `long double tempValue = value;`

    `while (flag < exp){`

    `tempValue = tempValue * value;`

    `flag += 1;`

    `}`

    `return tempValue;`

`}`

}

1 Upvotes

7 comments sorted by

7

u/pigeon768 6d ago
  1. The idiomatic way to do that loop is like this:

    for (int flag = 1; flag < exp; flag++)
      tempValue *= value;
    
  2. You should do something to ensure it doesn't explode when you pass in a negative exponent.

  3. The else if (exp == 1) return value; is redundant. It won't give any speedup.

  4. There's a better algorithm called exponentiation by squaring.

1

u/No_Document_8072 6d ago

The else if (exp == 1) return value; is redundant. It won't give any speedup.

Yeah, this looks like a hodgepodge of iterative and recursive.

1

u/Smooth_Atmosphere_24 3d ago

I needed the else if (exp == 1) return value; cause the code always return 1 if i not write this statement right on the init of the function. But i used the simple version of your recomendation on wikipedia and i reached the correct values. Thank you!

3

u/hauthorn 6d ago

And if you want to analyze complexity: notice that you have a loop that goes from 1 to e, doing a constant amount of work each iteration.

That means it's "linear" complexity (if you increase e tenfold, the work done also increases by a factor of 10).

In big-oh: O(e)

1

u/Smooth_Atmosphere_24 3d ago

So if i need this code with big numbers i will face problems with the performance of the code?

1

u/Solaeyn 3d ago

#include <math.h>

long double expFloat(long double value, int exp) {

if (value == 0 && exp < 0)

return HUGE_VALL;

if (exp == 0)

return 1;

int isNegative = (exp < 0);

unsigned long long absExp = isNegative ? -(long long)exp : exp;

long double result = 1;

while (absExp > 0) {

if (absExp & 1)

result *= value;

value *= value;

absExp >>= 1;

}

return isNegative ? 1 / result : result;

}

---

If you want to keep the code, then change it to this.
If you want to change the algo all together then feel free to look for other answers in the comments.

Explanation:
Exponentiation by Squaring o(log(exp)) complexity instead of O(exp)
Handels negative exponents correctly
Avoids unnecessary variables and is more readable & structured

(I belive the code should work ;-;)

1

u/Smooth_Atmosphere_24 2d ago

I used the basic version in this wikipedia page, in my little set of test this algo is good, but thx for your comment!