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

Abstract

(57)【要約】 【目的】平方根を算出する演算装置に関し、除算器に補
正回路を付加することにより、平方根の演算を高速化す
ることを目的とする。 【構成】除数レジスタ12と、部分剰余レジスタ16と、部
分商予測回路21と、部分商補正回路23と、除倍数生成回
路19と、部分剰余演算回路20とを備え、一度に複数ビッ
トの部分商を求める除算器１において、オペランドから
平方根の上位桁の値を予測して除数レジスタ12に設定す
る初期値設定回路２と、前の演算サイクルで求めた商の
２倍に今回予測した部分商を加え、その値に今回予測し
た部分商を掛けた値を補正された除倍数とする除倍数補
正回路３と、演算サイクル毎に、部分商補正回路23によ
って補正された部分商によって除数レジスタの除数を補
正する除数補正回路４とを備えるように構成する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、平方根を算出する演算
装置に関する。

【０００２】

【従来の技術】従来の平方根の算出を行なう演算装置
は、平方根の計算方法に従って、根を１ビットずつ求め
るものであった。

【０００３】

【発明が解決しようとする課題】従って、従来の技術に
よれば計算時間が長いという問題がある。本発明は除算
器に補正回路を付加することにより、複数ビットを同時
に計算でき、平方根の演算を高速化した演算装置を実現
することを目的としている。

【０００４】

【課題を解決するための手段】平方根は、次に示すよう
に、商と除数とが同値になるような、除算における１つ
の特殊解とみなすことができる。

【０００５】Ｚ：被除数（平方根を求めるもとの数） Ｘ：商（平方根） Ｙ：除数 として、 Ｚ＝Ｘ・Ｙ ・・（１） Ｘ＝Ｚ／Ｙ ・・（２） 平方根は（２）式において、商と除数が同値（Ｘ＝Ｙ）
となるような除算における１つの特殊な解である。この
ことを利用して、近年複数ビットを同時処理することに
より高速化されている除算器を用いて平方根を求める。

【０００６】図１に本発明の原理ブロック図を示す。除
数レジスタ12と、部分剰余レジスタ16と、部分商予測回
路21と、部分商補正回路23と、除倍数生成回路19と、部
分剰余演算回路20とを備え、一度に複数ビットの部分商
を求める除算器１において、オペランドから除数の初期
値と最初の除倍数とを生成する初期値設定回路２と、除
算器１の除倍数生成回路19の生成値を補正する除倍数補
正回路３と、除算器１の除数レジスタ12の値を部分商補
正回路23で補正された部分商で補正する除数補正回路４
とを設ける。

【０００７】初期値設定回路２は、入力されたオペラン
ドから平方根の上位桁の値を予測して除数レジスタ12に
設定し、かつ、その内の部分商生成ビット数分の上位桁
の値の自乗を生成して部分剰余演算回路20に入力する。
除数レジスタ12に設定する桁数は、除算器の部分商の予
測に必要な上位の桁数分である。

【０００８】除倍数補正回路３は、最初の演算サイクル
では、初期値設定回路２から与えられた、部分商生成ビ
ット数分の上位桁の値の自乗値を補正された除倍数とし
て、部分剰余演算回路20に入力し、２回目以後の演算サ
イクルでは、その前の演算サイクルで求めた中間商の２
倍に今回予測した部分商を加え、その値に今回予測した
部分商を掛けた値を補正された除倍数として、部分剰余
演算回路20に入力する。

【０００９】部分剰余演算回路20は、部分剰余レジスタ
16にある、前の演算サイクルで得られた部分剰余からこ
の補正された除倍数を減算した値を新たな部分剰余とし
て部分剰余レジスタ16にセットする。

【００１０】除数補正回路４は、演算サイクル毎に、部
分商補正回路23によって補正された部分商によって除数
レジスタ12の除数を補正する（新しい除数すなわち商を
生成する）ように構成する。

【００１１】なお、除倍数補正回路３は、後述の（1
6）’式により、２回目以後の演算サイクルでは、その
前の演算サイクルで求めた中間商と今回予測した部分商
とを掛けた値を２倍した値と、今回予測した部分商の自
乗との和を補正された除倍数としてもよい。

【００１２】また、後述の（16）”式により、２回目以
後の演算サイクルでは、その前の演算サイクルで求めた
中間商に今回予測した部分商を加え、今回予測した部分
商を掛けてこれを２倍した値から今回予測した部分商の
自乗を引いた値を用いても上述した値と同じになる。

【００１３】

【作用】以下に図２に示すように、オペランドＺの、 Ｚ＝（Ａ・16³ ＋Ｂ・16² ＋Ｃ・16¹ ＋Ｄ）² となる１６進４桁（４Digit,16bit)の平方根 Ｘ＝Ａ・16³ ＋Ｂ・16² ＋Ｃ・16¹ ＋Ｄ の各桁の数Ａ，Ｂ，Ｃ，Ｄを求める場合を例にとり説明
する。 除算器でＸ＝Ｚ／Ｙを行なうときと同様に、最初に被
除数Ｚを最初の部分剰余として設定する。 Ｒ０＝Ｚ 除算においては、部分商を予測し除数との積（除倍数）
を求め、それを部分剰余から減算して新しい部分剰余を
求め、また、その正負により予測した部分商の補正を行
なう。これを桁毎に繰り返し、所定の桁数の処理をして
終了する。平方根を求める場合に当てはめると、以下の
ようになる。

【００１４】除算では除数は固定値であるが、平方根演
算では除数と商が等しいので、新たに部分商を求める毎
に除数を補正する。 最上位桁Ａを求めたときの部分剰余Ｒ１は、 Ｒ１＝Ｚ−（Ａ・16³ ）² ＝Ｚ−Ａ² ・16⁶ ・・（３） 第２位の桁Ｂを求めたときの部分剰余Ｒ２は、 Ｒ２＝Ｚ−（Ａ・16³ ＋Ｂ・16² ）² ＝Ｚ−（Ａ² ・16⁶ ＋２ＡＢ・16⁵ ＋Ｂ² ・16⁴ ) ＝Ｒ１−（２Ａ・16³ ・Ｂ・16² ＋Ｂ² ・16⁴ ) ・・（４）’ ＝Ｒ１−（２Ａ・16³ ＋Ｂ・16² ) Ｂ・16² ・・（４） 第３位の桁Ｃを求めたときの部分剰余Ｒ３は、 Ｒ３＝Ｚ−（Ａ・16³ ＋Ｂ・16² ＋Ｃ・16¹ ）² ＝Ｚ−（Ａ² ・16⁶ ＋Ｂ² ・16⁴ ＋Ｃ² ・16² ＋２ＡＢ・16⁵ ＋２ＡＣ・16⁴ ＋２ＢＣ・16³ ) ＝Ｚ−（Ａ² ・16⁶ ＋２ＡＢ・16⁵ ＋Ｂ² ・16⁴ ） −（２ＡＣ・16⁴ ＋２ＢＣ・16³ ＋Ｃ² ・16² ) ＝Ｒ２−〔２（Ａ・16³ ＋Ｂ・16² ) ・Ｃ・16＋Ｃ² ・16² 〕 ・（５）’ ＝Ｒ２−〔２（Ａ・16³ ＋Ｂ・16² ) ＋Ｃ・16〕Ｃ・16 ・・（５） 第４位の桁Ｄを求めたときの部分剰余は同様にして、 Ｒ４＝Ｚ−（Ａ² ・16⁶ ＋Ｂ² ・16⁴ ＋Ｃ・16¹ ＋Ｄ）² ＝Ｒ３−〔２ＡＤ・16³ ＋２ＢＤ・16² ＋２ＣＤ・16＋Ｄ² 〕 ＝Ｒ３−〔２（Ａ・16³ ＋Ｂ・16² ＋Ｃ・16) ・Ｄ＋Ｄ² 〕 ・・（６）’ ＝Ｒ３−〔２（Ａ・16³ ＋Ｂ・16² ＋Ｃ・16) ＋Ｄ〕Ｄ ・・（６） ここで、Ｒ４を例にとると前の演算サイクルまでに求め
た中間商は、Ａ・16³＋Ｂ・16² ＋Ｃ・16であり、今回
予測した部分商はＤである。すなわち、前の演算サイク
ルまでに求めた中間商の２倍に今回予測した部分商を加
えたものを除数とみなし、それに今回予測した部分商を
掛けたものを除倍数とすれば除算と同じ操作となる。

【００１５】なお、（４）〜（６）式は、次のように変
形することもできる。 Ｒ２＝Ｒ１−〔２（Ａ・16³ ＋Ｂ・16² ）Ｂ・16² −Ｂ² ・16⁴ 〕・・（４）” Ｒ３＝Ｒ２−〔２（Ａ・16³ ＋Ｂ・16² ＋Ｃ・16) ・Ｃ・16−Ｃ² ・16² 〕 ・・（５）” Ｒ４＝Ｒ３−〔２（Ａ・16³ ＋Ｂ・16² ＋Ｃ・16＋Ｄ) ・Ｄ−Ｄ² 〕 ・・（６）” 除倍数を（６）’式または（６）”式によって生成する
ようにしても同じ結果をうる。

【００１６】以上を一般化すると以下に示すとおりであ
る。オペランドＺ、その平方根Ｘは、 ｒ：基数 ｋ：指数 ｘ：平方根の仮数 ｚ：オペラン
ドの仮数 とすると、 Ｚ＝Ｘ² ＝（ｘ・ｒ^k ）² ＝ｘ² ・ｒ^2k と表され、 ・・（11） Ｚ＝ｚ・ｒ^2k とおくと、ｚ＝ｘ² である。 ・・（12） ここで、 ｚ＝（Ａ・ｒ^-1＋Ｂ・ｒ^-2＋・・＋Ｍ・ｒ^-(n-1)＋Ｎ・ｒ^-n）² となるｚの平方根 x ＝Ａ・ｒ^-1＋Ｂ・ｒ^-2＋・・＋Ｍ・ｒ^-(n-1)＋Ｎ・ｒ^-n の各桁の数Ａ，Ｂ，・・Ｍ，Ｎを求める場合を考える
と、Ｒ０＝ｚとして、最上位桁Ａを求めたときの部分剰
余Ｒ１は、 Ｒ１＝ｚ−（Ａ・ｒ^-1）² ・・（13） 第２位の桁Ｂを求めたときの部分剰余Ｒ２は、 Ｒ２＝ｚ−（Ａ・ｒ^-1＋Ｂ・ｒ^-2）² ＝ｚ−〔（Ａ・ｒ^-1）² ＋２（Ａ・ｒ^-1）・（Ｂ・ｒ^-2） ＋（Ｂ・ｒ^-2）² 〕 ＝Ｒ１−（２Ａ・ｒ^-1＋Ｂ・ｒ^-2）・（Ｂ・ｒ^-2） ・・（14） 第３位の桁Ｃを求めたときの部分剰余Ｒ３は、 Ｒ３＝ｚ−（Ａ・ｒ^-1＋Ｂ・ｒ^-2＋Ｃ・ｒ^-3）² ＝Ｒ２−〔２（Ａ・ｒ^-1＋Ｂ・ｒ^-2）＋Ｃ・ｒ^-3〕・Ｃ・ｒ^-3 ・・（15） 一般に、第ｊ位の桁Ｊを求めたときの部分剰余Ｒｊは、 Ｒｊ＝ｚ−〔Ａ・ｒ^-1＋Ｂ・ｒ^-2＋・・＋Ｉ・ｒ^-(j-1)＋Ｊ・ｒ^-j〕² ＝Ｒ_j-1 −〔２（Ａ・ｒ^-1＋Ｂ・ｒ^-2＋・・＋Ｉ・ｒ^-(j-1)）＋Ｊ・ｒ^-j〕 ・Ｊ・ｒ^-j ここで、前の演算サイクルでの中間商を ｘ’＝（Ａ・ｒ^-1＋Ｂ・ｒ^-2＋・・＋Ｉ・ｒ^-(j-1)） とすると、 Ｒｊ＝Ｒ_j-1 −〔２ｘ’＋Ｊ・ｒ^-j〕・Ｊ・ｒ^-j〕 ・・（16） となる。

【００１７】（16）式に示すように、また、（４）〜
（６）式においても示されているように、部分剰余Ｒｊ
は、前の演算サイクルで求めた、中間商ｘ’の２倍に今
回予測した部分商Ｊ・ｒ^-jを加え、それに今回予測した
部分商Ｊ・ｒ^-jを掛けた値を前のサイクルの部分剰余Ｒ
_j-1 より引いた値となる。すなわち、中間商ｘ’の２倍
に今回予測した部分商Ｊ・ｒ^-jを加えたものを除数とみ
なせば、除算における、部分商を予測して除倍数を生成
し、それを順次減じて部分剰余を求める処理と同じであ
る。

【００１８】従って、平方根の計算は、除算において、
平方根の上位の桁を予測して除数の初期値として与え、
各演算サイクルの部分剰余を計算するにあたっては、最
初の演算サイクルは（13）式に示す演算を、その後の演
算サイクルについては（16）式による演算を行ない、各
演算サイクルで中間商を求める度にそれを新たな除数と
すればよい。

【００１９】除数として与える初期値は、除算器におい
て部分商の予測を行なうに充分なだけの桁数の上位桁の
値を与える。各演算サイクルにおける部分商の予測およ
び補正は除算における公知の処理である。

【００２０】浮動小数点数の場合、仮数部は以上によっ
て求められるが、指数部については、（11）式に示され
るように偶数となるように桁合わせされているオペラン
ドの指数（２ｋ）の２分の１を平方根の指数（ｋ）とす
ればよい。

【００２１】なお、（16）式の展開を変えて、 Ｒｊ＝Ｒ_j-1 −〔２ｘ’・Ｊ・ｒ^-j＋（Ｊ・ｒ^-j）² 〕 ・・（16）’ Ｒｊ＝Ｒ_j-1 −〔２（ｘ’＋Ｊ・ｒ^-j）・Ｊ・ｒ^-j−（Ｊ・ｒ^-j）² 〕 ・・（16）” とすることもできる。これらは（６）’式、（６）”式
に対応する。

【００２２】以上のように、従来の除算処理に対して、
除数の初期値の生成と、除倍数の補正と、部分商を求め
る毎の除数の補正とを追加することにより平方根を高速
に求めることができる。

【００２３】

【実施例】以下、図面を参照して浮動小数点数の平方根
を求める実施例を説明する。図３は本発明の実施例の要
部の構成を示すブロック図である。基本の構成は図１の
原理ブロック図に示すように、除算器に、除数の初期値
を予測して設定する初期値設定回路２と、被除数（部分
剰余）を算出するための補正された除倍数を生成する除
倍数補正回路３と、演算サイクル毎に除数を補正する除
数補正回路４を設けたものである。除倍数補正回路３は
新たに設けた除数変形回路18と元の除倍数生成回路19と
で構成する。本実施例は浮動少数点演算であるので、部
分剰余レジスタ16、除数レジスタ12等は仮数部を扱い、
他に指数を扱うレジスタ14、15とその制御回路を付加し
ている。

【００２４】除算器１の構成について説明する。被除数
入力端10からはオペランドを被除数として与える。除数
入力端11は割算のときは除数を与えるところである。し
かし、平方根を求める場合は除数は与えられないので関
係はない。代わりに初期値設定回路２により上位桁の予
測値を除数として設定する。

【００２５】12は除数レジスタで、除数として入力され
たデータを保持する。16は部分剰余レジスタで、最初は
オペランドを、その後は演算サイクル毎の部分剰余を格
納するレジスタである。これらは除数、被除数の仮数部
を保持するもので、指数部はそれぞれレジスタ14、15に
保持する。19は除倍数生成回路で、除数と予測された部
分商の積を生成する。部分剰余演算回路20は新たな被除
数つまり部分剰余を演算するもので、前のサイクルの部
分剰余を部分剰余レジスタ16より入力し、この部分剰余
から除倍数生成回路19で算出した除倍数を減算する。こ
の出力は部分剰余レジスタ16に新たな部分剰余として格
納されると共に次の部分商を予測するのに用いられる。

【００２６】部分商予測回路21には除数と部分剰余演算
回路20からの部分剰余が入力されており新しい部分商を
予測する。この新しい部分商はレジスタ22に保持され
る。23はこの新しい部分商を補正する回路で、この部分
商が大きすぎた場合に補正する。レジスタ24はこの補正
された最終部分商を格納する結果レジスタである。

【００２７】次に平方根を求める動作を図４を参照して
説明する。入力されたオペランドＺ（平方根を求めたい
数）は被除数として部分剰余レジスタ16に仮数部 X`CA0
D1F'（および15に指数X`6'）が格納され最初の剰余Ｒ０
となる (注：X`n'は16進数表現) 。このとき、（11）式
に示すように指数が偶数で、少数点が最上位有効桁の左
または右になるように正規化しておく。初期値設定回路
２はオペランドの仮数部ｚから、平方根の上位桁の値、
X`E3' を生成して初期値として除数レジスタ12にセット
する。また、その内の上位４ビットの値の自乗値(X`E')
² も生成して部分剰余演算回路20に与える。

【００２８】部分剰余演算回路20で（13）式に基づく演
算を行い、部分剰余Ｒ１を得る。以後の演算サイクルで
は、順次部分商 X`3',X`6',X`E',X`7',X`B',が予測さ
れ、除倍数補正回路３内の除数変形回路18と除倍数生成
回路19に入力される。除数変形回路18は除数レジスタ12
の上位の内容を１ビット左シフトして（すなわち前サイ
クルで得た除数すなわち中間商を２倍して）予測部分商
を付加して、除倍数生成回路19に入力する。ここで除数
レジスタの内容はすでに確定した上位桁以外は意味をも
たないので予測部分商はその下位桁を入替えればよく、
加算する必要はない。除倍数生成回路19はこの値に予測
部分商を掛けることにより除倍数を生成するので、これ
により補正された除倍数が得られる。そして部分剰余演
算回路20により演算すると、順次、（16）式に基づいた
部分剰余Ｒ2 〜Ｒ6 を得る。

【００２９】部分商予測回路21で求めた部分商は、必要
があれば部分商補正回路23で補正する。部分商補正は除
算器の公知技術である。除数補正回路４は、補正された
部分商を除数レジスタ12の対応する桁に挿入する。これ
により除数レジスタの内容は中間商となり、結果レジス
タ24の内容と同じく、演算サイクルが終わる毎に更新さ
れ、真の平方根に近づく。

【００３０】所定の桁数の演算がおわれば演算は終了す
る。指数は１／２すればよく、図の例では X`3' とな
る。本実施例は16進数の演算として説明したが、２進数
としても同じであり、浮動小数点数の表現形式をIEEE形
式等に合わせて構成することは容易である。

【００３１】なお、除倍数補正回路は、（16）’式、ま
たは（16）”式に基づいた補正を行なう回路として構成
してもよい。

【００３２】

【発明の効果】以上説明したように、本発明によれば除
算器をベースにして簡単な回路を追加することにより、
高速平方根演算器を実現することができる。

【図面の簡単な説明】

【図１】本発明の原理ブロック図である。

【図２】４桁の平方根を有する数の構成を示す図であ
る。

【図３】本発明の平方根演算器の実施例の要部の構成ブ
ロック図である。

【図４】実施例の平方根演算器の動作説明図である。

【符号の説明】

１ 除算器 ２ 初期値設定回路 ３ 除倍数補正回路 ４ 除数補正回路 10 被除数入力端 11 除数入力端 12 除数レジスタ 16 部分剰余レジスタ 18 除数変形回路 19 除倍数生成回路 20 部分剰余演算回路 21 部分商予測回路 22 予測商レジスタ 23 部分商補正回路 24 結果レジスタ

Claims (3)

【特許請求の範囲】
1. 【請求項１】 除数レジスタ（12）と、部分剰余レジス
   タ（16）と、部分商予測回路（21）と、部分商補正回路
   （23）と、除倍数生成回路（19）と、部分剰余演算回路
   （20）とを備え、一度に複数ビットの部分商を求める除
   算器（１）において、 オペランドから除数の初期値と最初の除倍数とを生成す
   る初期値設定回路（２）と、 除算器（１）の除倍数生成回路（19）の生成値を補正す
   る除倍数補正回路（３）と、 除算器（１）の除数レジスタ（12）の値を補正する除数
   補正回路（４）とを設け、 初期値設定回路（２）は、入力されたオペランドから平
   方根の上位桁の値を除算器（１）の部分商予測に必要な
   桁数分予測して除数レジスタ（12）に設定し、かつ、そ
   の内の部分商生成ビット数分の上位桁の値の自乗を生成
   して部分剰余演算回路（20）に入力し、 除倍数補正回路（３）は、最初の演算サイクルでは、初
   期値設定回路（２）から与えられた、部分商生成ビット
   数分の上位桁の値の自乗値を、補正された除倍数として
   部分剰余演算回路（20）に入力し、２回目以後の演算サ
   イクルでは、その前の演算サイクルで求めた中間商の２
   倍に今回予測した部分商を加え、その値に今回予測した
   部分商を掛けた値を、補正された除倍数として部分剰余
   演算回路（20）に入力し、 部分剰余演算回路（20）は、部分剰余レジスタ（16）に
   ある前の演算サイクルで得られた部分剰余からこの補正
   された除倍数を引いた値を新たな部分剰余として部分剰
   余レジスタ（16）にセットし、 除数補正回路（４）は、演算サイクル毎に、部分商補正
   回路（23）によって補正された部分商によって除数レジ
   スタの除数を補正するように構成したことを特徴とする
   平方根演算装置。
2. 【請求項２】 除倍数補正回路（３）は、２回目以後の
   演算サイクルでは、その前の演算サイクルで求めた中間
   商と今回予測した部分商とを掛けた値を２倍した値と、
   今回予測した部分商の自乗との和を補正された除倍数と
   するように構成したことを特徴とする請求項１に記載の
   平方根演算装置。
3. 【請求項３】 除倍数補正回路（３）は、２回目以後の
   演算サイクルでは、その前の演算サイクルで求めた中間
   商と今回予測した部分商との和に今回予測した部分商を
   掛けた値を２倍した値より今回予測した部分商の自乗を
   引いた値を補正された除倍数とするように構成したこと
   を特徴とする請求項１に記載の平方根演算装置。