Page 33 of 36

Re: C++ quiz - Maths and acccuracy

Posted: April 13th, 2018, 7:46 pm
by Traden4Alpha
Of course, std::hypot is too slow I reckon for graphics/CAD apps (sqrt?).In some case a cubic accuracy Taylor expansion will work.
I was always fond of the Java approach for trying the simple formula first and catching exceptions on the back end. Burdening 100% of the executions of some bit of code to handle a 1-in-a-million corner case always seemed silly although I can understand the appeal of slow fixed-time algorithms over fast, variable-time ones.

Re: C++ quiz - Maths and acccuracy

Posted: April 25th, 2018, 3:21 pm
by Cuchulainn
Image

Re: C++ quiz - Maths and acccuracy

Posted: May 8th, 2018, 3:45 pm
by Cuchulainn
Quiz: Compute the first derivative of [$]f(x) = e^{e^{e^x}}[$] for let's say x = 0.001. 

Your answer should be accurate to 3 decimal digits, robust  and minimise the number of calls to the exponential function.

Any approach is fine but don't forget performance (even the pencil-and-paper variety).

Re: C++ quiz - Maths and acccuracy

Posted: May 8th, 2018, 5:47 pm
by Traden4Alpha
The easiest and most accurate solution is to take the derivative analytically to get  [$]f'(x) = e^{x}*e^{e^{x}}*e^{e^{e^x}}[$] which then only needs three calls to the exponential function by reusing the intermediate terms. In Excel, this formula works overflows somewhere in [1.87,1.88] and underflows somewhere around [-709,-708].

A better solution might be to analytically compute the mantissa and exponent separately.

Re: C++ quiz - Maths and acccuracy

Posted: May 8th, 2018, 6:52 pm
by Cuchulainn
The easiest and most accurate solution is to take the derivative analytically to get  [$]f'(x) = e^{x}*e^{e^{x}}*e^{e^{e^x}}[$] which then only needs three calls to the exponential function by reusing the intermediate terms. In Excel, this formula works overflows somewhere in [1.87,1.88] and underflows somewhere around [-709,-708].

A better solution might be to analytically compute the mantissa and exponent separately.
This is a solution but not optimal going forward 1) you have to compute f'(x) by hand (not always possible) 2) boiler-plate code (autodiff will do it for you). The function blows up of course (that why I said x = 0.001).
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.

Re: C++ quiz - Maths and acccuracy

Posted: May 8th, 2018, 7:46 pm
by Traden4Alpha
I doubt I understand the requirements.

1) What does "robust" mean if one is only calculating this at x=0.001?

2) What does "performance" mean? My method requires three calls to the standard exponential function and two multiplies. Your method require three calls to the complex version of the exponential function and a division.

Re: C++ quiz - Maths and acccuracy

Posted: May 8th, 2018, 7:57 pm
by Cuchulainn
The message is computing derivatives without fd or calculus. The (somewhat silly) example was taken from a ML book.
You need boilerplate code. And we haven't got to Jacobian and Hessian. No free lunch. I use complex. Amen. 

Let's take a call option. Compute the theta and vega using any method you llke.(and assume you only know the call price).

(Shamelessly copied from the Heston thread).


[$] C(t_0,T,S_0) = S_0 \Phi(d_1) - K \Phi(d_2)[$],



(thanks Alan)

Re: C++ quiz - Maths and acccuracy

Posted: May 8th, 2018, 8:06 pm
by Cuchulainn
Or even

[$]f(x) = cos(sin(sin(cos(x))))[$]

Good luck.

Re: C++ quiz - Maths and acccuracy

Posted: May 9th, 2018, 12:24 am
by Traden4Alpha
Ah, so I did not understand the requirements. They really had nothing to do with that particular function (which I did find numerically interesting including thinking about how to separately compute the exponent and mantissa for a broader range of x).

You failed to specify that you wanted an numerical method that could handle arbitrary functions.

Re: C++ quiz - Maths and acccuracy

Posted: May 9th, 2018, 7:08 am
by Cuchulainn
Ah, so I did not understand the requirements.  They really had nothing to do with that particular function (which I did find numerically interesting including thinking about how to separately compute the exponent and mantissa for a broader range of x).  

You failed to specify that you wanted an numerical method that could handle arbitrary functions.
It happens a lot in maths that we take a specific example and filter inessential complexities. The issue is not messing with signifcand an exponent. What you are suggesting is a home-grown version of autodiff or DiffSharp AD libraries. I think you zoomed in on a subset of the aspects.

Here is the approach I used above. Not many people know it and it was lost in action since the late 60s.

https://pdfs.semanticscholar.org/3de7/e ... 7aaae9.pdf

Re: C++ quiz - Maths and acccuracy

Posted: May 9th, 2018, 7:20 am
by Cuchulainn
You failed to specify that you wanted an numerical method that could handle arbitrary functions.

I can't remember having said that. It is a bridge too far.Better to scope the class of functions for which the method works.
Anyways, that's not the way maths works, i.e. top-down. 

So, take an example and then use induction. That's the general direction.

I've invited you in my previous posts to examine how to compute option theta and vega given the call price. I see solutons:

1. Calculus
2. Classic FDM
3. Symbolic differentiaton
4. Automatic Differentiation (AD)
5. By complexifying the function whose derivative is needed.


Image

Re: C++ quiz - Maths and acccuracy

Posted: May 9th, 2018, 1:25 pm
by Traden4Alpha
Ah, so I did not understand the requirements.  They really had nothing to do with that particular function (which I did find numerically interesting including thinking about how to separately compute the exponent and mantissa for a broader range of x).  

You failed to specify that you wanted an numerical method that could handle arbitrary functions.
It happens a lot in maths that we take a specific example and filter inessential complexities. The issue is not messing with signifcand an exponent. What you are suggesting is a home-grown version of autodiff or DiffSharp AD libraries. I think you zoomed in on a subset of the aspects.

Here is the approach I used above. Not many people know it and it was lost in action since the late 60s.

https://pdfs.semanticscholar.org/3de7/e ... 7aaae9.pdf
Yet the first things I thought of with the original example was that the essential complexity of that the function was: 1) f(x) gets extremely large at very low positive x (and extremely small for negative x); 2) f'(x)/f(x) is very large or very small for most x; and 3) higher derivatives are even larger implying that real-number first differences have dubious accuracy. To me, the most salient numerical issue is that f'(x) overflows or underflows most floating point types for almost half the possible values of x. That was why I was discussing a version for the separate computation of the significand and exponent.

Your solution is extremely clever, but only works if one has complex versions of the functions. It also requires quite a lot of computation in the case of the example function: three calls to exp(), three calls to sin(), three calls to cos(), assorted multiplications, and one division.

Re: C++ quiz - Maths and acccuracy

Posted: May 9th, 2018, 2:26 pm
by Cuchulainn
Your solution is extremely clever, but only works if one has complex versions of the functions.

Actually, it is due to Squire and Trapp 1998 as already mentoned.
And C++11 and C# have them these days. Well, it's catchiing up.
In the case of option greeks you can compude CDF() for complex arguments using the Faddeeva function.

http://ab-initio.mit.edu/wiki/index.php ... va_Package

Re: C++ quiz - Maths and acccuracy

Posted: May 9th, 2018, 2:29 pm
by Cuchulainn
Or even

[$]f(x) = cos(sin(sin(cos(x))))[$]

Good luck.
What's the derivative, T4A? At any point x of your choosing.
I'm getting a bit weary of communicating through the medium of English, it's sooh ambiguous.

Re: C++ quiz - Maths and acccuracy

Posted: May 9th, 2018, 3:40 pm
by Traden4Alpha
Or even

[$]f(x) = cos(sin(sin(cos(x))))[$]

Good luck.
What's the derivative, T4A? At any point x of your choosing.
I thought you specifically wanted the derivative of [$]f(x) = e^{e^{e^x}}[$] computed with the highest-possible performance and without restriction on using calculus (another unstated requirement). And my answer has higher performance than your answer but it's only for that specific f(x). Was this second f(x) meant to be a second, independent quiz question or was it related to the first one?

It now seems that this second example implies a change in the requirements from creating highest-possible-performance computation of the first derivative of a specific formula to a lower-performance but generalized computation of derivatives of various functions. Right? If you are seeking a general method that handles both [$]f(x) = e^{e^{e^x}}[$] and [$]f(x) = cos(sin(sin(cos(x))))[$] as well as other f(x), what are the bounds on f(x)?

How about [$]f(x) = 1/(sin(x))[$] evaluated at x=0.001? When I use your method of [$]f(z)[$] where [$]z = x + ih[$], with h = 0.001, and compute the imaginary part of [$]f(z)/h[$], I get f'(0.001) ≈ -499,999.833335 whereas the correct answer is 1,000,000. Is there a robust approach to picking h?