JP2508286B2 - 平方根演算装置 - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は計算機における平方根の演算装置に関する。

〔従来の技術〕

一般に、平方根の演算機能は、数値計算を行う計算機
において是非とも備えなければならない機能の一つであ
る。

従来、マイクロプログラム制御の計算機では、平方根
は二分法によって行なわれていた。この二分法はｎ桁の
平方根を得るために、加減算をシフトなどの演算をｎ回
繰り返す必要がある。そのため、二分法には演算時間が
長くなるという欠点があった。

また、高速な乗除算器を持つ計算機では、New−ton法
を用いた逐次近似によって平方根を求めることが多い。
以下、このNewton法について説明する。

まず、ａの平方根 は、ｆ（ｘ）＝x²−ａ＝０の解であることからNewton法
を用いると、初期値x_mから近似値x_m+1は以下のように求
まる。ここで、ａは1/4≦ａ＜１の範囲を満たすものと
する。

x_m+1＝x_m−ｆ（x_m）/f′（x_m） ＝x_m−（x_m ²−ａ）／（２×x_m） ＝（1/2）×（x_m＋a/x_m） …（１） 初期値x_mは の近似値である。Newton法の２乗収束の性質より、x_m+1
で2n桁の精度を期待するならばｎ桁の精度のx_mを用意
し、（１）式の除算と加算を2n桁の精度で演算すればよ
いことが知られている。よって、適当な初期値x₀を用意
し、式（１）の処理をｍ＝0,1,2,…,M−１と繰り返すこ
とにより、希望の精度の近似値x_mが得られる。この方式
では、除算１回と加算１回を要する（１）式の演算を数
回繰り返す必要があるため、演算時間を短くするには精
度の良い初期値x₀を用意することが重要である。

そこで、平方根の高速演算が重要な計算機では初期値
x₀として、あらかじめ計算された のテーブルROMを用意し、（１）式の計算回数を１回に
する方式が採用されている。

このテーブルROMは、2n桁の入力値ａをｎ桁ずつに分
離した上位ｎ桁をアドレスとし、2n桁の近似値 を出力する。このx_mでａを除算し、x_mを加算し、さらに
定数1/2を乗じる（または、１ビット右にシフトする）
ことによって、（１）式のx_m+1が得られる。

かかるテーブルROMを使用しても、平方根の演算時間
は、テーブル検索，除算，加算の演算時間の和である。
一般的に除算は演算時間が長いため、上述の方式では演
算時間の短縮は困難である。また、平方根の演算機能を
LSI化したい場合、除算機能をLSI上に取込むとチップ上
で大きな面積を必要とするため、上記Newton法も好まし
くない。

そこで、除算を避けるために（１）式を変形して、 x_m+1＝（1/2）×〔x_m＋（1/x_m）×ａ〕 …（２） とし、テーブルROMに を追加すると、乗算１回と加算１回の演算ですむ。

ところが、 の方のテーブルROMは2n桁の出力を要し、乗算の精度が2
n桁を必要とする。更に、LSI化する場合には、2n×2nビ
ットの乗算器をチップ内に必要としている。

〔発明が解決しようとする課題〕

上述した従来の平方根演算装置には、以下の問題点が
ある。

すなわち、第一には演算時間が長いという問題があ
る。

（１）式の演算には、テーブル検索が１回、除算が１
回，加算が１回必要である。しかも、テーブル検索，除
算，および加算は並列に演算できないため、逐次的に演
算するしかなく、演算時間はこれらの実行時間の和にな
る。

また、第二にはハードウェアが大規模になり、チップ
面積を増大させるという問題がある。

（１）式の除算は、2n桁の精度で行なう必要がある。
つまり、2n桁×2n桁の除算器が必要になるので、LSI化
する上で面積の増大をまねく。

更に、（２）式の計算では、テーブルROMをｎ×2nビ
ットのものと、2n×2nビットのものの２組が必要な上、
2n×2nビットの乗算器が必要なため、前述の除算器と同
様に、LSI化する上で面積の増大をまねく。

本発明の目的は、かかる演算時間の短縮とチップ面積
の増大を防止することのできる平方根演算装置を提供す
ることにある。

〔課題を解決するための手段〕

本発明の平方根演算装置は、初期値を上位桁Ｈと下位
桁Ｌに分割する分割手段と、前記分割手段から上記桁Ｈ
を入力し予め計算された上位桁の平方根 の値を出力するメモリと、前記分解手段の下位桁Ｌおよ
び前記メモリの 出力の乗算を行なう乗算器と、前記メモリの平方根 の値および前記乗算器の出力値を加算する加算器とを備
えることを特徴としている。

〔作用〕

次に、本発明の平方根演算原理を説明するが、ここで
は2n桁の２進数で表現されたａから、2n桁の平方根 を求めることを考える。

先ず、ａをｎ桁ずつ上位桁Ｈと下位桁Ｌに分割する。

ただし、a_k＝｛1,0｝ 1/4≦ａ＜１ ここで、（１）式で初期値 とすることにより、平方根 は、 となる。

かかる（３）式において、Ｈを入力とし、 を出力とするテーブルROMを用意すると、乗算１回と加
算１回で が得られる。

また、Ｈ＜1,L＜2^-nであるので、（３）式の第２項の
演算精度はｎ桁でよい。すなわち、 に２桁の精度を得るためには、2n桁×2ⁿ語の テーブルと、ｎ桁×2ⁿ語の テーブルと、 テーブル出力ｎ桁とＬのｎ桁を乗算する乗算器と、 テーブル出力2n桁に乗算結果の上位ｎ桁を加算する加算
器を必要とする。

〔実施例〕

次に、本発明の実施例について図面を参照して説明す
る。

第１図は本発明の第一の実施例を示す平方根演算装置
のブロック図である。

第１図に示すように、本実施例は、変数ａを入力する
2nビットのレジスタ１と、分割器によりレジスタ１から
出力される上位ｎ桁信号Ｈを制御信号に基づき平方根 の値に変換して記憶する2nビット×2ⁿ⁺¹語のROM2と、RO
M2の出力値を保持する2nビットのレジスタ３と、レジス
タ１の下位ｎ桁信号Ｌおよびレジスタ３の上位ｎ桁を出
力する信号８の積を演算するｎ×ｎビットの乗算器４
と、乗算器４の出力2nビットのうち上位ｎビットを保持
するレジスタ５と、レジスタ５の値を下位ｎビットとし
て出力し且つ上位ｎビットはゼロを出力する2nビットの
信号９をレジスタ３の値に加算する2nビットの加算器６
と、加算器６の出力、すなわち平方根 を保持する2nビットのレジスタ７とを有している。尚、
上述したROM2へ入力する制御信号はROM2の出力が かを指定する１ビットの制御信号である。

また、上述したレジスタ1,3,7では、小数点をMSBの上
に置いた固定小数点数を扱い、レジスタ１上のａは、1/
4≦ａ＜１を満たすものとする。

第２図は第１図に示す演算装置の平方根の演算処理を
説明するためのフロー図である。

第２図に示すように、まず第一のステップS1では、レ
ジスタ１に指定されたａの値の上位桁Ｈ信号をアドレス
としてROM2から の値を取り出し、レジスタ３に保持する。次に、第二の
ステップS2では、乗算器４によって の上位桁信号８とａの下位桁Ｌ信号を乗算し、積の上位
桁をレジスタ５に保持する。同時に、レジスタ１に設定
されたａの値の上位桁Ｈ信号をアドレスとしてROM2から の値を取り出し、レジスタ３に保持する。更に、第三の
ステップS3では、レジスタ３からの の値およびレジスタ５の値を加算器６で加算し、レジス
タ７に保持する。

このように、レジスタ１上の値ａからレジスタ７上の
平方根 が３つのステップで得られる。

すなわち、本実施例の平方根演算装置は、３ステップ
で演算を行ない、１ステップの処理時間はテーブルROM2
の読み出し時間，乗算時間，加算時間のうち、最も長い
時間となる。従って、本実施例では、乗算とテーブルの
読み出しを並行して行なうことにより、演算時間を短縮
している。

また、本実施例の演算手段は、テーブルROM2と、乗算
器４と、加算器６だけあるので、ハードウェア構成が小
規模である。

すなわち、従来のNewton法による演算装置は、2nビッ
ト×2nビットの除算器または乗算器が必要であったが、
本実施例による演算装置はｎビット×ｎビットの乗算器
でよい。これにより、乗算器の面積は従来例の約1/4に
なる。

更に、本実施例では従来例とは別に のテーブルROMが必要であるが、LSI化を考慮すると、乗
算器よりもテーブルROMの方が小面積且つ容易に設計で
きるので、テーブルROMの面積増加は大きな問題となら
ない。

第３図は本発明の第二の実施例を示す平方根演算装置
のブロック図である。

第３図に示すように、本実施例は平方根 と、 とのテーブルROMを独立に持ち、平方根 を演算する装置である。

すなわち、本実施例は、変換ａを入力する2nビットの
レジスタ１と、レジスタ１から出力される上位ｎ桁信号
Ｈに基づき平方根 の値を記憶する２ビット×2ⁿ語のROM2Aおよび の値を記憶するｎビット×2ⁿ語のROM2Bと、レジスタ１
から出力される下位ｎ桁信号ＬとROM2Bの の積を演算するｎ×ｎビットの乗算器４と、乗算器４の
出力2nビットのうち上位ｎビットを下位ｎビットして形
成される信号10およびROM2Aの値を加算する2nビットの
加算器６と、加算器６の出力値を保持する2nビットのレ
ジスタ７とを有している。

かかる本実施例の平方根演算装置におけるレジスタ1,
ROM2Aおよび2B,乗算器4,加算器６では、小数点がMSBの
上に置いた固定小数点数を扱うものとする。

先ず、レジスタ１上に、1/4≦ａ＜１を満たすａの値
を与える。すると、その出力には分割器によりａの値を
上位および下位に分割したＨおよびＬ信号が出力され
る。この信号Ｈをアドレスとして、ROM2Aからは が、またROM2Bからは の値がそれぞれ出力される。乗算器４では、ROM2Bの出
力およびレジスタ１の下位Ｌ信号 の演算が行なわれる。また、加算器６ではROM2Aからの
出力 および乗算器４の出力に基づく信号 の加算が行われ、レジスタ７に平方根 の値が出力される。

このように、本実施例では、ａの平方根 を１ステップで演算することができるので、演算時間は
テーブル検索１回，乗算１回および加算１回に要する時
間の和になる。

上述した第二の実施例の変形を以下に説明する。

ROM2A,2Bは同一のアドレス信号Ｈでアクセスされるの
で、3nビット×2ⁿ語のROMとしても実現できる。また、
乗算器４を桁上げ保存加算器と桁上げ伝播加算器で構成
する場合は、桁上げ伝播加算器を加算器６で代用する
と、演算時間が短くなり、ハードウェア量も減少する。

また、ROM2A,2Bと、信号Ｌの出力側とにレジスタを挿
入することにより、パイプライン方式の演算装置が実現
できる。このパイプライン方式では、テーブル乗算およ
び加算を行なっている期間に、次の平方根 の演算のためのテーブルROM検索を行うことができる。
そのため、大量の配列データ｛a_i｝に対して を求める場合に、演算時間を第二の実施例の約半分にす
ることができる。

以上、第二の実施例について説明したが、本実施例は
１ステップで演算を行ない、また１ステップの処理時間
はテーブルROMの読み出し時間，乗算時間，加算時間の
和になるので、２つのテーブルの読み出しを同時に行う
ことにより、演算時間を短縮することができる。またハ
ードウェア構成を小規模化し、チップ面積の増大を防止
できることは、前述した第一の実施例と同様である。

要するに、上述した２つの実施例は初期値ａに対し のテーブルを持ち、テーブル検索を２回，乗算を１回，
加算を１回実行し、除算を行なわずに初期値ａの平方根 を求めるので演算時間は短縮される。

また、従来の平方根演算装置は2n桁の演算精度を得る
ために、 の除算あるいは乗算を2n桁の精度で行なう必要があった
のに対し、本実施例ではｎ桁の精度の乗算を行なえばよ
いので、チップ面積の増大をまねくこともない。

〔発明の効果〕

以上説明したように、本発明の平方根演算装置は、演
算時間が短くなる上、演算ハードウェアが小規模化でき
るという効果がある。

【図面の簡単な説明】

第１図は本発明の第一の実施例を示す平方根演算装置の
ブロック図、第２図は第１図に示す演算装置の平方根の
演算処理を説明するためのフロー図、第３図は本発明の
第二の実施例を示す平方根演算装置のブロック図であ
る。 1,3,5,7……レジスタ、2,2A,2B……ROM、４……乗算
器、６……加算器。

Claims (1)

(57)【特許請求の範囲】
1. 【請求項１】初期値を上位桁Ｈと下位桁Ｌに分割する分
   割手段と、前記分割手段から上位桁Ｈを入力し予め計算
   された上位桁の平方根 の値を出力するメモリと、前記分割手段の下位桁Ｌおよ
   び前記メモリの 出力の乗算を行なう乗算器と、前記メモリの平方根 の値および前記乗算器の出力値を加算する加算器とを備
   えることを特徴とする平方根演算装置。