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: thijs_at_[hidden]
Date: 2012-01-24 05:05:55

On Jan 24, 2012, at 10:38 AM, John Maddock <boost.regex_at_[hidden]> wrote:

> Folks,
> 
> I'm continuing to add to the multiprecision arithmetic library in the sandbox (under "big_number"), and I've just added a Boost licensed fixed-precision integer type which on Win32 at least looks to be very competitive with GMP for reasonable numbers of bits (up to about 1024), see http://svn.boost.org/svn/boost/sandbox/big_number/libs/multiprecision/doc/html/boost_multiprecision/perf/integer_performance.html
> 
> However, as we all know there are lies damn lies and performance stats ;-) Plus the test results I have above ignore the effect of memory allocations (needed by libtommath and GMP, but not the fixed_int code - which in theory should make it faster still).  So I'd be really interested to put the type through it's paces with some real world code that really thrashes an extended precision integer type.  Any suggestions?  Anything in Boost?

The first thing I could think of is primality testing! Im not sure if it's doable with little effort, but perhaps it *is*.
Currently the fastest deterministic algorithm ( big O) is described in the paper below which describes an implementation of the algorithm. They ran the following performance test:

"Testing was conducted on the linux platform using kernel version 2.6.8 on a Pentium 4-M processor running at 1.8 GHz. The C++ compiler was GNU g++ version 3.3.5. The kernel, system libraries, and AKS implementation were all compiled with i686 optimizations enabled. Version 2.1.3 of LiDIA was used. NTL version 5.2 was used. Both LiDIA and NTL were compiled with support for GMP large integers."

http://teal.gmu.edu/courses/ECE746/project/F06_Project_resources/Salembier_Southerington_AKS.pdf

Cheers,
Thijs