2006-03-24 0:12| 
2 Comments | 本文内容遵从 确实好久没更新了……花功夫去做Vijos了，一天2道……
把去年重庆选拔赛的那个最小公倍数做了，把高精代码贴在这里供大家瞻仰。
每种运算都开了a、b、c三个数组，a、b是输入的要算的数，c是返回的结果。按惯例，数组倒序存字串，就是说a[1]表示的个位。
加法：c[i]:=c[i]+a[i]+b[i];
c[i+1]:=c[i] div 10;
c[i]:=c[i] mod 10;
减法（默认了a比b大）：if a[i]<b[i] then
begin
dec(a[i+1],1);
inc(a[i],10);
end;
c[i]:=a[i]-b[i];
乘法：inc(c[i+j-1],a[i]*b[j]);
inc(c[i+j],c[i+j-1]div 10);
c[i+j-1]:=c[i+j-1]mod 10;
除法有点复杂，需要调用前面的三种运算。算法和人做竖式计算一样，模拟试商。
简单说一下：
始终保持两个变量直到最后返回，一个当前得数，一个当前余数。初始化得数为0，余数为被除数。然后不断用当前的余数去减除数，同时当前得数不断跟着加1。
当除数远远小于被除数时，这种方法显然效率很低。为了能一次减很多，可以在每次减之前试商以减去尽可能大的整数倍的除数。试商方法很简单，先搜i再搜j，搜索小于当前余数的最大的“除数*j*10^i”。然后当前余数减去除数*j*10^i，得数加j*10^i。反复这个过程，直到余数小于除数。可以看到，对j的枚举即是试商的过程。
代码写出来不难，十几行搞定。
24的编剧越来越大胆了。
2 条回复
您也随便说几句吧：
你确认这个模拟要比正常的二进制计算要快？？
在通用cpu下乘法比加法快（两个二进制数相乘通用cpu架构下仅仅移位就可以，而加法不行）
我始终认为如果寄存器足够大的话普通的Pascal乘法或Fortran的乘法比这个模拟算法要快！！
（cpu的底层构架我也不很了解，，这个结论是在网上讨论一个在只能做加减法的cpu下高效开跟的一个问题时，，一个会计算电路的同学提出的。。。[当然乘法的引申--开方的效率，，，对于这可以加减的cpu进行开方利用奇等差数列{不知道这个说法准不准确，即使1，3，5，7，9，…………}来开方是最高效的，，但在通用cpu下呢？这种算法是否仍然最快呢？？{与c的或是Pascal的标准方法比较}当然，，当时的讨论没有个结果，，没有只可以进行加减法的cpu做实验{因为当时没有资料，也不清楚通用cpu下与很老式的只可以加减的cpu的内部电路构造是否相同，，是否对特殊的运算进行优化，，所以无法从理论角度分析。。}]最后，，仍然表示怀疑，，也希望，，matrix67在有物质条件和时间条件的情况下，，进行一下论证，，模拟算法真的快么？？希望matrix67能看一下risc架构有关的算法，，如果单纯的计算，，那么就目前来看risc最快）
ls很有意思，8086下加法是十几个cycle，乘法是二百多个cycle，移位不能代替乘法
普通乘法显然快于模拟，这个模拟在于高精
risc是cpu构架吧，不见得对cisc有明显优势