Brent's Method in C++

[VTQ]

Hi All,

I am looking for an efficient implementation of Brent's method. I understand it is available in Boost. However is there any other implementation which you would recommend ?

Any suggestions for implementing indenpendently are also welcome.

Thanks in advance!

@Daniel Duffy

 

[Daniel Duffy]

Yes, it is in Boost. It works very well.

Can you be more precise? Do you want other solvers for a problem? etc.

 

[VTQ]

Yes, it is in Boost. It works very well.

Can you be more precise? Do you want other solvers for a problem? etc.

Hi Daniel, Thank you for the response. To be precise, I am looking for implementation of Brent's method without boost libraries. My purpose is solving for implied vol.
I want to use this in Python wherever possible for faster compute. So instead using Scipy, I want to keep my library light. I hope that makes sense.

 

[Daniel Duffy]

That's a good argument I might even try it myself.

1.

• Brent, R. P. (1973), "Chapter 4: An Algorithm with Guaranteed Convergence for Finding a Zero of a Function", Algorithms for Minimization without Derivatives, Englewood Cliffs, NJ: Prentice-Hall, ISBN 0-13-022335-2 (can alway write f(x) = 0 as min f(x)*f(x) ==. very robust fo iv Ihave found).

2. Numercal,Recipes section 9.3 vn Wijngaarden-Dekker-Brent ==> 1 page of C code.
3. Use source code in Boost C++ and leave the rest behind. (boost\maths\tools\minima.hpp)
(4. solve min f(x)*f(x) by formulating as an ODE .... more advanced).

I reckon this should help! Good luck.

//

http://www.ijlret.com/Papers/Vol-05-issue-12/1.B2019072.pdf

Boost Code >> NR Code

 

[VTQ]

That's a good argument I might even try it myself.

1.

• Brent, R. P. (1973), "Chapter 4: An Algorithm with Guaranteed Convergence for Finding a Zero of a Function", Algorithms for Minimization without Derivatives, Englewood Cliffs, NJ: Prentice-Hall, ISBN 0-13-022335-2 (can alway write f(x) = 0 as min f(x)*f(x) ==. very robust fo iv Ihave found).

2. Numercal,Recipes section 9.3 vn Wijngaarden-Dekker-Brent ==> 1 page of C code.
3. Use source code in Boost C++ and leave the rest behind. (boost\maths\tools\minima.hpp)
(4. solve min f(x)*f(x) by formulating as an ODE .... more advanced).

I reckon this should help! Good luck.

//

http://www.ijlret.com/Papers/Vol-05-issue-12/1.B2019072.pdf

Boost Code >> NR Code

Thanks a lot, let me give this a go.

 

[Daniel Duffy]

If you get time, give us a shout on how it went.
You can benchmark againg Python and Boost. It would be an interesting test of accuracy, robustness, effiiciency etc.

 

[VTQ]

Thanks a lot, let me give this a go.

If you get time, give us a shout on how it went.
You can benchmark againg Python and Boost. It would be an interesting test of accuracy, robustness, effiiciency etc.

Sure, it may not be immediate but I will definitely update on this post. All I can say now is brentq from Scipy is robust, however it is on slow side

 

[Daniel Duffy]

Brainstormin idea; assuming iv has a single root, write f(x) = 0 as a least squares problem and compute its minimum using Golden Search/Fibonacci.

Golden-section search - Wikipedia

en.wikipedia.org

A lot less coding than Brent.