Recursive Transform and Conquer Exponentiation?

[Spreegem]

I had to develop a brute force, a recursive, divide and conquer, and transform and conquer algorithms for calculating the nth power of a, a^n, for an assignment. I got the first three done pretty easy but I'm completely stumped at how to do the transform and conquer algorithm.

I've been looking around and I was thinking of using modular exponentiation or exponentiation by squaring but I can't seem to find any recursive algorithm examples for how to do it and I can't figure out how to take something that is not recursive and make it recursive for example I found this modular exponentiation algorithm.

Bignum modpow(Bignum base, Bignum exponent, Bignum modulus) {
    Bignum result = 1;
 
    while (exponent > 0) 
    {
        if ((exponent & 1) == 1) 
        {
            // multiply in this bit's contribution while using modulus to keep result small
            result = (result * base) % modulus;
        }
        // move to the next bit of the exponent, square (and mod) the base accordingly
        exponent >>= 1;
        base = (base * base) % modulus;
    }
 
    return result;
}

How could I take something like that and make it recursive? Or would a different algorithm be better for doing a recursive transform and conquer algorithm for finding a^n?

Thanks a bunch in advance.

[Narue]

>How could I take something like that and make it recursive?
Loops are simulated using recursion, so your first step should be to take the loop and turn it into recursive calls without losing the changes made to local data.

The condition of the loop represents a base case, so you can do something like this:

Bignum modpow_r(Bignum base, Bignum exponent, Bignum modulus) {
  if (exponent > 0) {
    // Recurse
  }

  return /* something */;
}

You know how the algorithm works, presumably, so you can fill out that part a little bit before hitting a stumbling block. What do you do with result so that it persists between recursive calls?

There are generally two options for a persisted object. If you can build the value of the object when returning back up the recursive chain, you don't need a variable for it. This is more of an ideal recursive solution:

Bignum modpow_r(Bignum base, Bignum exponent, Bignum modulus) {
  if (exponent <= 0)
    return 1;

  Bignum next_base = (base * base) % modulus;
  Bignum next_exp = exponent >> 1;
  Bignum result = modpow_r(next_base, next_exp, modulus);

  if ((exponent & 1) == 1)
    result = (result * base) % modulus;

  return result;
}

Alternatively, you can use function parameters as the persisted objects and simply pass them in. This is typically a closer match to the iterative solution:

Bignum modpow_r(Bignum base, Bignum exponent, Bignum modulus, Bignum result = 1) {
  if (exponent > 0) {
    Bignum next_base = (base * base) % modulus;
    Bignum next_exp = exponent >> 1;
    Bignum next_result = (exponent & 1) == 1 ? (result * base) % modulus : result;

    result = modpow_r(next_base, next_exp, modulus, next_result);
  }

  return result;
}

[Spreegem]

I wasn't getting the answers I'm supposed to, I guess I should have read into the algorithm more. I thought it was supposed to return a^n, but I guess not. So now I found an algorithm that I have tested and does return a^n like I want. However it is not recursive.

I'm trying to do this. http://en.wikipedia.org/wiki/Exponentiation_by_squaring#Computation_by_powers_of_2

Here is the non recursive function.

long sqpower(long a, unsigned long n)
{
	long result = 1;

	while (n > 0) 
	{
	        /* n is odd, bitwise test */ 
	        if (n & 1)
		{
	            result *= a;
	            n -= 1;
	        }
	
	        a *= a;
	        n /= 2;     /* integer division, rounds down */
	}

	return result;
}

Here is my attempt at making it recursive, but it's not working, I always get 1 returned no matter what I put in. Could I get some help with turning the above algorithm into something recursive.

int next_a, next_n;
long resqpower(long a, unsigned long n)
{
    if (n <= 0)
		return 1;
	
	/* n is odd, bitwise test */ 
    if (n & 1)
	{
		next_a = a * a;
		next_n = n - 1;
    }

	next_a = a * a;
    next_n = n / 2;     /* integer division, rounds down */
	
	result = resqpower(next_a, next_n);

    return result;
}

I'm just lost when it comes to taking something that isn't recursive and turning it into something that is. Any good articles on methods or such to do it, any special tricks?

[Narue]

>Any good articles on methods or such to do it, any special tricks?
See my previous post for methods and tricks. Other than that, you need to have a keen understanding of how the algorithm works, you need to know how recursion works, and you need to practice. The key is to do the same steps in the same order. The actual mechanics of that are irrelevant.

[Spreegem]

Well I was able to get this to work by cutting out the modulus bits.

Bignum modpow_r(Bignum base, Bignum exponent, Bignum modulus) {
  if (exponent <= 0)
    return 1;

  Bignum next_base = (base * base) % modulus;
  Bignum next_exp = exponent >> 1;
  Bignum result = modpow_r(next_base, next_exp, modulus);

  if ((exponent & 1) == 1)
    result = (result * base) % modulus;

  return result;
}

I would still like to figure out the other one, but no variation on what I've posted seems to want to work, I'll probably just play with it some more but I just can't figure out what I'm doing wrong with it.

Thanks a bunch for your help.

[Nimmy Chohan]

i need help..i want a algorithm by using transform and conquer. its efficiency and a running program in C++