完全平方数的判定及整数平方根的快速求解

2024-05-04 23:18

本文主要是介绍完全平方数的判定及整数平方根的快速求解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在上个星期的“有道难题”网络预赛中,某些Group的第二题涉及到了完全平方数的判定问题。相信大多数人的判定语句都差不多是这样写的:if(sqr((int)sqrtl(n))==n){...},把这条语句整理一下,大概是这样:

inline __int64 sqr( int n){ return  static_cast<__int64>(n)*n;} 

inline  int directSqrt( int n) 

     int root =  static_cast< int>(sqrtl(n)); //求n的开方,但是double类型的
     if (sqr(root+ 1) <= n) 
     { 
         return root +  1
     } 
     else  return root; 


inline  bool isSquareNumber( int n) 

   int root = directSqrt(n); 
   return sqr(root) == n; 
}

这个判定方法主要是利用标准库的sqrt函数来求整数平方根(integer square root),正确性不用怀疑,效率也足够。但是如果想要更快呢?通常来说,要判定任意一个数是否是完全平方数,求根的过程在所难免。但是,标准库的sqrt函数是求浮点平方根的,而我们只需要获取整数平方根即可,所以在这里肯定还有性能提升的空间。于是接下来就列举一些计算整数平方根的方法(后两个算法不是我写的),按照计算速度从慢到快依次排列,其中最后一个算法的效率大概是上述直接利用sqrtl的方法的四倍。

1. 线性搜索,直接从小到大依次取数试探,最原始的办法,代码如下:

inline  int linearSqrt( int n) 

     int i =  0
     while (sqr(i) <= n) ++i; 
     return i- 1
}


2. 二分法寻找根

inline  int bisectionSqrt( int n) 

     int l =  0, r = n/ 2 +  1
     while (r - l >  1
     { 
         int m = (l+r)/ 2
         __int64 sqrm = sqr(m); 
         if (sqrm == n) 
         { 
             return m; 
         } 
         else  if (sqrm > n) r = m; 
         else l = m; 
     } 
     
     if (sqr(r) == n) 
     { 
         return r; 
     } 
     else  return l; 
}

3. 牛顿迭代法,令方程 x^2 - n = 0,则求sqrt(n)也即是求这个方程的根,根据牛顿法的迭代公式有:x' = x - (x^2-n)/(2x) = (x^2+n)/(2x),选定合适的初始值迭代,很快就能收敛到根。另外,这个迭代其实也就是不动点迭代的松弛形式,由 x^2= n => x = n/x, 得不动点迭代x' = n/x,加上松弛系数1/2(算数平均),得x'= 1/2 * (x + n/x),即 x' = (x^2+n)/(2x),与前面牛顿法的迭代公式相同。算法的代码如下:

inline  int newtonSqrt( int n) 

     static  int table[ 16] = { 
         11<< 21<< 41<< 61<< 81<< 101<< 121<< 141<< 16
         1<< 181<< 201<< 221<< 241<< 261<< 281<< 30
     }; 
     unsigned i =  0, x0 =  0, x1 =  0
     while (table[i] < n && i!= 16) ++i; x0 =  1 << i; //寻找迭代的初识值
     while (x0 !=  0
     {     
         x1 = static_cast< int>((sqr(x0) + n)/ ( 2*x0)); 
         if (x1 >= x0) 
         { 
             break
         } 
         x0 = x1; 
     } 
     return x0; 
}

4. 逐位确定法,从高到低依次确定根的各个二进制位。见下面这个代码,看起来似乎很飘逸,但实际上算法很简单明晰,具体的解释可以搜索James Ulery的论文:"Computing Integer Square Roots".

inline  int fastIntSqrt( int n) 

     int temp, nHat =  0, b =  0x8000, bshft =  15
     do 
     { 
         if (n >= (temp = (((nHat<< 1)+b)<<bshft--))) 
         { 
             nHat += b; 
             n -= temp; 
         } 
     }  while (b >>=  1); 
     return nHat; 
}

5.建表+牛顿迭代,这个算法号称是要用来替代java数学包中的(int)(java.lang.Math.sqrt(integer))函数的,速度奇快,首先建立了一张强大的表来确定初值,然后最多经过两次牛顿迭代后就得到精确解。

inline  int javaIntSqrt( int n) 

     static  int table[ 256] = { 
         0,     16,   22,   27,   32,   35,   39,   42,   45,   48,   50,   53,   55,   57
         59,    61,   64,   65,   67,   69,   71,   73,   75,   76,   78,   80,   81,   83
         84,    86,   87,   89,   90,   91,   93,   94,   96,   97,   98,   99101102
         103104106107108109110112113114115116117118
         119120121122123124125126128128129130131132
         133134135136137138139140141142143144144145
         146147148149150150151152153154155155156157
         158159160160161162163163164165166167167168
         169170170171172173173174175176176177178178
         179180181181182183183184185185186187187188
         189189190191192192193193194195195196197197
         198199199200201201202203203204204205206206
         207208208209209210211211212212213214214215
         215216217217218218219219220221221222222223
         224224225225226226227227228229229230230231
         231232232233234234235235236236237237238238
         239240240241241242242243243244244245245246
         246247247248248249249250250251251252252253
         253254254255 
     }; 

     int xn; 
     if (n >=  0x7FFEA810return  0xB504
     if (n >=  0x10000) { 
         if (n >=  0x1000000) { 
             if (n >=  0x10000000) { 
                 if (n >=  0x40000000) { 
                     xn = table[n>>  24] <<  8
                 }  else { 
                     xn = table[n>>  22] <<  7
                 } 
             }  else { 
                 if (n>=  0x4000000) { 
                     xn = table[n>>  20] <<  6
                 }  else { 
                     xn = table[n>>  18] <<  5
                 } 
             } 

             xn = (xn +  1 + (n/ xn)) >>  1
             xn = (xn +  1 + (n/ xn)) >>  1
             return ((xn * xn) > n) ? --xn : xn; 
         }  else { 
             if (n>=  0x100000) { 
                 if (n>=  0x400000) { 
                     xn = table[n>>  16] <<  4
                 }  else { 
                     xn = table[n>>  14] <<  3
                 } 
             }  else { 
                 if (n>=  0x40000) { 
                     xn = table[n>>  12] <<  2
                 }  else { 
                     xn = table[n>>  10] <<  1
                 } 
             } 

             xn = (xn +  1 + (n/ xn)) >>  1
             return ((xn * xn) > n) ? --xn : xn; 
         } 
     }  else { 
         if (n>=  0x100) { 
             if (n>=  0x1000) { 
                 if (n>=  0x4000) { 
                     xn = (table[n>>  8]) +  1
                 }  else { 
                     xn = (table[n>>  6] >>  1) +  1
                 } 
             }  else { 
                 if (n>=  0x400) { 
                     xn = (table[n>>  4] >>  2) +  1
                 }  else { 
                     xn = (table[n>>  2] >>  3) +  1
                 } 
             } 
             return ((xn * xn) > n) ? --xn : xn; 
         }  else { 
             if (n>=  0) { 
                 return table[n] >>  4
             } 
         } 
     } 
     return - 1
}

依次计算从1到1000000的每个数的整数平方根,下面分别是上面6个算法所用的时间:

0. 利用标准库sqrtl, directSqrt : 610 ms
1. 线性搜索, linearSqrt : 81256 ms
2. 二分法, bisectionSqrt : 2734 ms
3. 牛顿迭代法, newtonSqrt : 691 ms
4. 逐位确定法, fastIntSqrt : 301 ms
5. 建表+牛顿迭代, javaIntSqrt : 150 ms

可见牛顿迭代法与利用标准库sqrtl的方法速度相当,逐位确定法的速度大概是牛顿迭代法的两倍。当然,最快的还是建表+牛顿迭代,看来以其来替代(int)(java.lang.Math.sqrt(integer))也不是没有道理的。另,以上测试数据相对来说都比较小,可以想象,若是计算接近于2^31这样的大数的整数平方根,逐位确定法和建表+牛顿迭代应该更占据优势。

这篇关于完全平方数的判定及整数平方根的快速求解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/960313

相关文章

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

Linux find 命令完全指南及核心用法

《Linuxfind命令完全指南及核心用法》find是Linux系统最强大的文件搜索工具,支持嵌套遍历、条件筛选、执行动作,下面给大家介绍Linuxfind命令完全指南,感兴趣的朋友一起看看吧... 目录一、基础搜索模式1. 按文件名搜索(精确/模糊匹配)2. 排除指定目录/文件二、根据文件类型筛选三、时间

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Win32下C++实现快速获取硬盘分区信息

《Win32下C++实现快速获取硬盘分区信息》这篇文章主要为大家详细介绍了Win32下C++如何实现快速获取硬盘分区信息,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 实现代码CDiskDriveUtils.h#pragma once #include <wtypesbase

JavaScript中的Map用法完全指南

《JavaScript中的Map用法完全指南》:本文主要介绍JavaScript中Map用法的相关资料,通过实例讲解了Map的创建、常用方法和迭代方式,还探讨了Map与对象的区别,并通过一个例子展... 目录引言1. 创建 Map2. Map 和对象的对比3. Map 的常用方法3.1 set(key, v

Spring AI与DeepSeek实战一之快速打造智能对话应用

《SpringAI与DeepSeek实战一之快速打造智能对话应用》本文详细介绍了如何通过SpringAI框架集成DeepSeek大模型,实现普通对话和流式对话功能,步骤包括申请API-KEY、项目搭... 目录一、概述二、申请DeepSeek的API-KEY三、项目搭建3.1. 开发环境要求3.2. mav

Python如何快速下载依赖

《Python如何快速下载依赖》本文介绍了四种在Python中快速下载依赖的方法,包括使用国内镜像源、开启pip并发下载功能、使用pipreqs批量下载项目依赖以及使用conda管理依赖,通过这些方法... 目录python快速下载依赖1. 使用国内镜像源临时使用镜像源永久配置镜像源2. 使用 pip 的并

SpringBoot快速接入OpenAI大模型的方法(JDK8)

《SpringBoot快速接入OpenAI大模型的方法(JDK8)》本文介绍了如何使用AI4J快速接入OpenAI大模型,并展示了如何实现流式与非流式的输出,以及对函数调用的使用,AI4J支持JDK8... 目录使用AI4J快速接入OpenAI大模型介绍AI4J-github快速使用创建SpringBoot