Thread: logarithmic loop calculations

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    39

    logarithmic loop calculations

    Help with math calc

    Calculating efficiency of loops from both

    Gilberg and Hortsmann books...


    Logarithmic Loops (multiplication and division):



    Where log x (log base x) is the multiple/divisor value

    Note with division we flip n and m in the formulas above.

    Basically I trying to find an all purpose formula- derived from the following..

    A loop where the loop control body is multiplied or divided...

    f(n) = ceil(log2 n) or where N is the iterations...

    what I came up with

    Cases 1 and 2 are applicable to logarithmic loops as well.
    3. Valid Execution:

    Same test as above except:

    for (i = m; i < n; i *= x)
    do something

    o If the condition is < or > the formula is:

    num = ceiling (log x (n / m))

    o If the condition is ≤ or ≥ the formula is:

    num = floor (log x (n / m)) + 1


    Any additional insight for those math inclined with my quest of a general formula..

  2. #2
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    I'm having trouble understanding your problem. Please summarize the problem in one or two sentences while adhering to commonly accepted rules of English grammar.

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  3. #3
    Registered User
    Join Date
    May 2009
    Posts
    39
    Basically I trying to find an all purpose formula- derived from the following..

    A loop where the loop control body is multiplied or divided...

    for (i = m; i < n; i *= x)
    do something

    If the condition is < or > the formula is:

    num = ceiling (log x (n / m))

    If the condition is ≤ or ≥ the formula is:

    num = floor (log x (n / m)) + 1

    Where log x (log base x) is the multiple/divisor value


    Note with division we flip n and m in the formulas above.


    Based upon the following

    f(n) = ceil(log2 n) or where N is the iterations...

    Do the formulas I post look correct- they seem to hold up on paper...

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    The num = are correct, so far as I can tell. I have no idea what you want f(n) to be, so who knows about that.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. nested loop, simple but i'm missing it
    By big_brother in forum C Programming
    Replies: 19
    Last Post: 10-23-2006, 10:21 PM
  2. While loop misbehaving (or misunderstanding)
    By mattAU in forum C Programming
    Replies: 2
    Last Post: 08-28-2006, 02:14 AM
  3. Personal Program that is making me go wtf?
    By Submeg in forum C Programming
    Replies: 20
    Last Post: 06-27-2006, 12:13 AM
  4. while loop help
    By bliznags in forum C Programming
    Replies: 5
    Last Post: 03-20-2005, 12:30 AM
  5. loop issues
    By kristy in forum C Programming
    Replies: 3
    Last Post: 03-05-2005, 09:14 AM