Small Solver Program

[Thomas Klemm]

(02-25-2019 08:39 PM)Csaba Tizedes Wrote:  Not really, because in my idea no needed to bracket the root.

There's nothing wrong with a digit-by-digit algorithm.
However after the first change of sign you already bracket the root.

So let's assume that this interval has length \(I\).
And we want to bring it down to a small value, say \(\epsilon\).

Digit-by-digit method

With each digit we divide the interval by 10.
After \(k\) digits we end up with:

\(\epsilon=\frac{I}{10^k}\)

Thus \(k=\frac{\log I - \log \epsilon}{\log 10}\).
But on average we need 5 steps until we can decide on the digit.
All in all we use about \(\frac{5}{\log 10}(\log I - \log \epsilon)\) steps.

Binary search

We divide the interval consecutively by 2.
After \(k\) bisections we end up with:

\(\epsilon=\frac{I}{2^k}\)

Thus \(k=\frac{\log I - \log \epsilon}{\log 2}\).
We only need 1 step to decide which interval to keep.
All in all we use \(\frac{1}{\log 2}(\log I - \log \epsilon)\) steps.

Conclusion

Now compare \(\frac{5}{\log 10} \approx 2.1715\) with \(\frac{1}{\log 2} \approx 1.4427\) to see that the binary search is about \(1.5051\) times faster than the digit-by-digit method.

The only advantage to use a digit-by-digit method is when calculating the function value of the next step can be done easier based on the function values of the previous steps.
Therefore, it's used in calculating the square root or the trigonometric functions (CORDIC).

However, I do not see any way to do this with an arbitrary function like the one given in the video:

\(f(x)=\left (\frac{e \ln(\pi)}{\ln(x)} \right )^x-e^\pi\)

Cheers
Thomas