Re: [boost] Name andNamespace forPotential BoostExtended Floating-Point

Subject: Re: [boost] Name andNamespace forPotential BoostExtended Floating-Point
From: John Maddock (boost.regex_at_[hidden])
Date: 2011-09-19 12:54:43

>> OK sounds like that might not be as simple as I'd hoped, will
>> investigate as I get time,
>
> Actually, it turns out it is simple if you use the trunk instead of 
> release version of Polygon.  I have directed_line_segment_concept in the 
> trunk with generic function:

I've started investigating this - although I got the code for this working, 
I couldn't find any documentation on directed_line_segments?

> If you replace pack.compute_intersection with 
> pack.compute_exact_intersection it will not do the lazy intersection 
> computation and you will get maximal usage of your bignum type.  You still 
> need to #include gmp_override.hpp and provide your own for other types.

Nod.

> Just specify your own bignum as the specialization of high_precision_type 
> for coordinate type int and your own conversion specialization to convert 
> it to int.
>
> Here is the expressions I use for computing the intersection point:
>        x_num = (x11 * dy1 * dx2 - x21 * dy2 * dx1 + y21 * dx1 * dx2 - y11 
> * dx1 * dx2);
>        x_den = (dy1 * dx2 - dy2 * dx1);
>        y_num = (y11 * dx1 * dy2 - y21 * dx2 * dy1 + x21 * dy1 * dy2 - x11 
> * dy1 * dy2);
>        y_den = (dx1 * dy2 - dx2 * dy1);
>        x = x_num / x_den;
>        y = y_num / y_den;
>
> As you can see, I'm not caching my temporaries, despite being concerned 
> about that sort of thing.  The reason is that lazy exact evaluation pushes 
> the use of high precision type down to one in a thousand or lower odds, so 
> I don't really care about the cost of getting the right answer in the 
> unlikely event that long double gave me the wrong answer, it just needs to 
> be right.  My concern about efficiency is more about getting the best 
> bignum library, not for my use case.

I tried this, as well as instantiating my version of the intersection 
function directly on the big-number-rational type.... but I saw pretty much 
no difference between mpq_class and my expression-template-enabled version. 
Investigating further, it seems that there are a lot of superfluous 
temporaries being created which completely swamp anything gained in 
evaluating complex expressions.  For example in compute_exact_intersection:

        dy2 = (high_precision)(he2.second.get(VERTICAL)) -
          (high_precision)(he2.first.get(VERTICAL));

What benefit are the typecasts here?  They create 2 additional temporaries 
(and there are quite a few of these statements), but add no further 
precision to the calculated result, unless, possibly the arguments are 
floating point types - even then it's questionable?

Then another bunch of typecasts:

x11 = (high_precision)(he1.first.get(HORIZONTAL));

which all create an extra temporary.  Presumably if type high_precision can 
be copy-constructed from the argument, it can have that argument assigned to 
it as well?  A clearer conceptual model would sort that one out I guess.

Then:

          x = x + (high_precision)0.5;
          y = y + (high_precision)0.5;

Only one temporary with value 0.5 is required, and maybe none at all if type 
high_precision supports mixed arithmetic with type double (that can be 
checked with the operator traits extension to type traits that should be in 
Trunk fairly soon - I hope!).

Then:

        if(x < (high_precision)x_unit) --x_unit;
        if(y < (high_precision)y_unit) --y_unit;

Again, if mixed comparisons are supported they're likely to be more 
efficient than a temporary creation.

Of course arguably internal caching could fix all this....

HTH, John.