big_integer numeric error
I believe there is a numeric error in big_integer. I am working to isolate it to a single operation. I can find the error now because the library is fast enough to run one of my sims. I get a different value when running with rational<big_integer> then with any of these choices (which give identical results) rational<long long> rational<big_integer (cln)> rational<big_integer (gmp)> cln::cl_RA Not that it is much use but the wrong answers are: Inonsistent Value: 38485535445/562949953421312 6375930541/562949953421312 Consistent Value: 42780502741/562949953421312 10670897837/562949953421312 Again, I'll try to narrow down the exact point where things go wrong but it might take a while. Joel
From: Joel Young <jdy@cs.brown.edu>
I believe there is a numeric error in big_integer_0.3. I am working to isolate it to a single operation.
Ok. I have it isolated to a piece of test code: ///////////////////////////////////////////////////////////////// #include <iostream> #ifdef _CLN #define BOOST_BIG_INTEGER_USE_CLN #elif _GMP #define BOOST_BIG_INTEGER_USE_GMP #endif #include "boost/big_integer.hpp" #include "boost/rational.hpp" typedef boost::big_integer bi; typedef boost::rational<bi> data_t; // Main Program int main(int argc, char* argv[]) { data_t a = data_t(bi("3280993285"))/bi("281474976710656"); data_t b = data_t(bi("-2706319761"))/bi("140737488355328"); std::cout << (a - b) << '\n'; /* __correct__ values: 8693632807/281474976710656 __incorrect__ values: 4398665511/281474976710656 */ } ///////////////////////////////////////////////////////////////// If you compile the above code with cln or gmp support it gets the correct answer (checked with matlab and with double in C++) and if you compile it with plain old big_integer then it gets the wrong answer. Above was using gcc 3.3.2 on redhat 9 Joel
I have found the error, it's in the addition algorithm, line 93, default_impl.hpp. Swap these two lines: std::size_t n = std::min(u.size(), v.size()); w.resize(m, 0); so that it reads w.resize(m, 0); std::size_t n = std::min(u.size(), v.size()); then it all works correctly again (for now :) ) I'll try to come up with faster multiplication and division algorithms in the upcoming week, I'll upload a version of the library with the above error corrected when the faster versions of the algorithms are implemented. The division algorithm didn't contain the bugs of Knuth, I had already found them and gave a correct implementation. (well, at least with respect to _those_ bugs). best regards, Richard Peters From: "Joel Young" <jdy@cs.brown.edu>
I believe there is a numeric error in big_integer_0.3. I am working to isolate it to a single operation.
Ok. I have it isolated to a piece of test code:
On Thu, 13 May 2004 13:17:29 -0400 Joel Young <jdy@cs.brown.edu> wrote:
I believe there is a numeric error in big_integer. I am working to isolate it to a single operation.
What operations are you doing on the numbers? I read earlier that Richard reimplemented the division algorithm based on Knuth's algoithm. However, the division algorithm in TAOCP Vol 2, sec 4.3.1 has at least one bug (and I have a $2.56 check ;-). So, if it is anything to do with division, I guess Richard should look at which printing he used to get the algorithm, and also look at the errata (http://www-cs-faculty.stanford.edu/~knuth/all2.ps.gz) to make sure he has a correct definition of the algorithm, and a correct implementation.
From: Jody Hagins <jody-boost-011304@atdesk.com>
On Thu, 13 May 2004 13:17:29 -0400 Joel Young <jdy@cs.brown.edu> wrote:
I believe there is a numeric error in big_integer. I am working to isolate it to a single operation.
What operations are you doing on the numbers?
Rational addition so prolly a few divs. :-) See other post for code
I read earlier that Richard reimplemented the division algorithm based on Knuth's algoithm. However, the division algorithm in TAOCP Vol 2, sec 4.3.1 has at least one bug (and I have a $2.56 check ;-). So, if it
Yup. I just checked. It is a regression against big_integer-0.2. Joel
participants (3)
-
Jody Hagins -
Joel Young -
Richard Peters