Re: [boost] [xint] Boost.XInt formal review

Subject: Re: [boost] [xint] Boost.XInt formal review
From: Artyom (artyomtnk_at_[hidden])
Date: 2011-03-08 15:13:22

> >
> > - Move  Semantics:
> >
> >   It is not clear, and not  documented!
> 
> That's because it's presently not used. The code is all there  for it,
> but it's disabled because the future of Boost.Move was still up in  the
> air when I wrote it.
> 
> To turn it on, define BOOST_XINT_USE_MOVE  before including any XInt
> headers. [...]
> >         boost::xint::integer a,b;
> >        a =  100;
> >        b = boost::move(a);  
> >         // expect like swap(a,b) acts like a=b
> >         std::cout << a<<" " <<b <<  std::endl;
> >        // expect 0 100, get 100,  100
> >
> 
> I haven't tried it, but that code should work the way you  expect with
> the move code enabled.

Yes adding this define makes it work... So it would be good to have
it documented :-)

And this is really nice feature. Seems that integer is capable of
handling all possible styles: copy, copy-on-write, move.

Way to go!

+1

> >
> > This is the  weakest point of this library, the performance of too
> > many algorithms is  very low [...]
> 
> A lot of that may be due to pass-by-value instead of const  references,
> rather than the algorithms, which I've already corrected for the  next
> release. I'll be testing that soon, maybe today, along with the  CoW/move
> speeds.
> 

Not so sure because I've tried with cow turned on and off and results
were almost the same.

AFAIK xint uses "naive" multiplication algorithm and probably
some others.

For me it seems like O(f(n)) issues. Because the ratio
between GMP and Xint gets lower as numbers grow.

I'd suggest to take a look on algorithms that GMP and other use
and re-implement them.

> John Bytheway introduced  me to a
> new primality algorithm that I plan to add.

If you are talking about deterministic primality check (ASK)... Don't bother
too much, nobody uses them in reality and they have O(scary) complexity.
It is something like O(n^6) where n is number of digits...

So don't bother. It is the last thing that users would actually need.

> >
> > First problem that  should be solved are actually algorithms
> > complexities, I don't think it  is something too hard. Reading few
> > books and papers would guide a  strightforward direction to the
> > solution. [...]
> 
> I'll report on  the speed changes from the alterations I've already made
> as soon as I have  them. I don't want to check any code into Subversion
> until the review is over  (the reviews should all be of the same code),
> but I can make the updated code  available earlier if anyone wants it.
> 

I'd suggest you to create a small set of benchmarks of xint vs GMP
so you can see progress.

Regards
  Artyom