有什么乘法算法可以只算有效数字部分的？

zeroieme

如两100位的浮点，可以直接得到有效数字100位的积。而不用算200再截断

gxqcn

这个，我也想知道，估计有点难。

只是呼吸

没有办法，只有1000位乘1000位（十进制），结果取前100位有效数字才有办法。或者像楼主的题目，100位乘100位，结果取前50位有效数字，才有办法。

zeroieme

做梦梦到 转成对数加法 ln(X)'=1/X dX X=1±x的对数有效部分和X自身有效数字相约。加法、自然指数……都可控制精度。 我记得有篇AGM对数的论文有提及 乘法变对数加法的。 但求对数指数时，内部的乘要再转换么？效率分析全蒙了

liangbch

若采用高位在前，低位在后的表示法。 被乘数 a 用数组 A[0..n-1]表示，共有n位有效数字。 被乘数 b 用数组 B[0..n-1]表示，共有n位有效数字。 他们的乘积c用数组 C[0..2n-2]表示。 其中C[k]=sum( A[ i ]*B[ j ],i,j满足条件i+j=k),当最高位c[0]小于Radix,c有2n-1位有效数字，否则c有2n位有效数字。当采用硬乘法计算c的时候，从后往前(从低位到高位)算，依次计算c[k](k=2n-2 .. 0)即可，当需要部分精度时，k可直接从某一数x(0

仙剑魔

$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$其实就是这个问题的子问题,递归吧...

liangbch

楼上的想法我早就考虑过。 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$的额外空间。。。)

sielw

显然bd是不用计算的

bd怎么能不算呢？bd会影响进位的.