不依赖外部库实现大数加、减、乘、除、开根

[523066680]

好久没折腾了
呼叫 @rubyish @24Game，有兴趣吗

语言不限。

happy886r 之前已经写过相当完善的计算工具，这里引用一下：
逆波兰计算器revpolish.exe
数学计算工具i

[523066680]

先说开根吧，Wikipedia 上有很齐全的方案收集

Methods of computing square roots
https://en.wikipedia.org/wiki/Methods_o ... uare_roots

其中有一种手算开根的方法，个人认为，对于需要获取高精度数值的情况，比牛顿开根要容易实现

1. 4  1  4  2
  _______________
\/ 02.00 00 00 00
   02                  1*1 <= 2 < 2*2                 x = 1
   01                    y = x*x = 1*1 = 1
   01 00               24*4 <= 100 < 25*5             x = 4
   00 96                 y = (20+x)*x = 24*4 = 96
      04 00            281*1 <= 400 < 282*2           x = 1
      02 81              y = (280+x)*x = 281*1 = 281
      01 19 00         2824*4 <= 11900 < 2825*5       x = 4
      01 12 96           y = (2820+x)*x = 2824*4 = 11296
         06 04 00      28282*2 <= 60400 < 28283*3     x = 2
                       The desired precision is achieved:
                       The square root of 2 is about 1.4142

Coding Contest Byte: The Square Root Trick

libgmp 库中的开根算法
"Karatsuba Square Root" algorithm by Paul Zimmermann

这里有一段根据手算法写的C语言代码，摘自csdn
但是可读性很差，阅读起来很抓狂……
https://blog.csdn.net/enjoying_science/ ... s/38401817

代码: 全选

/*
    https://blog.csdn.net/enjoying_science/article/details/38401817
*/

#include <stdio.h>
#include <string.h> 
 
int id;
int work(int o, char *num, int ID)
{
    char c, *tnum=num ;
    if( o > 0 )
    {
        for ( id = 0; tnum[id]; id++ )
        {
            tnum[ id ]-=120;
            id++;
            tnum[ id ]-=110;
            while ( !work(0, num, id) )
            {
                tnum[id]+=20;
            }
            putchar( (tnum[id]+1032)/20 );
            tnum[id] -= 10;
        }
        putchar(10);
    }
    else
    {
        c = o + (tnum[ID]+82)%10 - (ID>id/2) * (tnum[ID-id+ID]+72)/10-9;
        tnum[ID]+=ID < 0 ? 0 : !( o = work(c/10, num, ID-1) ) * ( (c+999)%10-(tnum[ID]+92) % 10 );
    }
   
    return o;
}

int main() 
{ 
    char s[1200];
    s[0]='0';
    sscanf("123456787654321", "%s", s+1);
    if(strlen(s)%2 == 1) 
        work(2,s+1,0); 
    else 
        work(2,s,0); 
    return 0; 
} 

[523066680]

照着手算的方案，撸了一段C++版的，用VS2015 做了性能分析，好像开销主要在于字符串数组的[]取址操作，
待优化

sqrt_decimal.cpp

(5.4 KiB) 尚未被下载

sqrt_decimal.cpp

(5.4 KiB) 尚未被下载

prof.png (28.38 KiB) 查看 6 次

prof.png (28.38 KiB) 查看 6 次