The Frog Leap target constant

[skypi]

The Frog Leap target constant

assuming a frog can only leap half its last leap to a target and its first leap is halfway to its target what is the target distance that a frog will never get to? (LOL/NO-LOL)

target distance 2.2 units frog gets there in 53 hops

target distance 2.3 units, python float runs out of precision calulating the next leap at about leap 1000 (LOL)

an interesting learning/educational algorithmn that gives some insight into machine implementation (use the decimal type in python eh?)

Code: Select all

#SkyPi.org
import time
target=2.3
nextleap=target/2
distancetravelled=0
count=0
while  distancetravelled < target :
  count+=1
  distancetravelled += nextleap 
  nextleap = nextleap/2
  print (count,distancetravelled,nextleap)
  time.sleep(0.02)

[W. H. Heydt]

If you start with a large room with a line of women along one wall and line of men along the opposite wall and at given, periodic, signal each line moves to halve the distance between the lines, a mathematician will tell you that the two lines will never meet. An engineer will tell you that in a very small number of moves, the two lines will be close enough for ALL practical purposes.

[skypi]

yeah That's a good learning/educational example as well eh!

of course it depends on the part tolerance!!!

and I am not sure there is not this frog leap constant where target < dconst where contact can be made anyway?

[W. H. Heydt]

yeah That's a good learning/educational example as well eh!

of course it depends on the part tolerance!!!

and I am not sure there is not this frog leap constant where target < dconst where contact can be made anyway?

It's an example of the difference between mathematicians and engineers. You can lump physicists in with the mathematicians. In one course we were told to measure an unknown resistor using a Wheatstone Bridge. We were to measure the unknown to 3 places. The physicists all nodded and went to work. The engineers looked at the bridge, noted that it was made from 20% tolerance (then the common standard) resistors--as was the "unknown" (it had standard markings)--and went, "What? Three places is meaningless. Even one place is highly suspect!"

[Heater]

W. H. Heydt,

You can lump physicists in with the mathematicians.

I have met a few mathematicians and physicists that would strongly disagree with that.

Your physicists might have had the right approach, provided they calibrated those 20% resistors first.

Back in the day we would get marked down if we did not include an error analysis in our physics experiment write ups and a bound on the accuracy of our results.

Personally, after much reflection, I have concluded that mathematics is a branch of physics.

[skypi]

The false positives I was getting were also a result of precision errors, it is a theory that holds true whatever the target distance, given that a frog could even hop that accurately LOL

reworking with decimal type

Code: Select all

#skypi.org
import time
from decimal import *
getcontext().prec = 500
target=Decimal(1)
nextleap=target/Decimal(2)
print( type(nextleap))
distancetravelled=Decimal(0)
count=0
while  distancetravelled < target :
  count+=1
  distancetravelled += nextleap 
  nextleap = nextleap/2
  print (count,distancetravelled,nextleap)
  time.sleep(0.02)

[PeterO]

If you had chosen an initial spacing that had an exact (and short) representation in binary then rounding errors would not have been a problem as next leap would have been held exactly. The limit then becomes when the difference in the binary exponents becomes so large that the addition of the smaller number looses precision as some bits are lost off the least significant end of the mantissa.

Using a loop step size of 1/2,1/4,1/8,1/16,1/32,1/64,1/128 is better than using 1/10,1/100/,1/1000 etc

PeterO.

[hippy]

The Frog Leap target constant

assuming a frog can only leap half its last leap to a target and its first leap is halfway to its target what is the target distance that a frog will never get to? (LOL/NO-LOL)

target distance 2.2 units frog gets there in 53 hops

Hmm. I figured it would never get there, the furthest it can jump is just under 2 full leaps.

If one ignores its first full leap and calls its second leap a binary 0.1 which represents half a full leap, the third quarter leap being 0.01, the fourth eighth leap 0.001, we can see the furthest it can jump is, one, plus a half, plus a quarter etc leaps; 1+0.111111111111...

And that's less than 2 full leaps.

If each full leap is 1.1 units, it can only leap less than 2 x 1.1, and will never reach 2.2

And your Frog Constant would be something like 2-(1/∞)

Or maybe I've gone wrong somewhere.

[PeterO]

The Frog Leap target constant

assuming a frog can only leap half its last leap to a target and its first leap is halfway to its target what is the target distance that a frog will never get to? (LOL/NO-LOL)

target distance 2.2 units frog gets there in 53 hops

Hmm. I figured it would never get there, the furthest it can jump is just under 2 full leaps.

If one ignores its first full leap and calls its second leap a binary 0.1 which represents half a full leap, the third quarter leap being 0.01, the fourth eighth leap 0.001, we can see the furthest it can jump is, one, plus a half, plus a quarter etc leaps; 1+0.111111111111...

And that's less than 2 full leaps.

If each full leap is 1.1 units, it can only leap less than 2 x 1.1, and will never reach 2.2

And your Frog Constant would be something like 2-(1/∞)

Or maybe I've gone wrong somewhere.

"its first leap is halfway to its target " is the important thing. It rescales the whole problem to make the total target distance 1.0. The actual distance (2.2 or 2.3) is irrelevant. Otherwise your analysis that distance jumped after N jumps is 1 - 2^-N is correct.

PeterO

[W. H. Heydt]

The Frog Leap target constant

assuming a frog can only leap half its last leap to a target and its first leap is halfway to its target what is the target distance that a frog will never get to? (LOL/NO-LOL)

target distance 2.2 units frog gets there in 53 hops

Hmm. I figured it would never get there, the furthest it can jump is just under 2 full leaps.

If one ignores its first full leap and calls its second leap a binary 0.1 which represents half a full leap, the third quarter leap being 0.01, the fourth eighth leap 0.001, we can see the furthest it can jump is, one, plus a half, plus a quarter etc leaps; 1+0.111111111111...

And that's less than 2 full leaps.

If each full leap is 1.1 units, it can only leap less than 2 x 1.1, and will never reach 2.2

And your Frog Constant would be something like 2-(1/∞)

Or maybe I've gone wrong somewhere.

The whole thing is just a variant on "Achilles and the Hare" that goes back quite a ways.

[Heater]

hippy,

Hmm. I figured it would never get there, the furthest it can jump is just under 2 full leaps....

...Or maybe I've gone wrong somewhere.

It might surprise you but in decimal 0.999..., recurring forever, is actually equal to 1.0.
For proof see here: https://en.wikipedia.org/wiki/0.999...

Similarly in binary 0.111..., recurring forever is actually equal to 1.0.

Whatever, our frog makes a jump half the size of the previous one each time. So what we have is the infinite sum:

1/2 + 1/4 + 1/8 + 1/16 + ...

Which as we see above is equal to 1.0. Or for a proof see wikipedia again: https://en.wikipedia.org/wiki/1/2_%2B_1 ... _%E2%8B%AF

So our or frog will always make any target in an infinite number of steps. (Targets other than 1.0 are just a mater of scaling which has no effect on the argument).

All this is generally known as Zeno's paradox. Don't they teach this stuff in school anymore?

There are two possibilities then for the algorithm given on any finite machine:

1) It will loop forever and never arrive at the correct result.

2) It will bail out early with the wrong result. Either not quite reaching the target or still having a finite jump size it has not done.

[hippy]

All this is generally known as Zeno's paradox. Don't they teach this stuff in school anymore?

No idea what they teach now and I have an incomplete recollection of everything I was taught decades ago but I am sure I would have refused to accept that 'anything which has a little bit taken away is the same as the original' back then as much as now.

If someone told me that then I'd probably listen to the theory, note that if it were true - that if the smallest slither removed didn't reduce the original - nor would any finite number of smallest slithers removed.

I'd take their lunch, remove and eat a finite number of smallest slithers, then hand it back for them to enjoy. Leaving them to convince me that they still had the lunch to eat which I had already eaten

[Burngate]

People seem hung up on 2 - dividing the remaining distance by that for the next jump - but it should work with any number. It might take a bit longer to reach the target, but it'll take the same number of jumps - my keyboard hasn't got a key for Aleph null, which is irritating.

But if we chose an irrational number - π or e - it might take a bit longer.

[skypi]

All this is generally known as Zeno's paradox. Don't they teach this stuff in school anymore?

There are two possibilities then for the algorithm given on any finite machine:

1) It will loop forever and never arrive at the correct result.

2) It will bail out early with the wrong result. Either not quite reaching the target or still having a finite jump size it has not done.

I had come to the conclusion that this is quite possibly a problem that cannot be proved by a computer LOL

(I mean apart from the fact it would have to run for ever to prove it could not be solved LOL)

though in the process discovered python maxint is now infinite!

and... it does prove the engineering approach as explained by W. H. Heydt in reply 1 is what it is!

the constant is the tolerance of the part/machine/program

[skypi]

kind of related to the mythology surrounding the "towers of hanoi" game, in that supposedly when the monks had completed the problem (which involved puzzling out the solution and then doing the actual moves) the world would end... but they could only move one perforated-cylinder per quite long time unit, LOL

[Heater]

Deleted gibbersih.

[Heater]

In what way related? Apart from being old maths problems with catchy names. One is dealing with an infinite sum, the other can be computed in finite time.

...but they could only move one perforated-cylinder per quite long time unit, LOL

You missed the point of the towers story. Those monks don't need to be moving disks very slowly for it to take an incredibly long time to complete the problem.

The time taken to solve the Towers of Hanoi is proportional to 2 to the power n, where n is the number of disks to move (assuming each move takes constant time). https://www.geeksforgeeks.org/time-comp ... recursion/

So even if those monks were moving one disk per second it would take them the current age of the universe to finish if they had a tower only 59 disks high.

The original problem as stated by Lucas involved 64 disks. So that would be 2^64 moves. 16 times the age of the universe for our monks at one move per second.

---------------------------------------------------------------------

Age of the universe is about 13.8 billion years = 4.3e17 seconds.

Time to move 59 disks = 5.7e17 seconds.

Somebody like to check my arithmetic here?

[skypi]

yeah, but 1 second is a very long unit of time in computer terms... the 64 disk stack could be solved by fastest computer a lot quicker than 1 nanosecond per move. And for educational purposes it is a nice recursive solution. Mind you no solution that you can make parrallel LOL!

As for the frog (or two lines of people) my summary would be, if a move must be taken each time, there comes a time where the minimum move possible by an object (frog or person or whatever) exceeds the theoretical desired distance to travel and the object must overshoot/collide with the target object with the next move.

[Heater]

skypi,

1 second is a very long unit of time in computer terms... the 64 disk stack could be solved by fastest computer a lot quicker than 1 nanosecond per move.

Something tells me you are not really feeling the size of the problem in your gut.

Certainly we could kick out all the monks, shut down the monastery and get a computer to go though the motions of the Towers of Hanoi instead. A typical computer today might manage one move per nano second. That's pretty quick right?

Not really, it's a billion times faster than our monks were, it will get the job done in 200 years or so rather than 16 times the age of the universe as I calculated before.

But, all I have to do is make the problem a little bit harder, just double the height of the stack of disks from 64 to 128.

Boom, our new improved computer solution is not going to end until 16 times the age of the universe!

That is the depressing realization with these kind of problems. No matter how fast your machine is it soon gets bogged down if the problem is made just a little bit bigger.

That of course is why the crypto algorithms we use work. There just isn't the compute power available. When it looks like there might be as computers get faster what do we do? We double the size of the keys. Safe again.

As for the frog (or two lines of people) my summary would be, if a move must be taken each time, there comes a time where the minimum move possible by an object (frog or person or whatever) exceeds the theoretical desired distance to travel and the object must overshoot/collide with the target object with the next move.

Mathematicians might not worry about "the minimum move possible". Why would they? Whatever small thing you have you can always have a smaller one. That is how we think about real numbers.

Physicists on the other hand will worry about it. They will point out that quantum mechanics tells us that when things get really small we cannot know where a thing is. We won't know if the frog crossed the line or not, we won't be really sure where the line is.

Worse still, if you really try to measure down to really small distances, around about the Plank Length, 1.6 x 10-35 m, then the energy we have to put in is so huge that the whole experiment will collapse into a black hole.

Where is our frog now?

[skypi]

actually it just dawned on me that the recursive solution to 64 disk towers of hanoi is probably doomed to fail!... stack overflow!

but what I mean is for an object to observe things of a different scale or be capable of movement in a different scale it needs to be of a different scale....

the exercise here is observing it fail.... or how fast it can be done...

the regular particles that pass through the human body and do or do not hit anything relative to their size vs the gap between particles..... (why lead is one of best at blocking radiation, it is dense)

as an interesting aside, reading about specs of exascale computers, Japs working on an arm8 based one that will consume less than 30 megawatts! 30 MEGAWATTS to run a human brain simulation! That's a large power station! (and credit to them for observing that limiting factor)

Question I have is are the exaflops actually linear exaflops or only there if you can suitably parallelize the problem.... I reckon not linear exaflops.... (hopefully more than 200 years left until the monks that bought a supercomputer get the task that was set them solved )

[davidcoton]

the whole experiment will collapse into a black hole.

Where is our frog now?

It wasn't a frog in the first place. It was a toad.
Toad in the (Black) Hole.

[Andyroo]

Just fill a bath with milk and add the frog and all that leaping will give you a lifetime of cream

Neat puzzle though, it reminds me of trying to draw a circle with short straight lines in Logo and a Turtle robot - the work was in trying to work out the number of short lines you needed to draw to make a visually clean circle.

[Heater]

skypi,

actually it just dawned on me that the recursive solution to 64 disk towers of hanoi is probably doomed to fail!... stack overflow!

If you think about it for a little while you may be surprised. The recursive Towers of Honoi solution only uses a stack depth of N - 1. Where N is the number of disks on the tower at the start.

My proposed 128 high tower may require many times the age of the universe to complete but it only requires a stack depth of 127. No problem there.