Cordic algoritması ile sin, cos, tan fonksiyonlarını hesaplamak

Yıllardır Cordic algoritmasının varlığından haberdarım. Fakat hiç bir zaman algoritmanın mantığını anlayamadım. Taa ki picproje sitesinde Aliçavuşlu nickli arkadaşla konuyu tartışıncaya kadar.

Bu yazımın değerini çok iyi bilin.

sin, cos gibi fonksiyonları hesaplamak için bilinen yollardan birisi bu fonksiyonları seriye açmaktır.  Seri açılım için tıklayınız.

Seri açılım, hesap makinelerinde kullanılan bir yöntemdir. Çarp ve topla yöntemi ile serinin yeterince elemanı hesaplamalara katılırsa oldukça doğru sonuçlara ulaşılır. Ancak daha hızlı sonuç veren Cordic (COordinate Rotation DIgital Computer) yöntemi de  HP ve TI hesap makinelerinde ve de bazı matematik işlemcilerde kullanılmaktadır. Yapısında çarpma yada bölme barındırmadığından seri açılımdan daha hızlı şekilde sonuca ulaşır.

Trigonometriden biliyoruz ki   tan(\theta+\Delta\theta)=\frac{tan(\theta)+tan(\Delta\theta)}{1-tan(\theta)*tan(\Delta\theta)}

Cordic

\frac{y_n}{x_n}=tan(\theta_n)

\frac{y_{n+1}}{x_{n+1}}=tan(\theta_n+\Delta\theta)

\theta_{n+1}=\theta_n+\Delta\theta

\frac{y_{n+1}}{x_{n+1}}=tan(\theta_n+\Delta\theta)=\frac{tan(\theta)+tan(\Delta\theta)}{1-tan(\theta)*tan(\Delta\theta)}=\frac{\frac{y_n}{x_n}+tan(\Delta\theta)}{1-\frac{y_n}{x_n}*tan(\Delta\theta)}

\frac{y_{n+1}}{x_{n+1}}=\frac{y_n+x_n*tan(\Delta\theta)}{x_n-y_n*tan(\Delta\theta)}*\frac{\frac{1}{x_n}}{\frac{1}{x_n}}

\frac{y_{n+1}}{x_{n+1}}=\frac{y_n+x_n*tan(\Delta\theta)}{x_n-y_n*tan(\Delta\theta)}

y_{n+1}=y_n+x_n*tan(\Delta\theta)

x_{n+1}=x_n-y_n*tan(\Delta\theta)

Eğer \Delta\theta kadar geri gidecek isek bu durumda

y_{n+1}=y_n-x_n*tan(\Delta\theta)

x_{n+1}=x_n+y_n*tan(\Delta\theta)

olmak üzere sadece toplama ve çıkarma işlemleri yer değiştirir.

Şimdi 1, \frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{16},\frac{1}{32},...  değerlerine ait Atan değerlerini tablo olarak hazırlayalım. Bu değerler işlemcimizde lookup table olacak.

Girdi      Tablo değeri
1                     45◦
1/2                 26.565◦
1/4                 14.036◦
1/8                   7.125◦
1/16                 3.576◦
........                .......

İterasyon kısmına bakalım.

Verilen herhangi bir  \beta  açısının tanjantını bulmak isteyelim. Daha sonra açının sinüs yada cosinüs değerlerini de hesaplayabiliriz.

45 derecelik üçgenimizde X ve Y 1 değerini alır.

O halde başlangıç değerleri olarak

X_n=1

Y_n=1

30 derecenin tanjan değerini hesaplamak isteyelim.

Tablodaki ilk açımız 45◦dir. Bir başka deyişle Tablodaki ilk terimin sıra numarasının ArcTangent değeri 45 dir.

45◦>30◦ dur.  Bir sonraki açı değerimiz 26.565◦

O halde \Delta\theta=26.565  Bunun tangent değeri de 1/2 dir.

y_{n+1}=1-1*1/2=0.5

x_{n+1}=1+1*1/2=1.5

Bu yaptığımız işlem  45-26.565 açısının tanjant değerini veren y ve x değerlerini bulmak oldu.

Gerçekten de y/x=0.5/1.5=0.3333333 dür ve bu da tan(45-26.565) değeridir.

45-26.565 yani 18.435 < 30 dur.

O halde bir sonraki açı değeri olan 14.036◦ i  18.435 ye ekleyeceğiz.

Bu durumda

y_{n+1}=0.5+1.5*1/4=0.875

x_{n+1}=1.5-0.5*1/4=1.375

Burada yapılan işlem 14.036◦ +  18.435 = 32.471 açısının tanjant değeri olan 0.636 sonucunu veren 0.875/1.375 oranını hesaplamak oldu.

32.471 > 30 olduğundan bir sonraki açıyı bundan çıkartalım. Bir sonraki açımız 7.125◦ ve bunun ArcTangent değeri 1/8 dir.

y_{n+1}=0.875-1.375*1/8=0.703

x_{n+1}=1.375+0.875*1/8=1.484

Bu yeni değerlerden Tanjant değeri 0.703/1.484=0.473  ve açımız 25.346 dır.

Aynı işlemleri tablomuzun her bir elemanı için yapmaya kalktığımızda açımız 30 dereceye yaklaşırken bulunan x ve y değerlerinden hesaplanacak y/x oranı da 30 derecenin yaklaşık tangent değeri olacaktır.

Burada hesaplamalarda

y_{n+1}=y_n+x_n*tan(\Delta\theta)

x_{n+1}=x_n-y_n*tan(\Delta\theta)

işleminde tan(\Delta\theta) 2 nin alt kuvvetleridir ve bir önceki değerin 1 bit sağa kaydırılması anlamına gelir. O halde y_{n+1}=y_n+x_n*tan(\Delta\theta)

işleminde x_n*tan(\Delta\theta)  x_n i bir bit sağa kaydır demektir.

geriye  yn ile bunu toplamak yada çıkartmak kalıyor

Toplama ya da çıkartma işleminden hangisinin yapılacağı son bulunan açıya yeni değerin eklenecekmi yoksa çıkartılacakmı cevabına göre belirlenir.

Dolayısı ile Cordic algoritması çok hızlı işletilir. Yapısında ne çarpma ne de bölme barındırır.

Bu nedenle de seri açılım yöntemine tercih edilir.

Peki verilen açının tangent değerini hesapladık sinüs ya da cosinüs değerini nasıl hesaplayacağız?

Yukarıdaki link bir çözüm ancak bir başka seçeneğimiz daha var.

Daha önce aşağıdaki bağıntıları yazmıştık.

\frac{y_{n+1}}{x_{n+1}}=tan(\theta_n+\Delta\theta)=\frac{tan(\theta)+tan(\Delta\theta)}{1-tan(\theta)*tan(\Delta\theta)}=\frac{\frac{y_n}{x_n}+tan(\Delta\theta)}{1-\frac{y_n}{x_n}*tan(\Delta\theta)}

\frac{y_{n+1}}{x_{n+1}}=\frac{y_n+x_n*tan(\Delta\theta)}{x_n-y_n*tan(\Delta\theta)}*\frac{\frac{1}{x_n}}{\frac{1}{x_n}}

\frac{y_{n+1}}{x_{n+1}}=\frac{y_n+x_n*tan(\Delta\theta)}{x_n-y_n*tan(\Delta\theta)}

ve pay ve paydada \frac{1}{x_n} ifadelerini sadeleştirmiştik.

tan(\theta)=\frac{sin(\theta)}{cos(\theta)}=\frac{y_n}{x_n} olduğundan

x(n) ve y(n) değerlerini iterasyonlarda hesaba girmeyen 1/x(n) değerleri ile yani cos değerleri ile çarparsak

daha açık ifade ile Cos(45) * cos(26.6) * cos(14) * cos(7.1) .... = 0.607252935 ile çarparsak

sin ve cos değerlerini bulmuş oluruz.

sin(\theta)=x_n*0.607252935

cos(\theta)=y_n*0.607252935 olarak kolayca hesaplanabilir.

Aşağıda Delphi için yazdığım algoritma var. -45..+45 derece aralığında tanjant değerlerini hesaplıyor.

 

Bu yazı 2- Arm ve Asm, 7- Matematik kategorisine gönderilmiş ve , , ile etiketlenmiş. Kalıcı bağlantıyı yer imlerinize ekleyin.