一种计算任意大整数的整数平方根(isqrt)的有效算法

概述注意 有关Erlang或C/C++的解决方案,请转到下面的试用版4. 维基百科文章 Integer square root >可以在此处找到“整数平方根”的定义 Methods of computing square roots >这里可以找到一个“魔术”的算法 [试验1：使用库功能] 码 isqrt(N) when erlang:is_integer(N), N >= 0 -> erla 注意

有关Erlang或C/C++的解决方案,请转到下面的试用版4.

维基百科文章

Integer square root

>可以在此处找到“整数平方根”的定义

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)).123456789012345671682>

[试验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 0isqrt(1) = 1   # <-+isqrt(2) = 1   #   |- Three 1'sisqrt(3) = 1   # <-+isqrt(4) = 2   # <-+isqrt(5) = 2   #   |isqrt(6) = 2   #   |- Five 2'sisqrt(7) = 2   #   |isqrt(8) = 2   # <-+isqrt(9) = 3   # <-+isqrt(10) = 3  #   |isqrt(11) = 3  #   |isqrt(12) = 3  #   |- Seven 3'sisqrt(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

相关问题

Integer square root in python

> 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 boundhigh = pow(10,log10(target)/2+1);*/high = targetwhile(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 = targetlog10 = 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)的有效算法所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。