大佬教程收集整理的这篇文章主要介绍了一种计算任意大整数的整数平方根(isqrt)的有效算法,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
有关Erlang或C/C++的解决方案,请转到下面的试用版4.
维基百科文章
>可以在此处找到“整数平方根”的定义
Methods of computing square roots
>这里可以找到一个“魔术”的算法
[试验1:使用库功能]
码
isqrt(N) when erlang:is_Integer(N),N >= 0 -> erlang:trunc(math:sqrt(N)).
问题
此实现使用C库中的sqrt()函数,因此它不适用于任意大整数(请注意,返回的结果与输入不匹配.正确答案应为12345678901234567890):
Erlang R16B03 (erts-5.10.4) [source] [64-bit] [smp:8:8] [async-threads:10] [hipe] [kernel-poll:false] EsHell V5.10.4 (abort with ^G) 1> erlang:trunc(math:sqrt(12345678901234567890 * 12345678901234567890)). 12345678901234567168 2>
[试验2:仅使用Bigint]
码
isqrt2(N) when erlang:is_Integer(N),N >= 0 -> isqrt2(N,3,0). isqrt2(N,I,_,Result) when I >= N -> Result; isqrt2(N,Times,Result) -> isqrt2(N,I + Times,Times + 2,Result + 1).
描述
此实现基于以下观察:
isqrt(0) = 0 # <--- One 0 isqrt(1) = 1 # <-+ isqrt(2) = 1 # |- Three 1's isqrt(3) = 1 # <-+ isqrt(4) = 2 # <-+ isqrt(5) = 2 # | isqrt(6) = 2 # |- Five 2's isqrt(7) = 2 # | isqrt(8) = 2 # <-+ isqrt(9) = 3 # <-+ isqrt(10) = 3 # | isqrt(11) = 3 # | isqrt(12) = 3 # |- Seven 3's isqrt(13) = 3 # | isqrt(14) = 3 # | isqrt(15) = 3 # <-+ isqrt(16) = 4 # <--- Nine 4's ...
问题
这个实现只涉及bigint添加,所以我希望它能够快速运行.但是,当我用1111111111111111111111111111111111111111 * 1111111111111111111111111111111111111111喂它时,它似乎永远在我(非常快)的机器上运行.
[试验3:仅使用Bigint 1,-1和div 2进行二进制搜索]
码
变式1(我的原始实现)
isqrt3(N) when erlang:is_Integer(N),N >= 0 -> isqrt3(N,1,N). isqrt3(_N,Low,High) when High =:= Low + 1 -> Low; isqrt3(N,High) -> Mid = (Low + High) div 2,MidSqr = Mid * Mid,if %% This also catches N = 0 or 1 MidSqr =:= N -> Mid; MidSqr < N -> isqrt3(N,Mid,High); MidSqr > N -> isqrt3(N,Mid) end.
变式2(修改上面的代码,以便边界与中间1或中间1相反,参考answer by Vikram Bhat)
isqrt3a(N) when erlang:is_Integer(N),N >= 0 -> isqrt3a(N,N). isqrt3a(N,High) when Low >= High -> HighSqr = High * High,if HighSqr > N -> High - 1; HighSqr =< N -> High end; isqrt3a(N,if %% This also catches N = 0 or 1 MidSqr =:= N -> Mid; MidSqr < N -> isqrt3a(N,Mid + 1,High); MidSqr > N -> isqrt3a(N,Mid - 1) end.
问题
现在,它解决了在闪电般的速度的79位数字(即1111111111111111111111111111111111111111 * 1111111111111111111111111111111111111111),其结果是立即显示.但是,它需要60秒时间 – 我的机器上解决一百万(1,000,000)61位数字(即从1000000000000000000000000000000000000000000000000000000000000到1000000000000000000000000000000000000000000000000000001000000)(2秒).我想更快地做到这一点.
[试验4:使用牛顿方法与Bigint和div仅]
码
isqrt4(0) -> 0; isqrt4(N) when erlang:is_Integer(N),N >= 0 -> isqrt4(N,N). isqrt4(N,Xk) -> Xk1 = (Xk + N div Xk) div 2,if Xk1 >= Xk -> Xk; Xk1 < Xk -> isqrt4(N,Xk1) end.
C/C++代码(为了您的兴趣)
递归变体
#include <stdint.h> uint32_t isqrt_impl( uint64_t const n,uint64_t const xk) { uint64_t const xk1 = (xk + n / xk) / 2; return (xk1 >= xk) ? xk : isqrt_impl(n,xk1); } uint32_t isqrt(uint64_t const n) { if (n == 0) return 0; if (n == 18446744073709551615ULL) return 4294967295U; return isqrt_impl(n,n); }
迭代变体
#include <stdint.h> uint32_t isqrt_iterative(uint64_t const n) { uint64_t xk = n; if (n == 0) return 0; if (n == 18446744073709551615ULL) return 4294967295U; do { uint64_t const xk1 = (xk + n / xk) / 2; if (xk1 >= xk) { return xk; } else { xk = xk1; } } while (1); }
问题
Erlang代码在我的机器上在40秒(-1秒)内解决了一百万(1,000)个61位数字,所以这比试用版3更快.它可以更快吗?
关于我的机器
处理器:3.4 GHz Intel Core i7
内存:32 Gb 1600 MHz DDR3
操作系统:Mac OS X版本10.9.1
相关问题
> answer by user448810使用“牛顿法”.我不确定使用“整数除法”进行除法是否合适.我稍后会尝试将其作为更新. [更新(2015-01-11):可以这样做]
> answer by math涉及使用第三方Python软件包gmpy,这对我来说不是很有利,因为我主要感兴趣的是只用内置工具在Erlang中解决它.
> answer by DSM似乎很有趣.我真的不明白发生了什么,但似乎那里有“魔法”,所以它也不太适合我.
Infinite Recursion in Meta Integer Square Root
>这个问题适用于C,而AraK(提问者)的算法看起来与上面的试验2的想法相同.
low = 1; /* More efficient bound high = pow(10,log10(target)/2+1); */ high = target while(low<high) { mid = (low+high)/2; currsq = mid*mid; if(currsq==target) { return(mid); } if(currsq<target) { if((mid+1)*(mid+1)>target) { return(mid); } low = mid+1; } else { high = mid-1; } }
这适用于O(logN)迭代,因此即使非常大的数字也不应该永远运行
Log10(目标)计算如果需要: –
acc = target log10 = 0; while(acc>0) { log10 = log10 + 1; acc = acc/10; }
注意:acc / 10是整数除法
编辑: –
有效界限: – sqrt(n)的位数大约是n的一半,因此你可以传递高= 10 ^(log10(N)/ 2 1)&&低= 10 ^(log10(N)/ 2-1)以获得更紧密的限制,它应该提供2倍的加速.
评估范围: –
bound = 1; acc = N; count = 0; while(acc>0) { acc = acc/10; if(count%2==0) { bound = bound*10; } count++; } high = bound*10; low = bound/10; isqrt(N,low,high);
以上是大佬教程为你收集整理的一种计算任意大整数的整数平方根(isqrt)的有效算法全部内容,希望文章能够帮你解决一种计算任意大整数的整数平方根(isqrt)的有效算法所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。