[Boost-commit] svn:boost r4143

From: zeux_at_[hidden]
Date: 2007-05-19 19:42:05

Author: zeux
Date: 2007-05-19 19:42:04 EDT (Sat, 19 May 2007)
New Revision: 4143
URL: http://svn.boost.org/trac/boost/changeset/4143

Log:
Resolved issues with conversion to numbers (did not need make_unsigned, fixed unit test), implemented <<, >> and pow for 64-bit type properly, investigated negative number behavior, todo changed accordingly

Text files modified: 
   sandbox/SOC/2007/bigint/boost/bigint/bigint_gmp.hpp             |    74 +++++++++++++++++++++++++++++++++++++-- 
   sandbox/SOC/2007/bigint/libs/bigint/test/bigint_simple_test.cpp |    12 +++++                                   
   sandbox/SOC/2007/bigint/libs/bigint/todo.txt                    |    14 +++++--                                 
   3 files changed, 90 insertions(+), 10 deletions(-)

Modified: sandbox/SOC/2007/bigint/boost/bigint/bigint_gmp.hpp
==============================================================================
--- sandbox/SOC/2007/bigint/boost/bigint/bigint_gmp.hpp	(original)
+++ sandbox/SOC/2007/bigint/boost/bigint/bigint_gmp.hpp	2007-05-19 19:42:04 EDT (Sat, 19 May 2007)
@@ -217,12 +217,46 @@
 
                 void lshift(const bigint_gmp_implementation& lhs, boost::uint64_t rhs)
                 {
-			mpz_mul_2exp(data, lhs.data, rhs);
+			unsigned long max_arg = (std::numeric_limits<unsigned long>::max)();
+
+            if (rhs <= max_arg)
+            {
+	            mpz_mul_2exp(data, lhs.data, static_cast<unsigned long>(rhs));
+	        }
+	        else
+	        {
+	            mpz_clear(data);
+	            mpz_init_set(data, lhs.data);
+
+    	        while (rhs > 0)
+	            {
+					unsigned long value = (rhs > max_arg) ? max_arg : static_cast<unsigned long>(rhs);
+	        	    mpz_mul_2exp(data, data, value);
+	            	rhs -= value;
+				}
+			}
                 }
 
                 void rshift(const bigint_gmp_implementation& lhs, boost::uint64_t rhs)
                 {
-			mpz_div_2exp(data, lhs.data, rhs);
+			unsigned long max_arg = (std::numeric_limits<unsigned long>::max)();
+
+            if (rhs <= max_arg)
+            {
+	            mpz_div_2exp(data, lhs.data, static_cast<unsigned long>(rhs));
+	        }
+	        else
+	        {
+	            mpz_clear(data);
+	            mpz_init_set(data, lhs.data);
+
+    	        while (rhs > 0)
+	            {	
+					unsigned long value = (rhs > max_arg) ? max_arg : static_cast<unsigned long>(rhs);
+	        	    mpz_div_2exp(data, data, value);
+	            	rhs -= value;
+				}
+			}
                 }
 
                 void inc()
@@ -274,8 +308,11 @@
                         
                         boost::uint64_t max_value = static_cast<boost::uint64_t>(-static_cast<boost::int64_t>((std::numeric_limits<T>::min)()));
                         
-			int count = data->_mp_size >= 0 ? data->_mp_size : -data->_mp_size; // abs() does not work on MSVC8
+			int count = -data->_mp_size; // we have a negative number
                         
+			if (GMP_NUMB_BITS >= sizeof(boost::uint64_t) * 8) // we're going to have problems with >>= down there - but the check is simple
+				return (count == 1 && max_value >= data->_mp_d[0]);
+				
                         for (int i = 0; i < count; ++i)
                         {
                                 if (max_value < data->_mp_d[i]) return false;
@@ -293,7 +330,10 @@
                         case -1: return false; // Negative numbers can't fit into unsigned types
                         }
                         
-			T max_value = (std::numeric_limits<T>::max)();
+			boost::uint64_t max_value = (std::numeric_limits<T>::max)();
+			
+			if (GMP_NUMB_BITS >= sizeof(T) * 8) // we're going to have problems with >>= wodn there - but the check is simple
+				return (data->_mp_size == 1 && max_value >= data->_mp_d[0]);
                         
                         for (int i = 0; i < data->_mp_size; ++i)
                         {
@@ -341,7 +381,31 @@
                 
                 void pow(const bigint_gmp_implementation& lhs, boost::uint64_t rhs)
                 {
-			mpz_pow_ui(data, lhs.data, rhs);
+			unsigned long max_arg = (std::numeric_limits<unsigned long>::max)();
+
+            if (rhs <= max_arg)
+            {
+	            mpz_pow_ui(data, lhs.data, static_cast<unsigned long>(rhs));
+	        }
+	        else
+	        {
+	            mpz_clear(data);
+	            mpz_init_set_ui(data, 1);
+
+				mpz_t temp;
+
+				mpz_init(temp);
+
+    	        while (rhs > 0)
+	            {	
+					unsigned long value = (rhs > max_arg) ? max_arg : static_cast<unsigned long>(rhs);
+	        	    mpz_pow_ui(temp, lhs.data, value);
+	        	    mpz_mul(data, data, temp);
+	            	rhs -= value;
+				}
+
+				mpz_clear(temp);
+			}
                 }
                 
                 void ldiv(const bigint_gmp_implementation& lhs, const bigint_gmp_implementation& rhs, bigint_gmp_implementation& remainder)

Modified: sandbox/SOC/2007/bigint/libs/bigint/test/bigint_simple_test.cpp
==============================================================================
--- sandbox/SOC/2007/bigint/libs/bigint/test/bigint_simple_test.cpp	(original)
+++ sandbox/SOC/2007/bigint/libs/bigint/test/bigint_simple_test.cpp	2007-05-19 19:42:04 EDT (Sat, 19 May 2007)
@@ -36,7 +36,7 @@
         b %= a;
         
         BOOST_CHECK_EQUAL(!(a / b), false);
-	BOOST_CHECK(a - b);
+	BOOST_CHECK(a);
 
         BOOST_CHECK_EQUAL(a * b, bigint("42258228219342334666689684483132205000478474"));
         BOOST_CHECK_EQUAL(!(a / b), 0);
@@ -115,6 +115,16 @@
         BOOST_CHECK_EQUAL(bigint("ffffffff", 16).to_number<unsigned int>(), 0xffffffff);
         BOOST_CHECK_EQUAL(bigint("7fffffff", 16).to_number<int>(), 0x7fffffff);
         BOOST_CHECK_EQUAL(bigint("-80000000", 16).to_number<int>(), -0x80000000);
+	
+	// 3 == 11
+	// -3 = 1....1101
+	//      0...01101
+	BOOST_CHECK_EQUAL((bigint("-3") | bigint("1101", 2)).str(2), "-11");
+	BOOST_CHECK_EQUAL((bigint("-3") & bigint("1101", 2)).str(2), "1101");
+	BOOST_CHECK_EQUAL((bigint("-3") ^ bigint("1101", 2)).str(2), "-10000");
+	
+	BOOST_CHECK_EQUAL(bigint("-1") << 5, -32);
+	BOOST_CHECK_EQUAL(bigint("-33") >> 3, -5); // 33 is 100001, -33 is 1....1011111, >>3 is 1...1011, which is complement for 101
 }
 
 int test_main( int argc, char* argv[] )

Modified: sandbox/SOC/2007/bigint/libs/bigint/todo.txt
==============================================================================
--- sandbox/SOC/2007/bigint/libs/bigint/todo.txt	(original)
+++ sandbox/SOC/2007/bigint/libs/bigint/todo.txt	2007-05-19 19:42:04 EDT (Sat, 19 May 2007)
@@ -71,11 +71,17 @@
 + proper 64-bit support for converting to bigint (implement one of suggestions given for the request at gmp devlist)
 Status: implemented
 
-* proper converting to numbers (including 64-bit)
-Status: implemented, but need Jeff's assistance with make_unsigned<T>
++ proper lshift, rshift and pow functions (work in case of large exponents/bit counts)
+Status: implemented
 
-- check semantics of bitwise and shift operations for negative numbers
-Status: needs investigation
++ bug fix: problems with unit tests (not all of can_convert_to pass)
+Status: fixed
+
++ proper converting to numbers (including 64-bit)
+Status: implemented
+
++ check semantics of bitwise and shift operations for negative numbers
+Status: investigated, bitwise and shift operations behave as if numbers were 2-complement (as expected).
 
 - what if there is not enough memory for the request - what happens then? Investigate.
 Status: needs investigation