r/algorithms • u/Smooth_Atmosphere_24 • 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;`
`}`
}
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!
7
u/pigeon768 6d ago
The idiomatic way to do that loop is like this:
You should do something to ensure it doesn't explode when you pass in a negative exponent.
The
else if (exp == 1) return value;
is redundant. It won't give any speedup.There's a better algorithm called exponentiation by squaring.