-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Christopher Kormanyos Sent: Friday, April 06, 2012 11:57 AM To: boost@lists.boost.org Subject: Re: [boost] [Review Request] Multiprecision Arithmetic Library
But let's face it, my O(N^2) is very slowwww for digits.
In your opinion, should I take a crack at this if I find a spare afternoon?
Maybe. My understanding is that FFT doesn't become viable until the digit count grows truely huge? Would the Karatsuba algorithm be viable sooner and help more users? My gut feeling is that the current implementation is perfectly fine up to a few hundred (and maybe a thousand?) decimal places, which will probably take care of most use cases.... well my use cases anyway!
In my previous unpublished work (mp_cpp, also using base-10^8), I tuned to the following: static const INT32 mp_elem_karatsuba_min = static_cast< INT32>(40); // Approx. 280 digits. static const INT32 mp_elem_fft_min = static_cast< INT32>(129); // Approx. 900 digits.
I've got a recursive Karatsuba template available in my catalog already. Maybe we should try it out. The FFT mentioned above was FFTW (a sadly non-BPL wonder of mankind) so a vanilla FFT would be, maybe, 2 or 3 times slower.
So maybe examples are a higher priority for now?
Yes, you are right. I just don't want to get into trouble with the community. Everyone wants to compute a million digits of pi, and they might get mad at us if boost can't do it.
But you're right below. We need to stop and get a work of high quality out there to the world---maybe improving it later, like in the fall of 2012.
Agreed - it needs user exposure.
In fact, as I told you and Paul Bristow (both of whom have helped so much in this project), I'm actually booked solid through summer.
I fully understand that. But I'd be willing work up the handful of examples that you mentioned if that would help (I think it would - I think novices need much more help). Novice views on whether they find the package useful to them would a (small part) factor in a review. Paul --- Paul A. Bristow, Prizet Farmhouse, Kendal LA8 8AB UK +44 1539 561830 07714330204 pbristow@hetp.u-net.com