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
(a+b) > (c+d) kareleri dikkate almasak yetiyor sanki?
Alıntı yapılan: esensoy - 06 Aralık 2020, 13:10:06(a+b) > (c+d) kareleri dikkate almasak yetiyor sanki?
(3+2) ve (4+0) de patlar hocam örnek olarak.
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}
Kareler tablosu yaptım. Biraz süre kısaldı.
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.
(|a|+|b|)^2 - (|c|+|d|)^2 > 2(|ab|-|cd|) ise
(a^2 + b^2) > (c^2 + d^2) dir.
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?
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,
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?
a=-25 ise;
kare[0xE7]=625 yerleştireceksiniz,
(-25 = 0xE7)
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.
İşaretli değişkeni işaretsizmiş gibi algılamasını sağlatabiliyor musunuz?
yani;
kare[(uint8_t) a] gibi??
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.
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
Şimdi programın başka bir yeri önemli vakit alıyor.
Elimizdeki baytın bir sınır içinde olduğunu algılamamız gerekiyor.
if a > ust then
sonuc = 5
else if a < alt then
sonuc = 3
else
sonuc = 1;
Baytın bir aralıkta olduğunu nasıl daha HIZLI algılarım?
Sonra asm ne işe yarayacak boşverin diyorlar.
Ust Alt değerleri sabit ise Switch case ile hızlanır.
Ust Alt değerleri sabitse yine tablo kullanabilirsin.
Daha başka yöntemlerde vardır, düşünmek lazım.
Bu haliyle ne kadar sürüyor, asm çıktısına baktın mı?
Pin toggle yaparak frekansmetre ile ölçüyorum. Bu kısmı iptal edince 2 kat kadar hızlanıyor.
İki kare farkı olarak denediniz mi?
Farkı değil toplamı kıyaslanması gerekiyor
Bu tip sorulara verilecek cevapta islemcinin komut kumesinde neler var sorusu cok kritiktir.
beden kareleri yada mutlak değerleri üzerinde uğraşıyorsunuz..?
Neden sıfırdan büyük olup olmadıkları ve parantez içi (Kareleri olmadan) toplamlarının kıyasını yapmıyorsunuz..?
a>c ve b>d ise kestirmeden (a+b)>(c+d) ve (a² + b²) > (c² +d²) diyebiliriz sanırım.
negatif iseler işaretini değiştirip test etmek ayrıca gerekir.
Tablo falanda gerekmez.
Sen sayıların hepsini pozitif kabul etmişsin.
Üstelik a>c fakat d>b ise ne olacak?
Derleyicinin optimizasyon ayarlarını da mutlaka kontrol edin,
Belki hız yönündeki optimizasyon fark yaratır,
Alıntı yapılan: Kılıç - 08 Aralık 2020, 00:05:35Farkı değil toplamı kıyaslanması gerekiyor
(https://i.ibb.co/P9j9vw6/IMG-20201208-111501.jpg) (https://ibb.co/P9j9vw6)
Bu şekilde daha hızlı olabilir
@serdararikan Gösterdiğiniz yöntem bayağı mantıklı benim aklıma gelmemişti daha önceki yorumlarda benimde bu kıyaslamaya çözüm aradığımı söylemiştim.
Sizin yaklaşımınız 4 çarpımı 2 çarpıma indiriyor.
Bunu kullanıcağım.
Alıntı yapılan: Emre_Tuncay_ - 08 Aralık 2020, 12:21:49@serdararikan Gösterdiğiniz yöntem bayağı mantıklı benim aklıma gelmemişti daha önceki yorumlarda benimde bu kıyaslamaya çözüm aradığımı söylemiştim.
Sizin yaklaşımınız 4 çarpımı 2 çarpıma indiriyor.
Bunu kullanıcağım.
En son kısımda c-d yazmışım c-b olacak