你会如何计算j在这个函数中？

考虑低于该函数A * B的结果转换在几个数字i和j，其中：你会如何计算j在这个函数中？

的a，b，x，y是INT（假设他们总是=> 32位长的）
a和b是< = n * m，其中n = 10^3和m = 10^5。 n * m = BASE。
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; 
}

来源

2011-06-21 m0nst3r

这功课吗？没关系，如果是 - 只是让我们知道。 :) –

@taryn，看起来更像是一个采访问题 –

大声笑，编辑狂热:-D –

您开始正确，但是在计算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而不溢出）。

来源

2011-06-21 11:11:31 vhallac

嗯，我认为这个逻辑需要一个算法。 – m0nst3r

不是。识别组件的数学在那里。只要仔细地加上'a0 * b0'，'a0b1_0'和'a1b0_0'（注意溢出，就像我在回答结束时提示的那样），并且你有'j'。 – vhallac

我认为答案是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

来源

2011-06-21 11:27:23 CantGetANick

你好CantGetANick，尝试编译我给出的程序，它应该服从你所说的相同的数学运算。尝试在代码中设置x.j = a0 * b0，然后运行它./program 1234578 8754321。为什么是a0 * b0 31397538而不是92111538？我错过了一些东西.. – m0nst3r

好..这是因为在分区时失去了精度..数学是好的，但我们在计算a0时使用整数，b0 – m0nst3r

这个答案是错误的，因为'o'不一定是整数。（例如，尝试使用n = 1，m = 7，a = 3，b = 3的算法。） – Nemo

你会如何计算j在这个函数中？

回答

相关问题