Boost logo

Boost :

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.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk