Ways to evaluate loops quickly

This is a discussion on Ways to evaluate loops quickly within the C++ Programming forums, part of the General Programming Boards category; Need some help with a formula: What is the quick formula/way for evaluating no. of times a loop will be ...

  1. #1
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511

    Ways to evaluate loops quickly

    Need some help with a formula:

    What is the quick formula/way for evaluating no. of times a loop will be processed without actually evaluating the loop?

    I was told this:

    (Final - Initial)/Step

    final is final value
    initial is initial value
    step is the increment value

    for <= condition increment final by one

    Example 1

    Code:
    int i= 5;
    while (i <= 10)
    {
       cout << "hi" <<endl;
       i++;
    }
    using formula (11- 5)/1 = 6 times which is correct

    but

    with Example 2
    Code:
       int count = 1;
       int num = 25;
       while (count < 25)
       {
         num = num - 1;
         count++;
       }
       cout <<count << num << endl
    would print 25 and 1.
    Formula (25- 1)/1 =24 times which would make the formula found not work for all cases.

    Do any of you the correct formula for this?

    FYI: Asking here first- will ask fellow math instructors later...

    mrc
    Mr. C: Author and Instructor

  2. #2
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    But it is executed 24 times... Think about it: It is executed once for count=1, once for count=2, etc... up to count=24 at which time, the loop executes, incrementing the variable of count to 25 (which is why it executes no more). The number of times count was incremented was 24 times (1+24=25). Similarly with the other variable.

  3. #3
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    In the second case FINAL should be 24 not 25. Your using < which means the loop will execute with a max value of 24.

  4. #4
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by Mister C
    Need some help with a formula:

    What is the quick formula/way for evaluating no. of times a loop will be processed without actually evaluating the loop?

    I was told this:

    (Final - Initial)/Step

    final is final value
    initial is initial value
    step is the increment value

    for <= condition increment final by one

    Example 1

    Code:
    int i= 5;
    while (i <= 10)
    {
       cout << "hi" <<endl;
       i++;
    }
    using formula (11- 5)/1 = 6 times which is correct

    but

    with Example 2
    Code:
       int count = 1;
       int num = 25;
       while (count < 25)
       {
         num = num - 1;
         count++;
       }
       cout <<count << num << endl
    would print 25 and 1.
    Formula (25- 1)/1 =24 times which would make the formula found not work for all cases.

    Do any of you the correct formula for this?

    FYI: Asking here first- will ask fellow math instructors later...

    mrc

    Two things wrong:

    1. Your formula is wrong.

    2. You plugged the wrong values into the formula.

    Let's forget C programming loops, and look at a couple of cases.

    Suppose initial = 1, final = 6, step = 1

    How many values are used? Count them:

    1, 2, 3, 4, 5, 6

    Number of values = 6

    Now, let initial = 1, final = 5, step = 2

    1, 3, 5

    Number of values = 3

    Now I propose that the formula should be

    ((final - initial)/step) + 1

    Apply the formula to your examples

    First example: initial = 5, final = 10, step = 1

    Number of values = 6

    Second example: initial = 1, final = 24, step = 1

    Number of values = 24.

    See the pattern? A few examples does not prove that the proposed formula is correct. How would you prove it? (Mathematical induction comes to mind.)

    Regards,

    Dave

    Engineer's rule of mathematical induction: If it works for n = 1, and it works for n = 2, it works for all n.

    ---Anonymous, but I think that engineer was one of the casualties when his bridge collapsed at its opening ceremony

  5. #5
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511
    Dave,

    I realize I can use induction proofs. I would have to go back and refresh myself with this.

    I was just trying to see if anyone would know this without me doing the mathematical rigor.

    I also realize this is not a hard one to solve either. (Someone else has allready figured this out)

    jc
    Mr. C: Author and Instructor

  6. #6
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by Mister C
    Dave,

    I realize I can use induction proofs. I would have to go back and refresh myself with this.

    I was just trying to see if anyone would know this without me doing the mathematical rigor.

    I also realize this is not a hard one to solve either. (Someone else has allready figured this out)

    jc
    (I didn't actuallly mean that you should go through a formal proof before using the formula. I wanted to point out that your formula was incorrect. I think you can use enough sample cases to convince youself that the proposed correction is valid, then use it forever.)

    Mathematical induction is rarely useful for discovering formulas, but if an instructor insists on proving a given formula, mathematical induction is a possibility. Not that I would expect any one actually to do this.

    To show a formula is incorrect, you only have to give an example for which the formula gives the wrong answer.

    Regards,

    Dave

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Too many loops D:
    By F5 Tornado in forum C++ Programming
    Replies: 6
    Last Post: 12-03-2007, 12:18 AM
  2. Evaluation of nested loops
    By Mister C in forum C Programming
    Replies: 2
    Last Post: 08-13-2004, 01:47 PM
  3. recoursion or loops?
    By Mecnels in forum C++ Programming
    Replies: 2
    Last Post: 01-14-2002, 11:09 AM
  4. help with arrays and loops
    By jdiazj1 in forum C Programming
    Replies: 4
    Last Post: 11-24-2001, 03:28 PM
  5. exiting loops with ease?
    By KingRuss in forum Game Programming
    Replies: 3
    Last Post: 09-24-2001, 08:46 PM

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