F***e
发帖数: 23 | 1 1. 几千年前，人们就发明了乘法。
2. 1960年，前苏联数学家科尔莫哥洛夫猜想：两个n位整数相乘的复杂度为O(n^2)。
3. 2021年，两位数学家提出了𝑂(𝑛log𝑛)复杂度算法。这是
否是最低复杂度，仍然不知道。
Integer multiplication in time 𝑂(𝑛log𝑛)
Annals of Mathematics
Pages 563-617 from Volume 193 (2021), Issue 2 by David Harvey, Joris van der
Hoeven
Abstract
We present an algorithm that computes the product of two n-bit integers in &
#119874;(𝑛log𝑛) bit operations, thus confirming a conjecture
of Schönhage and Strassen from 1971. Our complexity analysis takes
place in the multitape Turing machine model, with integers encoded in the
usual binary representation. Central to the new algorithm is a novel “
Gaussian resampling” technique that enables us to reduce the integer
multiplication problem to a collection of multidimensional discrete Fourier
transforms over the complex numbers, whose dimensions are all powers of two.
These transforms may then be evaluated rapidly by means of Nussbaumer’s
fast polynomial transforms. |
F***e
发帖数: 23 | 2 算法的关键思想是中国余数定理这一步：
reduce the integer multiplication problem to a collection of
multidimensional discrete Fourier transforms |
s******e
发帖数: 1751 | 3 Joris van der Hoeven 是ecole polytechnique的。这个学校是法国最好的应用科学研
究学院。里面出来的人大多数都很靠谱。
der
&
【在 F***e 的大作中提到】
: 1. 几千年前，人们就发明了乘法。
: 2. 1960年，前苏联数学家科尔莫哥洛夫猜想：两个n位整数相乘的复杂度为O(n^2)。
: 3. 2021年，两位数学家提出了𝑂(𝑛log𝑛)复杂度算法。这是
: 否是最低复杂度，仍然不知道。
: Integer multiplication in time 𝑂(𝑛log𝑛)
: Annals of Mathematics
: Pages 563-617 from Volume 193 (2021), Issue 2 by David Harvey, Joris van der
: Hoeven
: Abstract
: We present an algorithm that computes the product of two n-bit integers in &
|
g****t
发帖数: 31659 | 4 之前我在程序員版貼過這個結果。討論過一輪。
第二作者維護一個免費數學寫作軟件十幾二十年了。
我很早前
就知道他。
他的研究方向不是乘法。偶然發現的這個算法。
: 算法的关键思想是中国余数定理这一步：
: reduce the integer multiplication problem to a collection of
: multidimensional discrete Fourier transforms
【在 F***e 的大作中提到】
: 算法的关键思想是中国余数定理这一步：
: reduce the integer multiplication problem to a collection of
: multidimensional discrete Fourier transforms
|
T*******x
发帖数: 8565 | 5 这个我记得。
【在 g****t 的大作中提到】
: 之前我在程序員版貼過這個結果。討論過一輪。
: 第二作者維護一個免費數學寫作軟件十幾二十年了。
: 我很早前
: 就知道他。
: 他的研究方向不是乘法。偶然發現的這個算法。
:
:
: 算法的关键思想是中国余数定理这一步：
:
: reduce the integer multiplication problem to a collection of
:
: multidimensional discrete Fourier transforms
:
|
g****t
发帖数: 31659 | 6 這就叫好人有好報。你從軟件能看出來。這個人很有意思。
有空的可以考慮給他的軟件捧個場。gnu texmacs
: 这个我记得。
【在 T*******x 的大作中提到】
: 这个我记得。
|
F***e
发帖数: 23 | 7 这个算法不仅理论意义很大，而且很有应用价值。数据时代很大程度上靠数学，靠算法。
本质上，离散傅立叶变换是中国余数定理的一个特例，洋人都是认可的。
【在 g****t 的大作中提到】
: 這就叫好人有好報。你從軟件能看出來。這個人很有意思。
: 有空的可以考慮給他的軟件捧個場。gnu texmacs
:
:
: 这个我记得。
:
|
s******e
发帖数: 1751 | 8 FFT是一个比较复杂的算法，里面有很多理念。 常用的implementation 是Cooley-
Tukey，用递归，所以有O(nlgn)。
数学就是数学，不需要什么权威来认可。
特例这个词什么意思？全世界所有算法都是加法的特例？
法。
【在 F***e 的大作中提到】
: 这个算法不仅理论意义很大，而且很有应用价值。数据时代很大程度上靠数学，靠算法。
: 本质上，离散傅立叶变换是中国余数定理的一个特例，洋人都是认可的。
|
|
F***e
发帖数: 23 | 9 老兄，我说FFT了吗？自己不懂，不要瞎讲。不是一个层次，说了也不懂。
【在 s******e 的大作中提到】
: FFT是一个比较复杂的算法，里面有很多理念。 常用的implementation 是Cooley-
: Tukey，用递归，所以有O(nlgn)。
: 数学就是数学，不需要什么权威来认可。
: 特例这个词什么意思？全世界所有算法都是加法的特例？
:
: 法。
|
s******e
发帖数: 1751 | 10 你说的是dft?不用我来介绍dft和fft的关系吧。这些东西都是很简单的概念。
我没啥兴趣和你讲话。说句实话。你啥水平已经很清楚了。如果你觉得你自己很牛逼，
随你吧。
: 老兄，我说FFT了吗？自己不懂，不要瞎讲。不是一个层次，说了也不懂。
【在 F***e 的大作中提到】
: 老兄，我说FFT了吗？自己不懂，不要瞎讲。不是一个层次，说了也不懂。
|
