语言不限。可以使用容器库等辅助操作,可以内联汇编,但是不允许直接使用大数相关的库。
happy886r 之前已经写过相当完善的计算工具,这里引用一下:
逆波兰计算器revpolish.exe
数学计算工具i
资料整理:
Coding Contest Byte: The Square Root Trick
libgmp 库中的开根算法
"Karatsuba Square Root" algorithm by Paul Zimmermann
GNU MP 库中用到的算法和理论,完整版:
《Modern Computer Arithmetic》
http://maths.anu.edu.au/~brent/pd/mca-cup-0.5.9.pdf
不依赖外部库实现大数加、减、乘、除、开根
- 523066680
- Administrator
- 帖子: 573
- 注册时间: 2016年07月19日 12:14
- 联系:
Re: 不依赖外部库实现大数加、减、乘、除、开根
先说开根吧,Wikipedia 上有很齐全的方案收集
手算开根法
Methods of computing square roots
https://en.wikipedia.org/wiki/Methods_o ... uare_roots
手算开根法
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
- 523066680
- Administrator
- 帖子: 573
- 注册时间: 2016年07月19日 12:14
- 联系:
性能分析
照着手算的方案,撸了一段C++版的,用VS2015 做了性能分析,好像开销主要在于字符串数组的[]取址操作,
待优化
2019-02-03
手算法 C++ vector 容器版,BASE=10^8,i7 CPU 4GHz, 1W位0.11秒,可能某些数字会触发问题吧?不管了过年了
待优化
2019-02-03
手算法 C++ vector 容器版,BASE=10^8,i7 CPU 4GHz, 1W位0.11秒,可能某些数字会触发问题吧?不管了过年了
![smile :confidence](./images/smilies/ext_confidence.gif)
// SQRT - Paper and Pencil method, C++ implementation (Only for Positive Integer Number)
// 523066680/vicyang
// 2019-02
// vector solution, BASE = 10^8, not finished yet
- 523066680
- Administrator
- 帖子: 573
- 注册时间: 2016年07月19日 12:14
- 联系:
大数减法、加法 C++实现 Re: 不依赖外部库实现大数加、减、乘、除、开根
使用向量容器存储 32位int值,每一段int存储8位数字( 按10^8 为进制处理)
减法运算效率测试(分为 vec_minus 和 s_minus 函数)
1W位数字减法,2W次循环,向量(10^8 进制) 和 string 逐位操作,效率对比
《Modern Computer Arithmetic》(后面简称MCA)里面关于采用高进制计算可能产生溢出问题的探讨
对于64位平台 unsigned long long int 支持的最大数字是 2^64-1=18446744073709551615,20位,如果我们充分利用,使用2^64,或者10^19作为进制。
很容易会遇到溢出问题,MCA给出了几种方案:
Let T be the number of different values taken by the data type representing the coefficients ai, bi.
(Clearly, β ≤ T, but equality does not necessarily hold, for example β = 10^9 and T = 2^32.) At step 3, the value of s can be as large as 2β − 1, which is not representable if β = T. Several workarounds are possible:
either use a machine instruction that gives the possible carry of ai + bi,
or use the fact that, if a carry occurs in ai + bi, then the computed sum – if performed modulo T – equals t := ai +bi −T < ai; thus, comparing t and ai will determine if a carry occurred.
A third solution is to keep a bit in reserve, taking β ≤ T/2.
用 T 表示一个存储单元所能表示的数的量,则有 β <= T
(这里 β 表示采用的进制,以及β不一定等于T,例如T=2^32,但采用的进制为10^9)。
考虑加法操作 s=a+b+d (d为1或0,是上一次加法补进的数值),s的最大可能值为 2*β-1,当 β = T 时该公式无法正确计算。
考虑以下方案:
1. 内部编码实现 (水平有限,暂时这么翻译)
2. 通过-T取余数判断,t := a + b - T < a ,对比 t 和 a 断定是否进 1
3. 采用一个保守的进制数 β,令 β ≤ T/2.
偷个懒,暂时采用10^8而不是 10^9, 2^32
如果对相同的进制进行乘法运算,可以使用 unsigned long long int 类型获得最高19位数的运算空间,足以应付 8*2+1 位数的情况
减法运算效率测试(分为 vec_minus 和 s_minus 函数)
Code: [show] | [select all]
代码: 全选
s_minus, Time used: 0.860001
vec_minus, Time used: 0.12
对于64位平台 unsigned long long int 支持的最大数字是 2^64-1=18446744073709551615,20位,如果我们充分利用,使用2^64,或者10^19作为进制。
很容易会遇到溢出问题,MCA给出了几种方案:
Let T be the number of different values taken by the data type representing the coefficients ai, bi.
(Clearly, β ≤ T, but equality does not necessarily hold, for example β = 10^9 and T = 2^32.) At step 3, the value of s can be as large as 2β − 1, which is not representable if β = T. Several workarounds are possible:
either use a machine instruction that gives the possible carry of ai + bi,
or use the fact that, if a carry occurs in ai + bi, then the computed sum – if performed modulo T – equals t := ai +bi −T < ai; thus, comparing t and ai will determine if a carry occurred.
A third solution is to keep a bit in reserve, taking β ≤ T/2.
用 T 表示一个存储单元所能表示的数的量,则有 β <= T
(这里 β 表示采用的进制,以及β不一定等于T,例如T=2^32,但采用的进制为10^9)。
考虑加法操作 s=a+b+d (d为1或0,是上一次加法补进的数值),s的最大可能值为 2*β-1,当 β = T 时该公式无法正确计算。
考虑以下方案:
1. 内部编码实现 (水平有限,暂时这么翻译)
2. 通过-T取余数判断,t := a + b - T < a ,对比 t 和 a 断定是否进 1
3. 采用一个保守的进制数 β,令 β ≤ T/2.
偷个懒,暂时采用10^8而不是 10^9, 2^32
如果对相同的进制进行乘法运算,可以使用 unsigned long long int 类型获得最高19位数的运算空间,足以应付 8*2+1 位数的情况
- 523066680
- Administrator
- 帖子: 573
- 注册时间: 2016年07月19日 12:14
- 联系:
大数乘法 - BasecaseMultiply C++ 实现 Re: 不依赖外部库实现大数加、减、乘、除、开根
《MCA》中的BasecaseMultiply 函数实现,采用10^8为进制。
2019-02-01 初步版本
批量测试,1W位*1W位,100次,本机耗时 4.2秒,仍有很大优化空间
(按字符串处理的版本,1W位乘法10次已经耗时13秒。)
其中 容器相关的 []操作符重载、push_back、insert操作占较大比例。
使用"指针"代替容器[]操作符,使用 emplace_back 代替 push_back 可以获得轻微的提高。
考虑提前预判新容器的长度并使用静态大小的容器,又或者换成C数组操作(不要 insert 和 push_back,提供offset和length)
优化版,“静态”容器
对比初版,耗时为1.66s,时间缩短一半以上。
下一次尝试 KaratsubaMultiply (此算法仅针对两个乘数长度相同的情况),要等过年后了,放松一下。
2019-02-01 初步版本
Code: [show] | [select all]
(按字符串处理的版本,1W位乘法10次已经耗时13秒。)
其中 容器相关的 []操作符重载、push_back、insert操作占较大比例。
使用"指针"代替容器[]操作符,使用 emplace_back 代替 push_back 可以获得轻微的提高。
考虑提前预判新容器的长度并使用静态大小的容器,又或者换成C数组操作(不要 insert 和 push_back,提供offset和length)
优化版,“静态”容器
Code: [show] | [select all]
下一次尝试 KaratsubaMultiply (此算法仅针对两个乘数长度相同的情况),要等过年后了,放松一下。
在线用户
正浏览此版面之用户: 没有注册用户 和 1 访客