Apakah Cara Terpantas untuk Menentukan sama ada Punca Kuasa Dua Integer ialah Integer?

Cara terpantas untuk menentukan sama ada punca kuasa dua integer ialah integer

Penerangan Masalah

Saya sedang mencari cara terpantas Kaedah untuk menentukan sama ada integer panjang ialah kuasa dua sempurna (iaitu punca kuasa duanya ialah integer lain):

1. Saya melakukannya menggunakan fungsi Math.sqrt() terbina dalam, tetapi saya ingin tahu jika ada cara untuk melakukannya menggunakan medan integer , dengan itu meningkatkan kelajuan.


2. Adalah tidak praktikal untuk mengekalkan jadual carian (kerana terdapat lebih kurang 2^31.5 integer yang kuasa duanya kurang daripada 2⁶³).

Berikut ialah cara yang sangat mudah dan mudah yang saya lakukan sekarang:

{
jika (n < 0)

return false;

long tst = (long)(Math.sqrt(n) 0.5);
return tst*tst == n;
}

_{Nota: Saya menggunakan fungsi ini dalam banyak masalah Project Euler. Oleh itu, tidak akan ada sebarang penyelenggaraan pada kod ini pada masa hadapan. Dan pengoptimuman mikro ini sebenarnya boleh membuat perbezaan, kerana sebahagian daripada cabaran mengambil masa kurang daripada satu minit untuk menyelesaikan setiap algoritma, sedangkan fungsi ini perlu dipanggil berjuta-juta kali dalam beberapa masalah.}

---

Saya telah mencuba penyelesaian yang berbeza untuk masalah ini:

• Selepas ujian menyeluruh, saya mendapati bahawa menambah 0.5 pada keputusan Math.sqrt() adalah tidak perlu, sekurang-kurangnya pada mesin saya.


• Punca kuasa dua songsang pantas adalah lebih pantas daripada Math.sqrt() tetapi memberikan hasil yang salah untuk n >= 410881. Walau bagaimanapun, seperti yang dicadangkan oleh BobbyShaftoe, kita boleh menggunakan penggodaman FISR untuk n
• Kaedah Newton jauh lebih perlahan daripada Math.sqrt(). Ini mungkin kerana Math.sqrt() menggunakan sesuatu yang serupa dengan kaedah Newton, tetapi dilaksanakan dalam perkakasan dan oleh itu lebih pantas daripada di Java. Selain itu, kaedah Newton masih memerlukan penggunaan nombor titik terapung berketepatan ganda.
integer bertanda 64-bit positif), dan ia lebih perlahan daripada Math.sqrt().

• Carian binari adalah lebih perlahan. Ini masuk akal, kerana carian binari memerlukan purata 16 pas untuk mencari punca kuasa dua nombor 64-bit.


• Menurut ujian John, menggunakan pernyataan atau adalah lebih pantas daripada menggunakan suis dalam C, tetapi dalam Java dan C# nampaknya tiada perbezaan antara atau dan suis.


• Saya juga cuba membuat jadual carian (sebagai tatasusunan statik peribadi 64 boolean). Kemudian, daripada menggunakan suis atau atau pernyataan, saya hanya akan mengatakan if(lookup[(int)(n&0x3F)]) { test } else return false;. Yang mengejutkan saya, ini (sedikit) lebih perlahan. Ini kerana sempadan tatasusunan disemak dalam Java.

Atas ialah kandungan terperinci Apakah Cara Terpantas untuk Menentukan sama ada Punca Kuasa Dua Integer ialah Integer?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!