1. ## 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

biterman.

2. > 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 is just a matter of strategically placed conditional statements and math.

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

In this part of the code, I'm not sure what you want to do, but this code is right. Just to see how the problem is being caused, give me an instance like x = 4 and n = 6 and then tell me what c is equal to. Them I can work it through my head. I need to know what you placed in there to get c = 14.

3. ## Shutup

Shuit up

4. What??? Did I do something?

5. No, you didn't do anything wrong. There are just some people on message boards who have nothing better to do than to be obnoxious.

> 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.
Code:
```int y=1,n,x;

n=
x=

while( n > 0 )
{
if( n%2 == 1 )
{
y*=x;
n--;
}
x*=x;
n/=2;
}```
Should work.

Quzah.

6. > No, you didn't do anything wrong.
I didn't say he did anything wrong. Where did you come up with that? I just wanted to know what kind of output there was. Then, maybe, I could have figured it out.

> There are just some people on message boards who have nothing better to do than to be obnoxious.
You know, there really is no need for that. What are you here for? To critisize people that are trying to help. I mean, listen to yourself.

7. >> No, you didn't do anything wrong.
> I didn't say he did anything wrong. Where did you come up
> with that? I just wanted to know what kind of output there
> was. Then, maybe, I could have figured it out.

Who did I reply to? Why, if you look, you'll see I replied to _YOU_.

>> There are just some people on message boards who have
>> nothing better to do than to be obnoxious.
> You know, there really is no need for that. What are you here
> for? To critisize people that are trying to help. I mean, listen to
> yourself.

I think you need to calm down, Beavis. I was replying TO YOU
because YOU said "What? Did I do something wrong?". To which
I replied "No, you did not do anything wrong!" See? I was sticking
up for you. Calm down.

I was saying, the person that told you to shut up was one of
those people who juts likes to jump on people. Sheesh. Someone
is paranoid.

Quzah.

8. Sorry, Quzah. I'm so sorry. I feel like a real jerk. Did I ever tell me you're my favorite unregistered guy? You really should register. It is a great site. You seem to know your programming, too.

--Garfield

9. I have registered. I just can't remember what email I registered with, so I can't have it email me my password. :P

Quzah.

10. ## hmm...

/* 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.

11. 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

12. ## Thank you...

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.

13. > how would you get the multiplications needed?

add a counter incrementation after it.

Quzah.

14. ## I did that...

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.