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

G-Spider

10# liangbch
如果将
if (sum>=10000)
  {
   carry=1;
    sum-=10000;
   }
转化成总是执行的等效形式，会不会好一点呢。
比如，以2^B-1 为模，可以使用移位和掩码。

liangbch

　　使用不同的进制，效率会有差异。需要仔细权衡。
　　在当前的32位计算机，$R=2^32$可能是最直接的选择，如用高级语言处理进位处理就麻烦很多，使用汇编语言做长整数加法计算时，可使用带进位的加法指令ADC,但ADC指令比ADD慢很多。这种表示法，虽然节省空间，使得数的长度变短，运算次数减少，但进位和规约须增加额外的成本。我个人不推荐。
　　采用$2^31$为基，对于大数加法来算可使用移位和掩码求得本位和进位。
　　由于大数乘法是大数运算的核心（加减法的复杂度较小,可忽略, 乘法也是除法和开方运算的基础），因此，基于运算速度的考虑，进制的选择主要考虑的大数乘法的效率。采用$2^31$进制，每4次乘积的累加就需要一次规约运算，个人觉得这个进制仍然偏大。我建议，大数的表示宜采用$2^30$进制和$10^9$进制，这样，运算次数和规约/进位处理得到一个好的平衡。
　　另外，即使采用$10^k$进制，也有不用分支的进位处理办法，可使用汇编语言编程消除分支，只是比$2^K$进制更复杂些。

G-Spider

"ADC指令比ADD慢很多"  ，我查了一份文档，没有看出慢。http://bbs.chinaunix.net/thread-2133668-1-1.html

liangbch

你可能没有做过类似的编程，没有切实的感受。ADC指令确实比ADD慢多了。你的那个手册是旧的，不适合当前主流的CPU.  关于奔腾以后的cpu，其指令周期等数据请参考instruction_tables.pdf, 692K,更新时间2008-1-14.
文件开头写着。
Lists of instruction latencies, throughputs and microoperation
breakdowns for Intel and AMD CPU's
By Agner Fog. Copenhagen University College of Engineering.
Copyright © 1996 - 2008. Last updated 2008-01-14.

和执行时间有关的参数有2个，Additional latency  (额外的延时，越小越好）和 Reciprocal throughput (吞吐量的倒数，越小越好）。

intel P4 CPU
ADD  r,r 的值 0.5-1,0.25
ADC  r,r 的值 0, 6

intel core2 CPU
ADD  r,r 的值 1, 0.33
ADC  r,r 的值 2, 2

这意味者，对于P4，
   每个周期可以执行4条Add指令，0.5-1个周期后可以得到结果。
   每6个周期可以执行1条AdC指令，指令执行后，可立即得到结果。

由上表可知，对于core2CPU， ADD 指令的吞吐量是ADC的6倍，2/0.33.

gxqcn

instruction_tables.pdf 源于 optimization_manuals.zip，最近更新日期为 2011-01-30

似乎在 AMD CPU 上，ADC/ADD 指令周期差距没有 Intel CPU 的那么大。

另，对于$10^k$进制，怎样用汇编编程消除分支？

G-Spider

instruction_tables.pdf 源于 optimization_manuals.zip，最近更新日期为 2011-01-30

似乎在 AMD CPU 上， ADC/ADD 指令周期差距没有 Intel CPU 的那么大。

另，对于10^k进制，怎样用汇编编程消除分支？
gxqcn 发表于 2011-4-2 15:57

或许有更好的方法。

1. _asm
   
2.      {
   
3.        xor  eax,eax
   
4.        mov  edx,10000
   
5.        cmp  sum,edx
   
6.        cmovnb eax,edx
   
7.        sub  sum,eax
   
8.        shr  eax,13
   
9.        mov  carry,eax
   
10.      }

复制代码

性能有所改善
Elapsed time: 4.668000 s
Elapsed time: 6.032000 s

zeroieme

是否意味着让CPU做一点点无用功，反比判断分支还快。

liangbch

16# G-Spider
这个代码的效果应该不错。
我在数年前写过Radix为10^9的大数加法程序，使用了消除分支的代码，用到的adc指令，当时不知道可用cmovcc指令来消除分支，速度应该没有你这个代码快。

liangbch

粗粗的扫了一遍15楼给出的文章,真不错，内容全面翔实。另外，对作者Agner Fog google了一下，发现作者确实是X86优化的资深专家。

关于优化的参考 X86 平台，Agner Fog 是绝对的权威。

▄︻┻═┳一‥

还是没看明白楼主 说的 优势， [-M/2,M/2-1] 里面有负数，你这个负号“-”总要占bit位吧，那岂不是浪费？