


How Can I Quickly Determine if a Large Integer is a Perfect Square Using Bitwise Operations?
Although the algorithm is about 35% faster than the code you gave, the actual results may vary between different CPUs (x86) and programming languages (C/C). The method in this article is divided into three parts:
-
Filter obvious answers: include negative numbers, check the last 4 digits (found that checking the last 6 digits is not helpful), answer 0. (When reading the following code, please note that my input is an int64 The product of two different prime numbers, so the square modulo 255 only has a remainder of about 1/8. However, in my experience, the costs of using the modulo operator (%) outweigh the benefits, so I used a bit trick involving 255 to calculate the remainder. (Better or worse, I didn't use the trick of reading individual bytes from the word, just bitwise AND and shifting.)
if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) ) return false; if( x == 0 ) return true;
Copy after loginI used a precomputed table to actually check if the remainder is square number. - Trying to calculate the square root using a method similar to Hensel's Lemma
int64 y = x; y = (y & 4294967295LL) + (y >> 32); y = (y & 65535) + (y >> 16); y = (y & 255) + ((y >> 8) & 255) + (y >> 16); // At this point, y is between 0 and 511. More code can reduce it farther.
Copy after login: Before this, I used two The search divides all remainders raised by powers of 2:
if( bad255[y] ) return false; // However, I just use a table of size 512
Copy after login At this point, for our number to be a square number, its modulus must be 1 over 8. -
The basic structure of Hensel’s lemma is as follows. (Note: untested code; if that doesn't work, try t=2 or 8.)
The idea is that on each iteration, you add one bit to r," The square root of (Note that if r is the square root of Power of .) Since our actual square root is less than 2^32, at that point we can actually check if r or t/2-r is the actual square root of x. In my actual code, I used the following modified loop:if((x & 4294967295LL) == 0) x >>= 32; if((x & 65535) == 0) x >>= 16; if((x & 255) == 0) x >>= 8; if((x & 15) == 0) x >>= 4; if((x & 3) == 0) x >>= 2;
Copy after loginThe speed gain here can be obtained in three ways: Precomputed starting value (equivalent to about 10 loop iterations ), exit the loop earlier, and skip some t values. For the last part, I observe z=r-x*x and use bit tricks to set t to the largest power of 2 divided by z. This allows me to skip those t values that don't affect the r value anyway. My precomputed starting value picked out the "least positive" square root modulo 8192 in my case.if((x & 7) != 1) return false;
Copy after loginint64 t = 4, r = 1; t <<= 1; r += ((x - r * r) & t) >> 1; t <<= 1; r += ((x - r * r) & t) >> 1; t <<= 1; r += ((x - r * r) & t) >> 1; // Repeat until t is 2^33 or so. Use a loop if you want.
Copy after loginEven if this code doesn't work for you any faster, I hope you enjoy some of the ideas. The complete test code is as follows, including precalculated tables.
int64 r, t, z; r = start[(x >> 3) & 1023]; do { z = x - r * r; if( z == 0 ) return true; if( z < 0 ) return false; t = z & (-z); r += (z & t) >> 1; if( r > (t >> 1) ) r = t - r; } while( t <= (1LL << 33) );
Copy after login
The above is the detailed content of How Can I Quickly Determine if a Large Integer is a Perfect Square Using Bitwise Operations?. For more information, please follow other related articles on the PHP Chinese website!

Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

Troubleshooting and solutions to the company's security software that causes some applications to not function properly. Many companies will deploy security software in order to ensure internal network security. ...

When using MyBatis-Plus or other ORM frameworks for database operations, it is often necessary to construct query conditions based on the attribute name of the entity class. If you manually every time...

Field mapping processing in system docking often encounters a difficult problem when performing system docking: how to effectively map the interface fields of system A...

Solutions to convert names to numbers to implement sorting In many application scenarios, users may need to sort in groups, especially in one...

Start Spring using IntelliJIDEAUltimate version...

Conversion of Java Objects and Arrays: In-depth discussion of the risks and correct methods of cast type conversion Many Java beginners will encounter the conversion of an object into an array...

When using TKMyBatis for database queries, how to gracefully get entity class variable names to build query conditions is a common problem. This article will pin...

Detailed explanation of the design of SKU and SPU tables on e-commerce platforms This article will discuss the database design issues of SKU and SPU in e-commerce platforms, especially how to deal with user-defined sales...
