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)
{