


How Can I Quickly Determine if a Large Integer is a Perfect Square Using Bitwise Operations?
Jan 01, 2025 am 07:23 AMAlthough 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 Article

Hot tools Tags

Hot Article

Hot Article Tags

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

Top 4 JavaScript Frameworks in 2025: React, Angular, Vue, Svelte

How do I implement multi-level caching in Java applications using libraries like Caffeine or Guava Cache?

Node.js 20: Key Performance Boosts and New Features

How does Java's classloading mechanism work, including different classloaders and their delegation models?

Iceberg: The Future of Data Lake Tables

Spring Boot SnakeYAML 2.0 CVE-2022-1471 Issue Fixed

How can I use JPA (Java Persistence API) for object-relational mapping with advanced features like caching and lazy loading?

How do I use Maven or Gradle for advanced Java project management, build automation, and dependency resolution?
