Как бы вы рассчитали J в этой функции?

Question

рассмотрим функцию ниже, которая преобразует результат a * b в пару чисел i и j, где:

1. a, b, x, y являются целыми (предположим, что они всегда => 32-битные)
2. a и b равны <= n * m, где n = 10 ^ 3 и m = 10 ^ 5. n * m = BASE. </li>
3. a * b можно записать как i * BASE + j

Как бы вы вычислили j без использования каких-либо типов, больших чем int (на случай, если вы будете осторожны с переполнениями с целыми числами UB):

#include <iostream>
#include <cstdlib>

using namespace std;

int n = 1000, m = 100000;

struct N {
        int i, j;
};

N f(int a, int b) {
        N x;
        int a0, a1, b0, b1, o;
        a1 = a / n;
        a0 = a - (a1 * n); // a0 = a % n
        b1 = b / m;
        b0 = b - (b1 * m);  // b0 = b % m
        o = a1 * b1 + (a0 * b1) / n + (b0 * a1) / m;
        x.i = o;
        x.j = 0; // CALCULATE J WITH INTs MATH
        return x;
}

int main(int, char* argv[]) {
        int a = atoi(argv[1]),
        b = atoi(argv[2]);
        N x = f(a, b);
        cout << a << " * " << b << " = " << x.i << "*" << n*m 
             << " + " << x.j << endl;
        cout << "which is: " << (long long)a * b << endl;
        return 0;
}

Answer 1

Вы начали правильно, но потеряли сюжет из-за расчета o.Во-первых, мои предположения: вы не хотите иметь дело с любым целым числом больше n*m, поэтому взятие mod n*m - это мошенничество.Я говорю это, потому что, учитывая m > 2^16, я должен предположить, что int имеет длину 32 бита, что позволяет обрабатывать ваши числа без переполнения.

В любом случае.Вы правильно (я полагаю, поскольку цели n и m не указаны) написали:

a=a0 + a1*n (a0<n)
b=b0 + b1*m (b0<m)

Итак, если мы выполним математические вычисления:

a*b = a0*b0 + a0*b1*m + a1*b0*n + a1*b1*n*m

Здесь, a0*b0 < n*m, поэтому он является частью j, и a1*b1*n*m > n*m, поэтому он является частью i.Это два других термина, которые вам нужно снова разделить на два.Но вы не можете рассчитать каждый и взять mod n*m, так как это было бы обманом (согласно моему правилу выше).Если вы напишите:

a0*b1 = a0b1_0 + a0b1_1*n

Вы получите:

a0*b1*m = a0b1_0*m + a0b1_1*n*m

С a0b1_0 < n, a0b1_0*m < n*m, что означает, что эта часть переходит к j.Очевидно, что a0b1_1 переходит к i.

Повторите аналогичную логику для a1 * b0, и у вас есть три условия, которые нужно сложить для j, и еще три, чтобы сложить для i.

---

РЕДАКТИРОВАТЬ: Забыл упомянуть несколько вещей:

• Вам нужны ограничения a < n^2 и b < m^2, чтобы это работало.В противном случае вам нужно больше _i «слов».Например: a = a0 + a1*n + a2*n^2, ai < n.

• Окончательная сумма j может быть больше n*m.Вам нужно следить за переполнением (n*m - o < addend или аналогичной логикой и добавлять 1 к i, когда это происходит - при расчете j + addend - n*m без переполнения).

Answer 2

Я думаю, что ответ будет j = a0 * b0

(a*b)/(n*m) = (a/n) * (b/m)
            = (a1 + a0/n) * (b1 + b0/m)
            = a1*b1 + a1*b0/m + a0*b1/n + (a0*b0)/(n*m)

сейчас

o = a1*b1 + a1*b0/m + a0*b1/n

умножить обе стороны на n * m

a * b  = o * n*m  +  a0*b0

n * m является базовым

a * b  = o * BASE  +  a0*b0

j = a0*b0

QED