基于泰勒展开式的高精三角函数实现

liangbch

zeroieme 发表于 2016-5-12 19:48
2进制处理
1、容易求a，$1

22楼(http://bbs.emath.ac.cn/forum.php ... =8882&pid=62690)上的算法正是大物理学家费曼提出的算法，请参阅 https://en.wikipedia.org/wiki/Logarithm 中的 Feynman's algorithm

liangbch

有人建议我用binary spliting方法加速泰勒展开式运算

以下内容摘自《计算机代数系统数学原理》5.1.1 级数方法

折半求和(Binary Splitting)(参见[55])是用来计算超几何级数(参见[1])在有
理点处的值的一项重要方法.

   以下省略了公式推导部分...

从整体上来看, 折半求和并没有减少运算次数, 它只是让参与乘法的两个数的
数量级更接近, 这样就可以充分发挥Karatsuba, Toom-Cook 和FFT 等大整数快
速乘法算法的优势. 如果大整数乘法采用古典乘法算法, 那么折半求和是不起作用
的, 甚至可能比普通的级数求和方法更慢. 除此之外, 折半求和实际上是将截断的
级数先乘上分母的最小公倍数后再计算, 这样可以避免对中间结果进行除法等不
精确计算, 而只需要在最后做一次除法. 可以证明, 采用折半求和算法计算出部分
和S 的前N 位有效数字大约需要O((logN)2M(N)) 次基本运算, 其中M(N) 代
表两个N 位整数相乘所需要的基本运算的次数(如果采用有限域上的FFT 乘法,
那么M(N) = O(N logN log logN)). 折半求和利用两个独立的子区间的数据来
合成整个区间的数据, 因此也很适合于并行计算.

liangbch

关于23#http://bbs.emath.ac.cn/forum.php ... 2718&fromuid=25的具体实验结果。
例如，x=\(Pi~\approx3.1415926535897932384626433832795\),使用费曼算法
x=1.000000000000000000000000000000000000000809984847847974866788749996432706480836754251772210550932228*frac
frac=1729470995947852915036591017264680851121175522363245594831351686561770428819406292432291885890572157622950064744184597452639693515477185918035395091572622870164908249098857438098249788016329832118323401577395424700776197084792529550004614740782588564619349235311616918723016054861708304568290655513317691328158755316681150436719070124313812229002712087093921778630106127671283495173834425715893324919480341182008562560216087797342397902562151871875973954965595959931198217533806535459511768510401926541596780491250072800703096686384867663347092786674738292838254612353275417193272450370638178092559597428650382460870352145790235834994218300855072036632214161918565691414310178180266431230342134077815982695851206724120294930712789210098032415732282653265341982078943667142543897793454570621470477193141085698857202858419979802118042334378932922393370612759538616576788382718863524836213974266099720435988227280871480227287562431764956984217763972083788920133879169923511796861992455543160578905275649015453596975210733166762015852603731716906369412666126207417788458923745931279017898603395016379536630651733128129764681532647137446168260798309326171875/550507715878328159080412480866164102719206228181489282317878108407855484860532631772034918412722056263548464130272650463100584837831950655712313979867631451046290902247937871318676953494903612891335487917961953191211008962744449666388167946727260513433908364463838718130467522688369870004054503103644135520143689267615180747678158111769191723888943630888138992511028868339821539028164880937358513531309955362453193406206120365362857163766849746374952474728104618254787943384901529000188761876628500928472781972281568678510170087971244490035777884762916391756972329029893270419241665753737238554436130652052915003427547146289136453805065974207053259100832466796000354383060129163004366407005548442256950830477695375817665736399282430655342648534311419086887774009792345497901050974432012345736463449817247084642755319495246599812530439401806986377022072552217916852766618688587845061720198297016481609959906894081191066550956897835739871543340042776656837184064723175736084761851913196617104928755680390489249990592927904536652532599874842487587875561711141314083705305324268183027868828007032704304952240654172675524660314054598692972081543875986980864
这个分数的分子是一个2653位10进制数，分母有是一个 2652位10进制数

而采用我的分解方法，

3.1415926535897932384626433832795028841971693993751058209749445923078164062862090
=1.000000000000000000000000000000000000002960993935851008447446754839159569
*3832014442888771646470018465512801870734823728305172799757503908813075813325718724034472306509050451732510903860567833545239475503403374526958669844586973146646532725932032
/1219768081170566921268855328849298222677009015409405760168337040462778507946278286072337719525269526046195409466597366002630196587692336129105046226114702746132821923828125
=1.000000000000000000000000000000000000002960993935851008447446754839159569
* (2^33 * 7^18 * 11^18 * 13 * 19 * 29^4 * 31^12 * 37^11 *43^17 * 67 * 79 * 89^3 * 97^8 * 101^4 * 103 * 109^3 * 131^6 * 167)
/(3^7 * 5^11 * 17^10 * 23 * 41^5 * 47^10 * 53^6 * 59^3 * 61^9 *71^5 * 73 * 83^2 * 107 * 113^9 * 127^2 * 137^4 * 151^13 * 157 * 163^2 * 173^3)
分子是一个 395 位10进制数，分母 394 位10进制数，分子和分母比费曼的那个结果小的多。

另外，费曼的方法需要存储128个数的对数，如果将这个128个数分解素因数，则有269个之多（删除重复）。而我的方法仅仅需要存储40个素数的对数。

liangbch

我在 2016-4-13 08:04:46 说：

By the way, "万位精度sinx在32位机上用时100秒左右"这个速度太慢了。 我的理想目标是 100万 做到10秒左右。

现在，我的诺言基本兑现。我的log(x)在精度为100万位时，在I7-4700HQ上耗时6.5秒。注意：这个速度是在大数乘法没有采用FFT，SSA，NTT算法的基础上取得的。
我的大数乘法只使用了karatsuba算法和9种Toom算法。sin(x)和log(x)复杂度应该差不多。

liangbch

我在2016-4-20 说

对于对数函数的任意精度计算，我还是有发言权的。我对对数函数的算法琢磨了将近30年。目前正在探索一种全新的算法并实现一个任意精度对数库，期望其性能超过目前所有的同类数学软件，包括Mathematics，Maple，PARI/GP,MPFP。

我搜索了一下，下面网页留下我的足迹。你可参考下。
http://bbs.pfan.cn/post-241245.html
http://www.cnblogs.com/skyivben/archive/2013/02/15/2912914.html

我的愿望已经实现，我的对数函数性能大幅领先于目前所有同类软件，计算log(x)万位精度在32位机上仅需3毫秒左右。

liangbch

liangbch 发表于 2016-5-9 18:54
\( \frac {5^4 \times 7} {2 \times 3^7}= \frac{4375}{4374} = 1.000228623685413808870598994 \)

\( \ ...

\( \frac{2^9 \times 5^{37}}{ 3^{28} \times 7^{18}} = 1.0000006193987026213171611768795 \)