Re: Big integer library

From: Richard Peters (r.a.peters_at_[hidden])
Date: 2004-05-01 05:40:39

From: "Joel Young" <jdy_at_[hidden]>
>
> Richard,
>
> From: "Richard Peters" <r.a.peters_at_[hidden]>
> > I managed to get the code to compile by adding 'explicit' to the
constructor
> > on line 132 of big_integer.hpp.
>
> That fix worked, in that my code compiles and runs.  The catch is now
> that the code is at least two orders of magnitude slower using
> boost::rational<boost::big_integer> for the core data_t vs using
> cln::cl_RA
>
> if I run using double as the data_t my alg takes 0.14 seconds cpu.  with
> cln::cl_RA it takes 90 seconds cpu, with
> boost::rational<boost::big_integer> it is taking more than 40 minutes
> and is still running (less than 1/3 complete).  I'll let it run through
> lunch, and then if it is still churning, I'll break it and check if it
> is stuck in a loop.
>
> I am working with numbers extremely close to zero so I can't challenging
> problems for exact solutions with boost::rational<long long> to get
> a timing comparison to see if rational is the bottleneck or big_integer.
>
> The work done up to the point where the running program is stuck at now
> checks out as exactly correct.
>
> Joel

I guess you can't use boost::rational<cln::cl_I> for comparison here?
I noticed that my division algorithm can be quite slow in some instances.
When dividing an integer by another, it first makes a guess and then starts
subtracting in a loop (around line 318 in big_integer_impl.hpp). It should
refine its first guess in a more subtle way, but implementing that is still
a todo item. I'll let you know when it is done.
Besides from that, the rest of the code also hasn't seen much optimization
yet, so the problem may be somewhere else.

best regards,

Richard Peters