SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
Cuchulainn
Posts: 51036
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: exp(5) = [$]e^5[$]

April 18th, 2017, 10:48 am

Instead of Newton, bisection, analytical approximations (too many assumptions that can break during stormy weather) we do least-squares minimisation of the unimodal(!) function [$](log(x) - 5.0)^2[$]  using the (most?) efficient three-point interval search on [32,243] with the least number of function evaluations. Does it do better than other algos for iv?

Here is the output (tol = 1.0e-5). Nice thing is the answer always lies in an interval.

Minimum: x, f(x) [84.75,190.25], 0.187801
Minimum: x, f(x) [111.125,163.875], 0.0467709
Minimum: x, f(x) [137.5,163.875], 0.00782745
Minimum: x, f(x) [144.094,157.281], 0.00212025
Minimum: x, f(x) [144.094,150.688], 0.000551828
Minimum: x, f(x) [147.391,150.688], 0.000139543
Minimum: x, f(x) [147.391,149.039], 3.27546e-05
Minimum: x, f(x) [147.803,148.627], 9.52942e-06
Minimum: x, f(x) [148.215,148.627], 1.93004e-06
Minimum: x, f(x) [148.318,148.524], 4.84548e-07
Minimum: x, f(x) [148.369,148.472], 1.23176e-07
Minimum: x, f(x) [148.395,148.447], 3.28335e-08
Minimum: x, f(x) [148.395,148.421], 8.72959e-09
Minimum: x, f(x) [148.408,148.421], 1.95913e-09
Minimum: x, f(x) [148.411,148.418], 5.47337e-10
Minimum: x, f(x) [148.411,148.414], 1.22007e-10
Minimum: x, f(x) [148.412,148.414], 3.37671e-11
Minimum: x, f(x) [148.413,148.414], 7.74401e-12
Minimum: x, f(x) [148.413,148.413], 2.22907e-12
Minimum: x, f(x) [148.413,148.413], 4.62369e-13
Minimum: x, f(x) [148.413,148.413], 1.17684e-13
Minimum: x, f(x) [148.413,148.413], 3.15131e-14
Minimum: x, f(x) [148.413,148.413], 8.20017e-15
Minimum: x, f(x) [148.413,148.413], 1.90432e-15
Bracket  [148.413,148.413]
Bracket [2.78939e-15,1.01925e-15]

For OP, tol = 1.0e-1 gives

Minimum: x, f(x) [84.75,190.25], 0.187801
Minimum: x, f(x) [111.125,163.875], 0.0467709
Minimum: x, f(x) [137.5,163.875], 0.00782745
Minimum: x, f(x) [144.094,157.281], 0.00212025
Minimum: x, f(x) [144.094,150.688], 0.000551828
Minimum: x, f(x) [147.391,150.688], 0.000139543
Minimum: x, f(x) [147.391,149.039], 3.27546e-05
Minimum: x, f(x) [147.803,148.627], 9.52942e-06
Minimum: x, f(x) [148.215,148.627], 1.93004e-06
Minimum: x, f(x) [148.318,148.524], 4.84548e-07
Minimum: x, f(x) [148.369,148.472], 1.23176e-07
Bracket  [148.369,148.472]
Bracket [8.70207e-08,1.59332e-07]
http://www.datasimfinancial.com

I tell the kids, somebody’s gotta win, somebody’s gotta lose. Just don’t fight about it. Just try to get better.
 
User avatar
Cuchulainn
Posts: 51036
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: exp(5) = [$]e^5[$]

April 21st, 2017, 9:46 am

We all know by now that the answer is 148.413 and that the function to be minimised is simple. For more complicated functions things can become more tricky and then we want to make C++ look more like mathematics (functional programming languages do it before breakfast). C++11 helps a bit by lambda functions so that you can build a vector space of functions to assemble functions from simpler ones. You would kind of expect that a library builder out there has done this (knowledge of maths is needed).
// TestHOF101.cpp
//
// Testing lambda functions; build complex functions using algebra. 
// A vector space of functions.
// In  this case compute x - e^5 = 0 using least squares and Brent's method
// x == 148.413
//
// DD

#include <functional>
#include <cmath>
#include <iostream>
#include <boost/math/tools/minima.hpp>

template <typename T>
 std::function<T (T)> operator * (std::function<T (T)>& f, std::function<T (T)>& g)
{ // Addition

 return [=](T x)
 {
 return  f(x) * g(x);
 };
}

template <typename T>
 std::function<T (T)> operator - (std::function<T (T)>& f, T a)
{ // Addition

 return [=](T x)
 {
 return  f(x) - a;
 };
}



template <typename T>
 std::function<T (T)> log(std::function<T (T)>& f)
{ // log

 return [=](T x)
 {
 return  std::log(f(x));
 };
}
template <typename T>
 std::function<T(T)> exp(std::function<T(T)>& f)
{ // log

 return [=](T x)
 {
 return  std::exp(f(x));
 };
}

double funcGlobal(double x)
{
 return (std::log(x) - 5.0)* (std::log(x) - 5.0);
}

int main()
{

 // Define interval [min, max] where search will take place
 double min = 5.0;
 double max = 300.0;

 int bits = 50;
 boost::uintmax_t maxIter = 10000;

 // Standard function call
 std::pair<double, double> result = boost::math::tools::brent_find_minima(funcGlobal, min, max, bits, maxIter);
 std::cout << "Abscissa, value f(x) : " << result.first << ", " << result.second << std::endl;

 // Now use lambda and algebra; assemble functions incrementally
 std::function<double(double)> f1 = [](double x) { return std::log(x); };
 decltype(f1) f2 = f1 - 5.0;
 decltype(f2) funcHOF = f2*f2;

 // Stress testing
 std::function<double(double)> f0 = [](double x) { return x; };
 decltype(f0) funcExtreme = exp(log(exp(log(f0))));
 std::cout << "? " << funcExtreme(5) << '\n';
 decltype(f0) f3 = log(funcExtreme);
 decltype(f0) f4 = exp(funcExtreme);
 std::cout << "? " << f3(5) << '\n';
 std::cout << "? " << f4(5) << '\n';
 //

 std::pair<double, double> result2 = boost::math::tools::brent_find_minima(funcHOF, min, max, bits, maxIter);
 std::cout << "Abscissa, value f(x) HOF: " << result2.first << ", " << result2.second << std::endl;
 
}


//
http://www.datasimfinancial.com

I tell the kids, somebody’s gotta win, somebody’s gotta lose. Just don’t fight about it. Just try to get better.
 
User avatar
Cuchulainn
Posts: 51036
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: exp(5) = [$]e^5[$]

April 22nd, 2017, 1:21 pm

Until now, we used double precision data types for the minimisation using interval searching. Will the algorithm work with multiprecision types? It would seem yes at the moment. We use 100-digit type and we get 148.413..... to 100 digits that we checked against Boost and that big online calculator.

And the run-time performance doesn't seem to be all that bad. No test done.

The output is

3-point interval Search method
148.4131 5910 2576 6034 2111 5580 0405 5227 9623 4876 6759 3878 9890 4675 2845 1109 1206 4820 9585 7607 9688 4094 5989 90211
 
Exact (yuge precision)
148.4131 5910 2576 6034 2111 5580 0405 5227 9623 4876 6759 3878 9890 4675 2845 1109 1206 4820 9585 7607 9688 4094 5989 9021 1
 
\-> etc.412 9280 8270 6663 2605 2909 9262 3769 4548 1827 8044 9112 4354 2477 7223 6978 7450 8409 7439 3799 2123 5516 6686 3241 8855 9697 6672 2232 1326 5623 4323 8300 9773 3581 8269
 
http://www.datasimfinancial.com

I tell the kids, somebody’s gotta win, somebody’s gotta lose. Just don’t fight about it. Just try to get better.
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...