[Boost-commit] svn:boost r38577 - in sandbox/SOC/2007/bigint: boost/bigint libs/bigint/src

From: arseny.kapoulkine_at_[hidden]
Date: 2007-08-10 12:36:39

Author: zeux
Date: 2007-08-10 12:36:38 EDT (Fri, 10 Aug 2007)
New Revision: 38577
URL: http://svn.boost.org/trac/boost/changeset/38577

Log:
Fixed modmul
Text files modified: 
   sandbox/SOC/2007/bigint/boost/bigint/bigint_fft_multiplicator.hpp |     2 +-                                      
   sandbox/SOC/2007/bigint/libs/bigint/src/modmul_test.cpp           |    16 +++++++++++-----                        
   2 files changed, 12 insertions(+), 6 deletions(-)

Modified: sandbox/SOC/2007/bigint/boost/bigint/bigint_fft_multiplicator.hpp
==============================================================================
--- sandbox/SOC/2007/bigint/boost/bigint/bigint_fft_multiplicator.hpp	(original)
+++ sandbox/SOC/2007/bigint/boost/bigint/bigint_fft_multiplicator.hpp	2007-08-10 12:36:38 EDT (Fri, 10 Aug 2007)
@@ -33,7 +33,7 @@
                 return static_cast<uint32_t>(static_cast<uint64_t>(a) * b % prime);
         #else
                 int r = a * b - prime * static_cast<uint32_t>(inv_prime * static_cast<int>(a) * b);
-		r = (r < 0 ? r + prime : r);
+		r = (r < 0 ? r + prime : r > prime ? r - prime : r);
                 BOOST_ASSERT(static_cast<uint32_t>(r) == static_cast<uint32_t>(static_cast<uint64_t>(a) * b % prime));
                 return r;
         #endif

Modified: sandbox/SOC/2007/bigint/libs/bigint/src/modmul_test.cpp
==============================================================================
--- sandbox/SOC/2007/bigint/libs/bigint/src/modmul_test.cpp	(original)
+++ sandbox/SOC/2007/bigint/libs/bigint/src/modmul_test.cpp	2007-08-10 12:36:38 EDT (Fri, 10 Aug 2007)
@@ -8,25 +8,31 @@
  */
 
 #include <iostream>
+#include <boost/cstdint.hpp>
+
+using boost::uint32_t;
 
 #include "fft_primes.hpp"
 
 unsigned int modmul_native(unsigned int a, unsigned int b, unsigned int prime)
 {
-	return static_cast<unsigned int>(static_cast<unsigned __int64>(a) * b % prime);
+	return static_cast<unsigned int>(static_cast<boost::uint64_t>(a) * b % prime);
 }
 
 unsigned int modmul_fast(unsigned int a, unsigned int b, unsigned int prime, double inv_prime)
 {
         int r = a * b - prime * static_cast<unsigned int>(inv_prime * static_cast<int>(a) * b);
-	r = (r < 0 ? r + prime : r);
+	r = (r < 0 ? r + prime : r > prime ? r - prime : r);
         return r;
 }
 
 int main()
 {
-	const unsigned int step_a = 100;
-	const unsigned int step_b = 100;
+	const unsigned int step_a = 1000;
+	const unsigned int step_b = 1000;
+
+	std::cout << modmul_native(126026000, 1353842000, 2013265921) << std::endl;
+	std::cout << modmul_fast(126026000, 1353842000, 2013265921, 1.0 / 2013265921) << std::endl;
 
         for (int p = 0; p < 2; ++p)
         {
@@ -37,7 +43,7 @@
 
                 for (unsigned int a = 0; a < prime; a += step_a)
                 {
-			std::cout << ".";
+			if (a % 700000 == 0) std::cout << ".";
 
                         for (unsigned int b = 0; b < prime; b += step_b)
                         {