貌似一种新的乘法快速计算方法已经提交论文，理论上可以达到大数乘法的效率极限。
文章链接：多项式乘法到快速傅里叶变换；此文介绍的非常详细，极力推荐。
文章链接：使用快速傅里叶变换计算大整数乘法；快速傅里叶变换，使用算法设计思想中的分治法，降低傅里叶变换的时间复杂度到 O(N logN)。
傅里叶变换，算法的时间复杂度还是 O(N2)。关键在于：直接进行离散傅里叶变换的计算复杂度是 O(N2)。快速傅里叶变换可以计算出与直接计算相同的结果，但只需要 O(N logN) 的计算复杂度。 N logN 和 N2 之间的差别是巨大的。例如，当 N = 106 时，在一个每秒运算百万次的计算机上，粗略地说，它们之间就是占用 30 秒 CPU 时间和两星期 CPU 时间的差别。
快速傅里叶变换的要点如下：一个界长为 N 的离散傅里叶变换可以重新写成两个界长各为 N/2 的离散傅里叶变换之和。其中一个变换由原来 N 个点中的偶数点构成，另一个变换由奇数点构成。这个过程可以递归地进行下去，直到我们将全部数据细分为界长为 1 的变换。
什么是界长为 1 的傅里叶变换呢？它正是把一个输入值复制成它的一个输出值的恒等运算。要实现以上算法，最容易的情况是原始的 N 为 2 的整幂次项，如果数据集的界长不是 2 的幂次时，则可添上一些零值，直到 2 的下一幂次。在这个算法中，每递归一次需 N 阶运算，共需要 log N 次递归，所以快速傅里叶变换算法的时间复杂度是 O(N logN)。

关键是把各位数字看成了多项式系数？如何把多项式表示法转换为点值表示法？
系数的数字都不是相等的，不规则变化的，与单位圆上均匀分布的点值不同，半径相等？
如何利用对称性，周期性？

不懂，大大的不懂！原理都不懂，咋变成程序？

好像明白了一点：
我们以两个 3 ( N = 3 ) 位数 a = 678 和 b = 432 的乘积来说明以上过程吧。
a = (678)'10 = 6x10^2 + 7x10^1 + 8x10^0
b = (432)'10 = 4x10^2 + 3x10^1 + 2x10^0
由此：
c = a x b = 10^4xc4 + 10^3xc3 + 10^2xc2 + 10^1xc1 + 10^0xc0
   = 10000x24 + 1000x46 + 100x65 + 10x38 + 1x16
   = 292896
如果按以上方法计算大整数的乘法，时间复杂度是 O(N^2)。
在我们的例子中，乘积 c = 292896，共 6 位数字，N 需要扩展到 2^3 = 8。那么，向量 {ai} 和向量 {bj} 如下所示：
{ a7, a6, a5, a4, a3, a2, a1, a0 } = { 0, 0, 0, 0, 0, 6, 7, 8 }
{ b7, b6, b5, b4, b3, b2, b1, b0 } = { 0, 0, 0, 0, 0, 4, 3, 2 }

ω^0~ω^7分别是1，0.7-0.7i，-i，-0.7-0.7i，-1，-0.7+0.7i，i，0.7+0.7i.
可见ω^1和ω^7是共轭的，ω^2和ω^6是共轭的，等，这就是对称性。
ω^0和ω^8是相等的，ω^4和ω^12是相等的，等，这就是周期性。

向量A0就是8，7，6依次乘以ω^0，再加起来得到21.
以此类推得到：
{ A7, A6, A5, A4, A3, A2, A1, A0 } = { 12.9+10.9i, 2+7i, 3.1-1.1i, 7, 3.1+1.1i, 2-7i, 12.9-10.9i, 21 }
{ B7, B6, B5, B4, B3, B2, B1, B0 } = { 4.1+6.1i, -2+3i, -0.1-1.9i, 3, -0.1+1.9i, -2-3i, 4.1-6.1i, 9 }

现在，将她们逐项相乘得到向量 {Ck}，即 { C7, C6, C5, C4, C3, C2, C1, C0 }
= { -13.6+123.4i, -25-8i, -2.4-5.8i, 21, -2.4+5.8i, -25+8i, -13.6-123.4i, 189 }

这样，我们就使用离散傅里叶变换和逆变换计算出了向量 {ai} 和向量 {bj} 的卷积向量 {ck}，如下所示：
{ c7, c6, c5, c4, c3, c2, c1, c0 } = { 0, 0, 0, 0, 24, 46, 65, 38, 16 }

这些两位数错位相加，就得到292896。

问题是如何利用对称性和周期性？使这个算法的时间复杂度由 O(N^2)，变成O(N logN)？

各位老师，请给与指点！谢谢！

[此贴子已经被作者于2020-9-5 21:53编辑过]

注意到（可以观察到）向量Ai和向量Bj，都有共轭复数，对称出现的。

由向量Ai和向量Bj，得到向量Ck仍然需要相乘？虽然向量Ck也有共轭复数，且是对称出现的。

还可注意到：3*7=21，9*21=189.
所以，可能是对应项相乘的。

希望指点，帮忙编成vb程序！谢谢！

还可注意到：3*7=21，9*21=189.
所以，可能是对应项相乘的，就是由向量Ai和向量Bj，得到向量Ck是对应项相乘的。

希望指点，帮忙编成vb程序！谢谢！

问题点数成了0？
希望老师指点！欢迎探讨和沟通！
谢谢指点！如果程序应许，我可以给您加分！

如下程序怎么不运行？如何用呢？

'VB版快速傅里叶变换模块
'模块说明
'pr(),pi()为输入序列的实部与虚部，fr(),fi()分别是输出序列的实部与虚部。
'数组长度为n, n=2^k.
'L为0时做正变换，为1时做反变换。

Public Sub kkfft(ByRef pr() As Double, _
ByRef pi() As Double, _
ByRef fr() As Double, _
ByRef fi() As Double, _
ByVal n As Integer, _
ByVal k As Integer, ByVal L As Integer)

Dim it As Integer
Dim m As Integer
Dim iis As Integer
Dim i As Integer
Dim j As Integer
Dim nv As Integer
Dim l0 As Integer
Dim p, q, s, vr, vi, poddr, poddi As Double
For it = 0 To n - 1
m = it
iis = 0
For i = 0 To k - 1
j = Int(m / 2)
iis = 2 * iis + (m - 2 * j)
m = j
Next
fr(it) = pr(iis)
fi(it) = pi(iis)
Next
pr(0) = 1#
pi(0) = 0#
p = 6.283185306 / (1# * n)
pr(1) = Cos(p)
pi(1) = -Sin(p)
If L <> 0 Then pi(1) = -pi(1)
For i = 2 To n - 1
p = pr(i - 1) * pr(1)
q = pi(i - 1) * pi(1)
s = (pr(i - 1) + pi(i - 1)) * (pr(1) + pi(1))
pr(i) = p - q
pi(i) = s - p - q
Next
For it = 0 To n - 2 Step 2
vr = fr(it)
vi = fi(it)
fr(it) = vr + fr(it + 1)
fi(it) = vi + fi(it + 1)
fr(it + 1) = vr - fr(it + 1)
fi(it + 1) = vi - fi(it + 1)
Next
m = n / 2
nv = 2
For l0 = k - 2 To 0 Step -1
m = m / 2: nv = 2 * nv
For it = 0 To (m - 1) * nv Step nv
For j = 0 To (nv / 2) - 1
p = pr(m * j) * fr(it + j + nv / 2)
q = pi(m * j) * fi(it + j + nv / 2)
s = pr(m * j) + pi(m * j)
s = s * (fr(it + j + nv / 2) + fi(it + j + nv / 2))
poddr = p - q
poddi = s - p - q
fr(it + j + nv / 2) = fr(it + j) - podd
fi(it + j + nv / 2) = fi(it + j) - poddi
fr(it + j) = fr(it + j) + poddr
fi(it + j) = fi(it + j) + poddi
Next
Next
Next
If L <> 0 Then
For i = 0 To n - 1
fr(i) = fr(i) / (1# * n)
fi(i) = fi(i) / (1# * n)
Next
End If
End Sub

如下是VB版快速离散傅立叶变换，能不能用?怎么用?

Public Function fft(ByRef Data() As Double) As Double()
    ReDim ffft(128, 2) As Double
    Dim length As Integer
    length = UBound(Data, 1) + 1
'    Dim numArray(length - 1, 2) As Double
      
    Dim index As Integer
    Dim num5 As Integer
    Dim num6 As Integer
    Dim num7 As Integer
    Dim num10 As Integer
    Dim num3 As Integer
    Dim num2 As Integer
    Dim num11 As Integer
    Dim num9 As Integer
    num9 = length
      
    Dim num8 As Integer
    num8 = CInt(Math.Log(CDbl(num9)) / Math.Log(2#))
      
    Dim numArray2(128) As Double
    Dim numArray3(128) As Double
    Dim numArray4(128) As Double
    Dim numArray5(128) As Double
    For index = 0 To num9 - 1
        numArray2(index) = Data(index)
        numArray3(index) = 0#
    Next
    Dim a As Double
    Dim num14 As Double
      
   num14 = 6.28318530717959 / CDbl(num9)
    index = 0
    While index < (num9 \ 2)
        numArray4(index) = Math.Sin(a)
        numArray5(index) = Math.Cos(a)
        a = a + num14
        index = index + 1
    Wend
    num7 = num9
    num3 = 1
    For num2 = 1 To num8
        num7 = num7 / 2
        num6 = 0
        For num11 = 1 To num3
            num10 = 0
            index = num6
            While index <= ((num7 + num6) - 1)
                num5 = index + num7
                a = numArray2(index) - numArray2(num5)
                num14 = numArray3(index) - numArray3(num5)
                numArray2(index) = numArray2(index) + numArray2(num5)
                numArray3(index) = numArray3(index) + numArray3(num5)
                If num10 = 0 Then
                    numArray2(num5) = a
                    numArray3(num5) = num14
                Else
                    numArray2(num5) = (a * numArray5(num10)) + (num14 * numArray4(num10))
                    numArray3(num5) = (num14 * numArray5(num10)) - (a * numArray4(num10))
                End If
                num10 = num10 + num3
                index = index + 1
           Wend
            num6 = (num6 + num7) + num7
        Next
        num3 = num3 + num3
    Next
    num5 = num9 \ 2
    For index = 1 To (num9 - 1)
        num6 = num9
        If num5 < index Then
            Dim num12 As Double
              
          num12 = numArray2(index)
            numArray2(index) = numArray2(num5)
            numArray2(num5) = num12
            num12 = numArray3(index)
            numArray3(index) = numArray3(num5)
            numArray3(num5) = num12
        End If
        num6 = num6 / 2
        Do While num5 >= num6
            num5 = num5 - num6
            num6 = num6 / 2
            If num5 = 0 Then
                Exit Do
            End If
        Loop
        num5 = num5 + num6
    Next
    For index = 0 To num9 - 1
        numArray(index, 0) = numArray2(index)
        numArray(index, 1) = numArray3(index)
        numArray(index, 2) = ((numArray2(index)) ^ 2# + (numArray3(index)) ^ 2#) ^ 0.5
    Next
   fft = numArray
End Function
默认了数组为128

原来的说明是：输出结果1维是实部，2维是虚部。