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

头像
523066680
Administrator
Administrator
帖子: 411
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 40 times
Been thanked: 55 times
联系:

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

帖子 #1 523066680 » 2018年12月24日 16:11

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

语言不限。

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

头像
523066680
Administrator
Administrator
帖子: 411
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 40 times
Been thanked: 55 times
联系:

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

帖子 #2 523066680 » 2018年12月25日 14:17

先说开根吧,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
Administrator
Administrator
帖子: 411
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 40 times
Been thanked: 55 times
联系:

性能分析

帖子 #3 523066680 » 2019年01月20日 21:48

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

sqrt_decimal.cpp
(5.4 KiB) 尚未被下载
sqrt_decimal.cpp
(5.4 KiB) 尚未被下载


prof.png
prof.png (28.38 KiB) 查看 1 次
prof.png
prof.png (28.38 KiB) 查看 1 次


回到 “算法和编码”

在线用户

用户浏览此论坛: 没有注册用户 和 0 访客