aspose file tools*
The moose likes Java in General and the fly likes Java loops- linear/log time- calculation Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Java loops- linear/log time- calculation" Watch "Java loops- linear/log time- calculation" New topic
Author

Java loops- linear/log time- calculation

James Chegwidden
Author
Ranch Hand

Joined: Oct 06, 2002
Posts: 201
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.


Author and Instructor, my book
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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

Joined: Oct 06, 2002
Posts: 201
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
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
OK, thanks for clarifying. Let's see, here's what it looks like to me:

Looks like n = max(1, ceil(lg(y/x)))

n = floor(lg(y/x)) + 1

n = ceil((y-x)/10)

n = 1
James Chegwidden
Author
Ranch Hand

Joined: Oct 06, 2002
Posts: 201
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
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
[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 ]
James Chegwidden
Author
Ranch Hand

Joined: Oct 06, 2002
Posts: 201
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
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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 ]
James Chegwidden
Author
Ranch Hand

Joined: Oct 06, 2002
Posts: 201
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
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
[B][JC]:
[/B]
It looks like this is covered by

num = 1 + floor(log2(1000/2))

or in Java
James Chegwidden
Author
Ranch Hand

Joined: Oct 06, 2002
Posts: 201
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
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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.
James Chegwidden
Author
Ranch Hand

Joined: Oct 06, 2002
Posts: 201
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
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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".
James Chegwidden
Author
Ranch Hand

Joined: Oct 06, 2002
Posts: 201
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
 
 
subject: Java loops- linear/log time- calculation