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

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

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会影响进位的.