recursive algorithms

hopesfall (179)
I've wrote a small recursive function that calculates xn where x is a floating point number and n is an integer. My textbook tells me to use the following formula:
x0 = 1
xn = (xn/2)2 if n > 0 and n is even
xn = x * (xn/2)2 if n > 0 and n is odd

So I wrote up the function:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
int main(){
float base = 3.0;
float exponent = 2;
powers(base,exponent);
}
float powers(float baseNumber, int exponentNumber){
	float sq = sqrt(3.0);
	int in = sq;
	if (exponentNumber == 0){
		return 1;
	}
	// exponent is even
	if (exponentNumber % 2 == 0 && exponentNumber > 0){
		float tt = power3(power3(baseNumber,exponentNumber /2),2);
		return tt;
	}
	// exponent is odd
	else if(exponentNumber % 2 != 0 && exponentNumber > 0){
		float i = baseNumber * power3(power3(baseNumber,exponentNumber /2),2);
		return i;
	}
	else
		return -1;
}


My results aren't what I expect....My guess is that I'm interpreting the algorithms wrongly when I write them in code. Can anyone help me out?
Cubbi (4774)
Good textbook.

Why is there a call to sqrt() in your implementation?

Also, you can't express squaring in terms of itself.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#include <iostream>
double powers(double baseNumber, unsigned int exponentNumber)
{
    if (exponentNumber == 0)
        return 1;

    double sq = powers(baseNumber, exponentNumber/2);
    sq *= sq;

    if (exponentNumber % 2 == 0 )
        return sq;
    else
        return baseNumber * sq; 
}
int main()
{
    double base = 3.0;
    unsigned int exponent = 2;
    std::cout << powers(base, exponent) << '\n';
    std::cout << powers(10, 100) << '\n';
    std::cout << powers(2, 100) << '\n';
}

hopesfall (179)
Oh wow. Thanks for the response. I think my problem was that I was thinking too hard about it.

Thanks!
hopesfall (179)
How would I know how many recursive calls were needed to solve a given base and exponent? Could I just add a "counter++" inside the powers function and get the correct answer by looking at what counter ends up being? This is what I tried:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
#include <iostream>
double powers(double baseNumber, unsigned int exponentNumber)
{
    counter++

    if (exponentNumber == 0)
        return 1;

    double sq = powers(baseNumber, exponentNumber/2);
    sq *= sq;

    if (exponentNumber % 2 == 0 )
        return sq;
    else
        return baseNumber * sq; 
}
int main()
{
    double base = 3.0;
    unsigned int exponent = 2;
    std::cout << powers(base, exponent) << '\n';
    std::cout << powers(10, 100) << '\n';
    std::cout << powers(2, 100) << '\n';
}
Topic archived. No new replies allowed.