Hızlı kıyaslama ? (a² + b²) > (c² +d²)

[power20]

a,b,c,d  işaretli 8 bit sayılar oluyor. (-128 .. 127)

Aşağıdaki kıyaslamayı MCU veya bilgisayar ile en kısa sürede nasıl yaparım?
Mevcut hız yetersiz geldi.

(a² + b²) > (c² +d²)


Sayıların gerçekten karesini almadan bit düzeyinde işlem yapabilmek isterim.

a²+ b² = (a + b)² – 2ab     ve
a² + b² = (a – b)² + 2ab    eşitliklerini kullanarak süre  kısalmış olmadı.

Şu sayfadakileri anlamadım. Konu için faydalı mıdır?
https://math.stackexchange.com/questions/153603/diophantine-equation-a2b2-c2d2

[esensoy]

(a+b) > (c+d) kareleri dikkate almasak yetiyor sanki?

[muuzoo]

(a+b) > (c+d) kareleri dikkate almasak yetiyor sanki?

(3+2) ve (4+0) de patlar hocam örnek olarak.

[esensoy]

O zaman kare tablosu oluşturup ordan çekmek mantıklı sanki

int16 kare[256] = {16384,16129,15876,15625,15376,15129,14884,14641,14400,14161,13924,13689,13456,13225,12996,12769,12544,12321,12100,11881,11664,11449,11236,11025,10816,10609,10404,10201,10000,9801,9604,9409,9216,9025,8836,8649,8464,8281,8100,7921,7744,7569,7396,7225,7056,6889,6724,6561,6400,6241,6084,5929,5776,5625,5476,5329,5184,5041,4900,4761,4624,4489,4356,4225,4096,3969,3844,3721,3600,3481,3364,3249,3136,3025,2916,2809,2704,2601,2500,2401,2304,2209,2116,2025,1936,1849,1764,1681,1600,1521,1444,1369,1296,1225,1156,1089,1024,961,900,841,784,729,676,625,576,529,484,441,400,361,324,289,256,225,196,169,144,121,100,81,64,49,36,25,16,9,4,1,0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841,900,961,1024,1089,1156,1225,1296,1369,1444,1521,1600,1681,1764,1849,1936,2025,2116,2209,2304,2401,2500,2601,2704,2809,2916,3025,3136,3249,3364,3481,3600,3721,3844,3969,4096,4225,4356,4489,4624,4761,4900,5041,5184,5329,5476,5625,5776,5929,6084,6241,6400,6561,6724,6889,7056,7225,7396,7569,7744,7921,8100,8281,8464,8649,8836,9025,9216,9409,9604,9801,10000,10201,10404,10609,10816,11025,11236,11449,11664,11881,12100,12321,12544,12769,12996,13225,13456,13689,13924,14161,14400,14641,14884,15129,15376,15625,15876,16129}

[power20]

Kareler tablosu yaptım. Biraz süre kısaldı.

[volkanunal]

Bu tarz hesaplamalarda her zaman lookup table daha mantıklı oluyor hocam. Run-time içerisinde değil de yaptığınız gibi bir array içerisinde bulundurmak daha avantajlı olmakta. CRC hesaplarında da genel de look-up table yapıları mevcut.

[z]

(|a|+|b|)^2 - (|c|+|d|)^2 > 2(|ab|-|cd|) ise

(a^2 + b^2) > (c^2 + d^2) dir.

[power20]

Burada kare almak asıl vakit harcıyor. Onu tabloyla hallettim. Sayıların bu uygulamada belli değerin üzerine çıkamayacağı anlaşıldığı için ufak tablo yeterli oldu.

Şimdi derleyicinin orijinal mutlak değer alma  fonksiyonu vakit harcıyor.

(Sayıyı kare almak için tabloya uygularken mutlak değer gerekiyor.)

Mutlak değerden kaçınmak için, negatif sayıyı yok edecek bir sayı ile toplarım, 2 kat büyük tablo yaparım diye düşündüm. Kare sorgulama tablosu.

Veya mutlak değeri kolay yoldan nasıl alırım?

[esensoy]

Mutlak değer almaya gerek var mı?
-1 i kare[0xFF] e ,
-2 yi kare[0xFE] ye
-3 ü kare[0xFD] ye
.
.
.
0 ve pozitifler kendi yerlerinde olacak, böylece kare[a] dan doğru değer gelecek,

[power20]

Sayının duruma göre ne çıktığını bilmiyorum sabit değil. -25 in karesini tablodan nasıl alırım?  Köşeli parantez içine negatif index olur mu?
25in karesi = Kare[25]
-25in karesi?

[esensoy]

a=-25 ise;
kare[0xE7]=625 yerleştireceksiniz,
(-25 = 0xE7)

[power20]

int sonuc, a;
a= 0xE7;
sonuc = kare[a];

   işretsiz sayı gibi düşünürsek E7 = 231 olduğunu gördüm.   C ile belki sorun çıkmaz .
Delphi hata verdi. Benim gibi düşünmüş. Negatif index olmaz diyor.

[esensoy]

İşaretli değişkeni işaretsizmiş gibi algılamasını sağlatabiliyor musunuz?

yani;

kare[(uint8_t) a]

gibi??

[Emre_Tuncay_]

Bu tarz bir şeye FPGA'de ihtiyacım olmuştu. Kare alırken çarpım işlemi yüzünden çok fazla saat frekansı harcıyordum işin içinden çıkamayınca öyle bıraktım.

Cordic algoritmasının sanki buna bir çözümü vardı. Sanırım kartezyen koorinat düzleminden, polar koordinat düzlemine geçişte kullanılıyordu. Cordic'in bu koordinat düzlemi çözümüne pek hakim değilim fikir vermesi açısından paylaşmak istedim.

[RaMu]

Kullanacağın mcu da DSP komutları varsa 3, 5 komut çevriminde yapılacak bir işlem gibi.
-----------------------------------

(a² + b²) > (c² +d²)

yaklaşık değer veren aşağıdaki işlem:
a,b,c,d nin mutlak değerleriyle,
a<b ve c<d ile

(a>>1)+b ?> (c>>1)+d

şeklinde deneyip hata var mı karşılaştıran bir program ile doğrularsan kullanılabilir.
Kaynak:

https://stackoverflow.com/questions/3506404/fast-hypotenuse-algorithm-for-embedded-processor