Re: [boost] Looking for some "real world" extended precision integer arithmetic tests

Subject: Re: [boost] Looking for some "real world" extended precision integer arithmetic tests
From: John Maddock (boost.regex_at_[hidden])
Date: 2012-01-27 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 256-bit outperforms multiprecision fixed_int
> 256-bit 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 higher-order 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.