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: Andrii Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2012-01-26 16:16:28

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.

Regards,
Andrii