你會如何計算j在這個函數中？

Question

考慮低於該函數A * B的結果轉換在幾個數字i和j，其中：

1. 的a，b，x，y是INT（假設他們總是=> 32位長的）
2. a和b是< = n * m，其中n = 10^3和m = 10^5。 n * m = BASE。
3. A * B可以爲我* BASE + 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