Recursive Help Needed

[gh24]

Here is the code I need help with. This is a recursive function that is supposed to complete the repeated squaring algorithm on a matrix. My problem comes in when k is odd. It runs the second part as it should but I can't figure out how to have B multiply by the recursive function like I need it to.

void repeated_squaring(Matrix B, int n, int k)
{
	Matrix C;
	{
	if (k == 1){
		cout << 1 << endl;
		cout << B << endl;
		exit(0);
	}

	if(k > 1 && k % 2!= 0){
		cout << 2 << endl;
		cout << endl;
		cout << B << endl;
		B * repeated_squaring(B*B, n, (k-1)/2);
	
	}
	else{
		cout << 3 << endl; 
		cout<< B << endl;
		repeated_squaring(B*B,n,k/2);
	}
	}
}

B is a randomly generated matrix. I have B being outputted in places in the code and 1, 2 and 3 being outputted so I can see whats going on when the code runs, not because it needs to be there.

In my main function the user inputs an n and k where n is the square matrix's size and k is the power to take the square matrix too. The code is supposed to be a repeated squaring algorithm that cuts down the amount of time it takes to take large matrices to large powers.

My problem is in the part where K is odd. I need to get B times the recursive function but I do not know how to do that.

[gh24]

Just to be clear the issue is at the B * repeated_squaring(B*B, n, (k-1)/2); line.

[WilliamW1979]

First I need to mention two things, there is an extra set of brackets that is useless in here, the set directly after the declaration of Matrix C and then Matrix C itself is declared and never used so those should be removed unless there is more code then you are showing here.

Your biggest problem is that you declared this as a void return so you are trying to multiply B by void. This isn't good at all. You need to change the return type and actually have it return something so it could have something to be multiplied by. So

void repeated_squaring(Matrix B, int n, int k)

should be

Matrix repeated_squaring(Matrix B, int n, int k)

Changing this won't instantly fix your code because you need to still return numbers to multiply by but this is the direction I believe you are trying to go.

[gh24]

Thanks for your help. Making it Matrix ... instead of void ... allows the multiplication to be there but the multiplication doesn't do anything.

I currently have a 2x2 matrix of 2s as matrix B. I can enter in the k value of my choice. I am doing this in order to check the output to make sure I am getting the right output.

When I have k = 3 I get the same value as when k =2. This seems to suggest to me that the recursive function isn't actually getting multiplied another time by the matrix B as it should.

Any suggestions here?

[gh24]

Here Is an example of what I would like the code to be doing:

Let's say B is simply an integer of 2 and I have K=5. That means I want the final answer to be 2^5 = 32, so output 3

the code should run through as follows:

repeated_squaring(2,1,5)

->2*repeated_squaring(4, 1, 2)

->-> 2*repeated_squaring(16, 1, 1)

->->-> 2* 16*repeated_squaring(16*16, 1, 0)

->->->->2*16*1 = 32

[WilliamW1979]

You still need to return a number for it to multiple

return 5;
[\code]

Try this, it is a for statement but it works more efficiently then what you are doing here

[code]
Matrix C = B;
for(int x=k-1;x>0;x--)
{
     C*=B;
}
return B;

Here you are running a for loop that will loop k amount of times minus one to give you the answer you want. Is this more of what you are looking for? Also there is a power function which works this way

double d = pow(2, 5);

This is 2^5 which is what I believe you are attempting to do.

[gh24]

Unfortunately I need to use the repeated squaring algorithm as requested by my prof.

The idea behind the repeated squaring is that when you get to large values of K you are doing the power more efficiently than for small values.

He also wants me to be using recursion in doing this.

I know I have some logical flaw in my recursion but for the life of me I can't seem to figure it out.
I have been working on this for what seems like years as well so I am at the point of frustration with it all.

[gh24]

Also what I currently have works for k values of 2, 4 ,8, 16 but any time it needs to use the odd k part nothing happens.

I am not sure how to return that number that it should multiply with because I can't be storing the number in any way because I will lose the scope won't I?

What I currently have just ignores the multiplication and runs the repeated_squaring, simply returning the B value.

I can't figure out how to get that multiplication to both stay as the correct value and then also multiply the final repeated squaring value by that value.

[gh24]

Does my explanation make sense? Do my confusions make sense? Is there anything I can clarify so as to make the question easier to understand?

[WilliamW1979]

Then try this:

Matrix repeated_squaring(Matrix n, int k)
{
	Matrix C;
	if(k == 1)
	{
		return n;
	}
	return n * repeated_squaring(n, k-1);
}

This doesn't help with bad variables like inputing a negative number for k but when I ran this for 2 to the 5th power, it worked.

[gh24]

That's just multiplying something to a power straight forward though.

The whole Idea behind this is that for 2⁵ do

2 * (2²*2²) or 2 * 16 *1

or for 2⁷ do

2 * 4 * 16

For K > ~100 and matrix size 5x5 this cuts down on computation time significantly because instead of actually calculating huge powers you are just multiplying smaller powers to get to the large power. In the case of

2⁷ its 2¹ * 2² * 2⁴ = 2⁷


You can also see that the 2 comes from the first iteration and k now becomes 3 and B is 4, then you get the 4 from the second iteration, k goes to 1 and B is now 16 and then you get the 16 and k = 0 and B = 256 so my code has 256 as the output.

[gh24]

I have a good feeling that the main issue at this point is that I simply output B when K=1. I need to output the multiplications but I don't know how to do that.

[WilliamW1979]

I get it!

Matrix repeated_squaring(Matrix n, int k)
{
	if(k == 0)
	{
		return n;
	}
	if (k == 1)
	{
		cout << 1 << endl;
		cout << n << endl;
		return n;
	}
	else if(k > 1 && k % 2!= 0)
	{
		cout << 2 << endl;
		cout << endl;
		cout << n << endl;
		return n * repeated_squaring(n*n, (k-1)/2);
	}
	else
	{
		cout << 3 << endl; 
		cout << n << endl;
		return repeated_squaring(n*n,k/2);
	}
}

[gh24]

I get an output of 4 when I do k = 3 instead of 8.

Also is there a difference between putting the 'return' in there or not putting it in there?

I think I may be outputting at the incorrect spot or in the incorrect way. How are you getting the actual value to output?

[gh24]

BTW thank you so much for the help. You've definitely gotten me to a better place than I was to begin with.

[gh24]

So here is the code I currently have:

Matrix repeated_squaring(Matrix B, int n, int k)
{
	
	if(k==0){
		return B;
	}

	if (k == 1){
		cout << B << endl;
		return B;
	}

	else if(k > 0 && k % 2!= 0){
		//cout << B << endl;
		return (B * repeated_squaring(B*B, n, (k-1)/2));
	}
	else{
		//cout<< B << endl;
		return (repeated_squaring(B*B,n,k/2));
	}
}

I get the output at line 9 where it simply outputs B. This doesn't give 8 when k=3.

I thought about removing the K=1 because that may be prematurely outputting the B value but that doesn't change anything.

[WilliamW1979]

Here is what I am using to test out the program. It works on my computer and I am guessing I get 8 because I am using the return in main as the answer. just change the int to Matrix to convert for your program for n and for the return type.

int repeated_squaring(int, int);

int main()
{
	int x=0;
	x = repeated_squaring(2, 5);
	std::cout << x;
	system("PAUSE");
}

int repeated_squaring(int n, int k)
{
	if(k == 0)
	{
		return n;
	}
	if (k == 1)
	{
		cout << 1 << endl;
		cout << n << endl;
		return n;
	}
	else if(k > 1 && k % 2!= 0)
	{
		cout << 2 << endl;
		cout << endl;
		cout << n << endl;
		return n * repeated_squaring(n*n, (k-1)/2);
	}
	else
	{
		cout << 3 << endl; 
		cout << n << endl;
		return repeated_squaring(n*n,k/2);
	}
}

[gh24]

YAY!!! it works!

But more importantly why???

Can you explain to me why you need the return in front of the functions?

Like what exactly changed that made the code work from what was there before (excluding the change from void to matrix)?

[gh24]

I can't thank you enough for helping me out tonight. This has been making me angry for nearly 2 weeks. You are awesome!

[WilliamW1979]

Well, you need numbers to multiply together so the return tells the compiler what number to return or pass back to the function calling the function. Like in main when it says

x = repeated_squaring(2, 5)

x is the variable waiting for the output. the function is obviously repeated_squaring(int, int) but the return is also int which you originally had as void. If you return a void, you return nothing. The return keyword tells the function what isw being returned and only errors if you don't return the right type like trying to return a string instead of a int. Now when you called the same program within the program, you needed it to also return a number so it would multiply it all out.

When a function is void, you don't have to use the keyword return but if you set it up as something else, you have to use a return for every exit point. Hope this helps to explain.