Tek satır kodla sinus hesaplama integer.

[devreci]

Bolmeler ve karekok olmasaydi tadindan yenmezdi.

Hocam gerçekten yaklaştın ama tam olarak anlamadın . Tartışmaya girmek istemiyorum aslında buna sevindim sen de anlamadıysan kimse anlamaz , o yüzden algoritma halen biraz gizli sayılır.

arcsin, acos, log2 , pow , pow'da yeni bir şey var mı bilmiyorum ama tamamen algoritmaları bana aittir. Ayrıca çok hızlı çalışan hiçbir döngünün olmadığı karekök de var.

Satıyorum ... kodlar test için yazıldı ve çok optimize edilebilir mesela karekök almaya ithiyaç yok ve diğer kodlarda çok sadeleştime yapılabilir .

Satın almak isteyen olursa devreci [Q] yahoo.com mailinden bana ulaşınız.

 

[Mikro Step]

Kendi algoritmani sen anlamamissin.

Hic bir dongunun olmadigi karekok. Bak bu ilginc iste. Hem de cok ilginc.

 

[czorgormez]

döngü-iterasyon olmadan ters kök alan bir yöntem var. tabi bu yöntem tek atışta çok yüksek doğruluğa ulaşamıyor ama çoğu işlem için yeterli. hikayesi de ilginç. 2005 yılında quake 3 oyununun kaynak kodları açılınca orada insanlar fark ediyor. kodun en son satırı açılarak precision arttırılabilir. tabi bu 1/kök buluyor. kalanı matematikçiler düşünsün.

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 );               // what the fuck?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

  return y;
}

burada mantığını detaylı anlatıyor.

Understanding Quake’s Fast Inverse Square Root – BetterExplained

 

[Mikro Step]

@devreci

Karekok algoritmana talip olabilirim biraz ozelliklerinden bahset.

Parasi ne ise oderim ama seni de temizletirim. Ona gore.

Baska turlu algoyu tekelimde tutamam.

 

[devreci]

İki sayfa önde log2 hesabı vermiştim orada da döngü yok , tek döngü var o da floata çevirmek için matiss vs uğraşamamak için öyle yaptım , direkt float girilirse hiç döngüye girmeden hesaplıyor sayıya göre e-4 ile e-7 arası hata yapıyor.

Karekökü de buradan türettim ne yazık ki hata payı var. Quake3 kodlarına benzemiyor , bakayım bu yüzde kaç hata yapıyor , orada 1/sqrt hesaplamış bendeki direkt karekök temelde aynı mantık olabilir. Satma işi için , söyle düşündüm bunlar kullanılarak bir tez yazılabilir

 

[Mikro Step]

Bana fixpoint karekok algoritmasi lazim.
32.32 formatta kendi yazdigim kod var. Senin ki iyiyse seninkini kullanirim.

 

[Mikro Step]

@devreci bu basligi acinca tum dikkatim dagildi havya projeme ara verip uzun suredir yazmak isteyipte surekli erteledigim sin ve cos fonksiyonlarimi nihayet yazdim.

sin ve cos <=1 oldugu cihetle 32 bitlik sonuc veren fonksiyonum bugun sorunsuz calismaya basladi.

Oncelikle Coordic mi yoksa Taylor mu?

Taylor serisi 4 terimle yeterince dogru sonuclar veriyor.

Fakat

sin(x)=x - (x*x*x/6)+ (x*x*x*x*x/120) - (x*x*x*x*x*x*x/5040) islemi cok sikintili.

Bu islemin dogru sonuclar verebilmesi icin denemedim ama 64x64 hatta daha fazlasina ihtiyac var gibi.

Cok fazla ram ve hesaplama istiyor.

Cordic ise harika. Dogrudan cordic ile tan hesaplatip ordan sin ve cos hesaplatmak yerine cordic ile Sin ve cos fonksiyonlarini hic ram kullanmadan dogrudan registerlar uzerinden 32 iterasyonda 32x32 ve 64 bit toplama ile hesaplatarak 0...1 araligindaki sonuclari 10 binde 1 hassasiyette hesaplattim. 64x64 bit ve 128 bit toplama ile hassasiyet modern hesap makinesi sinirlarina ulastirilabilir fakat hesaplama suresini artirmanin ve ram kullanmanin anlami yok.

Tan hesabi yapmak yerine sin ve cos hesaplatiyorum.

Fakat sin ve cos islemine ilave olarak tan hesabi icin 32 bit /32 bit isleminin sonucunu 64 bit olarak verecek bolme rutini canimi sikiyor. Henuz bu bolme rutinini yazmadim. Kaydir ve cikart islemi yerine oncelikle 1 cycle tutan 32x32 carpmadan ne kadar yararlanabilirim onu arastiracagim.

 

[devreci]

Hocam kafayı taktın ha , üç beş ateşle yollıyım işte kodu , bölme ve karekök yok , sadece çarpma ve if , iki satır
kimse sallamıyor ama gerçekten güzel bir buluş, mesela bu elinde varsa intel amd nvidia çok kolaylıkla işe girebilme imkanı olur iş derken dış kapı mandalı değil gerçek bir iş , akademik olarak da güzel şeyler olabilir.

Döngüsüz de sin cos hesabım var , fakat bu o kadar küçük ki döngü olasa da ondan daha hızlı olabilir diye hiç uğraşmadım.

Madem bu kadar matematiği seviyorsun neden oyunyapimi ile uğraşmıyorsun , havya yapıyorsun , elektronik işinden para kazanma şansı hiç yok hele ki bu cehennem çukuru ülkede , en azından bir ihtimal para kazanma şansı olur.

 

[Mikro Step]

Ben boyle boyle algoritmalar gelistirdim diye Intele, AMD'ye ARM'a iki satir mail yaz.
Bakarsin satin alirlar ya da is teklif ederler.

Ben el .iki ile gerdege girmem.

 

[Ahmet]

Madem bu kadar matematiği seviyorsun neden oyunyapimi ile uğraşmıyorsun , havya yapıyorsun , elektronik işinden para kazanma şansı hiç yok hele ki bu cehennem çukuru ülkede , en azından bir ihtimal para kazanma şansı olur.

Elektronik işinden para kazanmak ağaç yetiştirmek gibi.
Öğrenci ödevleri,
basit projeler örn;
555 ile çakar tahmin ettiğinizden çok daha fazla satılıyor özellikle büyük şehirlerde.
Veya sürekli bir iş çok temelden başlayıp istediğiniz düzeye gelmek çok kolay mesela bir elektronik kart dizgi işine girip orda tasarımcılar ile sohbet ederek çalışırken duyduklarınızı eve gelip tırmalarsanız çabuk öğreniyorsunuz.
Bunun bir üstü elektronik tamircisinde çalışmak buradan da tasarımsal çok detay öğreniyorsunuz böyle adım adım ürün geliştirmeye kadar gidersiniz ama malesef çağımız hep 1 adım atayım ve o adım çok büyük olsun istiyor bu yüzden ön yargı büyük.

Kendini ne kadar yetişririsen o kadar tatmin edici düzeyde çalışırsın ilk iş yerinin haftada 36 saat çalışma süresi olsun araba versin yemek kartı versin bilmem kaç bin dolar maaş versin diye hayaller kurarsan bilinçaltın sana bunları ancak rüyanda gösterir : ))

 

[Mikro Step]

Benim kullandigim algoritma dunyaca bilinen matematik altyapisini kullaniyor.

sin(a+b)=sin(a)cos(b)+sin(b)cos(a)
cos(a+b)=cos(a)cos(b)+sin(a)sin(b)

Programin icine 64, 32,16, 8, 4, 2, 1 acilarinin sin ve cos degerlerini bir tabloya gomdum.

Sin ve cos degeri hesaplanacak degerimiz acimiz a olsun. Mesela a=41 olsun.

41>=64 sorusunu cevaplayalim. Cevap Hayir.
41>=32 sorusunu cevaplayalim. Cevap Evet.

o halde a=32 dir. Hemen sin 32 ve cos 32 yi tablodan okuyalim.
41-32=9

9>=16 ? hayir.

9>=8 evet.
Hemen sin 8 ve cos 8 i tablodan okuyalim.

sin(32+8)=sin(32)cos(8)+sin(8)cos(32)
cos(32+8)=cos(32)cos(8)+sin(32)sin(8)

9-8=1

simdi devam edelim.

1>=4 hayir.
1>=2 hayir.
1>=1 evet.

sin(40+1)=sin(40)cos(1)+sin(1)cos(40)
cos(40+1)=cos(40)cos(1)+sin(40)sin(1)

sin 40 ve cos 40 daha onceden hesaplanmisti. sin1 ve cos 1 de tabloda var.

Cevap bulundu.

Bu cordic algoritmasinin temeli sayilir. Standart cordic hesabinda tan hesaplanir ve sadece tan tablosu tutulur.
tan degeri hesaplandiktan sonra sin ve cos basitce hesaplanir.
Standart cordicde acimiz acilar toplamindan buyuk ise acilar toplanir kucuk ise cikartilir.
Benim modifiye ettigimde buyuk yada esitse toplama kucukse dokunma mantigi uygulandigi icin
algoritmada hissedilir hiz artisi da oluyor.

Cordic mantiginin aciklamasina bakarsaniz vektoru dondurmekten bahsedilir zaten cordic ismi ordan gelir.
Vektoru dondurmeyi anlamaya calismayin. Iki acinin toplam ve farkini hesaplamaya yarayan yukaridaki iki baginti bu algoritmanin kalbi oluyor.

Zaten bu iki baginti da vector dondurmeyle alakali.

 

[Hazel]

@Mikro Step Cordic te senin yaptigin gibi sin(a+b) acilimi yoktu sanki, orada dogrudan tablodaki belirli tan degerlere yakinsamayla yapilmiyormuydu.

 

[Mikro Step]

Hazir verilen algoritmalari okursaniz sihir gorursunuz.

Isin matematiginden yola cikarsaniz ortada sihir olmadigini gorursunuz.

Yukaridaki mesajimda sorunun cevabini kismen vermistim.

sin(a+b) ve cos(a+b) yerine tan(a+b) den yola cikarsan standart cordic algoritmasini elde edersin.

 

[Hazel]

himmm sen yazana kadar farketmedim, zaten ben gelistirdim demissin.

 

[czorgormez]

elektronik veya otomotiv veya emlakçılık para kazanmak ya da kazanamamak sadece sizin yaklaşımınızla alakalı. mühendis gibi düşünüp ticaret yapmaya kalkarsanız (çoğumuz gibi) para kazanamaz ancak geçinirsiniz. işadamı-girişimci gibi düşünüp oyun oynamayı bırakır. satılabilir çözüm üretmeye odaklanırsanız zengin olabilirsiniz. benim şahit olduğum örnekleri çoktur.

 

[ex_machina]

Arkadaşlar sayfalarca bomboş tartışmışsınız. Bir tane bile test raporu eklenmemiş. Bir de sözde mühendis olacaksınız.

Eğer oyun geliştiricilerinin takıldığı forumları incelerseniz, zaten bu tarz hızlı trigonometrik hesaplama algoritmaları üzerine yıllardır kafa yorduklarını görürsünüz. Yalnız bu algoritmaların zayıf noktası kümülatif hesaplamada ortaya çıkıyor. Bir işlemin çıktısı sonraki işleme girdi olarak verildiğinde ve bu iterasyon defalarca kez tekrarlandığında o küçük hatalar birikerek ihmal edilemez hatalara sebep oluyor. (Grafik motorlarında işlemler çoğunlukla böyle)

O yüzden ben yaptım oldu derseniz kimse sizi ciddiye almaz. Bunun için benchmark testleri var. Klasik algoritmalar ile kendi algoritmanızı, hız, hassasiyet, kümülatif hata, vb. gibi değişkenler üzerinden karşılaştıran benchmark test sonuçlarını paylaşırsanız daha ayakları yere basan bir tartışma olurdu.

Ayrıca kod paylaşmanıza gerek yok. İşlemci mimarisine özel tamamen kapalı kaynak kodlu ve önceden derlenmiş kütüphane oluşturup satabilirsiniz. Ama ondan önce şuraya bir algoritma analizi raporu koyun ki, almayı düşünen kişi neyi satın aldığını bilsin.

 

[taydin]

Arkadaşlar sayfalarca bomboş tartışmışsınız.

Yapılmış güzel bir çalışmaya böyle negatif bir yaklaşım hoş değil. Yapılan her türlü çalışma, sonuç getirse de getirmese de değerlidir, yararlıdır, öğreticidir. Ki burada sonuç alınmadığını de söylemek yanlış olur. Belki de kümülatif hesap yapılmayacak, sadece sinüs hesabı yapılıp sonuç kullanılacak.

Hatta bazan üzerinde çalıştığın problemin çözüldüğünü bilmeden uğraşırsın, bağımsız olarak çözümü bulursun, sonra da başkasının daha önce çözdüğünü farkedersin. Bu da çok değerlidir. Var olanı farkında olmadan keşfettiysen, var olmayanı da keşfetme potansiyelinin olduğunu gösterir. Ama bizim millet bunu yapanlarla dalga geçmeyi sever "tekerleği yeniden keşfetmişsin " şeklinde.

İlla bir şeylerde negatif tepki göstereceksen, ödevini mesaj olarak yazmaya bile tenezzül etmeden resmini koyan, başlığa "ACİİİİLLLLL yarın lazım lütfen yardım" yazan, mesaja da "hocam bu ödevleri yarına teslim etmem lazım, konu hakkında EN UFAK bilgim yok, lütfen yardım edin" diyene göster.

 

[devreci]

Arkadaşlar sayfalarca bomboş tartışmışsınız. Bir tane bile test raporu eklenmemiş. Bir de sözde mühendis olacaksınız.

Eğer oyun geliştiricilerinin takıldığı forumları incelerseniz, zaten bu tarz hızlı trigonometrik hesaplama algoritmaları üzerine yıllardır kafa yorduklarını görürsünüz. Yalnız bu algoritmaların zayıf noktası kümülatif hesaplamada ortaya çıkıyor. Bir işlemin çıktısı sonraki işleme girdi olarak verildiğinde ve bu iterasyon defalarca kez tekrarlandığında o küçük hatalar birikerek ihmal edilemez hatalara sebep oluyor. (Grafik motorlarında işlemler çoğunlukla böyle)

O yüzden ben yaptım oldu derseniz kimse sizi ciddiye almaz. Bunun için benchmark testleri var. Klasik algoritmalar ile kendi algoritmanızı, hız, hassasiyet, kümülatif hata, vb. gibi değişkenler üzerinden karşılaştıran benchmark test sonuçlarını paylaşırsanız daha ayakları yere basan bir tartışma olurdu.

Ayrıca kod paylaşmanıza gerek yok. İşlemci mimarisine özel tamamen kapalı kaynak kodlu ve önceden derlenmiş kütüphane oluşturup satabilirsiniz. Ama ondan önce şuraya bir algoritma analizi raporu koyun ki, almayı düşünen kişi neyi satın aldığını bilsin.

İyi de exelerde zaten kıyaslama var. Oyunyapimi forumlarından alıntı değil , öyle ise linkini buraya ekleyebilrsin biz de inceleriz . Sen oyunyapimi ile mi uğraşıyorsun ?

 

[ex_machina]

Arkadaşlar sayfalarca bomboş tartışmışsınız.

Evet konuya böyle giriş yapmak pek hoş olmamış. Bunu kabul ediyorum.

Ben kodları başka yerden arakladın imasında bulunmadım. Benim asıl demek istediğim, biz sayılarla ilgili tartışıyoruz ama ortada sayısal değerlendirme yok. Daha önce paylaştığın exelerden herhangi bir çıkarımda bulunmak bizim için çok zor. Ayrıntılı bir testi ancak sen yapabilirisin. Çünkü bu kodun mimarı sensin.

Eğer gerçekten O(1) karmaşıklıkta sonucu buluyorsan bu çok büyük bir başarıdır. (Daha önceki mesajlarını da okudum, o yüzden bunu başardığına inanıyorum). Mesela @Mikro Step float değişkene, kareköke vs. takılmış. Oysa bunların hiçbir önemi yok. Çünkü algoritma karmaşıklığı bu şekilde ölçülmez. Eğer bir kod parçası O(1) karmaşıklık ile çalışıyorsa, teoride o kod optimize edilerek tek saykıla indirgenebilir. Aynı kodu float yerine Q-data format(integer) ile de kullanabilirsin. Bunun için bir herhangi bir engel yok.

Hatta ne demek istediğimi daha iyi anlatabilmek için, link verip başımdan savmak yerine doğrudan örnek koyuyorum;
Cmsis-DSP kütüphanesi için oldukça basit bir test hazırladım. Bu test sadece hız üzerine, hassasiyet için daha kapsamlı testler lazım. Ama en azından bir fikir veriyor.

Çalışma Süreleri(Cortex-M0, 48MHz):
arm_float_to_q15 -> 10.45us
arm_float_to_q31 -> 35.8us
arm_sin_f32 -> 35.15us
arm_sin_q15 -> 1.31us
arm_sin_q31 -> 4.33us
arm_q15_to_float -> 6.15us
arm_q31_to_float -> 6.93us

Sonuçlar:

Test Kodu:

 // MCU: STM32F030R8, Cortex-M0
 // Clock: 48MHz
 // Cortex-M0'larda DWT Cycle Counter yok.
 // DWT yerine SysTick timer ile süre ölçüyoruz. Hata ihmal edilebilir.
 
  float pi = 3.141592654f;

  float angle_f = 0.0f;
  float angle_f_norm = 0.0f;
  float sin_f = 0.0f;
  int16_t angle_q15 = 0;
  int32_t angle_q31 = 0;
  int16_t sin_q15 = 0;
  int32_t sin_q31 = 0;

  uint32_t T1 = 0, T2 = 0, T_delta = 0;
  float T_us = 0.0f;

  float angle_q15_in_f = 0.0f;
  float angle_q31_in_f = 0.0f;

  while (1)
  {
      angle_f = pi * (30.0f/180.0f); // 30 dereceden radyana dönüşüm
      angle_f_norm = angle_f * (1.0f / (2.0f * pi)); // Q1.15 ve Q1.31 format için normalizasyon

      T1 = SysTick->VAL;
      arm_float_to_q15(&angle_f_norm, &angle_q15, 1); // float(açı) -> Q1.15(açı)
      T2 = SysTick->VAL;
      T_delta = (T1-T2); // SysTick geriye sayıyıyor.O yüzden T2-T1 değil
      T_us = (float)T_delta * (1.0f/48.0f); // mikro saniye cinsinden işlem süresi
      __NOP(); // Breakpoint için boş saykıl

      T1 = SysTick->VAL;
      arm_float_to_q31(&angle_f_norm, &angle_q31, 1); // float(açı) -> Q1.31(açı)
      T2 = SysTick->VAL;
      T_delta = (T1-T2);
      T_us = (float)T_delta * (1.0f/48.0f);
      __NOP();

      T1 = SysTick->VAL;
      sin_f = arm_sin_f32(angle_f); // float ile çalışan sin() fonksiyonu
      T2 = SysTick->VAL;
      T_delta = (T1-T2);
      T_us = (float)T_delta * (1.0f/48.0f);
      __NOP();

      T1 = SysTick->VAL;
      sin_q15 = arm_sin_q15(angle_q15); // Q1.15 ile çalışan sin() fonksiyonu
      T2 = SysTick->VAL;
      T_delta = (T1-T2);
      T_us = (float)T_delta * (1.0f/48.0f);
      __NOP();

      T1 = SysTick->VAL;
      sin_q31 = arm_sin_q31(angle_q31); // Q1.31 ile çalışan sin() fonksiyonu
      T2 = SysTick->VAL;
      T_delta = (T1-T2);
      T_us = (float)T_delta * (1.0f/48.0f);
      __NOP();

      T1 = SysTick->VAL;
      arm_q15_to_float(&sin_q15, &angle_q15_in_f, 1); // Q1.15 -> float dönüşümü
      T2 = SysTick->VAL;
      T_delta = (T1-T2);
      T_us = (float)T_delta * (1.0f/48.0f);
      __NOP();

      T1 = SysTick->VAL;
      arm_q31_to_float(&sin_q31, &angle_q31_in_f, 1); // Q1.31 -> float dönüşümü
      T2 = SysTick->VAL;
      T_delta = (T1-T2);
      T_us = (float)T_delta * (1.0f/48.0f);
      __NOP();
  }

 

[Mikro Step]

@ex_machina

O kod optimize edilerek tek saykila indirgenebilir derken ne demek istedin anlamadim.

Mesela @Mikro Step float değişkene, kareköke vs. takılmış. Oysa bunların hiçbir önemi yok. Çünkü algoritma karmaşıklığı bu şekilde ölçülmez. Eğer bir kod parçası O(1) karmaşıklık ile çalışıyorsa, teoride o kod optimize edilerek tek saykıla indirgenebilir. Aynı kodu float yerine Q-data format(integer) ile de kullanabilirsin. Bunun için bir herhangi bir engel yok.