Thread: Interesting little exercise...

Let us examine the following program, where x, y and n are integer variables.


Step 1. Let y:=1.
Step 2. If n>0 go to step 3, otherwise end.
Step 3. If n is an odd number, let y:=y*x and n:=n-1.
Step 4. Let x:=x*x and n:=n/2.
Step 5. Go to step 2.

This i have written in C as follows:

int y, x, n, c;
int main()
{
y = 1;
printf("Enter n: ");
scanf("%d", &n);
printf("Enter x: ");
scanf("%d", &x);
while(n>0)
{
/* c is a counter for the # of multiplication ops */
if(n%2>0) y*=x, ++c, --n;
x*=x, ++c, n/=2;
}
printf("\ny = %d, x = %d, c = %d", y, x, c);
return 0;
}

I'm not very skilled at C, yet. I'm just starting. With this code i get the following answers to these questiosn, i made the program to corroborate the answers i deduced myself.

a) When the program has finished executing, what values do the variables x, y and n have, if the initial value of variable n is 5 and variable x is 3?

y = 243, x = 6561, c = 5

b) How many multiplication operations are performed in the program, if the initial value of variable n is 250 and variable x is 2?

y = 0, x = 0, c = 14
this is obviously wrong, but i can't figure out why i'm getting this.
I didn't calculate the value of y, but i did count the same number of multiplication operations (14).

c) The initial value of variable x is 4. What should the initial value of variable n be, if the value of variable y is 256 when the program has finished executing?

n, i believe, should be 4. If i feed the program that info it gives me this:
y = 256, x = 65536, c = 4

d) The initial value of variable n is 3. What should the initial value of variable x be, if the value of variable y is 216 when the program has finished executing?

I believe x should be 6. If i feed the program that info it gives me this:
y = 216, x = 1296, c = 4

e) Present the value of variable y when the program has finished executing, as a function of the initial values of the variables x and n.

This and question b are the ones i haven't been able to answer. And are the reason i'm making this post.

Oh, by the way, this is not homework, i'm doing this mostly as a brainteaser. I got the problems from this URL:

http://www.joensuu.fi/tkt/teh_eng.htm

adios,
biterman.

/* Steps 2 thru 4. */
> if(n%2>0) y*=x, ++c, --n;
> x*=x, ++c, n/=2;

To get c = 14, i simply inputed n=250 and x=2. If you go thru the steps in your head you can easily count the number of multiplication operations that occur, which is what i did before writting the program.

If i input n=6, x=4 the program returns this:
y = 4096, x = 65536, c = 5

I thought that maybe the program returned x and y as 0, because n was so large a number (250) that x became to big to be held within an int. I tried to make them all floats but it still didn't work, so again i'm baffled. Making them unsigned ints didn't help either.

thanks,
biterman.

y is just x to the nth power.
x is x to the base-2 logarithm of n without the decimal part power.
Shouldn't be too hard to get the multiplications needed.

hth

Though, you must pardon my ignorance. I do not really understand what you mean by:

x is x to the base-2 logarithm of n without the decimal part power.

is it x^log2n (where 2 is the base of log) ??

how would you get the multiplications needed?

thanks,
biterman.

If you look at the code i first posted you'll notice a counter doing exactly that.

When i asked how he (lmov) would get the number of ops that occured, i meant how he (or anyone) would do it with simple math and no programming. I don't know if that's even possible, but what he said gave me the impression that he might know how, so i thought i'd ask.

adios,
biterman.