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

Başlatan Kılıç, 06 Aralık 2020, 15:28:46

Kılıç

06 Aralık 2020, 15:28:46 Son düzenlenme: 06 Aralık 2020, 15:36:19 Kılıç
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



auto-reverse recording

esensoy

06 Aralık 2020, 16:10:06 #1 Son düzenlenme: 06 Aralık 2020, 16:18:10 esensoy
(a+b) > (c+d) kareleri dikkate almasak yetiyor sanki?
En tehlikeli an "zafer" anıdır.

muuzoo

06 Aralık 2020, 16:13:42 #2 Son düzenlenme: 06 Aralık 2020, 16:14:52 muuzoo
Alıntı yapılan: esensoy - 06 Aralık 2020, 16:10:06(a+b) > (c+d) kareleri dikkate almasak yetiyor sanki?

(3+2) ve (4+0) de patlar hocam örnek olarak.
gunluk.muuzoo.gen.tr - Kişisel karalamalarım...

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}
En tehlikeli an "zafer" anıdır.

Kılıç

Kareler tablosu yaptım. Biraz süre kısaldı.
auto-reverse recording

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

06 Aralık 2020, 19:32:13 #6 Son düzenlenme: 06 Aralık 2020, 19:43:25 z
(|a|+|b|)^2 - (|c|+|d|)^2 > 2(|ab|-|cd|) ise

(a^2 + b^2) > (c^2 + d^2) dir.
Bana e^st de diyebilirsiniz.   www.cncdesigner.com

Kılıç

06 Aralık 2020, 19:50:09 #7 Son düzenlenme: 06 Aralık 2020, 19:58:50 Kılıç
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?
auto-reverse recording

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,
En tehlikeli an "zafer" anıdır.

Kılıç

06 Aralık 2020, 20:19:24 #9 Son düzenlenme: 06 Aralık 2020, 20:20:46 Kılıç
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?
auto-reverse recording

esensoy

a=-25 ise;
kare[0xE7]=625 yerleştireceksiniz,
(-25 = 0xE7)
En tehlikeli an "zafer" anıdır.

Kılıç

06 Aralık 2020, 20:26:29 #11 Son düzenlenme: 06 Aralık 2020, 20:45:22 Kılıç
int sonuca;
a0xE7;
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.
auto-reverse recording

esensoy

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

yani;
kare[(uint8_ta] gibi??
En tehlikeli an "zafer" anıdır.

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

07 Aralık 2020, 01:19:54 #14 Son düzenlenme: 07 Aralık 2020, 01:36:20 RaMu
Kullanacağın mcu da DSP komutları varsa 3, 5 komut çevriminde yapılacak bir işlem gibi.
-----------------------------------


(a² ) > (c² +)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
Sorularınıza hızlı cevap alın: http://www.picproje.org/index.php/topic,57135.0.html

Yasal Uyarı: Picproje.org sitemizde 5651 sayılı kanunun 8. maddesine ve T.C.Knın 125. maddesine göre tüm üyelerimiz yaptıkları paylaşımlardan kendileri sorumludur. Picproje.org hakkında yapılacak tüm hukuksal şikayetleri İletişim sayfamızdan bize bildirdikten en geç 3 (üç) iş günü içerisinde ilgili kanunlar ve yönetmelikler çerçevesinde tarafımızca incelenerek gereken işlemler yapılacak ve site yöneticilerimiz tarafından bilgi verilecektir.