• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Java loops- linear/log time- calculation

 
Author
Posts: 201
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
James Chegwidden
Author
Posts: 201
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 201
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
[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
Posts: 201
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 201
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
[B][JC]:
[/B]
It looks like this is covered by

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

or in Java
 
James Chegwidden
Author
Posts: 201
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 201
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 201
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
If you want to look young and thin, hang around old, fat people. Or this tiny ad:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic