Home Java javaTutorial How Can I Quickly Determine if a Large Integer is a Perfect Square Using Bitwise Operations?

How Can I Quickly Determine if a Large Integer is a Perfect Square Using Bitwise Operations?

Jan 01, 2025 am 07:23 AM

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:

  1. 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 login
  2. I used a precomputed table to actually check if the remainder is square number.
  3. 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
    Trying to calculate the square root using a method similar to Hensel's Lemma

    : 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
  4. At this point, for our number to be a square number, its modulus must be 1 over 8.
  5. The basic structure of Hensel’s lemma is as follows. (Note: untested code; if that doesn't work, try t=2 or 8.)

    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 login
    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 & 7) != 1)
        return false;
    Copy after login
    The 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.

    int64 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 login

    Even 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!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
3 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
3 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Article Tags

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Top 4 JavaScript Frameworks in 2025: React, Angular, Vue, Svelte Top 4 JavaScript Frameworks in 2025: React, Angular, Vue, Svelte Mar 07, 2025 pm 06:09 PM

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? How do I implement multi-level caching in Java applications using libraries like Caffeine or Guava Cache? Mar 17, 2025 pm 05:44 PM

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 Node.js 20: Key Performance Boosts and New Features Mar 07, 2025 pm 06:12 PM

Node.js 20: Key Performance Boosts and New Features

How does Java's classloading mechanism work, including different classloaders and their delegation models? How does Java's classloading mechanism work, including different classloaders and their delegation models? Mar 17, 2025 pm 05:35 PM

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

Iceberg: The Future of Data Lake Tables Iceberg: The Future of Data Lake Tables Mar 07, 2025 pm 06:31 PM

Iceberg: The Future of Data Lake Tables

Spring Boot SnakeYAML 2.0 CVE-2022-1471 Issue Fixed Spring Boot SnakeYAML 2.0 CVE-2022-1471 Issue Fixed Mar 07, 2025 pm 05:52 PM

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 can I use JPA (Java Persistence API) for object-relational mapping with advanced features like caching and lazy loading? Mar 17, 2025 pm 05:43 PM

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? How do I use Maven or Gradle for advanced Java project management, build automation, and dependency resolution? Mar 17, 2025 pm 05:46 PM

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

See all articles