有什么乘法算法可以只算有效数字部分的？
如两100位的浮点，可以直接得到有效数字100位的积。而不用算200再截断 这个，我也想知道，估计有点难。 没有办法，只有1000位乘1000位（十进制），结果取前100位有效数字才有办法。或者像楼主的题目，100位乘100位，结果取前50位有效数字，才有办法。 做梦梦到:D 转成对数加法ln(X)'=1/X dX
X=1±x的对数有效部分和X自身有效数字相约。加法、自然指数……都可控制精度。
我记得有篇AGM对数的论文有提及 乘法变对数加法的。
但求对数指数时，内部的乘要再转换么？效率分析全蒙了:dizzy: 若采用高位在前，低位在后的表示法。
被乘数 a 用数组 A表示，共有n位有效数字。
被乘数 b 用数组 B表示，共有n位有效数字。
他们的乘积c用数组 C表示。
其中C=sum( A[ i ]*B[ j ],i,j满足条件i+j=k),当最高位c小于Radix,c有2n-1位有效数字，否则c有2n位有效数字。当采用硬乘法计算c的时候，从后往前(从低位到高位)算，依次计算c(k=2n-2 .. 0)即可，当需要部分精度时，k可直接从某一数x(0<x<=2n-2)算起,即如果需要精确到n位，k从n开始算起即可，当然为了适当保证精度，k可从n+1或者n+2开始算起,使用此法可节约大约50%的工作量。 n位的x,y
x=a*10^k+b
y=c*10^k+d
x*y=(a*10^k+b)*(c*10^k+d)
=ac*10^(2k)+(ad+bc)*10^k+bd
令k=n/2
如图:
显然bd是不用计算的
ac可以上FFT
ad+bc其实就是这个问题的子问题,递归吧... 楼上的想法我早就考虑过。
2个长度为n的数的乘法可分解为4次乘数长度为n/2的乘法，若仅需精确到n位，则只需计算3次乘数长度为n/2的乘法.
不过若n稍大，使用分治法，计算2个长度为n的数的完全精度乘法，同样可将转化为为3次乘数长为n/2的乘法，也就是说，不考虑分治法的辅助计算开销，使用分治法，同样的时间花费，可获得比此法多一倍的精度。故当n较大是，此法的意义不大。 7# liangbch
厄。。。
我那个说的是用分治的原理分割，但是计算用的FFT
所以时间复杂度f(n)=nlogn+2*f(n/2)
最后应该还是O(nlogn)的吧
比分治需要的内存开销要小一点
貌似只比直接用FFT算长度n的卷积快了那么一丁点。。。
我最后写了的：
ac上FFT
ad和bc直接递归
分治的做法是计算(a+b)*(c+d)-ac-bd(昨天算这个的时候蛋疼死我了。。。得开大约2n的额外空间。。。)
显然bd是不用计算的
bd怎么能不算呢？bd会影响进位的.
页:
[1]