"table of powers" problem

[Camellia]

hi all,

I wrote a "table of powers" program and made the 5th power the highest,
but when I tried to run the program I found a problem. Here's the
output:


Integer Square power 3rd power 4th power 5th
------- ------ --------- --------- ---------
1 1 1 1 1
2 4 16 256 65536
3 9 81 6561 43046721
4 16 256 65536 0
5 25 625 390625 -2030932031
6 36 1296 1679616 -683606016
7 49 2401 5764801 -1526366847
8 64 4096 16777216 0
9 81 6561 43046721 -501334399
10 100 10000 100000000 1874919424


and the code:
<code>
#include <stdio.h>
#define MAX 10

int power(int, int);

int main(void)
{
long int original = 1, p2, p3, p4, p5;
int i;

printf("%7s%15s%15s%15s%15s\n%7s%15s%15s%15s%15s\n",
"Integer", "Square", "power 3rd", "power 4th", "power
5th",
"-------", "------", "---------", "---------",
"---------");
for (i = 1; i <= MAX; ++i) {
original = i;
p2 = power(original, 2);
p3 = power(original, 3);
p4 = power(original, 4);
p5 = power(original, 5);
printf("%7d%15d%15d%15d%15d\n",
original, p2, p3, p4, p5);
}
}

int power(int a, int power)
{
int i;
for (i = 1; i < power; ++i)
a = a*a;
return a;
}
</code>


Why does the "5th power" not work properly? Is the problem with the
"int" declaration?

Any suggestions are appreciated.

 

[Walter Roberson]

I wrote a "table of powers" program and made the 5th power the highest,
but when I tried to run the program I found a problem.

Integer Square power 3rd power 4th power 5th
------- ------ --------- --------- ---------
1 1 1 1 1
2 4 16 256 65536
3 9 81 6561 43046721
4 16 256 65536 0

You are worried about 5th powers when you should be worrying about
lower powers! 2 to the third power is not 16. 2 to the fourth
power is not 256. 3 to the third power is not 81, and so on.

Hint: your code takes the square of the current value at each step,
instead of multiplying by the input value.

 

[Richard Bos]

I wrote a "table of powers" program and made the 5th power the highest,
but when I tried to run the program I found a problem. Here's the
output:

Integer Square power 3rd power 4th power 5th
------- ------ --------- --------- ---------

9 81 6561 43046721 -501334399
10 100 10000 100000000 1874919424

There are several problems with your code.

int main(void)
{
long int original = 1, p2, p3, p4, p5;
int i;

for (i = 1; i <= MAX; ++i) {
original = i;
p2 = power(original, 2);
p3 = power(original, 3);
p4 = power(original, 4);
p5 = power(original, 5);
printf("%7d%15d%15d%15d%15d\n",
original, p2, p3, p4, p5);
}
}

int power(int a, int power)
{
int i;
for (i = 1; i < power; ++i)
a = a*a;
return a;
}

Why does the "5th power" not work properly? Is the problem with the
"int" declaration?

First of all, yes, the int declaration is a problem. You're overflowing
the int. Declaring power() to return an unsigned long might solve that,
but if your ints happen to be as long as your longs, you're just stuck
unless you go to C99 long longs.
A related problem is that assigning ints back and forth to longs, when
you could just be using longs all the time, is asking for trouble. You
could get rid of your "original" long, and make i a long (preferably
unsigned, and the same for the rest) in the first place.
And a third problem related to _that_ is that you're printf()ing longs
using the specifier for (non-long) ints. Use "%ld" instead.

The most glaring, fundamental bug in your program, however, and one that
is not going to be solved by simply switching integer types, is that
power(a, power) (and btw, it's legal but suboptimally clear to have the
same name for a function and its parameter; better use another name for
the power param) does not actually compute the power'th power of a...

Richard

 

[CBFalconer]

I wrote a "table of powers" program and made the 5th power the
highest, but when I tried to run the program I found a problem.
Here's the output:

Integer Square power 3rd power 4th power 5th
------- ------ --------- --------- ---------
1 1 1 1 1
2 4 16 256 65536
3 9 81 6561 43046721
4 16 256 65536 0
5 25 625 390625 -2030932031
6 36 1296 1679616 -683606016
7 49 2401 5764801 -1526366847
8 64 4096 16777216 0
9 81 6561 43046721 -501334399
10 100 10000 100000000 1874919424

You are running into integer overflow, which results in undefined
behaviour. See the values in <limits.h>. Besides, your values are
wrong, 3 to the 3rd is 27, for example.

 

[Camellia]

Walter Roberson wrote:

You are worried about 5th powers when you should be worrying about
lower powers! 2 to the third power is not 16. 2 to the fourth
power is not 256. 3 to the third power is not 81, and so on.

Oh I see, silly me, I should make it:

int power(int a, int power)
{
int i, tmp;
tmp = a;
for (i = 1; i < power; ++i)
a = a*tmp;
return a;
}

Thank you very much for help

 

[Camellia]

A related problem is that assigning ints back and forth to longs, when
you could just be using longs all the time, is asking for trouble. You
could get rid of your "original" long, and make i a long (preferably
unsigned, and the same for the rest) in the first place.
And a third problem related to _that_ is that you're printf()ing longs
using the specifier for (non-long) ints. Use "%ld" instead.

The most glaring, fundamental bug in your program, however, and one that
is not going to be solved by simply switching integer types, is that
power(a, power) (and btw, it's legal but suboptimally clear to have the
same name for a function and its parameter; better use another name for
the power param) does not actually compute the power'th power of a...

Thank you I've learned a lot from your post
If I made the power() correct in the first place I wouldn't have so
many humble questions, sorry about that.

 

[arturosevilla]

hi all,

I wrote a "table of powers" program and made the 5th power the highest,
but when I tried to run the program I found a problem. Here's the
output:


Integer Square power 3rd power 4th power 5th
------- ------ --------- --------- ---------
1 1 1 1 1
2 4 16 256 65536
3 9 81 6561 43046721
4 16 256 65536 0
5 25 625 390625 -2030932031
6 36 1296 1679616 -683606016
7 49 2401 5764801 -1526366847
8 64 4096 16777216 0
9 81 6561 43046721 -501334399
10 100 10000 100000000 1874919424


and the code:
<code>
#include <stdio.h>
#define MAX 10

int power(int, int);

int main(void)
{
long int original = 1, p2, p3, p4, p5;
int i;

printf("%7s%15s%15s%15s%15s\n%7s%15s%15s%15s%15s\n",
"Integer", "Square", "power 3rd", "power 4th", "power
5th",
"-------", "------", "---------", "---------",
"---------");
for (i = 1; i <= MAX; ++i) {
original = i;
p2 = power(original, 2);
p3 = power(original, 3);
p4 = power(original, 4);
p5 = power(original, 5);

Though the cast from long int to int may cause a loss of precision
(specially with the problem you are handling here), it is not illegal.
However due to the fact that sizeof(int) <= sizeof(long int) you are
surely misusing the long int type by handling your program in this way.

printf("%7d%15d%15d%15d%15d\n",
original, p2, p3, p4, p5);

You are printing long int's with the %d format that is specified only
for int's. Use %ld instead. Remember that printf has no notion of the
types of the arguments you are passing to it.

}
}

int power(int a, int power)
{
int i;
for (i = 1; i < power; ++i)
a = a*a;
return a;
}

I don't think this is really a _power_ function... Follow the advices
already posted. However you should have this function (and its
prototype) changed to return long int and that the paramater `a' be
also a long int.

</code>


Why does the "5th power" not work properly? Is the problem with the
"int" declaration?

The problem you are having is due to an integer overflow, which is
undefined by the standard. If you are not using negative integers you
could use unsigned data types and then check if once the operation is
applied the value is consistent with your last result. This can work as
unsigned integers do not "overflow" because they follow a 2^n modulus
arithmetic. The following should explain better modulus arithmetic:

#include <stdio.h>
#include <limits.h>

int main(void)
{
/* This is like doing (UINT_MAX + 2) % (UINT_MAX + 1)
UINT_MAX + 1 = 2^n where n is implementation defined */
unsigned int x = UINT_MAX + 2;
printf("%u\n", x); /* It prints 1 to stdout */
return 0;
}


However if you really want more precision on these operations you
should look at the C99 `long long int' integer type, but remember that
they can also be overflowed as the `int' and `long int' types.

 

[Richard Heathfield]

Camellia said:

Walter Roberson wrote:


Oh I see, silly me, I should make it:

int power(int a, int power)
{
int i, tmp;
tmp = a;
for (i = 1; i < power; ++i)
a = a*tmp;
return a;
}

I'd make it this:

/* ipower: raises y to the power x, but is limited by
* the range of ints, so beware overflow. Later,
* when we know about unsigned types, we'll use
* them to increase the range of our power function.
* If x is INT_MIN, the behaviour of this function
* is undefined. Otherwise, if x is negative, this
* function will return 0. Otherwise, it will return
* y to the power x provided it doesn't overflow.
* All in all, it's so easy for this to go wrong that
* you'd be better off using pow()! But it's nice to
* see how these things work, isn't it?
*/
int ipower(int y, int x)
{
int result = (x >= 0); /* 1 if x>=0, 0 otherwise, guaranteed */

while(x-- > 0)
{
result *= y;
}
return result;
}

Future developments:

1) write a version that uses unsigned types (easy)
2) write a version that runs in O(log x) rather than O(x) (moderate)
3) write a version that will provide complete accuracy even where the result
is thousands of digits long (hard)