Congratulations Richard! From: "Richard Peters" <r.a.peters@student.tue.nl>

The divison algorithm is completely new, and this time it is fast (it now uses Knuth's algorithm). The code is also reorganised, which made it quite easy to build in support for GNU MP and CLN. When either of those two libraries is available, set BOOST_BIG_INTEGER_USE_GMP or BOOST_BIG_INTEGER_USE_CLN, and those libraries will be used to implement the basic arithmetic functions.

The new version is several thousand times faster then your previous version. There is still some room for improvement. The following timing results are for 10000 executions of following loop: //////////////////////////////// #ifdef _RB #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::rational<boost::big_integer> data_t; #elif _RL #include "boost/rational.hpp" typedef boost::rational<long long unsigned int> data_t; #elif _CR #include <cln/rational.h> #include <cln/rational_io.h> typedef cln::cl_RA data_t; #endif int main(int argc, char* argv[]) { for (int i=0;i<COUNTER;++i) { data_t tt = data_t(10000000); data_t ne1 = data_t( 2762) * tt + data_t(9706925); data_t de1 = data_t( 1441) * tt * tt + data_t(1518807) * tt + data_t(5855872); data_t e1 = ne1/de1; // 27629706925/144115188075855872 } return 0; } ///////////////////////////// set OPTFLAG="-O2" //////////////////////////// Rational of Big Integer using GMP: g++ $OPTFLAG -o c -I ~/boost/boost/include/boost-1_31/ c.cpp -DCOUNTER=$COUNT -l gmp -D_RB -D_GMP time ./c 0.570u 0.010s 0:00.62 93.5% 0+0k 0+0io 215pf+0w Rational of Big Integer using CLN g++ $OPTFLAG -o c -I ~/boost/boost/include/boost-1_31/ c.cpp -DCOUNTER=$COUNT -l cln -D_RB -D_CLN time ./c 0.280u 0.020s 0:00.40 75.0% 0+0k 0+0io 427pf+0w Rational of Big Integer g++ $OPTFLAG -o c -I ~/boost/boost/include/boost-1_31/ c.cpp -DCOUNTER=$COUNT -D_RB time ./c 1.610u 0.010s 0:01.88 86.1% 0+0k 0+0io 205pf+0w CLN Rational cln::cl_RA g++ $OPTFLAG -o c -I ~/boost/boost/include/boost-1_31/ c.cpp -DCOUNTER=$COUNT -l cln -D_CR time ./c 0.030u 0.010s 0:00.08 50.0% 0+0k 0+0io 423pf+0w Rational of unsigned long long g++ $OPTFLAG -o c -I ~/boost/boost/include/boost-1_31/ c.cpp -DCOUNTER=$COUNT -D_RL time ./c 0.030u 0.000s 0:00.09 33.3% 0+0k 0+0io 188pf+0w //////////////////////////// Note that Rational of Big Int of CLN has an order of magnitude cost vs. CLN Rational directly. For 1000 iterations runs, here are the top time consuming function calls. It seems like there is a lot of construction and destruction going on. First for Big Integer, then Big Integer with CLN, then Rational long long. Rational of Big Integer: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls us/call us/call name 66.67 0.02 0.02 72000 0.28 0.33 boost::integer_impl::detail::div_and_mod(std::vector<unsigned int, std::allocator 33.33 0.03 0.01 153000 0.07 0.07 std::vector<unsigned int, std::allocator<unsigned int> >::erase(__gnu_cxx::__norm 0.00 0.03 0.00 405000 0.00 0.00 std::vector<unsigned int, std::allocator<unsigned int> >::~vector() 0.00 0.03 0.00 266000 0.00 0.00 std::vector<unsigned int, std::allocator<unsigned int> >::operator=(std::vector<u 0.00 0.03 0.00 117000 0.00 0.00 std::vector<unsigned int, std::allocator<unsigned int> >::_M_fill_insert(__gnu_cx 0.00 0.03 0.00 109000 0.00 0.00 unsigned int* std::vector<unsigned int, std::allocator<unsigned int> >::_M_alloca 0.00 0.03 0.00 108000 0.00 0.00 std::vector<unsigned int, std::allocator<unsigned int> >::_M_insert_aux(__gnu_cxx 0.00 0.03 0.00 102000 0.00 0.00 std::allocator<unsigned int>::~allocator() 0.00 0.03 0.00 72000 0.00 0.00 std::__simple_alloc<unsigned int, std::__default_alloc_template<true, 0> >::alloc 0.00 0.03 0.00 59000 0.00 0.00 __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::alloca 0.00 0.03 0.00 58000 0.00 0.00 boost::integer_impl::equal(std::pair<std::vector<unsigned int, std::allocator<uns 0.00 0.03 0.00 48000 0.00 0.07 void boost::integer_impl::assign_from_integer<int>(int, std::pair<std::vector<uns 0.00 0.03 0.00 48000 0.00 0.13 void boost::big_integer_base::assign_from_integer<int>(int) 0.00 0.03 0.00 40000 0.00 0.33 boost::expression::expression<boost::expression::big_integer_tag>::operator%=(boo 0.00 0.03 0.00 40000 0.00 0.00 unsigned int* std::fill_n<unsigned int*, unsigned int, unsigned int>(unsigned int 0.00 0.03 0.00 35000 0.00 0.00 boost::big_integer_base::operator=(boost::big_integer_base const&) 0.00 0.03 0.00 33000 0.00 0.00 bool boost::expression::expression<boost::expression::big_integer_tag>::operator< 0.00 0.03 0.00 29000 0.00 0.00 boost::expression::do_div<boost::expression::expression<boost::expression::big_in Rational of Big Integer using CLN: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls us/call us/call name 33.33 0.01 0.01 48000 0.21 0.21 void boost::integer_impl::assign_from_integer<int>(int, cln::cl_I&) 33.33 0.02 0.01 40000 0.25 0.25 boost::expression::expression<boost::expression::big_integer_tag>::operator%=(bo 33.33 0.03 0.01 16000 0.62 1.46 boost::expression::expression<boost::expression::big_integer_tag> boost::gcd<boo 0.00 0.03 0.00 206000 0.00 0.00 cln::cl_I::operator=(cln::cl_I const&) 0.00 0.03 0.00 106000 0.00 0.00 cln::cl_gcobject::~cl_gcobject() 0.00 0.03 0.00 106000 0.00 0.00 cln::cl_I::~cl_I() 0.00 0.03 0.00 77000 0.00 0.00 boost::expression::expression<boost::expression::big_integer_tag>::~expression() 0.00 0.03 0.00 48000 0.00 0.00 void boost::big_integer_base::assign_from_integer<int>(int) 0.00 0.03 0.00 35000 0.00 0.00 boost::big_integer_base::operator=(boost::big_integer_base const&) 0.00 0.03 0.00 33000 0.00 0.00 bool boost::expression::expression<boost::expression::big_integer_tag>::operator 0.00 0.03 0.00 29000 0.00 0.00 boost::expression::do_div<boost::expression::expression<boost::expression::big_i 0.00 0.03 0.00 26000 0.00 0.00 boost::expression::expression<boost::expression::div<boost::expression::expressi 0.00 0.03 0.00 26000 0.00 0.00 boost::expression::binary_expression<boost::expression::expression<boost::expres 0.00 0.03 0.00 26000 0.00 0.00 boost::expression::div<boost::expression::expression<boost::expression::big_inte 0.00 0.03 0.00 26000 0.00 0.00 boost::expression::do_div<boost::expression::expression<boost::expression::big_i 0.00 0.03 0.00 26000 0.00 0.00 boost::expression::expression<boost::expression::div<boost::expression::expressi 0.00 0.03 0.00 26000 0.00 0.00 boost::expression::do_div<boost::expression::expression<boost::expression::big_i Long Long: % cumulative self self total time seconds seconds calls Ts/call Ts/call name 0.00 0.00 0.00 16000 0.00 0.00 unsigned long long boost::gcd<unsigned long long>(unsigned long long, unsigned long long) 0.00 0.00 0.00 4000 0.00 0.00 boost::rational<unsigned long long>::operator*=(boost::rational<unsigned long long> const&) 0.00 0.00 0.00 3000 0.00 0.00 boost::rational<unsigned long long>::operator+=(boost::rational<unsigned long long> const&) 0.00 0.00 0.00 1000 0.00 0.00 boost::rational<unsigned long long>::operator/=(boost::rational<unsigned long long> const&) 0.00 0.00 0.00 1 0.00 0.00 _GLOBAL__I_main 0.00 0.00 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int)

From: "Joel Young" <jdy@cs.brown.edu>

...

I made a simple program with some big numbers that demonstrate the speed difference: