
Boost : 
Subject: Re: [boost] Looking for some "real world" extended precision integer arithmetic tests
From: John Maddock (boost.regex_at_[hidden])
Date: 20120127 04:43:40
> John,
>
> Benchmark description follows (test code and results in the attachments):
>
> History:
> Voronoi diagram predicates use 256bit signed int type in case of voronoi
> of
> points and 4096bit signed int in case of voronoi of segments. This
> benchmark was run only for the point inputs.
> Input coordinates for the voronoi algorithm are from int32 domain.
> Fixed_int type was used only to compute center's of the inscribed circles
> and was not used to store any algorithm intermediate values.
> Voronoi fixed_int is not a complete integer type (it doesn't provide all
> the integer operations, just those required by the voronoi algorithm).
>
> Preconditions:
> Before running benchmark I made sure that output generated with your
> fixed_int and with mine implementation is completely the same over a set
> of
> 30000 random input data sets.
>
> Bencmark results (time in seconds per test):
>
> *Using voronoi extended_int256 type*:
>  Number of points  Number of tests  Time per one test 
>  10  10000  0.000038 
>  100  1000  0.000621 
>  1000  100  0.006990 
>  10000  10  0.073000 
>  100000  1  0.783000 
>
> *Using voronoi extended_int4096 type*:
>  Number of points  Number of tests  Time per one test 
>  10  10000  0.000038 
>  100  1000  0.000621 
>  1000  100  0.007130 
>  10000  10  0.074500 
>  100000  1  0.795000 
>
> *Using multiprecision type mp_int256_t:*
>  Number of points  Number of tests  Time per one test 
>  10  10000  0.000098 
>  100  1000  0.001720 
>  1000  100  0.019230 
>  10000  10  0.199800 
>  100000  1  2.045000 
>
> *Using multiprecision type mp_int512_t:*
>  Number of points  Number of tests  Time per one test 
>  10  10000  0.000238 
>  100  1000  0.004299 
>  1000  100  0.047770 
>  10000  10  0.491500 
>  100000  1  5.023000 
>
> *Using multiprecision type mp_int1024_t:*
>  Number of points  Number of tests  Time per one test 
>  10  10000  0.000686 
>  100  1000  0.012558 
>  1000  100  0.139440 
>  10000  10  1.428000 
>  100000  1  14.373000 
>
> Conclusions:
> 0) The main reason vornoi fixed_int outperforms multiprecision fixed_int
> is
> that it doesn't operate with leading bytes if those are not set (correct
> me
> if I'm wrong).
> 1) Performance of the voronoi fixed_int type is almost independent on the
> memory allocated for it.
> 2) Performance of the multiprecision fixed_int type strongly correlates
> with the memory allocated for it.
> 3) Voronoi fixed_int 256bit outperforms multiprecision fixed_int
> 256bit 2.5 times. Actually this number is even bigger as it doesn't
> substract time used by the other parts of the algorithm.
Well that's disappointing then ! :(
Certainly looks like lazy evaluation of higherorder limbs is a big win in
this case  I'm guessing that most operations use only one or two limbs, and
just every now and then you get a true big number?
Thanks, John.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk