Bagaimanakah Saya Boleh Menentukan dengan Cepat sama ada Integer Besar ialah Dataran Sempurna Menggunakan Operasi Bitwise?

Walaupun algoritma adalah kira-kira 35% lebih pantas daripada kod yang anda berikan, hasil sebenar mungkin berbeza antara CPU yang berbeza (x86) dan bahasa pengaturcaraan (C/C). Kaedah dalam artikel ini dibahagikan kepada tiga bahagian:

1. Tapis jawapan yang jelas: masukkan nombor negatif, semak 4 digit terakhir (dapati menyemak 6 digit terakhir tidak membantu), jawab 0. (Apabila membaca kod berikut, sila ambil perhatian bahawa input saya ialah int64 Hasil darab dua nombor perdana yang berbeza, jadi modulo segi empat sama 255 hanya mempunyai baki kira-kira 1/8. Walau bagaimanapun, dalam pengalaman saya, kos menggunakan operator modulo (%) melebihi faedah, jadi saya menggunakan sedikit helah yang melibatkan 255 untuk mengira bakinya. (Lebih baik atau lebih teruk, saya tidak menggunakan helah membaca bait individu daripada perkataan, hanya bitwise DAN dan beralih.)

   if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )
       return false;
   if( x == 0 )
       return true;

Saya menggunakan jadual prakiraan untuk benar-benar menyemak sama ada bakinya ialah nombor segi empat sama .

2. 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.

   Cuba mengira punca kuasa dua menggunakan kaedah yang serupa dengan Hensel's Lemma

   : Sebelum ini, saya menggunakan dua Carian membahagikan semua baki yang dibangkitkan dengan kuasa 2:

   if( bad255[y] )
       return false;
   // However, I just use a table of size 512

Pada ketika ini, untuk nombor kita menjadi nombor segi empat sama, modulusnya mestilah 1 berbanding 8.

3. Struktur asas lemma Hensel adalah seperti berikut. (Nota: kod yang belum diuji; jika itu tidak berkesan, cuba t=2 atau 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;

   Ideanya ialah pada setiap lelaran, anda menambah satu bit pada r," Punca kuasa dua bagi (Perhatikan bahawa jika r ialah punca kuasa dua bagi .) Memandangkan punca kuasa dua sebenar kita adalah kurang daripada 2^32, pada ketika itu kita sebenarnya boleh menyemak sama ada r atau t/2-r ialah punca kuasa dua sebenar bagi x. Dalam kod sebenar saya, saya menggunakan gelung yang diubah suai berikut:

   if((x & 7) != 1)
       return false;

   Pertambahan kelajuan di sini boleh diperolehi dalam tiga cara: Nilai permulaan yang diprakira (bersamaan dengan kira-kira 10 lelaran gelung ), keluar dari gelung lebih awal dan langkau beberapa nilai t. Untuk bahagian terakhir, saya perhatikan z=r-x*x dan gunakan helah bit untuk menetapkan t kepada kuasa terbesar 2 dibahagikan dengan z. Ini membolehkan saya melangkau nilai t yang tidak menjejaskan nilai r. Nilai permulaan prakiraan saya memilih modulo punca kuasa dua "paling positif" 8192 dalam kes saya.

   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.

   Walaupun kod ini tidak berfungsi untuk anda dengan lebih pantas, saya harap anda menikmati beberapa idea tersebut. Kod ujian lengkap adalah seperti berikut, termasuk jadual prakiraan.

   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) );

Atas ialah kandungan terperinci Bagaimanakah Saya Boleh Menentukan dengan Cepat sama ada Integer Besar ialah Dataran Sempurna Menggunakan Operasi Bitwise?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!