James Chegwidden

Author

Ranch Hand

Ranch Hand

Posts: 201

posted 11 years ago

Have some problems with my mathematics here. I was reading about algorithmic efficiency and

linear loops and logarithmic loops to determine the number of times a loop iterates

Linear loops f(n) =n

Logarithmic loops f(n) = ceil(logn)

Here are the answers

C:\>java Test

10 1

20 2

40 3

80 4

=============================================

10 1

20 2

40 3

40 30 3

=============================================

15 1

25 2

35 3

35 35 3

=============================================

7 1

=============================================

[/CODE]

Now I cannot get how use the formulas to determine the number of iterations

1. is logarithmic- how did it 4 get calculated mathematically, n is?

2. logarithmic- same here

3 linear looks like (y -x)/10= 3 times

4.linear (y -x)/2- but how do I get one loop iteration (which is what it did)

Help with my mathematic analysis skills appreciated.

linear loops and logarithmic loops to determine the number of times a loop iterates

Linear loops f(n) =n

Logarithmic loops f(n) = ceil(logn)

Here are the answers

C:\>java Test

10 1

20 2

40 3

80 4

=============================================

10 1

20 2

40 3

40 30 3

=============================================

15 1

25 2

35 3

35 35 3

=============================================

7 1

=============================================

[/CODE]

Now I cannot get how use the formulas to determine the number of iterations

1. is logarithmic- how did it 4 get calculated mathematically, n is?

2. logarithmic- same here

3 linear looks like (y -x)/10= 3 times

4.linear (y -x)/2- but how do I get one loop iteration (which is what it did)

Help with my mathematic analysis skills appreciated.

Author and Instructor, my book

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 11 years ago

OK, I haven't actually tried to analyze the code yet because... well... I'm still trying to figure out what the question is. Could you perhaps specify what it is you're trying to understand? With, ummm, sentences? Nouns, verbs, that sort of thing. And your items 1-4 - do those numbers 1-4 correlate with... anything? In particular, what's the intended difference between 1 and 2? We seem to be missing some context here. My telepathy powers are rather limited, unfortunately.

"I'm not back." - Bill Harding, *Twister*

James Chegwidden

Author

Ranch Hand

Ranch Hand

Posts: 201

posted 11 years ago

OK, I was just trying to figure out mathematically- using linear and logarithmic functions to calculate how many times the loop will iterate.

Here were the four loops:

Answer is 4 times-

Answer is 3 times

Answer: 3 times

Answer: 1 time

Now, I can trace the output by hand by computer and verify that the number of time loops go through are correct. Now, I am trying to figure out mathematically. Using for linear loops f(n)= n where n is proportional to the number of iternations. And for log loop (mult and divide) is f(n)= ceil(logn). Do that make more sense?

Here was a site that helped me get started:

loops

JC

Here were the four loops:

Answer is 4 times-

Answer is 3 times

Answer: 3 times

Answer: 1 time

Now, I can trace the output by hand by computer and verify that the number of time loops go through are correct. Now, I am trying to figure out mathematically. Using for linear loops f(n)= n where n is proportional to the number of iternations. And for log loop (mult and divide) is f(n)= ceil(logn). Do that make more sense?

Here was a site that helped me get started:

loops

JC

Author and Instructor, my book

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

James Chegwidden

Author

Ranch Hand

Ranch Hand

Posts: 201

posted 11 years ago

Jim, thanks but two more question. How did you come up with 1 mathematically for the last one?

And, how does the formulas change for > vs. <= other than adding 1..

Lets see if I can give those formulas you saw a try...JC

And, how does the formulas change for > vs. <= other than adding 1..

Lets see if I can give those formulas you saw a try...JC

Author and Instructor, my book

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 11 years ago

Well, given the direction of the inequality, and the way it was being modified, the condition would either always be true, or never. (In case of "always" there would be the prospect of numeric overflow eventually leading to termination, but that's another story.) Given the initial conditions in this case, it's never true. Since it's a do while loop, the minimum possible number of executions is 1.

I also switched from ceil to floor. Though I could well have erred at some point - don't hesitate to tweak those formulas if it looks like something's off.

[ June 04, 2006: Message edited by: Jim Yingst ]

**[JC]: Jim, thanks but two more question. How did you come up with 1 mathematically for the last one?**

Well, given the direction of the inequality, and the way it was being modified, the condition would either always be true, or never. (In case of "always" there would be the prospect of numeric overflow eventually leading to termination, but that's another story.) Given the initial conditions in this case, it's never true. Since it's a do while loop, the minimum possible number of executions is 1.

**[JC]: And, how does the formulas change for > vs. <= other than adding 1..**

I also switched from ceil to floor. Though I could well have erred at some point - don't hesitate to tweak those formulas if it looks like something's off.

[ June 04, 2006: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, *Twister*

James Chegwidden

Author

Ranch Hand

Ranch Hand

Posts: 201

posted 11 years ago

Ok, I see that answer of 1 now.

When you are saying lg with your answer do you mean log or natural log ln. Looks like the log base depends on the number being multiplyed/divide by

JC

When you are saying lg with your answer do you mean log or natural log ln. Looks like the log base depends on the number being multiplyed/divide by

JC

Author and Instructor, my book

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 11 years ago

I was taught to use log for common log, ln for natural log, and lg for base 2; the last is what I meant here. Usually in computer science it ends up not mattering since people typically just want an O(n) calculation anyway, and all logs are of equivalent order, being proportional to each other. But for this question the difference does matter, and base 2 is correct. More generally, you are correct that the formulas would use logs in whatever base you're multiplying or dividing by.

[ June 04, 2006: Message edited by: Jim Yingst ]

[ June 04, 2006: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, *Twister*

James Chegwidden

Author

Ranch Hand

Ranch Hand

Posts: 201

posted 11 years ago

Let my try the log formula on these (Ok it is in C...,but still..)

num = ceil(log b (ceil(y/x))), where b is the base your mult or div by...

Jim, does that formula work for the divide...cant seem to work

for (x = 1000; x >= 2; x /= 2)

printf("%d\n",x);

num = ceil(log2 (ceil(???))---> 9

num = ceil(log b (ceil(y/x))), where b is the base your mult or div by...

Jim, does that formula work for the divide...cant seem to work

for (x = 1000; x >= 2; x /= 2)

printf("%d\n",x);

num = ceil(log2 (ceil(???))---> 9

Author and Instructor, my book

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

James Chegwidden

Author

Ranch Hand

Ranch Hand

Posts: 201

posted 11 years ago

I got it using

num = ceil (log2(1000/2)) = 8.96 - 9 iterations

I think what through me off was what was x & y in this case try to keep the formula

I guess we can be consist either using the floor or the ceiling, but I would not prefer to waver between the two. Same

I will try to come up with a general forms for all forms I could come up with your help and will post tonight..

JC

num = ceil (log2(1000/2)) = 8.96 - 9 iterations

I think what through me off was what was x & y in this case try to keep the formula

I guess we can be consist either using the floor or the ceiling, but I would not prefer to waver between the two. Same

I will try to come up with a general forms for all forms I could come up with your help and will post tonight..

JC

Author and Instructor, my book

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 11 years ago

If you replace 1000 with 512 or 1024 (or any power of the base currently being used), the ceil formula gives incorrect results here.

Then again, it wouldn't surprise me if some of the formulas I gave earlier don't hold up for all inputs. There are often several very similar ways to formulate these things, and without careful testing it's easy to be off by one in some situations.

I had been using floor + 1 vs. ceil to switch between > or <, and >= or <=. However it may be easier to modulate the endpoints instead. E.g. with ints, x < y is equivalent to x <= (y-1). So replacing y with y-1 in a formula may be easier than switching between ceil and floor + 1 or similar things.

Then again, it wouldn't surprise me if some of the formulas I gave earlier don't hold up for all inputs. There are often several very similar ways to formulate these things, and without careful testing it's easy to be off by one in some situations.

I had been using floor + 1 vs. ceil to switch between > or <, and >= or <=. However it may be easier to modulate the endpoints instead. E.g. with ints, x < y is equivalent to x <= (y-1). So replacing y with y-1 in a formula may be easier than switching between ceil and floor + 1 or similar things.

"I'm not back." - Bill Harding, *Twister*

James Chegwidden

Author

Ranch Hand

Ranch Hand

Posts: 201

posted 11 years ago

Well for the log based loops: I will use:

if condition is >= or =< then formula: floor(loga(y/x)) + 1 where a is the multiple or divisor of the value

if > or < then: ceiling (loga (y/x))

Seems to work for me. Any comments..

JC

if condition is >= or =< then formula: floor(loga(y/x)) + 1 where a is the multiple or divisor of the value

if > or < then: ceiling (loga (y/x))

Seems to work for me. Any comments..

JC

Author and Instructor, my book

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 11 years ago

Yup, that seems good. I say that without having tested

*all*possible cases, of course - but it seems to hold up. With the caveat that depending on how the direction of the inequality is set up relative to the increment/decrement/multiply/divide, the answer may also be 0, 1, or "infinite"."I'm not back." - Bill Harding, *Twister*

James Chegwidden

Author

Ranch Hand

Ranch Hand

Posts: 201

posted 11 years ago

Well, I for excuting 0 or 1 time just check before you apply to see if the conditions are false right away (1 with do/while). As for infinite loop you should check if you update (could be missing, wrong, etc.)the condition properly before applying formulas...

Also, it does not take in consideration jump statement like break and continue...which would change the values.

I was trying to get the straight values when you have valid count controlled setups...

JC

Also, it does not take in consideration jump statement like break and continue...which would change the values.

I was trying to get the straight values when you have valid count controlled setups...

JC

Author and Instructor, my book

Consider Paul's rocket mass heater. |