JPH01205330A - 除算装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、高精度で高速の割算を実行する除算装置に関
するものである。

従来の技術 四則演算のなかでも除算は演算時間が長くかかり、しか
も単純なアルゴリズムを使う場合、除数と被除数（また
は部分剰余）との大きさを比較し、それによって次の演
算の種類を決定するような逐次処理をともなうため、乗
算のように並列動作回路数を増して演算時間を短縮する
ことも困難であった。そこで従来より改良された除算法
として収束型除算法が提案されている。これは高速の乗
算器と加減算器を使うものである。

この説明を簡単にするため、除数、被除数（または部分
剰余）ともに正規化されている場合（浮動小数点表現の
場合の仮数部はこれに該当する）を考える。

この場合、除数（Ｄ）は０．１ＸＸ・・・・・・×（有
効桁数Ｎ桁、××は０または１の数列）で、Ｄ−１−Ｄ
、　　とするとり、は０．１よりも小さい数となる。

（］）、＝Ｑ、１の場合、ｎ＝ｏ、１な９商は被除数（
または部分剰余）を２倍するだけでよく、これは２進数
の場合１桁（１ビツト）左シフト操作なので本格的な割
算を実行する必要がなく、この場合は除外しても一般性
を失わない） 割算器÷Ｄは次のように数式変換ができる。

Ａ／Ｄ＝Ａ／（１−Ｄ、　）＝Ａ（１＋Ｄ、　）／［（
４−Ｄ、　）（１＋Ｄ、　）］＝Ａ（１＋Ｄ、）（１＋
Ｄ、”）／［（１−Ｄ、）（１＋Ｄ、）（１＋Ｄ、’）
］＝ムＩＴ　（１＋Ｄ、　　）／（１−Ｄ、　　）　　
　　　・・・・・・（１）ｎ＝＋ 数値系の有効桁数ＮがＮ−６２の場合（倍精度の浮動小
数点表現形式の場合４８≦Ｎ≦５２が多い）、Ｄ１″は
有効桁数の範囲を超えて小さい数になっているため実質
的に０と同一であり結局下記のような近似式が成り立つ
。

Ａ／Ｄ＝Ａ　（１＋Ｄ、　）＝Ａ（１＋Ｄ、）（１＋Ｄ
、　）（１＋Ｄ、　）　　・・・・・・（１＋Ｄ、　　
） 従ってり、の２ｎ　　ベキ乗の計算と各々と１との加算
、各類６回の乗算を実行することで割算が実行できる。

ここでり、　はり、　　　’ｉ２乗することで求められ
るし、１＋Ｄ１　の計算はただＤ　、　２　ｎの最上位
桁（元々は０．０・・・・・・０１××と０であるが）
を１するだけでよいので演算時間は実質的に不要である
ことを考慮すれば、Ｄ、’ｅ求めるための減算が１回と
１１回の乗算で割算が可能である。

非常に高速な乗算器を使うと、これらの演算時間の総和
は１〜２μ秒程度になり、比較的高速な除算器が得られ
ていた。

発明が解決しようとする課題 従来の収束型除算は回路規模は乗算器と減算器と制御回
路があればよく比較的小さくて済むが乗算回数が多いた
めどうしても非常に高速な割算器が作りにくかった。

割算専用に大規模な回路を設けて非常に高速な除算を実
行する方法も知られてはいるが、通常の演算装置は四則
演算全てを実行する場合が多く、乗算機能や加減算機能
とともに除算機能をもたせている。即ち乗算器や加減算
器が近くに存在するので５これらの演算機能全うまく利
用すれば回路規模は大きくならずに除算が実行できる。

従って収束型除算のアルゴリズムに似た方法で乗算回数
がもっと少なくて済む方法が必要となる。

本発明は、かかる点に鑑み、より高速でコンパクトな除
算装置を提供することをその目的としている。

課厘を解決するための手段 本発明は、２進数、有効桁数Ｎ桁の正規化された数値系
で、除数（Ｄ）の上位Ｍ桁（Ｄ０）　（ただしｏ＜Ｍ＜
Ｎ）のうち少なくとも最上位桁は零でない２　　個の数
値各々に対応した値の逆数を格納する逆数テーブルと、
この逆数テーブルを前記上位Ｍ桁の数値でアクセスした
時に対応する前記逆数を出力する出力手段と、この出力
手段からの出力と被除数（または部分剰余）と前記除数
の下位（Ｎ−Ｍ）桁の反転値を入力する高速収束型際乗
算器とを備えたこと全特徴とする除算装置である０ 作用 除数（Ｄ）の上位Ｍ桁（Ｄ０）に対応した値の逆数をあ
らかじめ逆数テーブルに格納し、この値と除数（Ｄ）の
下位（Ｎ−Ｍ）桁の反転値とを用いて収束型除算に行う
ことにより、コンパクトで高速な除算を可能とするもの
である。

実施例 本発明では、従来の変換式（１）　、　（２）の代りに
次の式を用いる。

ム／Ｄ−ム／（Ｄｏ’−Ｄ、’）＝人／［Ｄｏ’（１−
Ｄ、’／ｎｏ’）］＝（ム／Ｄｏ’）／（１−ｒ）　ｉ
但しｒ＝１）、’／Ｄｏ’　＜（１＝（Ａ／Ｄｏ’）（
１＋ｒ）（１＋ｒ２）（１＋ｒ　）（１ａｒ　）・・・
・・・（３） 式中り。′としては有効桁数Ｎのうち、上位Ｍ桁だけが
除数りと同一で、下位（Ｎ−Ｍ）桁は全て１であるもの
を代表値として選び、この代表値に対して逆数テーブル
を用意している。このような代表値を選ぶと、実際の除
数りは次のように差の形で表わされ Ｄ　＝Ｄｏ’　−Ｄ、’　＝Ｄｏ’　（１−ｒ　）従っ
て分子は足し算だけを使った上記式（３）の形になる。

しかもり、°はＤの下位（Ｎ−Ｍ）ピットＤ、１反転す
るだけでもとめられ、減算をする必要がない。（従って
減算器もいらない。）具体的には、Ｄｏに対する（１／
Ｄｏ“）を出力する手段、乗算手段、反転手段、Ｎ桁数
値の最上位ピットを１にする加算器相当手段および、各
演算の実行を制御する制御手段によって構成するもので
ある。この逆数テーブルとその出力手段として読み出し
専用メモＩＪ（ＲＯＭ）１ｉ用い、高速収束型除算器１
０が乗算器１２．加算器相当手段および反転器１３を備
えた構成の一例を第１図に示す。

数値例として有効桁数６２で２進表示の例を考え、Ｄｏ
としては上位、例えば１２桁（最上位は１）をとる。従
ってり。′の候補としては、２　個（２，０４８）存在
するのでＲＯＭ１（７）規模は、２０４８語×６２ピッ
ト（約１００にビット）となる。通常この程度のＲＯＭ
１のアクセス時間は５２ビツトの乗算時間の約１／２程
度である。この場合の動作は次のようになる。

１）ＲＯＭ１ｉＤ。によってアクセス（即ち、Ｄ。

に対応するＭ−１ピツトの番地に格納されているデータ
を読みだす）すると、Ｄｏ“の逆数１／ｐ、ｌが出力さ
れる。

２）１／Ｄｏ′と除数の残留下位（Ｎ−Ｍ）ピットの反
転との積り、’　／Ｄｏ’　（＝ｒ　）　Ｔｈ乗算器１
２で求める。

３）これと被乗数の積ム／Ｄｏ”ｅ乗算器１２を用いて
計算する。

４）積ｒ　を乗算器１２を用いて計算する。

５）（１＋ｒ）ｋ加算器相当１４を用いて計算しく演算
時間は無視できる）、これとステップ３）で求めた積Ａ
／Ｄｏ’との積（ム／Ｄｏ’）（１＋ｒ）ｅ乗算器１２
を用いて計算する。

６）積ｒ　を乗算器１２を用いて計算する。

７）（１＋ｒ）を加算器相当１４を用いて計算し、これ
とステップ５）で求めた積（ム／Ｄｏ’）（１＋ｒ）と
の積：（人／ＤＯ’　）　（’　＋　ｒ　）　（１＋ｒ
）　ヲ乗算器１２を用いて計算する。

８）　　（１＋ｒ’）ｔ−加算器相当１４を用いて計算
し、これとステップ７）で求めた積（Ａ／Ｄｏ’　）（
１＋ｒ）（４＋ｒ２）との積：（人／Ｄｏ’）（１＋ｒ
）（１＋ｒ２）（１＋ｒ’）を乗算器１２を用いて計算
する０ ９）ステップ８）の結果を商として出力する。

従って、（３）式の計算を完了するには、各演算および
処理を次の回数だけ実行することになる。

５２桁乗算　ニア回 ４０桁反転　：１回（演算時間実質的にゼロ）ＲＯＭ読
み出し一１回（乗算０．６回相当）演算回数を全て乗算
に換算すると、７．５回相当になる。

制御手段１６ばこれらの一連の演算処理の実行を制御す
る部分である。

他の実施例の構成図を第２図に示す。

この場合、４乗器も別途用意する。（但し、４算器３６
は精度４桁（５２−１２Ｘ４）のＲＯＭで構成すれば充
分である）この場合の動作は１）ＲＯＭ１ｉＤ。によっ
てアクセス（即ち、Ｄ。

に対応するＭ−１ビツトの番地に格納されているデータ
を読みだす）すると、Ｄ。＋の逆数１／Ｄｏ′が出力さ
れる０ ２）１／Ｄｏ′と除数の残留下位（Ｎ−Ｍ）ビットの反
転との積り、’／Ｉ）ｏ’　（＝ｒ）　ｋ乗算器１２で
求める。

３）これと被乗数の積人／Ｄｏ＋を乗算器１２を用いて
計算する。

４）積ｒ２に乗算器１２を用いて計算する。

６）　　（１＋ｒ’）ｉ４乗算器６全用いて計算する。

６）（１＋ｒ）を加算器相当１４を用いて計算しく演算
時間は無視できる）、これとステップ３）で求めた積ム
／Ｄｏ＋との積（Ａ／Ｄｏ’）（１＋ｒ　）を乗算器１
２を用いて計算する。

７）（１＋ｒ２）を加算器相当１４を用いて計算し、こ
れとステップ６）で求めた（１＋ｒ　）　　積−（１＋
ｒ　）　（１−１−ｒ’）を乗算器１２全用いて計算す
る。

８）ステップ６）で求めた（Ａ／Ｄｏ’）　（１＋ｒ　
）とステップ７）で求めた積（１＋ｒ　　）（１＋ｒ’
）との積：　（Ａ／Ｄｏ’　）（１＋ｒ　）　（１＋ｒ
２）　（１＋ｒ’　）を乗算器１２全用いて計算する。

従って、（模式の計算を完了するには、各演算および処
理を次の回数だけ実行することになる。

６２桁乗算　二〇回 ４０桁反転　：１回（演算時間実質的に零）ＲＯＭ読み
出し１１回（乗算０．６回相当）４乗器読み出し＝１回
（乗算時間に隠れる）演算回数を全て乗算に換算すると
、６．６回相当になる。

また、有効桁数Ｎが少ない場合、例えば２４桁のときは
、Ｍを１２に選ぶと、１５以上の項は無視できるので、
次のような一連の処理で商が計算できる。

１）ＲＯＭ１’ｊｉＤ。によってアクセス（即ち、Ｄ。

に対応するＭ−１ピツトの番地に格納されているデータ
を読みだす）すると、Ｄｏ’の逆数１／Ｄｏ′が出力さ
れる。

２）１／Ｄｏ’と除数の残留下位（Ｎ−Ｍ）ビットの反
転との積り、’　／Ｄｏ’　（＝ｒ　）ｋ乗算器１２で
求める。

３）これと被乗数の積大／Ｄ０’ｅ乗算器１２を用いて
計算する０ リ　（１＋ｒ）を２乗器を用いて計算する。

５）（１＋ｒ）’ｅ加算器相当１４を用いて計算しく演
算時間は無視できる）、これとステップ３）で求めた積
Ａ　／　Ｄｏ’との積（人／　ＤＯ’）　（１＋　ｒ）
を乗算器１２を用いて計算する。

６）ステップ６〕で求めた（人／ＤＯ’　）　（１＋ｒ
）　　とステップ４）で求めた積（１＋ｒ２）　　との
積：（Ａ／Ｄｏ’）　（１＋ｒ　）　（１＋ｒ２）　’
ｉ乗算器１２を用いて計算する０ ７）ステップ６）の結果を商として出力する０従って、
（３）式の計算を完了するには、各演算および処理を次
の回数だけ実行することになる。

２４桁乗算　：４回 １２桁反転　：１回（演算時間実質的に零）ＲＯＭ読み
出し一１回（乗算０．５回相当）２乗器読み出し１１回
（乗算時間に隠れる）演算回数を全て乗算に換算すると
、４．６回相当になる。

発明の効果 実施例の説明から明きらかなとおり、本発明によれば乗
算を含めて、商を求めるために実行すべき全演算の実行
回数（即ち実行時間）が大幅に減っており、しかもハー
ドウェアとしては逆数出力手段（１’ｌＯＭ）と乗算器
および簡単な反転回路を設けることにより高速な除算が
行なえることがわかる。また、第２図に対応する実施例
では、２乗器、或いは４乗器が更に必要となるが、この
場合於いては、２）〜７）までの前後の演算オペランド
は独立であるので、乗算器が２段のパイプライン構成に
なっていると、各乗算実行時間が等測的に半分になる。

よって除算実行時間は １）　　　　　　　乗算０．５回相当 ２）　、　３）　、　４）　、　６）　　乗算０．５回
相当７）　、　８）　　　　　　乗算１　回相当全体で
乗算４．６回相当と更に高速にすることができる。

従来の収束型が乗算１１回、減算１回即ち、乗算１１．
６回相当だったのに対して、本発明に示した若干の素子
、回路の追加で演算時間が、１．５〜２．６倍改善され
る。

【図面の簡単な説明】

第１図は本発明の第１の実施例の構成図、第２図は本発
明の第２の実施例の構成図である。 １・・・・・・ＲＯＭ、１０・・−・・・収束型除算器
、１２・・・・・・乗算器、Ｄ・・・・・・除数、ム・
・・・・・被除数。 代理人の氏名　弁理士　中　尾　敏　男　はが１名第１
図 第２図

Claims (3)

【特許請求の範囲】
1. （１）基数２（二進数）、有効数字Ｎ桁の正規化された
   数値系で、除数（Ｄ）の上位Ｍ桁（Ｄ＿０、ただし０＜
   Ｍ＜Ｎ）のうち少なくとも最上位桁は零でない２＾Ｍ＾
   −＾１個の数値に対応し、上位Ｍ桁がＤ＿０と同一で下
   位（Ｎ−Ｍ）桁が全て論理１である数値Ｄ′＿０の有効
   数字Ｎ桁以上の逆数を格納する逆数テーブルと、この逆
   数テーブルを前記Ｍ桁の数値でアクセスした時に対応す
   る前記逆数を出力する出力手段と、この出力手段からの
   出力と、被除数と、前記除数の下位（Ｎ−Ｍ）桁の数値
   を入力する、収束型除算器とを備えたことを特徴とする
   除算装置。
2. （２）収束型除算器は有効桁数Ｎ桁以上の演算精度を持
   つ乗算手段、（Ｎ−Ｍ）個の論理反転手段とを備え、前
   記除数（Ｄ）の上位Ｍ桁（Ｄ＿０）で前記逆数出力手段
   をアクセスして、出力として上位Ｍ桁は前記Ｄ＿０と同
   一で、下位（Ｎ−Ｍ）桁は全て論理１である除数代表値
   （Ｄ′＿０）の有効数字Ｎ桁以上の逆数を得、この逆数
   と被逆数との積（積０）を前記乗算手段を使って求め、
   除数（Ｄ）の下位（Ｎ−Ｍ）桁を前記論理反転手段を使
   って反転した微小誤差（Ｄ′＿１）と前記逆数との積（
   積１）を前記乗算手段で求め、更にこの積（積１）の２
   ＾ｎ乗（ｎは１、２、３、・・・・・・各々積２、積４
   、積８・・・・・・）を２＾ｎ×ＭがＮを超える直前ま
   で順次前記乗算手段を使って求め、並行して、前記積０
   を被乗数とし、前記積２＾ｎ＾−＾１の最上位桁を１に
   変換した数値を前記乗算手段を用いて順次累積乗算し、
   最終積を商として出力することを特徴とする特許請求の
   範囲第１項記載の除算装置。
3. （３）収束型除算器は有効桁数Ｎ桁以上の演算精度をも
   つ乗算手段、（Ｎ−Ｍ）個の論理反転手段、および、Ｎ
   桁の２進の数値で上位Ｍ桁が全て０である数値（Ｄ′＿
   １）の２乗あるいは４乗の上位Ｎ桁の数値テーブルを持
   ち、各々、上記数値（Ｄ′＿１）の最上位から数えて（
   Ｍ＋１）桁目から（Ｎ−Ｍ＋１）桁目まで、もしくは最
   上位から数えて（Ｍ＋１）桁目から（Ｎ−３Ｍ＋１）桁
   目までの数値でアクセスし、対応する２乗または４乗の
   値を出力する出力手段を備え、前記除数（Ｄ）の上位Ｍ
   桁（Ｄ＿０）で前記逆数出力手段をアクセスして、出力
   として上位Ｍ桁は前記Ｄ＿０と同一で、下位（Ｎ−Ｍ）
   桁は全て論理１である除算代表値（Ｄ′＿０）の有効数
   字Ｎ桁以上の逆数を得、この逆数と被除数との積（積０
   ）を前記乗算手段で求め、更にこの積（積１）の２乗を
   前記２乗数値テーブル内蔵の出力手段もしくは前記乗算
   手段を用いて計算し積２とし、同じくこの積（積１）の
   ４乗を前記４乗数値テーブル内蔵の出力手段を用いて計
   算し積４とし、並行して、前記積０を被乗数とし、前記
   積１、積２、積４の各々の最上位桁を１に変換した各変
   換項を前記乗算手段を用いて順次累積乗算し、４Ｍ＞Ｎ
   の場合に対応する商として、積０から積２の変換項まで
   の累積、８Ｍ＞Ｎの場合の商を、積０から積４までの累
   積を各々出力することを特徴とする特許請求の範囲第１
   項記載の除算装置。