c++ - 理解 vector 乘法

标签 c++ algorithm vector

我必须在 C++ 中使用 vector 执行乘法运算,例如,要将数字 123 和 528 相乘,我必须将每个数字存储在一个 vector 中,然后将它们相乘。我的导师提供了乘法算法。以下段落的第一行可能看起来有点困惑,但我想让您知道,我正在努力重载运算符*,以使用 vector 在两个数字之间执行乘法。

ubigint::operator* 中的乘法通过分配一个新 vector 来进行,该 vector 的大小等于其他两个操作数的大小之和。如果 u 是大小为 m 的 vector ,v 是大小为 n 的 vector ,则在 O(mn)speed 中,对一个参数执行外部循环,对另一个参数执行内部循环,将新的部分乘积添加到乘积 p就像你用手一样。该算法可以在数学上描述如下:

p ←Φ   
for i ∈ [0, m):  
 c ← 0  
   for j ∈ [0, n):  
     d ← p_{i+ j} + u_iv_j + c  
     p_{i+ j} ← d % 10  
     c ← ceil(d÷10)  
  p_{i+n} ← c  

请注意,区间 [a,b) 指的是集合 {x|a ≤ x < b},即包含 a 但不包含 b 的半开区间。同理,C++中一对迭代器绑定(bind)一个区间。

问题是我不太明白这个算法是如何工作的。例如,u_iv_j 是什么?有人可以解决这个问题吗?

最佳答案

将您的算法视为对如何乘以大数的正式描述:

for i ∈ [0, m):                  # For every digit of the first number
   c ← 0                         # Initialize the carry
   for j ∈ [0, n):               # For every digit of the second number
     d ← p_{i+j} + u_i * v_j + c # Compute the product of the digits + carry + previous result
     p_{i+j} ← d % 10            # extract the lowest digit and store it
     c ← ceil(d÷10)              # carry the higher digits
 p_{i+n} ← c                     # In the end, store the carry in the
                                 # highest, not yet used digit

我遗漏了一些细节(操作顺序,......),但如果需要我可以添加它们。

编辑:为了阐明我的意思,我将展示代码对 56*12 的作用: p 初始化为 0

i = 0:                       # Calculate 6 * 12
  carry = 0
  j = 0:                     # Calculate 6 * 2
    d = p{0} + 6 * 2 + carry # == 0 + 12 + 0
    p{0} = d % 10            # == 2
    carry = ceil(d/10)       # == 1
  j = 1:                     # Calculate 6 * 1 + carry
    d = p{0} + 6 * 1 + carry # == 0 + 6 + 1
    p{1} = d % 10            # == 7
    carry = ceil(d/10)       # == 0
  p{2} = carry               # == 0
i = 1:                       # Calculate 5 * 12
  carry = 0
  j = 0:                     # Calculate 5 * 2
    d = p{1} + 5 * 2 + carry # == 7 + 10 + 0
    p{1} = d % 10            # == 7
    carry = ceil(d/10)       # == 1
  j = 1:                     # Calculate 5 * 1
    d = p{2} + 5 * 1 + carry # == 0 + 5 + 1
    p{2} = d % 10            # == 6
    carry = ceil(d/10)       # == 0
  p{3} = carry               # == 0

对于 i = 0,我们计算了 6 * 12 = 72,对于 i = 1,我们计算了 5 * 12 = 60。

由于5在第二位,我们实际计算出50 * 12 = 600。现在我们需要将结果相加(即72 + 600),这就是为什么我提到之前的值:在循环的第一次运行之后,72 存储在 p 中,要为此添加 600,我们只需将本地产品 u_i * v_j 添加到 p{i+j} 中的现有值 同时保留进位。

关于c++ - 理解 vector 乘法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44877412/

相关文章:

javascript - 将 C++ 函数传递给 emscripten 中的 javascript 函数

c++ - 如何告诉 lcov 忽略源文件中的行

c++ - 这个c++程序中栈是怎么一步步变化的?

c++ - O(N^2)最短路径算法

c# - 准确的 "Sieve of Erathostenes"在C#中判断BigInteger的素数

滚动应用于向量的子集

python - numpy中一维数组的乘法

C++ 读入一行字符串作为整数?

java - 归并排序的开放区间的中点

algorithm - 在数组中查找缺失整数的最有效方法