我发现的大数表示法，请各位评价下

zeroieme

当单个数字不足够表示我们所需精度时，基本都是利用进位制多个单精度数连接。$\sum _{i=0}^n a_iM^i$ 假如是M进位，通常是设置每位$[0,M-1]$，再加设一个符号位。而我发现设置每位$[-\frac{M}{2},\frac{M}{2}-1]$计算更便利。（设M是偶数） 1、现在已经是64位机时代，1个bit的符号位或者浪费，或者令首位与后面其他位不同，而增加计算复杂性。 2、加减不用对比绝对值，可直接计算。按多项式原理，乘除法也能直接计算。 3、最重要的是降低了进位的消耗。 $[0,M-1]$的加法每位得数平均值$\frac{M-1}{2}$，$[-\frac{M}{2},\frac{M}{2}-1]$的加法平均值$-\frac{1}{M}$，进位几率是常规的1/2。 乘法差异更大，$[-\frac{M}{2},\frac{M}{2}-1]$的乘法每位得数平均值$\frac{1}{4}$。而且大数乘法就是卷积，常规表示$[0,M-1]$中段会产生$O(M^2n)$的大结果。用每位$[-\frac{M}{2},\frac{M}{2}-1]$，因为各位正负参半，积也如此，因此它们的和能相互抵消，不会过度增长。 4、除法竖式法直除不用试除检查余数。不过我知道牛顿法以后没用竖式法了。 这是我发现的方法，我只在C上用带符号运算实现了，数论变换做乘法实现了2¹¹位。没有汇编优化，不知道带符号运算与无符号运算速度有多大差异。 请各位大大评价一下。或者有前人做过类似工作让我参考一下。

gxqcn

乘法卷积要考虑极端情形（而不是平均情况），比如每位的值的都是$-M/2$，此时与通常的表达形式没有任何优势。 该计数法在输入输出时的转换将成问题。 而且算法中对进位/借位的处理将麻烦一些。

zeroieme

都是 -M/2，平方是M^2/4，依然比(M-1)^2有优势。 由于依然是M进制，转换就是超M/2进1。是O(n)的复杂度。 由于每位都是带符号数，直接统一为进位，借位归结为进负数。

gxqcn

M^2/4 与 (M-1)^2 仅1:4的关系，几乎没什么优势。 而表达同样大的整数，你的计数法则可能得多用一“位”。 感觉这种计数法对固定长度的大整数计算还可以， 对于动态的大整数计算，比如一个小规模整数减去一个超大规模整数，新算法并没带来什么好处。 如果当$M$是奇数时，某些公式可能看起来更美妙一些。

liangbch

ooura fft代码中求圆周率的运算采用类似的表示法，使得作FFT运算时，误差更小。不同意大数运算就是做卷积，只有大数的规模很大时，卷积运算才有优势，在数的规模相对较小时，3,4 Toom-Cook算法仍然是最佳选择。将每个单元 从 0 --> M-1 转为-M/2 --> M/2-1花不了多少时间，当需要FFT运算时，将每个单元转为-M/2 --> M/2-1 即可。

zeroieme

同样“位数”，[-M/2,M/2-1]能比[0,M-1]多表示2^(L-1)倍，假设每位字长L。 卷积是一种向量运算定义，FFT是计算卷积的方法之一。恰好大数乘法的定义和卷积一致。 倒过来看， Toom-Cook3,4也能作为小向量的卷积速算法。 极限状态几乎没什么优势，起码没有更慢。但这个极限的概率是多少？极限没什么优势，平均有上明显优势。 算了下每位乘法结果的分布状态 [0,M-1] $E=\frac{1}{m^2}(\sum _{i=0}^{m-1} \sum _{j=0}^{m-1} i j)=\frac{1}{4} (-1+m)^2$ $D=\frac{1}{m^2}(\sum _{i=0}^{m-1} \sum _{j=0}^{m-1} (i j-E)^2)=\frac{1}{144} (-5+12 m-2 m^2-12 m^3+7 m^4)$ [-M/2,M/2-1] $E=\frac{1}{m^2}(\sum _{i=-\frac{m}{2}}^{\frac{m-1}{2}} \sum _{j=-\frac{m}{2}}^{m\frac{m-1}{2}} i j)=\frac{1}{4}$ $D=\frac{1}{m^2}(\sum _{i=-\frac{m}{2}}^{\frac{m-1}{2}} \sum _{j=-\frac{m}{2}}^{m\frac{m-1}{2}} (i j-E)^2)=\frac{1}{144} (-5+4 m^2+m^4)$ 奇怪的Mathematica输出

showjim

也许是我看不懂，怎么看都是把简单的事搞复杂了，一点优势也没有

gxqcn

无符号数相加时，需要考虑上溢出问题； 有符号数相加时，还得考虑下溢出问题。 而比较、进借位的判断，是比较耗clock的。

G-Spider

32位机取31位或32位还是多一些。32位进位有些麻烦，要经常看CF等标志，这又是汇编擅长的，好处之一是表示的位数多了，并且隐含了取模运算。符号位还是单独抽出来比较妥当，有符号数相加时，既要考虑上溢又要考虑下溢。

liangbch

8# gxqcn 　　我来谈一下关于分支预测的话题。 　　当代CPU均采用pipeline来实现多级流水线，在当前指令的执行阶段，其后的指令，有的已经完成译码，有的已经完成取指等操作，所以顺序执行的指令速度很快，但一旦遇到条件转移，事情就比较复杂了。 　　早期的CPU(如8086)没有分支预测部件，所以在执行条件转移指令时，如不跳转则速度很快，如跳转则速度很慢，这是因为，当执行跳转指令时，pipeline中的所有内容必须被清除，已经取到的指令，已经完成的译码等操作都白干了。如果你查看8086参考手册，你会发现，对于条件转移指令，如不跳转则仅需4个周期，如跳转则需要16个周期，见本站链接：资料：Intel 和 AMD CPU 资料。 　　当前的CPU都有分支预测部件，CPU在执行每个分支指令(比较跳转指令对)时，会保存这个指令的跳转情况，当下次执行这条指令时，根据这个指令的跳转情况历史记录，执行跳转概率比较高的那个分支，这个分支的后续指令会提前进入pipeline，这就是分支预测。如果预测正确，则跳转指令的执行速度很快，和普通的指令速度相当。如果预测失败，则必须付出相当的代价。对于当前的CPU，依赖于具体的程序逻辑，分支预测的正确率会有所不同，不过平均起来，分支预测的正确率很高，按照intel的文档，当前的CPU分支预测的正确率一般可达90%以上。 　　分支有数据依赖分支和非数据依赖分支，对于后者，分支预测的正确率非常高，速度很快，但对于前者速度就相当的慢了。下面的举2个例子来说明。 例子1, 非数据依赖分支 C代码：

1. int sum(int *p, int len)
2. {
3. int s=0;
4. int i;
5. for (i=0;i<len;i++)
6. s+=len;
7. return s;
8. }

复制代码

下面是我写的对应的汇编子程序

2. _sum PROC NEAR
3. push ebx
5. mov ebx, DWORD PTR [esp+4+4] //ebx为p
6. mov edx, DWORD PTR [esp+4+8] //edx为len
7. xor eax, eax //eax 为返回值是s
8. test edx, edx
9. jle SHORT this_exit //len<0, 直接返回0, eax为返回值，这里eax=0
10. xor ecx, ecx //ecx 为循环变量i,初值为0
12. //循环部分
13. Loop_start:
14. mov edx, DWORD PTR [ebx+ecx*4] //edx 为p[ i ]
15. add eax, edx //s+= p[ i ]
16. inc ecx //i++;
17. cmp ecx, DWORD PTR [esp+4+8] // i<len?
18. jl Loop_start // i<len 则继续循环
20. this_exit:
21. pop ebx
22. ret 0
23. _sum ENDP

复制代码

在这个子程序中，共有2处比较跳转指令对 第1处是： 　　test edx, edx 　　jle SHORT this_exit //len<0, 直接返回0, eax为返回值，这 第2处是： 　　cmp ecx, DWORD PTR [esp+4+8] // i

2. int arrayAdd(int array1[], int array2, int len)
3. {
4. int i,sum,carry;
6. carry=0;
7. for (i=0;i<len;i++)
8. {
9. sum= array1[ i ]+ array2[ i ] + carry;
10. carry=0;
11. if (sum>=10000)
12. {
13. carry=1;
14. sum-=10000;
15. }
16. array1[ i ]=sum;
17. }
18. return carry;
19. }

复制代码我写的等价的汇编代码

1. _arrayAdd PROC NEAR
2. push esi
3. push edi
5. xor eax, eax ; eax：返回值carry
7. mov edx, DWORD PTR [esp+8+12] //[esp+8+12]： len
8. test edx, edx
9. jle SHORT this_exit //len<=0，则直接返回0
11. mov esi, DWORD PTR [esp+8+4] //esi: array1
12. mov edi, DWORD PTR [esp+8+8] //edi: array2
13. xor ecx,ecx //ecx=0: ecx：循环变量i，
14. xor edx,edx //edx=0：edx：carry
16. loop_start:
17. mov eax, dword ptr [esi+ecx*4] //eax =array1[ i ]
18. add eax, dword ptr [edi+ecx*4] //eax对应于sum，sum= array1[ i ]+array2[ i ]
19. add eax, edx //eax对应与sum, sum= array1[ i ]+array2[ i ]+carry
20. xor edx, edx //carry=0
22. cmp eax, 10000
23. jl SHORT next_comp
25. mov edx, 1 //carry=1
26. sub eax, 10000 //sum-=10000
28. next_comp:
29. mov DWORD PTR [esi+ecx*4], eax //array1[ i ]=sum
30. add ecx, 1 //i++;
32. cmp ecx, DWORD PTR [esp+8+12] // i<len?
33. jl SHORT loop_start //i<len 则继续循环
35. mov eax,edx //eax:为返回值
36. pop edi
37. pop esi
38. this_exit:
39. ret 0
40. _arrayAdd ENDP

复制代码

在这个函数/过程中，共有3处比较跳转指令对 第2处是： 　　cmp eax, 10000 　　jl SHORT next_comp 第3处是： 　　cmp ecx, DWORD PTR [esp+8+12] // i