Как рассчитать (A * B)% C?

Question

Может кто-нибудь мне помочь, как рассчитать (A*B)%C, где 1<=A,B,C<=10^18 в C++, без большого числа, просто математический подход.

Answer 1

Off верхней части моей головы (не тщательно протестированы)

typedef unsigned long long BIG; 
BIG mod_multiply(BIG A, BIG B, BIG C) 
{ 
    BIG mod_product = 0; 
    A %= C; 

    while (A) { 
     B %= C; 
     if (A & 1) mod_product = (mod_product + B) % C; 
     A >>= 1; 
     B <<= 1; 
    } 

    return mod_product; 
} 

Это сложность O(log A) итераций. Вероятно, вы можете заменить большую часть из % условным вычитанием, чтобы получить большую производительность.

typedef unsigned long long BIG; 
BIG mod_multiply(BIG A, BIG B, BIG C) 
{ 
    BIG mod_product = 0; 
    // A %= C; may or may not help performance 
    B %= C; 

    while (A) { 
     if (A & 1) { 
      mod_product += B; 
      if (mod_product > C) mod_product -= C; 
     } 
     A >>= 1; 
     B <<= 1; 
     if (B > C) B -= C; 
    } 

    return mod_product; 
} 

Эта версия имеет только один длинное целое по модулю - это может быть даже быстрее, чем метод большого куска, в зависимости от того, как процессор реализует целое по модулю.

• Демо-версия: https://ideone.com/1pTldb - такой же результат, как у Якка.

Answer 2

Реализация (это) [http://stackoverflow.com/a/14859713/256138] стека переполнения ответ предыдущего:

#include <stdint.h> 
#include <tuple> 
#include <iostream> 

typedef std::tuple< uint32_t, uint32_t > split_t; 
split_t split(uint64_t a) 
{ 
    static const uint32_t mask = -1; 
    auto retval = std::make_tuple(mask&a, (a >> 32)); 
    // std::cout << "(" << std::get<0>(retval) << "," << std::get<1>(retval) << ")\n"; 
    return retval; 
} 

typedef std::tuple< uint64_t, uint64_t, uint64_t, uint64_t > cross_t; 
template<typename Lambda> 
cross_t cross(split_t lhs, split_t rhs, Lambda&& op) 
{ 
    return std::make_tuple( 
    op(std::get<0>(lhs), std::get<0>(rhs)), 
    op(std::get<1>(lhs), std::get<0>(rhs)), 
    op(std::get<0>(lhs), std::get<1>(rhs)), 
    op(std::get<1>(lhs), std::get<1>(rhs)) 
); 
} 

// c must have high bit unset: 
uint64_t a_times_2_k_mod_c(uint64_t a, unsigned k, uint64_t c) 
{ 
    a %= c; 
    for (unsigned i = 0; i < k; ++i) 
    { 
    a <<= 1; 
    a %= c; 
    } 
    return a; 
} 

// c must have about 2 high bits unset: 
uint64_t a_times_b_mod_c(uint64_t a, uint64_t b, uint64_t c) 
{ 
    // ensure a and b are < c: 
    a %= c; 
    b %= c; 

    auto Z = cross(split(a), split(b), [](uint32_t lhs, uint32_t rhs)->uint64_t { 
    return (uint64_t)lhs * (uint64_t)rhs; 
    }); 

    uint64_t to_the_0; 
    uint64_t to_the_32_a; 
    uint64_t to_the_32_b; 
    uint64_t to_the_64; 
    std::tie(to_the_0, to_the_32_a, to_the_32_b, to_the_64) = Z; 

    // std::cout << to_the_0 << "+ 2^32 *(" << to_the_32_a << "+" << to_the_32_b << ") + 2^64 * " << to_the_64 << "\n"; 

    // this line is the one that requires 2 high bits in c to be clear 
    // if you just add 2 of them then do a %c, then add the third and do 
    // a %c, you can relax the requirement to "one high bit must be unset": 
    return 
    (to_the_0 
    + a_times_2_k_mod_c(to_the_32_a+to_the_32_b, 32, c) // + will not overflow! 
    + a_times_2_k_mod_c(to_the_64, 64, c)) 
    %c; 
} 

int main() 
{ 
    uint64_t retval = a_times_b_mod_c(19010000000000000000, 1011000000000000, 1231231231231211); 
    std::cout << retval << "\n"; 
} 

Идея заключается в том, чтобы разделить ваши 64 разрядное целое число в пара 32-битных целых чисел, которые можно умножать на 64-битной земле.

Выражает a*b, как (a_high * 2^32 + a_low) * (b_high * 2^32 + b_low), сделать 4-кратное умножение (отслеживание 2^32 факторов, не сохраняя их в наших битах), то обратите внимание, что выполнение a * 2^k % c может быть сделана с помощью серии k повторов этой модели: ((a*2 %c) *2%c)... , Таким образом, мы можем взять этот 3-х элементный многочлен из 64-битных целых чисел в 2^32 и уменьшить его, не беспокоясь о вещах.

Дорогая часть - это функция a_times_2_k_mod_c (единственный цикл).

Вы можете сделать это много раз быстрее, если вы знаете, что c имеет более чем один высокий бит.

Вы могли бы вместо того, чтобы заменить a %= c с вычитанием a -= (a>=c)*c;

Doing как не все, что практично.

Live example