CORDIC algoritmasının kalbimde bedavaya yaşamasının nedeni
Floating Point'ten kaçınmak için Fixed Point kullanmak
- Floating Point yerine Fixed Point kullanarak gerçek sayılar ifade edilebilir
- 32 bit tamsayı türü kullanılarak üst 16 bit tam sayı kısmı, alt 16 bit ise kesir kısmı olarak ayrılır
- Bu sayede yaklaşık -32768.99997 ile 32767.99997 arası ifade edilebilir
- Programcı, ondalık noktanın konumunu belirleyerek hassasiyeti ayarlayabilir
- Float'tan Fixed Point'e dönüştürmek için 2^16 ile çarpıp ardından
int32_t'ye cast etmek gerekir
- Fixed Point'ten Float'a dönüştürmek için 2^16'ya bölmek gerekir
- Toplama ve çıkarma doğrudan çalışır; çarpma ve bölmede ise scaling factor'ü ayarlamak gerekir
CORDIC algoritmasına genel bakış
- CORDIC, "Co-ordinate Rotation Digital Computer" ifadesinin kısaltmasıdır ve 1950'lerin ortasında geliştirilmiştir
- Birim çember üzerindeki bir vektörü kademeli olarak küçük açılarla döndürerek sinüs ve kosinüs değerlerini bulma yöntemidir
- İkili aramaya benzer şekilde, hedef açıya yaklaşmak için önce büyük açılarla ilerlenir; ardından saat yönünde veya saat yönünün tersine açıyı her seferinde yarıya indirerek yakınsanır
- Maksimum dönüş açısı 90 derece (
π/2 radian) alınır ve 16 kez tekrar edilerek hedef açıya yakınsanır
- Yakınsanmış vektörün
y değeri yaklaşık sin(a), x değeri ise yaklaşık cos(a) olur
Matrisin yalnızca sabit çarpma kullanacak şekilde sadeleştirilmesi
- Dönüş matrisinde sinüs, kosinüs ve tanjant fonksiyonları bulunduğu için hesaplama karmaşıktır
- Tanjant fonksiyonu sabit açılarla döndürüldüğünden önceden hesaplanıp tabloda saklanabilir (yaklaşık 64 bayt)
- Kosinüs terimi her yinelemede ortaya çıkar, ancak yakınsama değeri sabittir (yaklaşık 0.6366); bu nedenle en sonda yalnızca bir kez çarpmak yeterlidir
Yalnızca Shift ve Add işlemlerini kullanmak
- Tanjant fonksiyonunda kullanılan açılar, arktanjant fonksiyonu ile
2^-i değerleri olacak şekilde seçilir
- Böylece çarpma yerine bit shift işlemleri kullanılabilir
- Kosinüs teriminin yakınsama değeri de yeniden hesaplanarak yaklaşık 0.60725 bulunur ve başlangıç vektörünün
x değeri olarak ayarlanır
- CORDIC algoritmasının her yinelemesi şu şekilde sadeleşir
z 0 veya daha büyükse saat yönünün tersine döndürülür (x'ten y>>i çıkarılır, y'ye x>>i eklenir)z 0'dan küçükse saat yönünde döndürülür (x'e y>>i eklenir, y'den x>>i çıkarılır)- Tablodaki açı değeri çıkarılarak veya eklenerek
z güncellenir
- Böylece sabit çarpma, bit shift ve toplama işlemleriyle trigonometrik fonksiyonlar hesaplanabilir
GN⁺ görüşü
- CORDIC, gömülü sistemler veya FPGA gibi donanım kaynakları sınırlı ortamlarda faydalı olabilecek bir algoritma gibi görünüyor. Özellikle kayan nokta işlemlerinin desteklenmediği durumlarda değerlendirilebilir.
- Tanjant fonksiyonunun açılarını stratejik biçimde seçerek çarpmayı bit shift ile değiştirme fikri etkileyici. Matematiksel içgörü ile bilgisayar mimarisi anlayışının birleştiği iyi bir örnek.
- Yalnızca trigonometrik fonksiyonlarda değil, logaritma, üstel fonksiyon, karekök gibi çeşitli fonksiyonların hesaplanmasında da kullanılabilmesi ilgi çekici. İlgili bir algoritma olan BKM'ye de bakmak faydalı olabilir.
- Ancak modern donanımlarda çoğu zaman zaten bir FPU bulunur ve fixed-point aritmetik kullanıldığında hassasiyet kaybı yaşanabilir; bu yüzden uygularken dikkatli olmak gerekir.
- Benzer hesaplamaların çok sık yapıldığı sistemlerde, CORDIC'e özel donanım tasarımı da düşünülebilir.
1 yorum
Hacker News görüşleri
CORDIC algoritması yalnızca FPGA'larda değil, oyun geliştirme veya dağıtık fizik simülasyonu gibi alanlarda da kullanılabilir. Kayan noktalı hesaplamalarda platformlar arasında deterministik davranışı garanti etmek zor olduğundan, sabit noktalı bir fizik motoru uygulayıp trigonometrik fonksiyonları CORDIC ile gerçekleştirmek bir çözüm olabilir.
CORDIC; sinüs ve kosinüsün yanı sıra logaritma, üstel, karekök, vektör büyüklüğü, kutupsal koordinat-kartesyen koordinat dönüşümü ve vektör döndürme gibi çeşitli işlemlerde de kullanılabilir. Kuaterniyonlar kullanılırsa CORDIC tabanlı işlemler daha verimli ve daha doğru biçimde yapılabilir gibi görünüyor.
Lisede üniversite öncesi kalkülüs dersinde hesap makinesindeki trigonometrik fonksiyonların nasıl uygulandığını öğrenmiştim; Taylor serisi değil de aslında CORDIC olduğunu fark edince bunu TI Basic ile bizzat uygulamayı denediğine dair bir deneyim paylaşılmış.
2023 itibarıyla STM32G4 gibi düşük maliyetli MCU'larda bile FPU yerleşik geliyor, bu yüzden sabit nokta yerine kayan noktayı rahatça kullanmak mümkün. Ancak G4'te özel donanım olarak uygulanmış bir CORDIC çevrebirimi de var; bunun kayan nokta hassasiyet kaybını önlemek için olduğu anlaşılıyor.
22.75° dönüşün, 45° dönüşten sonra -22.5° dönüşe eşit olduğu açıklamasında bir hata var gibi görünüyor. Muhtemelen 22.5° olması gerekiyor.
Meagher'in octree sistemi, tam sayı çarpma/bölme olmadan yalnızca tam sayı işlemleriyle uygulanmıştı. Bu da octree gösterimi için hızlı ve özel üretim VLSI grafik hızlandırma donanımı yapmayı kolaylaştırıyordu.
CORDIC, açılar için Farey dizisine (veya mediant, naive kesir toplaması) benzer bir kavram olarak görülebilir.
CORDIC, 4 bit CPU'ya sahip vintage programlanabilir HP hesap makinelerinde bile uygulanmıştı. Sinüs fonksiyonu için Taylor açılımını kullanan yaklaşım da programlanabiliyor.
Bu yazıyı beğendiyseniz, matematiksel algoritmaları örneklerle anlatan Donald Knuth'un klasik eseri "The Art of Computer Programming"i okumak da iyi olabilir.
CORDIC, geçmişte DSP alanında çok popüler olmuş bir algoritmaydı.
Harika bir algoritma; düşük performanslı donanımlarda sinir ağlarını çalıştırmak için faydalı olabilir.