Small Solver Program

02252019, 11:00 PM
(This post was last modified: 02252019 11:18 PM by Thomas Klemm.)
Post: #25




RE: Small Solver Program
(02252019 08:39 PM)Csaba Tizedes Wrote: Not really, because in my idea no needed to bracket the root. There's nothing wrong with a digitbydigit 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\). Digitbydigit 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 digitbydigit method. The only advantage to use a digitbydigit 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 )^xe^\pi\) Cheers Thomas 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)