Interesting little exercise...

This is a discussion on Interesting little exercise... within the C Programming forums, part of the General Programming Boards category; Let us examine the following program, where x, y and n are integer variables. Step 1. Let y:=1. Step 2. ...

  1. #1
    free(me);
    Join Date
    Oct 2001
    Location
    Santo Domingo, DN, Dominican Republic
    Posts
    98

    Lightbulb 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.
    Do you know how contemptous they are of you?

  2. #2
    the Corvetter
    Join Date
    Sep 2001
    Posts
    1,584
    > 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. #3
    Unregistered
    Guest

    Angry Shutup

    Shuit up

  4. #4
    the Corvetter
    Join Date
    Sep 2001
    Posts
    1,584
    What??? Did I do something?

  5. #5
    Unregistered
    Guest
    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. #6
    the Corvetter
    Join Date
    Sep 2001
    Posts
    1,584
    > 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. #7
    Unregistered
    Guest
    >> 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. #8
    the Corvetter
    Join Date
    Sep 2001
    Posts
    1,584
    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. #9
    Unregistered
    Guest
    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. #10
    free(me);
    Join Date
    Oct 2001
    Location
    Santo Domingo, DN, Dominican Republic
    Posts
    98

    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.
    Do you know how contemptous they are of you?

  11. #11
    Registered User
    Join Date
    Aug 2001
    Posts
    101
    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
    - lmov

  12. #12
    free(me);
    Join Date
    Oct 2001
    Location
    Santo Domingo, DN, Dominican Republic
    Posts
    98

    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.
    Do you know how contemptous they are of you?

  13. #13
    Unregistered
    Guest
    > how would you get the multiplications needed?

    Add a counter to your loop. Whenever a multiplication occurs,
    add a counter incrementation after it.

    Quzah.

  14. #14
    free(me);
    Join Date
    Oct 2001
    Location
    Santo Domingo, DN, Dominican Republic
    Posts
    98

    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.

    adios,
    biterman.
    Do you know how contemptous they are of you?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Line of data input method
    By larry_2k4 in forum C Programming
    Replies: 2
    Last Post: 04-28-2009, 11:34 PM
  2. A few interesting tools...
    By Mad_guy in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 03-10-2009, 06:07 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21