Bir `uzun' değerin tam kare olup olmadığını (yani karekökünün başka bir tamsayı olup olmadığını) belirlemenin en hızlı yolunu arıyorum:
Math.sqrt()
kullanarak yaptım.
fonksiyonunu kullanıyorum, ancak bunu daha hızlı yapmanın bir yolu olup olmadığını merak ediyorum.
Kendinizi yalnızca tamsayı alanıyla sınırlandırın.İşte benim şu anda yaptığım çok basit ve anlaşılır yöntem:
public final static boolean isPerfectSquare(long n)
{
if (n < 0)
return false;
long tst = (long)(Math.sqrt(n) + 0.5);
return tst*tst == n;
}
Not: Bu fonksiyonu birçok Project Euler probleminde kullanıyorum. Böylece başka hiç kimse bu kodu korumak zorunda kalmayacak. Ve bu tür bir mikro optimizasyon aslında bir fark yaratabilir, çünkü zorluğun bir kısmı her algoritmayı bir dakikadan daha kısa sürede yapmaktır ve bu fonksiyonun bazı problemlerde milyonlarca kez çağrılması gerekecektir.
Sorun için farklı çözümler denedim:
0.5
eklemenin gerekli olmadığını buldum, en azından benim makinemde.Math.sqrt()
metodundan biraz daha yavaştı. Bunun nedeni muhtemelen Math.sqrt()
metodunun Newton'unkine benzer bir şey kullanması, ancak donanımda uygulandığı için Java'dakinden çok daha hızlı olmasıdır. Ayrıca, Newton Yöntemi hala çiftlerin kullanılmasını gerektiriyordu.Math.sqrt()
den daha yavaştı.or
deyimlerini kullanmak C++'da switch
kullanmaktan daha hızlıdır, ancak Java ve C#'da or
ve switch
arasında bir fark yok gibi görünmektedir.or
deyimi yerine sadece if(lookup[(int)(n&0x3F)]) { test } else return false;
. Şaşırtıcı bir şekilde, bu (sadece biraz) daha yavaştı. Bunun nedeni dizi sınırlarının Java'da kontrol edilmesidir.Sayısal Analiz dersinde geçirdiğim korkunç zamanları düşünüyordum.
Ve sonra hatırladım, Quake Kaynak kodundan 'net etrafında dolaşan bir fonksiyon vardı:
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // wtf?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
#ifndef Q3_VM
#ifdef __linux__
assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
return y;
}
Temel olarak Newton'un yaklaşım fonksiyonunu (tam adını hatırlayamıyorum) kullanarak bir karekök hesaplar.
Kullanılabilir olmalı ve hatta daha hızlı bile olabilir, olağanüstü id software'in oyunlarından birinden!
C++ dilinde yazılmıştır, ancak fikri edindikten sonra aynı tekniği Java'da yeniden kullanmak çok zor olmayacaktır:
İlk olarak şu adreste buldum: http://www.codemaestro.com/reviews/9
Newton'un yöntemi wikipedia'da açıklanmıştır: http://en.wikipedia.org/wiki/Newton%27s_method
Nasıl çalıştığına dair daha fazla açıklama için bağlantıyı takip edebilirsiniz, ancak çok fazla önemsemiyorsanız, blogu okuduğumdan ve Sayısal Analiz dersini aldığımdan kabaca hatırladığım şey bu:
* (long*) &y
temelde hızlı bir uzun fonksiyona dönüştürme fonksiyonudur, böylece ham baytlar üzerinde tamsayı işlemleri uygulanabilir.* (float*) &i
değeri tekrar kayan noktaya dönüştürür.Yaklaşım fonksiyonu, fonksiyonu sonuç üzerinde ne kadar çok yinelerseniz o kadar kesin değerler verir. Quake'in durumunda, bir iterasyon "yeterince iyi", ama eğer sizin için değilse... o zaman ihtiyacınız olduğu kadar iterasyon ekleyebilirsiniz.
Bu daha hızlı olmalıdır çünkü naif kare köklemede yapılan bölme işlemlerinin sayısını basit bir 2'ye bölme işlemine (aslında bir * 0.5F
çarpma işlemi) indirger ve bunun yerine birkaç sabit sayıda çarpma işlemi ile değiştirir.
Eğer "doğru" karekökü bulmaya çalışmak için ikili bir doğrama yaparsanız, elde ettiğiniz değerin söylenebilecek kadar yakın olup olmadığını oldukça kolay bir şekilde tespit edebilirsiniz:
(n+1)^2 = n^2 + 2n + 1
(n-1)^2 = n^2 - 2n + 1
Yani n^2
yi hesapladıktan sonra seçenekler şunlardır:
n^2 - 2n + 1 < hedef < n^2
: aynentarget < n^2 - 2n + 1
: daha düşük bir n
üzerinde ikili doğramahedef > n^2 + 2n + 1
: daha yüksek bir n
üzerinde ikili doğrama(Üzgünüm, bu mevcut tahmininiz olarak n
ve parametre için hedef
kullanır. Karışıklık için özür dileriz!)
Bunun daha hızlı olup olmayacağını bilmiyorum ama denemeye değer.
EDIT: İkili doğrama tüm tamsayı aralığını almak zorunda değildir, (2^x)^2 = 2^(2x)
, bu nedenle hedefinizdeki en üst küme bitini bulduğunuzda (bu bir bit çevirme numarasıyla yapılabilir; tam olarak nasıl olduğunu unuttum) hızlı bir şekilde bir dizi potansiyel cevap alabilirsiniz. Unutmayın, saf bir ikili doğrama hala sadece 31 veya 32 iterasyona kadar sürecektir.
Hız istiyorsanız, tamsayılarınızın sonlu boyutta olduğu göz önüne alındığında, en hızlı yolun (a) parametreleri boyuta göre bölmek (örneğin, en büyük bit kümesine göre kategorilere ayırmak) ve ardından değeri bu aralıktaki mükemmel kareler dizisine karşı kontrol etmek olacağından şüpheleniyorum.