CORDICアルゴリズムによるTan関数の近似

はじめに

CORDICは、関数電卓などに用いられる簡易的な関数近似アルゴリズムである。そこで今回は、CORDICを用いてPythonで三角関数のTan関数の値を近似することを目的とし、誤差の評価を行う。

アルゴリズム

CORDICのアルゴリズムは以下の大変分かりやすい記事を参考にした。

例として、$tan 60^\circ$の近似値を算出することを考える。

以下のアルゴリズムについて図を用いて説明する。

(1)$tan 45^\circ$は上辺と底辺の比率が1対1の直角三角形の傾きである。

(2)上辺と底辺の比率が1対2の直角三角形を(1)の三角形の斜辺に底辺が来るような倍率で付け加える。

(3)目的角（図の赤線）が$60^\circ$と比較して大きいかどうかを調べ、大きければ、1対$2^2$の比率の直角三角形を(2)と同様のアルゴリズムで付け足し、小さければ負の角度方向に直角三角形を付け足す。

(4)(1)から(3)の操作を可能なだけ繰り返すことで、理論上は$tan 60^\circ$に漸近する近似値を求めることができる。

ただしこれには、(2)に相当するアルゴリズムで、$Arctan(\frac{1}{2^k})$の値を予め求めておく必要性がある。($k$は試行回数である。)

ここで、Arctanのマクローリン展開は単純な式によって以下のように与えられる。(tan関数のマクローリン展開は凄く複雑になる)

Arctan x=\Sigma^{\infty}_{n=1}\frac{(-1)^{n-1}}{2n-1}x^{2n-1}

これをもとに、以下のようなプログラムを作成した。

プログラム

基礎となるプログラム

　python cordic_basic.py

import numpy as np
import matplotlib.pyplot as plt
import math
import japanize_matplotlib
#m次までのアークタンジェントの計算（マクローリン展開）
m=17
n=50
err = 1.0*10**(-2)
def Arctan(x):
  arctan=0
  for i in range(1,m):
      x_i=((-1)**(i-1)/(2*i-1))*x**(2*i-1)
      arctan=arctan+x_i
  return arctan
#print(Arctan(1)*180/math.pi)
theta_degree=30
theta = (math.pi/180)*theta_degree

x_k=1
y_k=1

theta_c =(math.pi/180)*45
k=1
#CORDICアルゴリズムメイン
while abs(theta_c-theta) > err:
  z_k= x_k+1j*y_k
  if theta_c < theta:
      theta_c =theta_c+Arctan(1/(2**(k)))
      delta_z_k=(z_k)*1j*(2**(-(k)))
  else:
      theta_c =theta_c-Arctan(1/(2**(k)))
      delta_z_k=-(z_k)*1j*(2**(-(k)))
      # print(delta_z_k)
  z_k=z_k+delta_z_k
  x_k=z_k.real
  y_k=z_k.imag
      #print(y_k/x_k)
  k=k+1
  #print(y_k/x_k)
  if k>n:
    break
# 推定結果の表示
print(y_k/x_k)

tan曲線の描写

python cordic_tan.py

import numpy as np
import matplotlib.pyplot as plt
import math
import japanize_matplotlib
import matplotlib.animation as animation

m=17
n=50
err = 1.0*10**(-2)
def Arctan(x):
  arctan=0
  for i in range(1,m):
      x_i=((-1)**(i-1)/(2*i-1))*x**(2*i-1)
      arctan=arctan+x_i
  return arctan

#print(Arctan(1)*180/math.pi)

num=100

theta_degree_ary=np.linspace(0,85,num)
tan_ary=[]
for p in range(num):
  theta_degree=theta_degree_ary[p]
  theta = (math.pi/180)*theta_degree
  x_k=1
  y_k=1
  theta_c =(math.pi/180)*45
  k=1
  while abs(theta_c-theta) > err:
    z_k= x_k+1j*y_k
    if theta_c < theta:
        theta_c =theta_c+Arctan(1/(2**(k)))
        delta_z_k=(z_k)*1j*(2**(-(k)))
    else:
        theta_c =theta_c-Arctan(1/(2**(k)))
        delta_z_k=-(z_k)*1j*(2**(-(k)))
        # print(delta_z_k)
    z_k=z_k+delta_z_k
    x_k=z_k.real
    y_k=z_k.imag
        #print(y_k/x_k)
    k=k+1
    #print(y_k/x_k)
    if k>n:
      break
  #print(y_k/x_k)
  tan_ary.append(y_k/x_k)
    #print(k)
plt.title('Cordicアルゴリズムによるtan関数の計算')
plt.plot(theta_degree_ary,tan_ary,color='blue',label='tan_near(θ)')
plt.plot(theta_degree_ary,np.tan(theta_degree_ary*math.pi/180),color='red',label='tan(θ)')
plt.xlabel('θ[degree]')
plt.ylabel('tan_near(θ)')
plt.legend()
plt.savefig("Cordicアルゴリズムによるtan関数の計算.png")
plt.show()

これを実行すると以下の様な近似曲線を得ることができる。

このようにかなり正確であるといえる。ただし、御存じの通り$90^\circ$付近でtan関数は発散してしまうので角度が大きくなるにつれ近似精度が悪化する傾向がある。

誤差と試行回数の関係

次に、$30^\circ$においてCORDICを回していった際の計算精度について評価するために以下の様なプログラムを作成した。

python cordic_err.py

import numpy as np
import matplotlib.pyplot as plt
import math
import japanize_matplotlib
import matplotlib.animation as animation
m=17
n=50
err = 1.0*10**(-2)
def Arctan(x):
  arctan=0
  for i in range(1,m):
      x_i=((-1)**(i-1)/(2*i-1))*x**(2*i-1)
      arctan=arctan+x_i
  return arctan
#print(Arctan(1)*180/math.pi)
theta_degree=30
theta = (math.pi/180)*theta_degree
x_k=1
y_k=1
theta_c =(math.pi/180)*45
k=1
tan_theta_near_ary=[]
err_ary=[]
k_ary=[1]
while abs(theta_c-theta) > err:
  z_k= x_k+1j*y_k
  if theta_c < theta:
      theta_c =theta_c+Arctan(1/(2**(k)))
      delta_z_k=(z_k)*1j*(2**(-(k)))
  else:
      theta_c =theta_c-Arctan(1/(2**(k)))
      delta_z_k=-(z_k)*1j*(2**(-(k)))
      # print(delta_z_k)
  z_k=z_k+delta_z_k
  x_k=z_k.real
  y_k=z_k.imag
      #print(y_k/x_k)
  k=k+1
  #print(y_k/x_k)
  if k>n:
    break
  tan_theta_near=y_k/x_k
  tan_theta_near_ary.append(tan_theta_near)
  tan_theta=np.tan(theta)
  err_ary.append(abs(tan_theta_near-tan_theta)/tan_theta)
  k_ary.append(k)

tan_theta_near=y_k/x_k
tan_theta_near_ary.append(tan_theta_near)
tan_theta=np.tan(theta)
err_ary.append(abs(tan_theta_near-tan_theta)/tan_theta)
plt.title('Cordicアルゴリズムによるtan関数の計算と試行回数の関係')
plt.xlabel('試行回数')
plt.ylabel('誤差')
plt.plot(k_ary,err_ary)
plt.savefig('Cordicアルゴリズムによるtan関数の計算と試行回数の関係.png')
plt.show()

これを実行すると以下のようなグラフが出力される。

なるほど、確かに試行回数が増えるほど誤差は小さくなっているようである。

まとめ

今回は、関数電卓に使用されているアルゴリズムである、CORDICを用いてtan関数の近似曲線を描写した。また、誤差と試行回数の関係を調査することで、計算時間の許す限りではあるが、試行回数を上昇させていけば、近似精度は上昇するということが分かった。