Re: [boost] Re: Uploaded Prime.zip

From: Stephen Nutt (snutt_at_[hidden])
Date: 2003-09-18 21:25:26

Thank Daniel.  I hadn't thought about not using the BOOST_STATIC_CONSTANT,
but using enums directly.  Makes a BIG improvement.  I'll update when I've
made the changes, and some others I have in mind.  (BTW, uses a little over
half the memory in half the time when used with another change I made!)

The square root template I agree is not optimised.  However this shouldn't
present a problem as only one square root is used for each prime candidate.
I was actually hoping to breaking both power and root out into a separate
file, perhaps adding a floating point version (not sure how feasible that
would be) so fractions and negative powers could be passed.

Stephen

----- Original Message ----- 
From: "Daniel Frey" <daniel.frey_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Thursday, September 18, 2003 9:22 AM
Subject: [boost] Re: Uploaded Prime.zip

> Stephen Nutt wrote:
> > I've uploaded Prime.zip to yahoo.  It contains two files.  The first one
>
> > Please send feedback.  If someone can figure out how to do this with
> > Fermat's little theorem, it may be possible to do even better when
> > generating prime numbers.
>
> I had a look at it and I have some concerns about the implementation. I
> think that speed is an issue as you cannot predict how a project is
> going to use your templates. Thus, you should attempt to make them as
> fast as possible. One thing that might be worth trying is this:
> http://tinyurl.com/nt06
>
> Another way to speed things up might be an optimized version for
> square_root, something like:
>
> // Warning: Untested!
> template< unsigned x > struct square_root
> {
> private:
>    enum {
>      v0 = ( x >= 1<<30 ) ? 1<<15 : 0,
>      v1 = v0 + ( ( x - v0*v0 >= 1<<28 ) ? 1<<14 : 0 ),
>      v2 = v1 + ( ( x - v1*v1 >= 1<<26 ) ? 1<<13 : 0 ),
>      v3 = v2 + ( ( x - v2*v2 >= 1<<24 ) ? 1<<12 : 0 ),
>      v4 = v3 + ( ( x - v3*v3 >= 1<<22 ) ? 1<<11 : 0 ),
>      v5 = v4 + ( ( x - v4*v4 >= 1<<20 ) ? 1<<10 : 0 ),
>      v6 = v5 + ( ( x - v5*v5 >= 1<<18 ) ? 1<<9 : 0 ),
>      v7 = v6 + ( ( x - v6*v6 >= 1<<16 ) ? 1<<8 : 0 ),
>      v8 = v7 + ( ( x - v7*v7 >= 1<<14 ) ? 1<<7 : 0 ),
>      v9 = v8 + ( ( x - v8*v8 >= 1<<12 ) ? 1<<6 : 0 ),
>      v10 = v9 + ( ( x - v9*v9 >= 1<<10 ) ? 1<<5 : 0 ),
>      v11 = v10 + ( ( x - v10*v10 >= 1<<8 ) ? 1<<4 : 0 ),
>      v12 = v11 + ( ( x - v11*v11 >= 1<<6 ) ? 1<<3 : 0 ),
>      v13 = v12 + ( ( x - v12*v12 >= 1<<4 ) ? 1<<2 : 0 ),
>      v14 = v13 + ( ( x - v13*v13 >= 1<<2 ) ? 1<<1 : 0 ),
>      v15 = v14 + ( ( x - v14*v14 >= 1<<1 ) ? 1<<0 : 0 )
>    };
>
> public:
>    enum {
>      value = v15,
>      remainer = x - value*value
>    };
> };
>
> This avoids recursions and unnecessary instantiations. You might want to
> run some benchmarks for it, keeping an eye on both the compile time and
> the memory used by the compiler.
>
> Regards, Daniel
>
> -- 
> Daniel Frey
>
> aixigo AG - financial training, research and technology
> Schloß-Rahe-Straße 15, 52072 Aachen, Germany
> fon: [phone], fax: [phone]
> eMail: daniel.frey_at_[hidden], web: http://www.aixigo.de
>
>
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost