Serving the Quantitative Finance Community

 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Re: C++ quiz - Maths and acccuracy

May 10th, 2018, 8:25 pm

Give this discussion a chance to run its course. Going all defensive is a bit silly.

And less cherry picking, por favor ;)
Agreed! You should be less defensive when someone finds a higher-performance solution to a cherry-picked function. ;)
 
User avatar
Cuchulainn
Topic Author
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: C++ quiz - Maths and acccuracy

May 11th, 2018, 10:30 am

Give this discussion a chance to run its course. Going all defensive is a bit silly.

And less cherry picking, por favor ;)
Agreed!  You should be less defensive when someone finds a higher-performance solution to a cherry-picked function. ;)
Are you that 'someone'? As I said, using Mathematica is cheating in this case. So tell us what's the best solution? It's also OK to say you don't know.
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Re: C++ quiz - Maths and acccuracy

May 11th, 2018, 12:22 pm

Give this discussion a chance to run its course. Going all defensive is a bit silly.

And less cherry picking, por favor ;)
Agreed!  You should be less defensive when someone finds a higher-performance solution to a cherry-picked function. ;)
Are you that 'someone'? As I said, using Mathematica is cheating in this case. So tell us what's the best solution? It's also OK to say you don't know.
So now accessing Wolfram Alpha is out? (But accessing old math papers is still permitted?) Moving the goal posts once again?

How can I know the "best solution" if the requirements are kept hidden (e.g., solution can't use calculus) or are capriciously revised (e.g., solution must now work on a second equation but apparently other cherry-picked functions are out of scope)? Is performance still important? It was specifically required for the first function but that requirement seems to have been dropped for the second one. If performance is important in the case of your two functions, then calculus leads to a higher performance calculation of the first derivative with no worries about the accuracy issues associated with using a numerical differential variable.
 
User avatar
Cuchulainn
Topic Author
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: C++ quiz - Maths and acccuracy

May 11th, 2018, 12:42 pm

If you don't like the style, why don't you start your own thread? Save both of us all the hassle. BTW in all these years I cannot remember your ever having done that.

I will not respond forthwith if you keep going in English bla bla.
 
User avatar
Cuchulainn
Topic Author
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: C++ quiz - Maths and acccuracy

May 14th, 2018, 8:49 am

I complexify [$]f(z)[$]  where [$]z = x + ih[$] and h = 0.001, e.g.
Then compute the imaginary part of [$]f(z)/h[$] and you are done.(*)
For x = 1.87 I get 1.3684..... e+289 for both exact and this method.(12 digits accuracy)

No subtraction cancellation as with FD classic.
(*) Squire and Trapp 1998.
The use of the complex-step in calculating the derivative of an analytic function was introduced by Lyness & Moler.

Numerical Differentiation of Analytics Functions, SIAM Vol 4, N2, 1967 available here: link to the pdf paper

PS: In a previous life, I used the complex-step gradients to compute the sensittivity derivatives of the aerodynamic cost function.
Cool. 
The Lyness/Moler paper looks more computationally intensive than S&T for f'(x).  It uses a series solution + numerical integration(?)

I am examining the wider applicability of this method for gradients compared to AD method (I exclude exact methods and classic fdm for various reason). I tested first order call option greeks and bond sensitivities and the results so far agree with exact and fdm solutions. I even tried option speed by applying S&T to gamma.

For functions with several complex variables z1, z2, ...as arguments I can now perturb each z_j (j =1, 2,..) independendently and compute partial derivatives with ease. Is that how the work?

I feel the method is most applicable with a small number of parameters, like MLE(?) (your aerodynamics have 18 parameters?)
Would the approach work for ML and more general optimisation, i.e. does it scale?
//
It was mentioned that the compiler needs to support erfc(z) for z complex. Not in C++11 but I found that it can be written in terms of the Faddeeva function (See package "Faddeeva" and good to go). 

http://ab-initio.mit.edu/wiki/index.php ... va_Package
 
User avatar
FaridMoussaoui
Posts: 327
Joined: June 20th, 2008, 10:05 am
Location: Genève, Genf, Ginevra, Geneva

Re: C++ quiz - Maths and acccuracy

May 14th, 2018, 9:46 am

For the AD method for greeks, have to look to Mike Giles work.
 
User avatar
Cuchulainn
Topic Author
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: C++ quiz - Maths and acccuracy

May 14th, 2018, 9:58 am

For the AD method for greeks, have to look to Mike Giles work.
+ DiffSharp?
 
User avatar
FaridMoussaoui
Posts: 327
Joined: June 20th, 2008, 10:05 am
Location: Genève, Genf, Ginevra, Geneva

Re: C++ quiz - Maths and acccuracy

May 14th, 2018, 10:12 am

I stay with universal languages, e.g C++/Fortran
 
User avatar
Cuchulainn
Topic Author
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: C++ quiz - Maths and acccuracy

May 14th, 2018, 12:03 pm

I stay with universal languages, e.g C++/Fortran
There's a lot to be said for this approach for this computationally intensive problem. 
I reckon Fortran is the better of the two in this case?
 
User avatar
Cuchulainn
Topic Author
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: C++ quiz - Maths and acccuracy

September 9th, 2018, 11:51 am

Computing Dates of Rosh Hasbonah and Passover.

https://www.sciencedirect.com/science/a ... 2177900931
 
User avatar
Cuchulainn
Topic Author
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: C++ quiz - Maths and acccuracy

September 23rd, 2018, 10:03 am

Computing derivatives without the pain of 1) differentiation, 2) catastrophic round-off errors. Sample code.
The scalar (almost a 1-liner). I leave the vector case as an exercise.
// TestComplexStep.cpp
//
// Complex-step method to compute approximate derivatives.
// Example is scalar-valued function of a scalar argument.
//
// https://pdfs.semanticscholar.org/3de7/e8ae217a4214507b9abdac66503f057aaae9.pdf
//
// http://mdolab.engin.umich.edu/sites/default/files/Martins2003CSD.pdf
//
// (C) Datasim Education BV 2018
//

#include <functional>
#include <complex>
#include <iostream>
#include <iomanip>
#include <cmath>

// Notation and function spaces
using value_type = double;

template <typename T>
 using FunctionType = std::function < T(const T& c)>;
using CFunctionType = FunctionType<std::complex<value_type>>;


// Test case from Squire&Trapp 1998
template <typename T> T func(const T& t)
{
 T n1 = std::exp(t);
 T d1 = std::sin(t);
 T d2 = std::cos(t);

 return n1 / (d1*d1*d1 + d2*d2*d2);
}

template <typename T> T func2(const T& t)
{ // Derivative of e^t, sanity check

 return std::exp(std::pow(t,1));
// return std::exp(std::pow(t, 5));

}
 
value_type Derivative(const CFunctionType& f, value_type x, value_type h)
{ // df/dx at x using tbe Complex step method

 std::complex<value_type> z(x, h); // x + ih, i = sqrt(-1)
 return std::imag(f(z)) / h;
}

int main()
{
 // Squire Trapp
 double x = 1.5; double h = 0.1;
 do
 {
 std::cout << std::setprecision(12) << Derivative(func<std::complex<value_type>>, x, h) << '\n';
 h *= 0.1;

 } while (h > 1.0e-300);

 // Exponential function (101 sanity check)
 x = 5.0;
 h = 1.0e-10;
 std::cout << "Exponential 1: " << std::setprecision(12) << Derivative(func2<std::complex<value_type>>, x, h) << '\n';

 return 0;
}
 
User avatar
Cuchulainn
Topic Author
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: C++ quiz - Maths and acccuracy

November 27th, 2018, 8:01 pm

Can this be parallelised?
ublas::matrix<W> d = ...
 std::size_t n = ...

 for (std::size_t v = 0; v < n; ++v)
 {
 d(v, v) = 0.0;
 }

 for (std::size_t k = 0; k < n; ++k)
 {
 for (std::size_t i = 0; i < n; ++i)
 {
 for (std::size_t j = 0; j < n; ++j)
 {
 d(i, j) = std::min<W>(d(i, j), d(i, k) + d(k,j));
 }
 }
 }
elised?
 
User avatar
FaridMoussaoui
Posts: 327
Joined: June 20th, 2008, 10:05 am
Location: Genève, Genf, Ginevra, Geneva

Re: C++ quiz - Maths and acccuracy

November 29th, 2018, 1:30 am

Computing derivatives without the pain of 1) differentiation, 2) catastrophic round-off errors. Sample code.
The scalar (almost a 1-liner). I leave the vector case as an exercise.
// TestComplexStep.cpp
//
// Complex-step method to compute approximate derivatives.
// Example is scalar-valued function of a scalar argument.
//
// https://pdfs.semanticscholar.org/3de7/e8ae217a4214507b9abdac66503f057aaae9.pdf
//
// http://mdolab.engin.umich.edu/sites/default/files/Martins2003CSD.pdf
//
// (C) Datasim Education BV 2018
//

#include <functional>
#include <complex>
#include <iostream>
#include <iomanip>
#include <cmath>

// Notation and function spaces
using value_type = double;

template <typename T>
 using FunctionType = std::function < T(const T& c)>;
using CFunctionType = FunctionType<std::complex<value_type>>;


// Test case from Squire&Trapp 1998
template <typename T> T func(const T& t)
{
 T n1 = std::exp(t);
 T d1 = std::sin(t);
 T d2 = std::cos(t);

 return n1 / (d1*d1*d1 + d2*d2*d2);
}

template <typename T> T func2(const T& t)
{ // Derivative of e^t, sanity check

 return std::exp(std::pow(t,1));
// return std::exp(std::pow(t, 5));

}
 
value_type Derivative(const CFunctionType& f, value_type x, value_type h)
{ // df/dx at x using tbe Complex step method

 std::complex<value_type> z(x, h); // x + ih, i = sqrt(-1)
 return std::imag(f(z)) / h;
}

int main()
{
 // Squire Trapp
 double x = 1.5; double h = 0.1;
 do
 {
 std::cout << std::setprecision(12) << Derivative(func<std::complex<value_type>>, x, h) << '\n';
 h *= 0.1;

 } while (h > 1.0e-300);

 // Exponential function (101 sanity check)
 x = 5.0;
 h = 1.0e-10;
 std::cout << "Exponential 1: " << std::setprecision(12) << Derivative(func2<std::complex<value_type>>, x, h) << '\n';

 return 0;
}
It is much more "complex" to use it with a computer code. Suppose you have a C++ program which output some "cost" function and you want compute the derivative of this cost function to do some optimisation problem with respect to the cost function.

You have no choice but complexify your code, e.g define a new class (complex_type) and all the functions that are required for the complex-step method. Replace all "double" with "complex_type" and some cosmetics dealing with IO.
 
User avatar
ExSan
Posts: 493
Joined: April 12th, 2003, 10:40 am

Re: C++ quiz - Maths and acccuracy

November 29th, 2018, 1:45 pm

In regard of the "C++ quiz - Maths and acccuracy"
I found this The quadratic formula and low-precision arithmetic   one of the roots is wrong
I coded the problem in C
/***********START***************/
void quad(double a, double b, double c, double & x1, double & x2 ){
 double r = sqrt(b*b - 4 * a*c);
 x1 = (-b + r) / (2 * a);
 x2 = (-b - r) / (2 * a);
}
double quad2(double a, double b, double c, double x ) {
 return a*x*x +b*x+c;
}
void QuadraticLossPrecision(){
 
 double x1(0), x2(0);
 quad(1, 1e8, 1, x1, x2);

 fout <<  "\n\tx1:" << x1 << "\n\tx2:" << x2;
 fout << "\n\tx1: " << x1 << "\n\tquad2(x1):" << quad2(1, 1e8, 1, x1);
}
/***********END QuadraticLossPrecision*****************/
Output looks like:
    °ExSan++ High Performance C++ Computing V.6.00.L°
 NOT VALID FOR DISTRIBUTION ---BE---careful
                                                        Thu Nov 29 08:36:52 2018


    [email protected]   https://twitter.com/#!/ExSan_com
    JOB:  quad_V.6.00.L__3652


 x1:-0.000000007450580596923828125000
 x2:-100000000.000000000000000000000000000000
 x1:-0.000000007450580596923828125000
 quad2(x1): 0.254941940307617187500000000000
 


 ENDS  quad_V.6.00.L__3652   Elapsed Time: 0.008000000000000000166533453694  sec
 NOT VALID FOR DISTRIBUTION ---BE---careful
    EXIT FROM EXSAN                                    
°°° About ExSan bit.ly/3U5bIdq °°°
 
User avatar
Cuchulainn
Topic Author
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: C++ quiz - Maths and acccuracy

November 29th, 2018, 9:12 pm

Image