Hi, Dino,
Ok, let me give you an example: Suppose one wants to determine the square root of 2 numerically. You start with x=0 and increment at each step x by 0.1 until x**2>2. The last value of x is then the numerical value of sqrt(2). In our case, it would be x=1.5, since 1.4**2=1.96<2 and 1.5**2=2.25>2. The accuracy of the answer is 0.1, since the real value of sqrt(2) is known to be found between 1.4 and 1.5.
If one applies linear search for large numbers (let’s say one wants to find the square root of 20000 (which is approx. 141)), the algorithm is kind of slow (starting with x=0 and incrementing by 0.1). If one increments by a larger value (let’s say 10), the answer will be less precise.
A simple way to improve this algorithm is to start with a large increment (let’s say 10) until you find a value x such that x**2> 20000. In our case it would be x=150. Then, one knows that the value before x=150, that is x=140, fulfills 140**2< 20000. One can then start with this new value x=140, but with a smaller increment (let’s say 1). Repeating this procedure, one can find the desired square root with any precision desired. Note that this algorithm is more suitable for sufficiently small numbers.
Another algorithm is to use nested intervals. Again, we want to determine sqrt(2).
The idea is to start with two values, x_lower and x_higher, such that x_lower**2<2 and x_higher**2>2. Let’s take x_lower=0 and x_higher=2 (we know that 2**2>2). Then take the arithmetic mean x_m=0.5*(x_lower+x_higher)=1 and calculate x_m**2=1<2. Since x_m is smaller than sqrt(2), we replace x_lower->x_m and start over again. Then, x_m=0.5*(x_lower+x_higher)=0.5*(1+2)=1.5 and x_m**2=1.5**2=2.25>2. Since x_m is greater than sqrt(2), we replace x_higher ->x_m and start over again. You may stop this algorithm if the value of x_m is not changing any longer, up to a certain precision. For sqrt(20000), you can take x_lower=0 and x_higher= 20000 as starting points.
The advantage of this algorithm is that it converges very fast (exponentially), regardless of the number you want to determine. Furthermore, you have control over the error of your approximation.
Regarding your program, I think you can take another ellipse initially, which is known not to intersect EL1 and then take the arithmetic mean of the axis of the inner and outer ellipse. By this, one could implement the nested interval algorithm.
By this method, it doesn’t matter if your ellipse EL1 is very large or very small in the beginning.
Best,
Max
Fusion
