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

posted

0

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?

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

posted

0

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

posted

0

[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

posted

0

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

posted

0

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

posted

0

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

posted

0

[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

posted

0

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

posted

0

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

posted

0

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

posted

0

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

posted

0

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...