Bagaimanakah Kita Boleh Menentukan dengan Cekap jika Nombor Besar ialah Segiempat Sempurna?

Pada permulaan program, lakukan beberapa pra-penapisan untuk mempercepatkan operasi dan menapis nombor bukan kuasa dua yang jelas, termasuk nombor negatif, nombor dengan 4 digit terakhir ialah 0 , dan nombor dengan 2 digit terakhir memenuhi keperluan tertentu Nombor keadaan (5 atau 8 dalam perpuluhan). Untuk 0, anggap ia sebagai nombor kuasa dua.

Seterusnya, gunakan teknik bitwise untuk menyemak sama ada baki modulo 255 = 3 = 3 5 17 ialah nombor segi empat sama Tatasusunan bad255 merekodkan sama ada setiap baki adalah nombor segi empat sama atas meja.

Untuk nombor yang melepasi pra-penapis, bahagikan dengan semua kuasa 2 (dalam cara carian binari) sehingga hasil bagi adalah ganjil.

Langkah terakhir ialah menganggarkan punca kuasa dua menggunakan kaedah yang serupa dengan lemma Hensel. Gelung dalam bermula dengan nilai awal yang diberikan oleh tatasusunan mula, yang memberikan anggaran sqrt (mod 8192). Anggaran ini dipertingkatkan secara berterusan melalui pengiraan berturut-turut, menggunakan helah bitwise untuk meningkatkan kelajuan.

Struktur kasar kaedah ini adalah seperti berikut:

1. Pratapis untuk mengalih keluar nombor bukan persegi yang jelas.
2. Semak sama ada baki modulo 255 ialah nombor segi empat sama.
3. Dibahagikan dengan kuasa 2.
4. Anggaran hitung punca kuasa dua menggunakan varian lemma Hensel.

Perlu diperhatikan bahawa pengarang algoritma ini mendakwa bahawa ia berjalan 35% lebih pantas daripada kaedah lain.

Atas ialah kandungan terperinci Bagaimanakah Kita Boleh Menentukan dengan Cekap jika Nombor Besar ialah Segiempat Sempurna?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!