Как рассчитать (время б) делится на C, используя только 32-битные целочисленные типы, даже если время B не соответствует такому типу
-
30-09-2019 - |
Вопрос
Рассмотрим следующее в качестве справочной реализации:
/* calculates (a * b) / c */
uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c)
{
uint64_t x = a;
x = x * b;
x = x / c;
return x;
}
Я заинтересован в реализации (в C или псевдокоде), который не требует 64-разрядного целочисленного типа.
Я начал зарисовать реализацию, которая контурирует, как это:
/* calculates (a * b) / c */
uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c)
{
uint32_t d1, d2, d1d2;
d1 = (1 << 10);
d2 = (1 << 10);
d1d2 = (1 << 20); /* d1 * d2 */
return ((a / d1) * (b /d2)) / (c / d1d2);
}
Но сложность состоит в том, чтобы выбрать значения для D1 и D2, который удается избежать переполнения ((A / D1) * (b / d2) <= uint32_max) и минимизировать ошибку всего расчета.
Есть предположения?
Решение
Я адаптировал алгоритм, размещенный Павел для unsigned int-ints (пропуская части, которые имеют дело с признаками). Алгоритм в основном Древнее египетское умножение из a
с фракцией floor(b/c) + (b%c)/c
(Слэш, обозначающий реальное деление здесь).
uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c)
{
uint32_t q = 0; // the quotient
uint32_t r = 0; // the remainder
uint32_t qn = b / c;
uint32_t rn = b % c;
while(a)
{
if (a & 1)
{
q += qn;
r += rn;
if (r >= c)
{
q++;
r -= c;
}
}
a >>= 1;
qn <<= 1;
rn <<= 1;
if (rn >= c)
{
qn++;
rn -= c;
}
}
return q;
}
Этот алгоритм даст точный ответ до тех пор, пока он соответствует 32 битам. Вы можете также вернуть остаток r
.
Другие советы
Самый простой способ преобразовать промежуточный результат к 64 битам, но, в зависимости от значения C, вы можете использовать другой подход:
((a/c)*b + (a%c)*(b/c) + ((a%c)*(b%c))/c
Единственная проблема в том, что последний термин все еще может переполнить большие значения c
. Отказ все еще думая об этом ..
Поиск дальше www.google.com/CodeSearch. Поднижает ряд реализаций, в том числе удивительного очевидного. Я особенно люблю обширные комментарии и хорошо выбранные имена переменных
INT32 muldiv(INT32 a, INT32 b, INT32 c)
{ INT32 q=0, r=0, qn, rn;
int qneg=0, rneg=0;
if (c==0) c=1;
if (a<0) { qneg=!qneg; rneg=!rneg; a = -a; }
if (b<0) { qneg=!qneg; rneg=!rneg; b = -b; }
if (c<0) { qneg=!qneg; c = -c; }
qn = b / c;
rn = b % c;
while(a)
{ if (a&1) { q += qn;
r += rn;
if(r>=c) { q++; r -= c; }
}
a >>= 1;
qn <<= 1;
rn <<= 1;
if (rn>=c) {qn++; rn -= c; }
}
result2 = rneg ? -r : r;
return qneg ? -q : q;
}
Сначала вы можете разделить A CONC, а также получить напоминание о разделении и умножить напоминание с B перед делением его по C. Таким образом, вы теряете только данные в последнем дивизионе, и вы получаете тот же результат, что и изготовление 64 битного подразделения.
Вы можете переписать формулу, подобную этой (где это целочисленное разделение):
a * b / c =
(a / c) * b =
(a \ c + (a % c) / c) * b =
(a \ c) * b + ((a % c) * b) / c
Убедившись, что A> = B, вы можете использовать большие значения, прежде чем они переполнены:
uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c) {
uint32_t hi = a > b ? a : b;
uint32_t lo = a > b ? b : a;
return (hi / c) * lo + (hi % c) * lo / c;
}
Другой подход будет петли добавления и вычитания вместо умножения и разделения, но это, конечно, много больше работы:
uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c) {
uint32_t hi = a > b ? a : b;
uint32_t lo = a > b ? b : a;
uint32_t sum = 0;
uint32_t cnt = 0;
for (uint32_t i = 0; i < hi; i++) {
sum += lo;
while (sum >= c) {
sum -= c;
cnt++;
}
}
return cnt;
}
Если B и C оба константах, вы можете рассчитать результат очень просто используя египетские фракции.
Например. y = a * 4/99 можно записать как
y = a / 25 + a / 2475
Вы можете выразить любую фракцию как сумму египетских фракций, как объяснено в ответах на Египетские фракции в C.
Наличие B и C, прикрепленное заранее, может показаться немного ограничением, но этот метод намного проще, чем общий случай, ответил другим.
Если B = 3000000000 => Qn = 3000000000, Qn * 2 будет переполнен. Поэтому я редактирую код Свен Марнача.
uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c)
{
uint32_t q = 0; // the quotient
uint32_t r = 0; // the remainder
uint32_t qn = b / c;
uint32_t rn = b % c;
while (a)
{
if (a & 1)
{
q += qn;
if (qn >= UINT32_MAX) {
cout << "CO CO" << endl;
}
r += rn;
if (r >= c)
{
q++;
r -= c;
}
}
a >>= 1;
qn <<= 1;
int temp = rn;
if (rn > INT32_MAX) {
// rn times 2: overflow
rn = UINT32_MAX;// rn
temp = (temp - INT32_MAX) * 2; // find the compensator mean: rn * 2 = UINT32_MAX + temp
qn++;
rn = rn - c + temp;
}
else {
rn <<= 1;
if (rn >= c)
{
qn++;
rn -= c;
}
}
}
//return r;
return q;
}
Я полагаю, есть причины, которые вы не можете сделать
x = a/c;
x = x*b;
здесь? И, возможно, добавить
y = b/c;
y = y*a;
if ( x != y )
return ERROR_VALUE;
Обратите внимание, что, поскольку вы используете целочисленное разделение, a*b/c
а также a/c*b
может привести к разным значениям, если c
больше, чем a
или b
. Отказ Также, если обе a
а также b
меньшие, чем c
Это не будет работать.