了解矢量乘法

我必须通过在C++中使用矢量来执行乘法运算，所以例如要将数字123和528相乘，我必须将每个数字存储在一个矢量中并将它们相乘。乘法算法由我的导师提供。以下段落的第一行可能看起来有点令人困惑，但我想让你知道我正在重载运算符*以通过使用向量执行两个数字之间的乘法运算。了解矢量乘法

ubigint :: operator *中的乘法是通过分配一个新的向量来实现的，该向量的大小等于其他两个操作数的大小之和。如果u是大小为m的矢量，v是大小为n的矢量，则以O（mn）速度对一个参数执行外部循环，对另一个参数执行内部循环，将新的部分产品添加到产品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 |一个≤X < B}，即，一个半开区间，包括但不包括b。以同样的方式，C++中的一对迭代器限定了一个时间间隔。

问题是我不清楚这个算法是如何工作的。例如，什么是u_iv_j ?.任何人都可以清楚这一点吗？

来源

2017-07-03 itachi_uchiha

我相信这意味着'u_i×v_j' –

你可能已经教过这种算法 - 但是以一种非正式的方式 - 当你很少，并已经使用过它几百次。 – molbdnilo

你的意思是什么“矢量乘法”？请定义或参考！你所说的与我所知的两件事都没有什么共同之处。他们没有连接到数字乘法。顺便说一句，你是混合数字和数字，你有没有注意到？ – Gangnus

认为你的算法，如您如何繁殖大量的正式描述：

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}中的现有值同时保留进位。

来源

2017-07-03 05:19:58

以前的结果是什么？ –

我编辑了答案来更详细地描述它。 –

谢谢......... –

了解矢量乘法

回答

相关问题