PDA

View Full Version : logarithmic loop calculations



ninety3gd
06-01-2009, 01:53 PM
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..

Snafuist
06-01-2009, 02:03 PM
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

ninety3gd
06-01-2009, 02:09 PM
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...

tabstop
06-01-2009, 03:04 PM
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.