Fun with mathematics

[HCHTech]

I spent the first 22 years of my working career in actuarial science, so my brain is broken a bit to the point where I like it when I run into math problems in my encore career of computer repair.

I had a customer problem I described here the other day where I had to run a ping command over and over again with different MTU guesses until I zeroed in on the correct answer. That made me think of this:

So....when you have a function you have to iterate with an initial variable that you have to guess and then change with the iteration, there are a couple of ways to do this.

Let's say your initial guess ends up being too low of a number. How do you figure out what the next guess should be? You can always brute-force the calculation and just increase your guess by 1 or 10 or some other increment you decide, run the calculation again, determine whether the guess was too high or too low and repeat until you find the right answer.

There is a more efficient way to do this, however. If your guess is too low, your second guess should be a number that you think will be too high. THIS sets the two endpoints of the guessing continuum. After you know the end points, you calculate each future guess as 1/2 way between the last guess and the endpoint. As you proceed, each new guess sets a new endpoint. This way, you reach the answer in fewer guesses (statistically, that is - unless you are a really good guesser!) This is called Iteration by Bifurcation.

There is an even more efficient take on this process where instead of guessing 1/2 way between the current guess and the endpoint, you find a way to estimate how far you are off and guess that percentage of the way between your last guess and the endpoint. I'm not sure what that's called, but maybe some of the programmers here have heard of it. Maybe geometric bifurcation?

Mostly, this whole concept is only important when you are programming an iterative function and you know there will be potentially thousands of iterations. In that case, finding a way to guess efficiently makes your program run faster.

 

[Larry Sabo]

find a way to estimate how far you are off and guess that percentage of the way between your last guess and the endpoint

How? If you are just guessing a number/percentage, I believe it will be more efficient to just use regular bifurcation.

 

[brandonkick]

This may interest you, I occasionally find myself wondering off
the beaten path when researching solutions to a problem or
trying to dig up info on some API that I'm programming in. And
I found this. Liking math myself, these types of complexity/efficency
problems always interest me.

https://www.facebook.com/video.php?v=910320979112561

 

[NviGate Systems]

This reminds me of one of EEVBlog videos where he shows that a guy figured out that each calculator chip renders a certain function slightly different, and you can use the result (last few digits) to identify which chip is in the calculator.

The interesting part for me is that you think a calculator would be immune to this, that it would remain true across every calculator. However, in silicon chips are essentially software firmware as I call it, a software designed by the die pattern. So each implementation will handle differently. Some dies will have a bias to this operation, others will bias another way.

It really makes you think. I wonder if there is a calculator that is a pure calculator that won't be affected by such hacks.

 

[HCHTech]

How? If you are just guessing a number/percentage, I believe it will be more efficient to just use regular bifurcation.

It has to do with comparing how much the result changed compared with how much the guess changed - then using that ratio to affect the what the next guess would have been according to regular bifurcation. I recall an example with an oscillating function that it showed the "zeroing in" on the final answer as a graph. Geometric bifurcation (or whatever it's called) had a much steeper angle than regular bifurcation. In other words, it got to the result in fewer iterations. I'll have to do some digging to see if I have anything from those days. Neat stuff, though.

 

[HCHTech]

This may interest you,

That's awesome! I feel another internet rabbit hole coming on. Dammit, I have to get up early tomorrow, too!

 

[glennd]

I spent the first 22 years of my working career in actuarial science, so my brain is broken a bit to the point where I like it when I run into math problems in my encore career of computer repair.

I had a customer problem I described here the other day where I had to run a ping command over and over again with different MTU guesses until I zeroed in on the correct answer. That made me think of this:

So....when you have a function you have to iterate with an initial variable that you have to guess and then change with the iteration, there are a couple of ways to do this.

Let's say your initial guess ends up being too low of a number. How do you figure out what the next guess should be? You can always brute-force the calculation and just increase your guess by 1 or 10 or some other increment you decide, run the calculation again, determine whether the guess was too high or too low and repeat until you find the right answer.

There is a more efficient way to do this, however. If your guess is too low, your second guess should be a number that you think will be too high. THIS sets the two endpoints of the guessing continuum. After you know the end points, you calculate each future guess as 1/2 way between the last guess and the endpoint. As you proceed, each new guess sets a new endpoint. This way, you reach the answer in fewer guesses (statistically, that is - unless you are a really good guesser!) This is called Iteration by Bifurcation.

There is an even more efficient take on this process where instead of guessing 1/2 way between the current guess and the endpoint, you find a way to estimate how far you are off and guess that percentage of the way between your last guess and the endpoint. I'm not sure what that's called, but maybe some of the programmers here have heard of it. Maybe geometric bifurcation?

Mostly, this whole concept is only important when you are programming an iterative function and you know there will be potentially thousands of iterations. In that case, finding a way to guess efficiently makes your program run faster.

we call this a binary search and is very useful for searching an ordered list. we compare the middle item, divide the list in half and take either the upper or lower half (depending on the result of the comparison). this really limits the number of comparisons required for a large list. for example, an ordered list of a million items requires around 21 comparisons to reach an answer. 8 billion items requires 35 comparisons.

 

[HCHTech]

8 billion items requires 35 comparisons.

That's amazing - it's reverse exponential growth. Cool.

 

[Eagle21]

There is a more efficient way to do this, however. If your guess is too low, your second guess should be a number that you think will be too high. THIS sets the two endpoints of the guessing continuum. After you know the end points, you calculate each future guess as 1/2 way between the last guess and the endpoint. As you proceed, each new guess sets a new endpoint. This way, you reach the answer in fewer guesses (statistically, that is - unless you are a really good guesser!) This is called Iteration by Bifurcation.

In the study of computer algorithms this is called a "Binary Search".
https://en.wikipedia.org/wiki/Binary_search_algorithm
If you are searching unbounded/infinite lists it is called an "Exponential Search"

There is an even more efficient take on this process where instead of guessing 1/2 way between the current guess and the endpoint, you find a way to estimate how far you are off and guess that percentage of the way between your last guess and the endpoint. I'm not sure what that's called, but maybe some of the programmers here have heard of it. Maybe geometric bifurcation?

This is an "Interpolation Search".
Intuitively it would seem this method is much more efficient than binary search. But a binary search is already very efficient having a complexity of O(log n), so even using a clever guessing method you may not save much time, especially if the list is short or the guess is expensive to calculate.

 

[Eagle21]

That's amazing - it's reverse exponential growth. Cool.

It is O(log n) complexity.

 

[HCHTech]

It is O(log n) complexity.

Yes! makes sense. You are halving the items with each step. So, in the example above for 8 Billion items, you would be solving 2^x = 8 Billion. x = Log(8Billion) / Log(2) = 32.9. Hmm. it looks like it would only take 33 iterations. Close enough for back-of-the-forum scribbling.

 

[Altster]

Oh brother!

My brain hurts.

 

[glennd]

Yes! makes sense. You are halving the items with each step. So, in the example above for 8 Billion items, you would be solving 2^x = 8 Billion. x = Log(8Billion) / Log(2) = 32.9. Hmm. it looks like it would only take 33 iterations. Close enough for back-of-the-forum scribbling.

I lost the source but I think it adds 1 to account for the first comparison before the first divide (or something) so rounding up would make it 34 or in mathematical terms, "less than 34"

 

[brandonkick]

It has to do with comparing how much the result changed compared with how much the guess changed - then using that ratio to affect the what the next guess would have been according to regular bifurcation. I recall an example with an oscillating function that it showed the "zeroing in" on the final answer as a graph. Geometric bifurcation (or whatever it's called) had a much steeper angle than regular bifurcation. In other words, it got to the result in fewer iterations. I'll have to do some digging to see if I have anything from those days. Neat stuff, though.

I think that what Larry is getting at, is that even though the list you have is "ordered" in a sense that you know
what the starting and ending boundaries are for possible MTU values. I didn't read the post you linked in which
I assume you talked about the problem that inspired this thought exercise... but if each iterations result is either
correct or incorrect without any way to confirm that the solution is within some subset of the remaining possibilities,
then you cannot truly perform a binary search.


In a binary search, the result set is reduced by half on each iteration. Determine, if you can, on which half of the
dataset resides the solution you are looking for. If you can't determine that... only that the value is correct or incorrect,
then really the binary search efficiency goes out the window. You can't eliminate any subset if you can't determine
that the solution is not within it. That becomes a complexity of O(n), linear time.

 

[glennd]

I think that what Larry is getting at, is that even though the list you have is "ordered" in a sense that you know
what the starting and ending boundaries are for possible MTU values. I didn't read the post you linked in which
I assume you talked about the problem that inspired this thought exercise... but if each iterations result is either
correct or incorrect without any way to confirm that the solution is within some subset of the remaining possibilities,
then you cannot truly perform a binary search.


In a binary search, the result set is reduced by half on each iteration. Determine, if you can, on which half of the
dataset resides the solution you are looking for. If you can't determine that... only that the value is correct or incorrect,
then really the binary search efficiency goes out the window. You can't eliminate any subset if you can't determine
that the solution is not within it. That becomes a complexity of O(n), linear time.

If we're still talking about the MTU problem then the test itself has a binary outcome. That is to say the test MTU value either works or it doesn't. 1500 doesn't work and some arbitrary value less than that does work. The lower value works, the upper value doesn't work. the entire set is ordered from a value or working to a value or not working. So you perform a binary search to find the threshold between working and not working, 1 and 0, etc...

 

[HCHTech]

Yeah, I wasn't really talking about using this methodology with the MTU problem, only that the MTU problem made me think of this methodology. In the example from my past, you did indeed have a way to know if the result is higher or lower than the final answer, you just didn't know by how much. As long as your guesses proceeded correctly, you'd eventually arrive at the answer (it was dollars and cents, so you didn't need to fuss with decimal places higher than 3). Using the bifurcation method just got you there faster. I'm old enough that we started out doing those calculations on paper, so faster was pretty valuable. It got fun when you could put that all in a spreadsheet (Lotus123 for the win!) with circular references and just hit the Calc button over and over and watch the answer finalize.

I was fascinated by chaos theory back when it first hit public awareness in the 80s. Lots of iterative functions that were nonlinear, so these kinds of methods were useless. In the Mandlebrot set, for example, you just feed the answer back into the equation and calculate it again. Eventually, it would approach zero (your starting value was IN the set) or infinity (your starting value was NOT IN the set), depending on the value - but it did so in a nonlinear fashion.

 

[HCHTech]

I lost the source but I think it adds 1 to account for the first comparison before the first divide (or something) so rounding up would make it 34 or in mathematical terms, "less than 34"

Yeah, I figured it was something like that. haha.

 

[Larry Sabo]

I vaguely recall doing this in a computer programming class back in '62-'65, and recall there wasn't always a unique solution, e.g., you were looking for the point where the function crossed the zero axis, and the function turned out to be a parabola or a more complex function that had two or more roots. I sometimes regret discarding my old notebooks, having carted them from house to house with each move but never opening them.

 

[brandonkick]

Oh, ok so I misunderstood... there is not just one single value that "works"....
there are ranges of values... and it's understood that when a value works
you know for sure values either above or below it will work (I'm sure only
one of those cases are true). In that case, yes a binary search would work
as expected. I'm not sure how you'd land on an "optimal" value, if there
were one as it seems more like a pass / fail type result.

 

[Larry Sabo]

there are ranges of values... and it's understood that when a value works
you know for sure values either above or below it will work

With the problem I was describing, it's not a range, it's a number of discrete values, not necessarily in a series (adjacent). Depending on the function and the initial guess, the iteration could diverge, i.e., send you off on a wild goose chase.