Serving the Quantitative Finance Community

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

C++ quiz - Maths and acccuracy

December 3rd, 2015, 2:28 pm

QuoteOriginally posted by: CuchulainnQuoteOriginally posted by: ExSanQuoteOriginally posted by: CuchulainnHow many times is this loop executed?I would say it depends of the internal representation of aHow many times?It depends on the exact amount of round-off error in those first arithmetic operations but I'd guess about [51,54] or ∞ if the initial value of a is nonpositive.
 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

C++ quiz - Maths and acccuracy

December 3rd, 2015, 3:47 pm

QuoteOriginally posted by: Traden4AlphaQuoteOriginally posted by: CuchulainnQuoteOriginally posted by: ExSanQuoteOriginally posted by: CuchulainnHow many times is this loop executed?I would say it depends of the internal representation of aHow many times?It depends on the exact amount of round-off error in those first arithmetic operations but I'd guess about [51,54] or ∞ if the initial value of a is nonpositive.well done; 54
 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

C++ quiz - Maths and acccuracy

March 21st, 2016, 12:01 pm

Let's say you want to clamp a value v to ensure it is not outside the range [A,B]. Easy for normal numbers.But do we do when any of v, A,B (esp. v) can be NaN? Does it 'depends' v is like a process value.Saturation Arithmetic
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

C++ quiz - Maths and acccuracy

March 21st, 2016, 3:16 pm

QuoteOriginally posted by: CuchulainnLet's say you want to clamp a value v to ensure it is not outside the range [A,B]. Easy for normal numbers.But do we do when any of v, A,B (esp. v) can be NaN? Does it 'depends' v is like a process value.Saturation ArithmeticHmmm.... If I understand what you're asking, this may not be possible unless you are willing to assert that Min ≤ NaN ≤ Max. Where is NaN in the interval?One could construct an algebra that encompasses {[Min,Max], NaN} as a kind of bimodal set but one would need to define special code for the math involving the NaN values. For example:0*NaN => 0 (if Min ≤ 0 ≤ Max)0*NaN => Min (if 0 < Min)0*NaN => Max (if Max < 0)And there may be complex identities:NaN - Max + Min = MinNaN - Min + Max = MaxSome rules would depend on whether NaNs are generated by a wide range of input conditions (e.g., log() of any negative number) versus one very specific condition (a single point singularity).NaN - NaN => NaN or 0NaN/NaN => NaN or 1
 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

C++ quiz - Maths and acccuracy

March 21st, 2016, 4:06 pm

QuoteOriginally posted by: Traden4AlphaQuoteOriginally posted by: CuchulainnLet's say you want to clamp a value v to ensure it is not outside the range [A,B]. Easy for normal numbers.But do we do when any of v, A,B (esp. v) can be NaN? Does it 'depends' v is like a process value.Saturation ArithmeticHmmm.... If I understand what you're asking, this may not be possible unless you are willing to assert that Min ≤ NaN ≤ Max. Where is NaN in the interval?One could construct an algebra that encompasses {[Min,Max], NaN} as a kind of bimodal set but one would need to define special code for the math involving the NaN values. For example:0*NaN => 0 (if Min ≤ 0 ≤ Max)0*NaN => Min (if 0 < Min)0*NaN => Max (if Max < 0)And there may be complex identities:NaN - Max + Min = MinNaN - Min + Max = MaxSome rules would depend on whether NaNs are generated by a wide range of input conditions (e.g., log() of any negative number) versus one very specific condition (a single point singularity).NaN - NaN => NaN or 0NaN/NaN => NaN or 1Indeed. Here is the linkI do not agree with the number of function arguments. See template<typename V> V clamp ( V val, V lo, V hi );Side effects here?I would prefer this below and + a well-defined contract.
Last edited by Cuchulainn on March 20th, 2016, 11:00 pm, edited 1 time in total.
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

C++ quiz - Maths and acccuracy

March 21st, 2016, 10:18 pm

Side effects indeed! What if hi < lo?Will the template version maintain the clamp automatically as arithmetic operations are done? That page of saturation arithmetic implies that clamping occurs after each operation.
 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

C++ quiz - Maths and acccuracy

March 22nd, 2016, 7:54 am

QuoteOriginally posted by: Traden4AlphaSide effects indeed! What if hi < lo?Will the template version maintain the clamp automatically as arithmetic operations are done? That page of saturation arithmetic implies that clamping occurs after each operation.Looks like big issue with the C++11 committee QuoteC++17 clamp() was voted in without clear preconditions. I had food poisoning during the review. WHEN THE CAT?S AWAY, THE MICE WILL PLAY. See this
Last edited by Cuchulainn on March 21st, 2016, 11:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

C++ quiz - Maths and acccuracy

March 22nd, 2016, 1:03 pm

It's a good test case to see if C++ contracts can be formalized a bit. Seems to be a new area of discourse for C++. Kind of ad-hoc.cfDesign by Contract If you call this procedure with a NaN argument for a compiler that applies IEEE 754 semantics, and monitor contracts at run time for testing and debugging, the execution will report a contract violation. This is very difficult for a programmer to accept.
Last edited by Cuchulainn on March 22nd, 2016, 11:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: C++ quiz - Maths and acccuracy

August 29th, 2016, 8:29 am

Regarding distributions in <random>, drawing variates boils down to solving an integral equation such as
y = cdf(dist, x) where 0 < y < 1 (could be uniformly generated or chosen as a quantile value), dist is some distribution and x has to be found.

1. It is not clear how C++11 does the numerical inversion (Newton, whatever). So we don't know what the performance is without numerical testing. What is needed is something like 'we get a accuracy of 1.0e-6 in three iterations using Steffensen's method ...".
2. <random> does not support quantiles.

feature or design flaw?
 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: C++ quiz - Maths and acccuracy

November 17th, 2016, 3:56 pm

Are all ill-posed numerical processes caused by floating-point finite precision?
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Re: C++ quiz - Maths and acccuracy

November 17th, 2016, 4:34 pm

Are all ill-posed numerical processes caused by floating-point finite precision?
Hmmmm... It depends on how you define ill-posed.

1. Some iterative solutions may produce gross inaccuracies due to poorly defined stopping conditions. Just because the most recent terms are less than some threshold of accuracy does not imply the solution is within some threshold of accuracy.

2. Measurement inaccuracy (as distinct from measurement precision) can certainly propagate poorly. Even if one uses infinite precision representations of the numbers, noise in those numbers

3. Processes linked to empirical data can be ill-posed if the historical sample size is small relative to the counterfactual future sample size (e.g., predicting 1-in-a-million occurrences from only 1000 data points).

4. Finally, there's the issue of model error especially for models that contain singularities or restricted ranges. Is the log-normal model "ill-posed" for interest rates than may be negative?
 
User avatar
Cuchulainn
Topic Author
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: C++ quiz - Maths and acccuracy

November 17th, 2016, 4:49 pm

 I am using precise mathematical terminology .. it is the opposite of well-posed.
https://en.wikipedia.org/wiki/Well-posed_problem

The points 1 to 4 are relevant but are probably tangential to the topic. A problem can be ill-posed on paper and/or in the finite computed. Venn diagram? How many problems disappear in an infinite computer?

To reduce scope, take the example of numerical differentiation  A-Z and then let the discussion drift in different directions, maybe.
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Re: C++ quiz - Maths and acccuracy

November 17th, 2016, 5:22 pm

 I am using precise mathematical terminology .. it is the opposite of well-posed.
https://en.wikipedia.org/wiki/Well-posed_problem

The points 1 to 4 are relevant but are probably tangential to the topic. A problem can be ill-posed on paper and/or in the finite computed. Venn diagram? How many problems disappear in an infinite computer?
#4 fits your definition of ill-posed in that the solution may not exist for real-world parameter values with the wrong model.

There's also at least two definitions of "infinite computer": infinite precision and infinite clock speed. A very slowly-converging series may be solvable on a finite-precision computer as long as it has near-infinite-clock speed. Or, a very simple equation may be solvable on a finite-clock speed computer but require near-infinite precision.

I'd also note that your cited definition is very imprecise! On the one had it asserts that existence, uniqueness, and continuity are sufficient properties. But then it says ill-conditioned means "that a small error in the initial data can result in much larger errors in the answers" which seems to imply that any function with a first derivative greater than 1 is ill-conditioned.

P.S. Are NP complexity problems ill-posed?
 
User avatar
outrun
Posts: 4573
Joined: January 1st, 1970, 12:00 am

Re: C++ quiz - Maths and acccuracy

November 17th, 2016, 8:36 pm

The NP class is well defined, it's an abstract class, and some members have been identified:
NP is the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs. More precisely, these proofs have to be verifiable by deterministic computations that can be performed in polynomial time
The trick is to deliver that deterministic polynomial time computations and proof that it always gives te correct "yes" answer. If you can't then you can't claim that a problem is in NP. If might be.. but maybe it's co-NP, or one of 1200 other complexity classes!
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Re: C++ quiz - Maths and acccuracy

November 17th, 2016, 11:58 pm

What's interesting about NP problems is it seems likely that they can be quickly solved by a quantum computer. Yet I would think one could emulate the "simultaneously compute f(x) for all combinatoric states" using superposition in the quantum system by cleverly encoding all states in very long bit string that is then run through the solution checker.