simple programming problem

[Antares]

Hi all,

Can anybody solve this problem without looking at books?
The goal is to write an iterative version of this recursiv algorithm:

Code: Select all

                n=0  : 1
              / 
       n    /           n/2    n/2
      x  = {- - n%2=0: x    * x
            \                  n-1
              \        x    * x

I have found one myself without using books and before i look at relevant books i wanted to know what other ideas could come to mind for solving this.

Writing an iterative version for this is required if you want to calculate modular values of numbers with large bases (1000+ digits) and large exponents (1000+ digits). A recursiv version would make any stack available explode.

This was an assigment of my university ^^ in numerics.

Thanx for your help.

PS:
If someone is interested, i can provide the next parts of the assigment, cause this one was just the first.

[Sarevok]

Using an infinite for or do while loop should solve the problem. I will post the code later if I can solve it.

[Antares]

Thank you for spending your time on this evilcat

[Antares]

C'mon

This is quite simple..
Can nobody else besides evilcat give me a hint how to solve this?

*sad*

[Xon]

Gimme the recursive version(of it implemented in code) and I'll rewrite it into iterative version.

And while your at it, try use MS Paint & draw a better diagram. Cos there is no way I can figure out WTF that equation is.

Or type it out with lots of brackets.

Also modern computer can have up to 1mb of stack for an app by default. Thats a shitload of stack.

[Antares]

Gimme the recursive version(of it implemented in code) and I'll rewrite it into iterative version.

And while your at it, try use MS Paint & draw a better diagram. Cos there is no way I can figure out WTF that equation is.

Or type it out with lots of brackets.

Also modern computer can have up to 1mb of stack for an app by default. Thats a shitload of stack.

ok a description in words then:
Calculating x to the power of n by:
1.Check if n = 0, if yes return 1
2.Check if n % 2 = 0, if yes do x^n/2 * x^n/2
3.Otherwise do x * (x^(n-1))
(a^b means a to the power of b)

I dont think you need code for this cause i never wrote code to solve this problem. I just developed it in my brain and on paper.

And for the stack thing:
Try to calculate the stack for a recursive depth of 100000 steps.
An exponent of 29 would already be (29-28-14-7-6-3-2-1-0) 8 steps, 101 would be (101-100-50-25-24-12-6-3-2-1-0) 11 steps. Now try to to this with a 1000+ digit number. Every recursion step takes a minium of 4 bytes. And cause global variables to solve this is bad style (side effect) you would need at least two pointers to the structures holding the values and one local copy for basic optimisation of the step x^n/2 * x^n/2.

There are also other performance reasons why this algorithm should be rewritten to iterativ. Every recursive call includes codes that can be saved by an iterativ solution.

[Xon]

Ok, so you are trying to calculate x^n, for when n >= 0, and an integer.(Didnt realise that before) That isnt very hard.

The recursive version looks like:

Code: Select all

double pow(double x, int n)
{
if (n == 0)
  return 1;
else if ((n %2) == 0)
  return pow( x,  n/2) * pow( x^ n/2 );
else
  return x * pow(x, n-1 );
}

The iterative version:

Code: Select all

double pow(double x, int n)
{
if (n == 0)
  return 1.0;
double res = x;
for ( ; n > 0; --n)
  res = res * x;
return res;
}

Not very fast for large values of 'n' (there are much much faster versions), but it should do.

Also C/C++ cant actually store floatpoint numbers can go to a max of ~10^350.

[Mad]

I assume you want to keep all three cases as an optimization? This should work... No books used.

Code: Select all

double pow_i(double x, int n)
{
    double answer;
    int i;
    if(n == 0) return 1;
    answer = x;
    for(i=1; 2*i <= n; i*=2)
        answer *= answer;
    for( ; i < n; ++i)
        answer *=x;
    return answer;
}

[Antares]

First of thanx to all that wasted their time for this

Ok, so you are trying to calculate x^n, for when n >= 0, and an integer.(Didnt realise that before) That isnt very hard.

The recursive version looks like:

Code: Select all

double pow(double x, int n)
{
if (n == 0)
  return 1;
else if ((n %2) == 0)
  return pow( x,  n/2) * pow( x^ n/2 );
else
  return x * pow(x, n-1 );
}

Very good , even if this algorithm isnt maximal optimized.
I already gave several hints what and where this algorithm could be improved.

Code: Select all

	return pow( x,  n/2) * pow( x^ n/2 );

instead of calculating pow( x, n/2) twice do the following:

Code: Select all

	tmp = pow( x,  n/2);
	return tmp * tmp;

The iterative version:

Code: Select all

double pow(double x, int n)
{
if (n == 0)
  return 1.0;
double res = x;
for ( ; n > 0; --n)
  res = res * x;
return res;
}

Not very fast for large values of 'n' (there are much much faster versions), but it should do.

Also C/C++ cant actually store floatpoint numbers can go to a max of ~10^350.

Right. This one would work but it isnt exactly what the assigment was.
The recursiv version got a complexity of O(lb(n)) with n as the exponent.
Your iterativ version got a complexity of O(n) which is way worse than O(lb(n)).
Thus you wrote used a algorithm, that solves the problem but isnt efficient.
O(n) means it takes n steps to solve the problem thus n=16 means 16 steps. O(lb(n)) means it takes the logarithm of n to the base of 2 steps tp solve the problem. for n=16 this would mean 4 steps. for n=32768 this would mean 15 steps instead of 32768 for O(n). lb is an abbreviation for binary logarithm.

I assume you want to keep all three cases as an optimization? This should work... No books used.

Code: Select all

double pow_i(double x, int n)
{
    double answer;
    int i;
    if(n == 0) return 1;
    answer = x;
    for(i=1; 2*i <= n; i*=2)
        answer *= answer;
    for( ; i < n; ++i)
        answer *=x;
    return answer;
}

Same for this algorithm. Complexity of O(n).

Both codes also lack the ability to deal with 1000+ exponents
cause you developed them by using a real programming language with all its limits.

Thats why i developed my version on paper first. This one is it in pseudo code:

Code: Select all

FUN pow(base, exponent, result) 
	BEGIN
		bitposition = most significant bit of exponent; 
		result = 1;
		WHILE (bitposition of exponent>0) DO
			result *= result;
			IF (bit at bitposition is set)  THEN
				result *= base;			
			FI
			bitposition >>= 1;
		OD
	END

As i said this code is needed for a later version of of calculating modular versions of large bases and large exponents.
Modular values are only usefull for integer values. Thus using floating point data taypes is not recommended.

After re-reading i realized, that i forgot to mention that the result has to be exact even if you have to calculate a number with 1000+ digits as base and 1000+ digits as exponent. Since i havent mentioned it i cannot blame you.

The following is the final version of the implemented function:

Code: Select all

/************************************************************
Name
			powMod
Arguments:		
			n		Exponent of Base this (this = x in the following)
			k		Modulo-Value
Returns:	
			   n
			(x)  mod k
************************************************************/

BigInteger& BigInteger::powMod(BigInteger& n, BigInteger& k) {
	BigInteger* retval = new BigInteger;
	ELEMENT elempos = n.size-1;
	ELEMENT bitpos = MOSTSIGBIT;	

	while((n.value[elempos] & bitpos) != bitpos) {
		bitpos >>= 1;
	}

	(*retval) = 1;
	while (elempos != 0xFFFFFFFF) {
		(*retval) = retval->square() % k;
		if((n.value[elempos] & bitpos) == bitpos) {
			(*retval) = ((*retval) * (*this)) % k;
		}
		bitpos >>= 1;
		if(bitpos == 0) {
			bitpos = MOSTSIGBIT;
			elempos--;
		}
	}

	return retval->setTmp();
}

Today i looked the algorithm up in a book by Donald Knuth and another by Micheal Weslchenbach and realized that my algorithm is the same they propose

Ok...
After this one is solved is somebody interested in the rest of the assignment?

[Mad]

Same for this algorithm. Complexity of O(n).

Oops, I underestimated how much the difference would've been between going forwards and backwards. This solution has the same complexity as the recursive version:

Code: Select all

double pow_i(double x, int n)
{
  double answer;
  stack<bool> ops;

  if(n == 0) return 1;
  while(n > 1)
  {
    if((n%2)==0)
    {
      ops.push(true);
      n /= 2;
    }
    else
    {
      ops.push(false);
      --n;
    }
  }
  answer = x;
  while(!ops.empty())
  {
    if(ops.top())
      answer *= answer;
    else
      answer *= x;
    ops.pop();
  }
  return answer;
}

With my first try, I thought I found a way around the stack, but it didn't cut down on the complexity from O(n) the way I hoped. This version won't run into the issues of the runtime stack running out the way a recursive version can, but it will have the same problems with handling large numbers as any other standard C++ code will (requires STL stack).

[Antares]

Nice stuff mad

You have understood the main problem. The resucriv version of the algorithm builds up a plan, that is stored in the exponents and is executing this plan by running through the recursiv strucute after build up.

You solved this plan with a stack. Even if your version has to employ 2 loops it has solved the main problem.


This was also my first version but i wanted to get the two loops out of it