关于FNT乘法， 我想可能有点误会，想讨论的进来

无心人

7#里你说apfloat是$3*2^t$长度的变换
是不是因为他要三个DWORD宽度的数字，使得总双字数为三的倍数，才让你认为的？

因为这个长度的快速算法不如$2^t$的简单

liangbch

当然不是！
  
你看一下aspstruct.cpp的源代码，在apmul函数中有一行，
    n = rnd23up (trueasize + truebsize);
而  rnd23up（x） 的功能是求一个数n ,使得n>=x and n=2^t or (n=2^t*3)

在看tablesit.cpp 中的tablesixstepfnttrans 函数，包含下面的一段：
    if (nn == n2)
    {
        // Transform length is a power of two
        tablesixstepfnttrans2 (data, pr, isign, nn);
        return;
    }

    // Transform length is three times a power of two

另外， joey5491在 http://topic.csdn.net/t/20041010/17/3441530.html 说过

一般來說,   基本   FFT   算法的長度必須為   2^m,   稱為   Radix-2   FFT,   而   apfloat   的長度可以是   3*2^m,   其實是做了三個長度為   2^m   的   FFT,   然後利用   CRT   組合成   3*2^m   的結果   (或許以後有空的話,   我們來談談這個部分),   並且質數   p   的形式必須是   p   =   k*3*2^n.   

liangbch

你在数论变换简述中提到 M,N ,$\alpha $的选择，但那篇文章中提到M需为合数，但apfloat却说，M必须为质数，你能解释一下吗？

gxqcn

我认为 joey5491 上面那句是占不住脚的。

因为我曾实现过以 $p = 2^96 - 2^32 + 1 = 79 228 162 514 264 337 589 248 983 041$ 为模的 NTT，
此时因为 p 足够大，就完全避免了用 CRT（中国剩余定理）凑结果了，只需一次 NTT 就可以了，

而此时仍然可以采用 3*2^m 变换长度，虽然需 3 次长为 2^m NTT，但还是比一次长为 2^m+2 的变换划算。

可惜，以如此之大的模进行 NTT 经对比速度并不理想（大家都尝过大数处理进位的苦恼吧 ）。

无心人

$M$可以是合数
也可以是质数

质数情况下，选择$N, \alpha$容易选择而已
因为好多条件都是显然的了
比如$GCD(M, N)=1$

无心人

TO: GxQ

用CRT的唯一理由就是减少字长
apfloat把字长限定在32位内
这样就能避免中间过程的大数运算了啊

选择三个质数$p_1, p_2, p_3 < 2^32$则可证明所有的NTT过程都不涉及大数运算了啊
而且使用CRT最后还能凑出$y_i < p_1p_2p_3 < 2^96$的真实卷积结果来

==================================================
另外，再次强调，并不是说大的$M$其变换就比NTT+CRT复杂

诸位可看我给出的$M=2^1024+1, N=2048, \alpha=2$的例子
这个例子如果做乘法的数字恰好和该例子所能卷积的数字的规模差不多
则应该远比NTT+CRT简单快速

同意该观点

[ 本帖最后由 liangbch 于 2008-4-17 21:16 编辑 ]

gxqcn

我知道用CRT的缘由，
但我想测试这个特殊的素数模 p=2⁹⁶-2³²+1：指数“断点”（96、32、0）都恰好落在32的整数倍上，实在太诱人了。。。

无心人

我发一个新帖子
大家看下这个方法好不好？

无心人

你说的例子叫三项式变换

确实是诱人
不过其$\alpha, N$都是多少?

liangbch

12# 使用很大的模，模具有很少的bit1(求x % M 来得容易)

这个我也曾想过，的确。使用大的模可减少变换次数，甚至不用CRT. 选择适当的模，比如像费马数，求模是简单了，但序列中每一个元素的字长却会增加，计算2个数的模乘法时，需要更大的工作量，如此则反而不如使用3次变换，再应用CRT 来得实惠。