Частное и остаток для деления произведения больших целых чисел на большое целое

Question

long long signed  A, B, C;

или

long long unsigned A, B, C;

Мне нужно вычислить частное и остаток для выражения A * B / C, где A, B, C - большие целые числа, так что произведение A * B вызывает переполнение, а A < C и B < C. Запрещено использование чисел с плавающей запятой и использование сторонних библиотек. Как это можно сделать?

Answer 1

Выполнить умножение с произвольным большим целым числом действительно довольно просто: вы делаете то же самое, что и в школе, и делали это вручную на бумаге. Но вместо обработки десятичных чисел в базе 10 вы работаете с байтами или целыми числами.

Например:

A = 12340;
B = 56789;
aa = new byte[] { A/256, A%256 };
bb = new byte[] { B/256, B%256 };

Теперь вы можете перебирать массив и выполнять умножение меньшими шагами.

Answer 2

Остаток A*B/C равен произведению остатков A/C и B/C по модулю C снова.

// РЕДАКТИРОВАТЬ: Ups, не видел условия A<C,B<C.В этом случае попробуйте что-то вроде этого:

tmp = A;
for (var i = 1; i<=B; i++)
{
   if (tmp + A == overflow || tmp + A >= C)
      tmp -= C;
   tmp += A;
}

Полученный tmp должен быть искомым остатком.Это будет работать до тех пор, пока все входные данные будут положительными, и мы делаем это в подписанной ситуации.Возможно, это будет работать и для unsigned, хотя и не проверял.

Конечно, вам нужна какая-то необычная функция для проверки условия oveflow.

Что касается частного, вы можете простооцените A/C, а затем умножьте его на B, не так ли?

Answer 3

например, вот так:

typedef long long ll;

const ll base = 1000*1000*1000; // 10^9 for example, could be also 1<<32 
               // or smth convenient, the goal is to store
               // the numbers and a result in 'base'-based numerical system
               // to avoid overflow

pair<ll, ll> p1 = make_pair( A/base, A%base ); // store the numbers in 
pair<ll, ll> p2 = make_pair( B/base, B%base ); // 'base'-based numerical system

vector<ll> v1(4);
v1[ 0 ] = p1.second * p2.second;
v1[ 1 ] = p1.first * p2.second + v1[ 0 ] / base; v1[ 0 ] %= base;
v1[ 2 ] = v1[ 1 ] / base; v1[ 1 ] %= base;

vector<ll> v2(4);
v2[ 1 ] = p1.second * p2.first;
v2[ 2 ] = p1.first * p2.first + v2[ 1 ] / base; v2[ 1 ] %= base;
v2[ 3 ] = v2[ 1 ] / base; v2[ 2 ] %= base;

ll tmp = 0;
for( i = 0; i < 4; ++i )
{
    v1[ i ] = v1[ i ] + v2[ i ] + tmp;
    tmp = v1[ i ] / base;
    v1[ i ] %= base;
}

теперь v1 хранит значение A * B, представленное в базе 10 ^ 9.Остальное - тщательно выполнить его деление на C, что является довольно простой математической задачей:)

Answer 4

Вы должны разделить A и B на их верхнюю и нижнюю 32-битные части

A = Au * (1<<32) + Al
B = Bu * (1<<32) + Bl

(вычислите как Au=A>>32; Al=A&(1<<(32)-1;) и рассмотрите продукты этих частей отдельно:

A*B = Au*Bu * (1<<64) + (Au*Bl+Al*Bu) * (1<<32) + Al*Bl

Далее вы должны разделить каждое из этих слагаемых на C и накапливать частное и остаток (будьте осторожны, чтобы избежать переполнения!). В частности, Au * Bu> C невозможно из-за вашего начального требования.

Answer 5

Для умножения 32-битных чисел без 64-битной арифметики существует метод Schrage .Может быть, вы можете расширить его до 64-битного умножения.

Answer 6

Я считаю, что для начала следует использовать c / c ++ с gmp .gmp - это библиотека произвольной точности, в которой все эти операции реализованы для произвольной точности.Он работает с целыми числами и с плавающей точкой.

Редактировать: (без сторонних библиотек)

Мое второе, хотя об этом (после gmp) была первичная факторизация.Вам нужен алгоритм для этого.Вы создаете вектор с Afactorization, Bfactorization и Cfactorization, которые имеют список простых чисел факторизации.Затем вы проверяете простые числа A / B относительно простых в C и начинаете стирать их из вектора A / B и C.После того, как все они протестированы, вы умножаете все элементы вектора и делаете нормальное деление.