JP2777265B2 - 高基数開平演算装置 - Google Patents

Description

【発明の詳細な説明】 〔目次〕 概要 産業上の利用分野 従来の技術（第３図、第４図） 発明が解決しようとする課題 課題を解決するための手段（第１図） 作用 実施例（第２図） 発明の効果 〔概要〕 高基数開平演算装置に関し、 高速で開平演算処理ができるようにすることを目的と
し、 最上位ビットより始めて、加減算及びシフトを繰り返
すことにより、順次下位ビットを求めていく、減算シフ
ト型の開平方式を用いて高基数の開平演算処理を行う高
基数開平演算装置において、答の近似値ａを入れるレジ
スタと、残余Ｒを入れるレジスタと、近似値ａ及び残余
Ｒを入力し、部分商予測によって予測値ｒを求める部分
商予測器と、近似値ａ及び求めた予測値ｒを入力して加
算処理を行い、新たな近似値を求める加算器と、残余
Ｒ、近似値ａ、及び求めた予測値ｒを入力し、新たな残
余を計算して求める残余計算部とを設け、１回の加算
と、１回の部分商予測と、残余計算部の１マシンサイク
ル中に、平方根のｎ（ｎ≧２）ビットが求められるよう
に構成する。

〔産業上の利用分野〕

本発明は高基数開平演算装置に関し、更に詳しく言え
ば、ディジタル計算機において用いられ、特に、平方根
を求める演算を高速化した高基数開平演算装置に関す
る。

〔従来の技術〕

第３図は従来例の構成図、第４図は従来例の処理フロ
ーチャートである。図中、１はセレクタ、２、３はレジ
スタ、４はCSA（桁上げ保存加算器）、５は加算器を示
す。なお、第４図の処理番号はカッコ内に示す。

従来、ディジタル計算機において、開平演算は、基本
的な演算であり、技術計算では頻繁に使用されている。

上記の開平演算の内、従来用いられていた減算シフト
型の開平法の基本的なアルゴリズムは、次のようなもの
である。

今、２進数で表わされる正の数Ｘの平方根を求めたい
とする。この場合適切なシフトによって、予め１≦Ｘ＜
４となるようにしておく。

ここで先ず、 の最初の１ビットの近似値として無条件にａ＝１をと
る。この時、 a²≦Ｘ＜（ａ＋１）^２ ……（１） が成り立っている。

また、残余ＲをＸ−a²として定義しておく。

次に、Ｋビットの近似値ａが得られていて、式（１）
が成り立っている時、次のようにしてＫ＋１ビットの近
似値a₁と対応する残余R₁を求める。但し、Ｘでなく4Xの
平方根を求めても同じことなので、こちらで考える。つ
まり、 a₁ ²≦4X＜（a₁＋１）^２を満たすa₁を求める。式（１）
より、 （2a）^２≦4X＜（2a＋２）^２ ……（２） が成り立っているから、a₁、R₁の取り方としては、 4X＜（2a＋１）^２なら、 a₁＝2a、R₁＝4Rとして、 （2a＋１）^２≦4Xなら、 a₁＝2a＋１、R₁＝4X−（2a＋１）^２＝ 4R−4a−１ とすればよい。上記の処理を繰り返して行うことにより
平方根が得られる。

上記アルゴリズムに基づく処理は次のようにして行わ
れる。

処理装置としては、第３図に示したように、セレクタ
１、レジスタ２、３、CSA4、加算器５によって構成され
る。上記セレクタ１では、加算器５からの符号出力をセ
レクト信号とし、4R、または4R−4a−１のいずれか一方
を選択する。また、レジスタ２は、残余Ｒを格納するレ
ジスタであり、レジスタ３は近似値ａを格納するレジス
タである。

上記処理装置による開平処理は、第４図に示したよう
に、先ず、ａ＝１、Ｒ＝Ｘ−a²とする（100）。

次に、4X＜（2a＋１）^２であれば、（101）、a₁＝2
a、R₁＝4Rとする（102）が、もし4X（2a＋１）^２ならば
（101）、a₁＝2a＋１、R₁＝4X−（2a＋１）^２＝4R−4a
−１とする（103）。

このような処理（101）〜（103）をｍ回繰り返すと、
ｍビットの平方根が得られる。

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

上記のような従来のものにおいては次のような欠点が
あった。

即ち、上記従来例で示した処理（101）〜（103）の主
要な演算は、4R−4a−１を求めることである。

これは、ハードウェア的に、１回の減算と、CSA1段で
実現できるので、常識的な１マシンサイクル中に容易に
納まる。しかし、１サイクルに１ビットしか結果が得ら
れないため、開平演算処理が遅くなる欠点があった。

本発明は、このような従来の欠点を解消し、高速で開
平演算処理ができるようにすることを目的とする。

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

第１図は本発明の原理図であり、図中、10、11はレジ
スタ、12は部分商予測器、13は残余計算部、14は加算器
を示す。

本発明は、上記の目的を達成するため、最上位ビット
より始めて加減算及びシフトを繰り返すことにより、順
次下位ビットを求めていく、減算シフト型の開平方式を
用いて高基数の開平演算処理を行う高基数開平演算装置
において、 答の近似値ａを入れるレジスタ10と、残余Ｒを入れる
レジスタ11と、上記近似値ａ及び残余Ｒを入力し、部分
商予測によって予測値ｒを求める部分商予測器12と、上
記近似値ａ及び求めた予測値ｒを入力して加算処理を行
い、新たな近似値 を求める加算器14と、上記残余Ｒ、近似値ａ、及び求め
た予測値ｒを入力し、新たな残余 を計算して求める残余計算部13とを設け、 １回の加算と、１回の部分商予測と、残余計算部13の
１マシンサイクル中に、平方根のｎ（ｎ≧２）ビットが
求められるようにしたものである（ただしＮ＝2ⁿ）。

〔作用〕

本発明は上記のように構成したので、次のような作用
がある。

最初に前処理として、答えの近似値ａ及び残余Ｒを求
めて、レジスタ10及びレジスタ11にそれぞれの値を入れ
ておく。

次に、本処理として、次の（１）〜（３）の処理をｍ
回繰り返して行う。

（１） レジスタ10内の近似値ａと、レジスタ11内の残
余Ｒを、部分商予測器12に入力し、予測値ｒを求める。

（２） レジスタ11内の残余Ｒと、レジスタ10内の近似
値ａと、上記部分商予測器12で求めた予測値ｒを、残余
計算部13に入力して、新たな残余 を求め、レジスタ11内の残余Ｒを更新する。

（３） レジスタ10内の近似値ａと、上記部分商予測器
12で求めた予測値ｒを、加算器14に入力し、新たな近似
値 を求めてレジスタ10内の近似値ａを更新する。

このようにすると、上記（１）及び（３）の処理が１
回と、（２）の処理の１マシンサイクル中に、平方根の
ｎ（ｎ≧２）ビットが求められる。従って、開平処理が
高速化できる。

〔実施例〕

以下、本発明の実施例を図面に基づいて説明する。

第２図は、本発明の１実施例の構成図であり、図中、
第１図と同符号は同一のものを示す。また、15は自乗
器、16〜18はCSA（桁上げ保存加算器）、19はCPA（桁上
げ伝播加算器）を示す。

この例では、残余計算部13を、自乗器15と、３段構成
のCSA16〜18と、CPA19によって構成し、加算器14にもCP
Aを用いる。そして、減算シフト型の開平方式で、高基
数の開平演算処理を行うものであり、以下、詳細に説明
する。

開平演算処理において、１サイクルにｎビット（ｎ≧
２）の結果を得るには、次のようにする。今、Ｎ＝2ⁿと
して、 の近似値ａが精度1/N^Kで求まっている（ただし、Ｋは、
近似値ａのＮ進数での桁数を示す）。即ち、 が成り立っていたとする。このａから精度1/N^Kの近似値 を求めたい。

即ち、 であるような整数ｒを求めたい。

なおこの時、式（３）より、−Ｎ＋１≦ｒ≦Ｎ−１の
範囲で解があるはずである。

残余R_kをN^K（Ｘ−a²）として定義しておく。式（３）
より、−2a＋1/N^K＜R_K＜2a＋1/N^Kである。

次に、式（４）を変形すると、 となる。ここで|r|＜Ｎより、 が成り立てば式（５）も成り立つ。

式（６）を変形すると、 今、2aN^K-1がある定数Ｃ以上であることが分かってい
るものとすると、 が成り立つようなｒが見つかれば上記（７）式が成り立
ち、上記（５）式も成り立つ。従って、近似値a₁が求ま
ったことになる。この時、新しい残余R_K+1は、 上記（８）式を満たすようなｒは、高基数非回復型除算
回路でよく知られた部分商予測の手法を用いて１マシン
サイクルに十分収まる論理段数で求められる。

以上のことをまとめると、アルゴリズムは次のように
なる。

Ｘに適当なシフトを施した後、ａ≧a₀となり、且つ
上記（３）式を満たすようなａを求める。Ｒ＝N^K（Ｘ−
a²）とおく。

上記（８）式を満たすｒを部分商予測により求め、 このの操作をｍ回繰り返すと、mnビットの近似式が求
まる。

中のａの更新は、何回繰り返しても、ａ＞a₀−１が
成り立つので、上記（８）式でＣ＝2a₀N^K-1とおいて部
分商予測を行えばよい。

ｒを掛けるという操作は、ｒが高々ｎビットなので、
CSA段数と加算器でできる。また、1/N倍は、ｎビット右
シフトに等しいので、特に回路は不要である。

ところで、第２図においては、ｎ＝２の場合を示して
ある。最初に64≦Ｘ＜256となるように、Ｘをシフトし
た後、表１に基づく初期予測を行った結果がレジスタ10
に入れられる。

表１の予測は、（ａ−１）^２＜Ｘ＜（ａ＋１）^２とな
るようになっている。a₀＝８、Ｃ＝４、Ｋ＝０である。
上記（８）式は、 となる。

また、残余R₀＝Ｘ−a²がレジスタ11に入れられる。

レジスタ10内のデータは、符号なしで、整数部は４ビ
ットであり、レジスタ11内のデータは、符号付きで、整
数部は符号を入れて６ビットである。

このケースでは、Ｒとａの整数部だけで部分商予測が
できる。整数部をＲ，ａとすると、２Ｒ≦2R＜２Ｒ＋
２、ａ≦ａ＜ａ＋１となるから、（９）式の十分条件
は、 である。

この（10）式を満たすようなｒを全てのａ、Ｒについ
て求めたのが表２である。

１サイクル毎に、先ず、Ｒとａの上位ビットから表２
に基づく部分商予測が行われる。結果ｒは、ここでは符
号付き３ビットである。また、r²を求めるために、自乗
器15に入れる。更に、ｒの各ビットがａの−４倍、２
倍、１倍に掛けられ、最後にＲ、r²、−4ar₂、2ar₁、ar
oが（各々適切にシフトされた後）加算されてレジスタ
Ｒに入る。

〔発明の効果〕

以上説明したように、本発明によれば、１回の加算
と、１回の部分商予測と、CSA数段程度から成る１マシ
ンサイクル中に、平方根のｎ（ｎ≧２）ビットを求める
ことができるから、高基数の開平演算処理が高速ででき
る効果がある。

【図面の簡単な説明】

第１図は本発明の原理図、 第２図は本発明の１実施例の構成図、 第３図は従来例の構成図、 第４図は従来例の処理フローチャートである。 10、11……レジスタ 12……部分商予測器 13……残余計算部 14……加算器

Claims (1)

(57)【特許請求の範囲】
1. 【請求項１】最上位ビットより始めて、加減算及びシフ
   トを繰り返すことにより、順次下位ビットを求めてい
   く、減算シフト型の開平方式を用いて高基数の開平演算
   処理を行う高基数開平演算装置において、 答の近似値ａを入れるレジスタ（10）と、 残余Ｒを入れるレジスタ（11）と、 上記近似値ａ及び残余Ｒを入力し、部分商予測によって
   予測値ｒを求める部分商予測器（12）と、 上記近似値ａ及び求めた予測値ｒを入力して加算処理を
   行い、新たな近似値（a₁＝ａ＋r/N^K+1）を求める加算器
   （14）と、 上記残余Ｒ、近似値ａ、及び求めた予測値ｒを入力し、
   新たな残余（R₁＝RN−2ar−r²/N^K+1）を計算して求める
   残余計算部（13）とを設け、 １回の加算と、１回の部分商予測と、残余計算部（13）
   の１マシンサイクル中に、平方根のｎ（ｎ≧２）ビット
   が求められるようにしたことを特徴とする高基数開平演
   算装置。