JPH0594280A

JPH0594280A - 逆数の計算方法と、該方法を実施するためのコンピユータ

Info

Publication number: JPH0594280A
Application number: JP8316391A
Authority: JP
Inventors: Georges Keryvel; ケリヴエルジヨルジユ; Jean-Louis Thomas; トマジヤン−ルイ
Original assignee: Bull SAS
Current assignee: Bull SAS
Priority date: 1990-03-21
Filing date: 1991-03-22
Publication date: 1993-04-16
Anticipated expiration: 2016-08-06
Also published as: DE69128656D1; EP0448448B1; DE69128656T2; JP3195609B2; FR2660086B1; EP0448448A1; FR2660086A1; CA2038463C

Abstract

(57)【要約】【目的】逆数の計算方法と、該方法を実施するための
コンピュータ【構成】本発明は、数Ｄの逆数Ｉを計算するためにデ
ジタルコンピュータで使用することのできる方法に関す
る。本発明では、逆数は、逆数表を基に得られる第１の
値Ｉ₀に基づいた線形近似により得られる近似値に相補
訂正Ｃ_jlを適用した後Ｉ₂により概算される。訂正値Ｃ
_jlは、縮小された寸法の表に記憶される予備設定データ
ＣＢ_lおよびＨ_jから得られる。本発明はまた上記の方
法を実施するためのデジタルコンピュータに関する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、デジタルコンピュータ
で使用することのできる、逆数の計算方法に関する。

【従来の技術】

【０００２】逆数の計算は、除算、特に浮動小数点形式
の十進法を用いた除算においてよく用いられる。特に、
２つの数の除算の結果は、除数の逆数による被除数の単
純な乗算で得られる。

【０００３】典型的には、数Ｄの逆数Ｉの除算または計
算は、下記の２つの主なグループに分けられる方法で達
成される。即ち、 ──減算と連続的なシフトを用いる方法と、 ──再帰方程式：Ｉ_n+1＝Ｉ_n×（２−（Ｄ×Ｉ_n)) （ただし、ＩｎはＩに向かって収束する）による、ニュ
ートンのアルゴリズムにほぼ基づいた反復法である。

【発明が解決しようとする課題】

【０００４】実際には、減算とシフト法で、各段階で１
つまたは２つだけの追加有効数字を得ることができる。
従って、これらの方法は、沢山のオペレータを必要と
し、このような回路は、一般に速度が遅く、集積化する
のが難しい。

【０００５】除算の性能を最も重視する科学用電子計算
機では、一般に反復法が好まれている。ニュートンの方
法を正規化した数に適用すると、反復毎の演算結果の精
度を２倍にすることができる。しかし、各演算は、順番
に行う２つの乗算を必要としている。これら乗算は並列
化することができない。さらに、反復回数を減らすた
め、一般に逆数表を用いて反復の初期値を得る。この場
合、初期値の精度は逆数表の物理的な大きさにより制限
される。例えば、約２²ⁿの精度、すなわち２ｎ個の有効
ビットの場合、逆数表の増分ｉを２^-nに等しく選択され
るならば、２^n-1個のエントリを必要とする。

【０００６】本発明は、上に述べた問題点を解決し、あ
るいはそれらの影響を小さくすることができ、回路の数
および寸法を減少して、オペレータを統合することが可
能な新規な逆数計算方法を提案することを目的とする。

【課題を解決するための手段】

【０００７】さらに詳細には、本発明によれば、ａ）与えられた数Ｄを２進数に変換し且つ正規化し、ｂ）入力値Ｘ_j＝１／２＋（ｊ×２^-n）（ただし、ｊは
０から２^n-1−１までの整数）に対応する数Ｄのｎ個の
上位ビットに基づいて、数Ｄの逆数の第１の近似値Ｉ₀
を逆数表Ｔ１中で検索し、ｃ）値Ｄをその区間内に含む区間ｉｊ＝〔Ｘ_j，（Ｘ_j
＋ｉ）〕（但し、ｉ＝２^-n）での逆数偏差勾配Ｇ₀＝Δ
Ｉ₀／ｉを偏差表Ｔ２で検索し、ｄ）線形近似により、アルゴリズムＩ_l＝Ｉ₀＋（ｄ×
Ｇ₀）（但し、ｄ＝Ｄ−Ｘ_jで、Ｇ₀は代数値として入
力される）を用いて第２の値Ｉ_lを決定し、ｅ）基本区間ｉ_B＝〔Ｘ_jB，（Ｘ_jB＋ｉ）〕での偏差Ｅ
＝Ｉ−Ｉ₁を表す、符号付あるいは符号付でない、予め
設定した基本訂正値ＣＢｌをｄに基づいて訂正表Ｔ３で
検索し、ｆ）Ｘ_jに基づいてスケールファクタＨ_jをスケール表
Ｔ４で検索し、ｇ）訂正値Ｃ_jl＝ＣＢ_l×Ｈ_jを決定し、ｈ）第３の近似値Ｉ₂＝Ｉ₁＋Ｃ_jlを決定する各操作を含むことを特徴とする数Ｄの逆数Ｉを計算する
方法が提供される。

【０００８】従って、本発明の原理は、第１の値Ｉ
₀（これ自体は逆数表から得られる）に基づく線形近似
により得られた近似値Ｉ１に相補訂正を適用することで
ある。訂正値は、寸法を小さくした表に記憶された予め
設定したデータから得られる。このように、時間の前半
で、ニュートンの反復法を用いることなく、容易に集積
化可能な寸法の表から相当の精度（28ビット) の逆数を
得ることができる。

【０００９】本発明の方法の第１の変形例において、本
方法は、ｋ番目の反復が、アルゴリズム：ＩＮ_k＝ＩＮ_k-1×｛２−（Ｄ×ＩＮ_k-1）｝（ただし、ＩＮ₀＝Ｉ₂）により与えられるニュートン
の反復法を用いる演算を含む。

【００１０】本発明の別の変形例では、訂正表Ｔ３のエ
ントリは、Ｄのｎ個の最上位ビットの後に続くｍ個のビ
ットと、ｌ×２^-m-n≦ｄ＜（ｌ＋１）×２^-m-n（ただ
し、ｌは０〜２^m−１の整数である）場合、ＣＢ_l＝Ｉ
｛Ｘ_jb＋（ｌ×２^-m-n）｝−Ｉ₁｛Ｘ_jb＋（ｌ×
２^-m-n）｝とに基づいて行う。

【００１１】スケール表Ｔ４中のＨ_jが、式Ｈ_j＝（Ｘ
_jb／Ｘ_j）³により与えられる。２つの表Ｔ３およびＴ
４を設けることにより、その出力に値Ｃ_jlを直接与える
同等の訂正表と比較して、オペレータのサイズを実質的
に改善することが可能である。

【００１２】本発明の方法は、特に、ベクトルコンピュ
ータ等のデジタルコンピュータのプロセッサにおいて、
浮動小数点形式の変数を含む科学用電子計算機を実現す
るために適用することができる。

【００１３】本発明はまた、上記した方法を実施するた
めのデジタルコンピュータであって、そのプロセッサの
少なくとも１つに、数Ｄの２進数への変換し且つ正規化
するための手段と、数Ｄのｎ個の上位ビットに応じてア
ドレス指定され、出力Ｉ₀を与える逆数表Ｔ１と、数Ｄ
のｎ個の上位ビットに応じてアドレス指定され、出力Ｇ
₀を与える偏差勾配表Ｔ２と、乗数入力に数Ｄのｎ個の
上位ビットに続く少なくともｍ個のビットを受け、被乗
数入力にＧ₀を受けて、出力Ｓ１を与える第１乗算回路
Ｍ１と、数Ｄのｎ個の上位ビットに続くｍビットに応じ
てアドレス指定され、出力ＣＢ_lを与える訂正表Ｔ３
と、数Ｄのｎ個の上位ビットに応じてアドレス指定さ
れ、出力Ｈ_jを与えるスケール表Ｔ４と、入力にＣＢ_l
とＨ_jを受け、出力Ｃ_jlを与える第２乗算回路Ｍ２と、
Ｉ_o、Ｓ₁およびＣ_jlを受ける３つの入力を備え、出力
Ｉ２を与える加算手段（Ａ１、Ａ２）とを含むことを特
徴とするデジタルコンピュータに関する。

【００１４】本発明のコンピュータの望ましい変形例で
は、表Ｔ２、乗算回路Ｍ１および加算手段Ａ１、Ａ２
が、符号付オペランド上で動作することを特徴とする。
従って少なくともさらに１ビットの精度を得ることが可
能である。

【００１５】本発明のその他の利点および特徴は、添付
の図面を参照にして以下の非限定的な説明から明らかに
する。

【実施例】

【００１６】本発明は、精度が、コンピュータにより使
用されているフォーマットの寸法に制限される固定小数
点形式または浮動小数点形式で表された数の逆数の計算
に広く適用可能である。浮動小数点形式の数の場合に
は、本発明は、この数の仮数の逆数を計算するのに直接
適用可能である。

【００１７】例外なく乗算器を含む科学用電子計算機に
おいては、本発明に従う逆数の計算により、追加的な補
正を行うことなく除算を実施可能となることは明らかで
ある。

【００１８】全ての逆数計算は、固定小数点形式の数の
逆数、または（浮動小数点形式の場合の）仮数（２進数
に変換されて、基数２に正規化され（この場合最上位ビ
ット（ＭＳＢ）は１に等しい）、10進数での値が0.5 〜
１である）の逆数を計算することに関することに留意し
なければならない。実際、その他の演算はすべて、２の
羃による乗算もしくは除算、すなわち、シフト操作であ
る。２進数への変換、正規化およびシフトのための演算
は従来通りであるので、以下には詳しく説明しない。こ
れらの演算をデジタルコンピュータ中で実施するための
手段および回路についても同じである。従って、本発明
の方法において実施すべき最初の演算は、この演算が前
もって為されていない場合には、問題となる数の２進数
への変換ならびに正規化である。

【００１９】例として与えられ、本発明をなんら制限し
ない以下の説明では、逆数Ｉの計算所望する数Ｄが、２
進数に変換され正規化された浮動小数点形式の数の仮数
として選択される。特に、科学用電子計算機で使用され
る浮動小数点形式は32ビット（単精度の浮動小数点表
現）または64ビット（倍精度の浮動小数点表現）であ
り、それぞれ24および56ビットの仮数を有する。

【００２０】図１は、本発明の方法の機能を概略的に示
す図であり、各演算は、次の参照番号ａ）〜ｈ）で表さ
れる。ａ）Ｄの正規化、ｂ）〔ａ）に基づく〕Ｉ₀の決定、ｃ）〔ａ）に基づく〕Ｇ₀の決定、ｄ１）〔ａ）およびｃ）に基づく〕ｄ＝Ｄ−Ｘ_jとして
のｄ×Ｇ₀の計算、ｄ２）〔ｂ）およびｄ１）に基づく〕Ｉ₁＝Ｉ₀＋（ｄ
×Ｇ₀）の計算、ｅ）〔ａ）に基づく〕ＣＢ_lの決定、ｆ）〔ａ）に基づく〕Ｈ_jの決定、ｇ）〔ｅ）およびｆ）に基づく〕Ｃ_jl＝Ｈ_j×ＣＢ_lの
計算、ｈ）〔ｄ２）およびｈ）に基づく〕Ｉ₂＝Ｉ₁＋Ｃ_jlの
計算。

【００２１】さらに、本発明の方法の変形例において、
ニュートンの方法による反復の出発値ＩＮ₀として、Ｉ
₂を使用する。結果はＩＮ₂である。

【００２２】以下に、使用した各記号の定義、ならびに
各演算がどのようにして行われるかについての詳細を説
明する。しかし、図１に示した一連の演算は、近似値Ｉ
２が循環式の反復なしで得られ、グループｅ）、ｆ）お
よびｇ）などのいくつかの演算は、例えば、「パイプラ
イン」アーキテクチャとして知られる方法を利用して、
グループｂ）、ｃ）、ｄ１）およびｄ２）の演算と並行
して実施可能であることを示している。この機能構造
は、計算速度の観点から特に有利である。

【００２３】0.5 ≦Ｄ＜１のとき、Ｉ＝１／Ｄ（ただ
し、ＩおよびＤは、使用した浮動小数点形式により定義
される有限精度ｐの値である）を計算するものとする。
Ｄは２進数：Ｄ＝０．１ａ₂・・・ａ_pをしている。

【００２４】従って、Ｄの逆数は、２進数：Ｉ＝１／Ｄ＝１．ｂ₁・・・ｂ_p（１＜Ｉ≦２）、なら
びにＤ＝0.100 ・・・０の場合、Ｉ＝10.000・・・０をしている。

【００２５】この値は、図２に示した曲線Ｙ（Ｘ）＝１
／Ｘと関連つけられる。この曲線は、区間0.5 〜１で２
^n-1個のセグメントに分割され、各区間ｉｊ（寸法ｉ＝
２^-n）は、Ｄの逆数の第１近似値Ｉ₀を与える逆数表Ｔ
１の２^n-1個のエントリＸ_jの１つに対応する。図３
は、図２の区間ｉｊ＝〔Ｘ_j，Ｘ_j＋ｉ〕を拡大して示
す図である。尚、明瞭化のため、２つの線図で示した曲
線は意図的に変形してある。

【００２６】定義以下の記載では、次のように定義した様々な記号を用い
る。

【００２７】＊Ｘ_j 表Ｔ１のエントリ値は、式Ｘ_j＝ 0.5＋（ｊ×２^-n）（ただし、ｊは０から２^n-1−１の整数である）により
与えられる。Ｘｊの値は、Ｄの次に低い値が選択され
る。ただし、Ｘ_j≦Ｄ＜Ｘ'_j＝Ｘ_j＋１である。

【００２８】従って、Ｘ_jは、Ｄのｎ個の上位ビット
（ＭＳＢを含んでＭＳＢからｎ個の上位ビット）に対応
する。実際には、10進小数点の後の位２〜ｎ（正規化の
後の位１のビットは常に１に等しい）までの（ｎ−１）
ビットだけが表Ｔ１をアドレス指定するのに使用され
る。以下にさらに明らかにされる理由のために、表Ｔ１
の出力値Ｉｏは、ｎ＋ｍの精度で与えなければならず、
これに保護ビットの数ｇを加える。これら保護ビットｇ
は、中間の計算の過程で精度を維持するために用いられ
る。

【００２９】別段の記載がない限り、以後、Ｉ₀＝ｙ_j
＝１／Ｘ_jであるとする。

【００３０】＊ｄＩｌを計算するための線形近似に用いられるシフトｄ
は、式ｄ＝Ｄ−Ｘ_j（ただし、０≦ｄ＜ｉ）により与え
られる。

【００３１】変数ｄは、数Ｄのｎ個の最初の上位ビット
に続くｐ−ｎ個のビットにより２進数で表される。しか
し、Ｉ２の計算の最終精度がｐより小さく場合には、ｄ
の値はｍ＋ｇに切り捨てることができる（これにより、
ｄとして、丸められた値ｄ＝Ｄ−Ｘ_j−εを与える）。
次に、Ｉ２の計算に組み込まれない残りの下位ビットの
値は無視する。しかし、これらのビットは、使用した表
の寸法を考慮してＩ２について得られた精度が不充分で
あれば、Ｉを計算する（例えば、ニュートンのアルゴリ
ズムにより）のに使用する。このような状況は、倍精度
浮動小数点形式で逆数を計算するとき現れる。

【００３２】＊Ｇ₀ ｙ_jの２つの連続した値、即ちｙ_j＝１／Ｘ_jとｙ'_j＝
１／｛Ｘ_j＋１｝の間の偏差ΔＩ₀により、区間ｉｊ＝
〔Ｘ_j，Ｘ_j＋ｉ〕における逆数偏差勾配Ｇ₀＝ΔＩ₀
／ｉを計算することができる。この偏差勾配Ｇｏは、表
Ｔ１に使用されたものと同じエントリに基づき、精度ｎ
＋ｍ＋ｇで表Ｔ２により与えられる。

【００３３】＊Ｃ_jl 近似値Ｉ₂を得るためＩ₁に施すべき相補訂正Ｃ_jlの値
は、問題の区間ｉｊおよびｄに応じて異なる。これを行
うためには、各区間ｉｊを２^m個のセグメントに分割す
る。セグメント各々の寸法は２^-n-mである。従って、区
間ｉｊにおいて、Ｘ_jl＝Ｘ_j＋（ｌ×２^-n-m）（ただし
ｌは０〜２^m−１の整数である）の各々の値について曲
線Ｃ_j＝Ｄ_j(Ｘ) ＝Ｙ（Ｘ）を描くことが可能である。
この曲線は、区間ｉｊ＝〔Ｘ_j，Ｘ_j＋ｉ〕での逆数曲
線（Ｙ）Ｘと、弦Ｄｊ（Ｘ）（従って、直線Ｙ_jＹ'_j）
の間の偏差を表す。一度曲線Ｃ_jが得られると、ｄに関
連する訂正の値は、ｌ×２^-n-m≦ｄ＜（ｌ＋１）×２
^-n-mの場合、Ｃ_jl＝Ｃ_j（Ｘ_jl）により与えられる。

【００３４】変位ｄｌ＝Ｘ_jl−Ｘ_jは、数Ｄのｎ個の上
位ビットに続くｍ個のビット〔ただしｍ＜（ｐ−ｎ）〕
の内容により２進数で表される。

【００３５】図２は、0.5 〜１の間の様々な区間ｉｊ＝
〔Ｘ_j，Ｘ_j＋ｉ〕について一連の曲線Ｃ_jを示すもの
である。明らかに、Ｘ_jlの各値について、加えるべき訂
正値を即座に与える訂正表を提供することが理論的に考
えられる。しかし、このような表の物理的寸法（２
^n+m-1個のエントリ）は、寸法が２^-n-mの区間で構成さ
れた逆数表に対して、僅かな寸法上の利点しかないこと
を意味する。

【００３６】本発明の主な特徴の１つは、様々な曲線Ｃ
_j（放物線状をなす）の明らかな類似性の利点を利用し
て、問題のセグメントｉｊを示すスケールファクタＨ_j
による単純な乗算によって基本曲線ＣＢから全ての曲線
Ｃｊを導き出すことである。表Ｔ３およびＴ４の容量と
同等の直接訂正表の寸法は、表Ｔ３の寸法の２^n-1倍と
あるはずである。図２において、基本曲線ＣＢ＝Ｃ
_jbは、例えば左から３番目のセグメント、即ち、ｊｂ＝
２のときのｉＢから与えられる。曲線ＣＢは表Ｔ３中に
記憶され、そのエントリ（数２^m）は、Ｘ_jlのｍ個の下
位ビット（ＬＳＢを含んでＬＳＢからｍ個の下位ビッ
ト）によりアドレス指定され、その出力ＣＢ_lは、Ｉ₂
について必要な精度で与えられる。スケールファクタＨ
ｊ自体は別の表Ｔ４に記憶され、この表はＸ_j、即ち、
Ｄの最上位ビットに続くｎ−１個のビットからアドレス
指定することができる。

【００３７】アルゴリズムＩｏ→Ｉ１→Ｉ２の精度とＨ
ｊの計算：Ａ）ニュートンの反復法前述の定義を用いて、逆数Ｉは次のように表すことがで
きる。Ｉ＝１／Ｄ＝１／（Ｘ_j＋ｄ）＝（１／Ｘ_j）×｛１／（１＋ｄ／Ｘ_j）｝＝ｙ_j×１／（１＋ｄ・ｙ_j）（１）（ただし、ｄ・ｙ_j＜ｉ・ｙ_j＜２^-n×２≪１）

【００３８】限定された展開により、Ｉは式：Ｉ＝ｙ_j｛１−ｄ・ｙ_j＋ｄ²・ｙ_j ²−ｄ³・ｙ_j ³・・・｝（２）Ｉ＝ｙ_j｛１−(Ｄ−Ｘ_j)・ｙ_j＋ｄ²・ｙ_j ²−ｄ³・ｙ_j ³・・・｝（３）Ｉ＝ｙ_j(２−Ｄ・ｙ_j) ＋ｄ²・ｙ_j ³・(１−ｄ・ｙ_j＋ｄ²・ｙ_j ²・・・）（４）により表される。

【００３９】式４が、ＩＮ₀＝１／Ｘ_jとして、ニュー
トンの方法を用いた結果生じる誤差を示すことに留意す
べきである。最大誤差ＥＮは、式ｄ²・ｙ_j ³により与え
られ、 0.5から１の区間でのその最大値はｙ_j＝２およ
びｄ＝ｉにより与えられる。その結果、ＩＮ＜８ｉ²、
従って、ＩＮ＜２^-(n-3)となる。

【００４０】Ｂ．線形近似法（Ｉ₁の計算）Ｉ₀＝ｙ_j＝１／Ｘ_jからの線形近似によるＩ₁の計算
は、Ｉ₁＝ｙ_j＋｛(ｙ'_j−ｙ_j)×(ｄ／ｉ)｝＝Ｉ₀(Ｇ₀×ｄ) （５）のように表すことができる。

【００４１】この式では、Ｉ₀およびＧ₀は表Ｔ１およ
びＴ２により与えられ、ｎ＋ｍ＋ｇビットに切り捨てら
れ、丸められる。さらに、ｄ＝Ｄ−Ｘ_j−εの丸めた値
は、Ｄを左側のｎビット切り捨ててｍ＋ｇビットに丸め
ることにより得られる。Ｇ₀の最上位ビットはゼロであ
り、これによって表Ｔ２をある程度簡略化し、寸法縮小
することが可能になることに留意すべきである。

【００４２】また、ｙ'_jは、ｙ'_j＝１／(Ｘ_j＋ｉ）＝(１／Ｘ_j)・［１／｛１＋（ｉ／Ｘ_j)｝］＝ｙ_j・｛１／(１＋（ｉ・ｙ_j)｝（６）従って、限定された展開、ｉ・ｙ_j＜２^-(n-1)によりｙ'_j＝ｙ_j・(１−ｉ・ｙ_j＋ｉ²・ｙ_j ²−ｉ³・ｙ_j ³・・・）（７）のように表すことができる。

【００４３】次に、式（５）は、Ｉ₁＝ｙ_j｛１＋（ｄ／ｉ)・(Ｘ_j・ｙ'_j−１) ｝（８）と表すことができ、従って、式（７）を用いて、Ｉ₁＝ｙ_j｛１＋（ｄ／ｉ)・(−ｉ・ｙ_j＋ｉ²・ｙ_j ²・・・)｝（９）Ｉ₁＝ｙ_j｛１−ｄ・ｙ_j＋ｄ・ｉ・ｙ_j ²−ｄ・ｉ²ｙ_j ³＋・・・｝（10）のように表すことができる。

【００４４】線形近似方法の結果生じる誤差ＥＬは、ＥＬ＝（１／Ｄ）＝Ｉ₁ （ただし、１／ＤおよびＩ₁は、それぞれ式（２）およ
び（10）によって与えられる）、従って、ＥＬ＝ｙ_j・(１−ｄ・ｙ_j＋ｄ²・ｙ_j ²・・・） −(１−ｄ・ｙ_j＋ｄ・ｉ・ｙ_j ²・・・）ＥＬ＝ｙ_j ³・｛ｄ・(ｄ−ｉ)｝｛１−ｄ・ｙ_j＋ｄ²・ｙ_j ²・・・｝（11）（ただし、ｄ・ｙ_j＜２^-n×２≪１）により与えられる。

【００４５】ｄとの比較により、誤差ＥＬはｄ＝ｄ−ｉ
＝ｉ／２のとき最大である。従って、ＥＬ＜(ｉ²/４)・ｙ_j ³＜(８ｉ²)／４＝２^-(2n-1)＝ＥＬＭＡＸとなる。

【００４６】その結果、Ｉ₀の同じ精度について（Ｄの
ｎ個の最上位ビットにアドレス指定される逆数表）、線
形近似は、２ｎ−１個の有効ビットの精度を与え、これ
は、ニュートンの方法による最初の反復の精度より４倍
優れている。

【００４７】不確定性（区間ｉｊにおけるＥＬの最大
値）は、Ｘ＝0.5 （ｙ＝２）で最大で、Ｘ＝１（Ｙ＝
１）の近傍で最小である。ＥＬについて、図２は、Ｘの
関数として誤差変化曲線Ｃ_j（Ｉ₀＝ｙ_jに基づく）を
示し、誤差ＥＬは実際常に負である。

【００４８】Ｃ．相補訂正のための近似（Ｉ₂の計算）
式（11）は、ＥＬ＝ｙ_j ³・｛ｄ・(ｄ−ｉ)｝・｛１＋ｆ(ｄ・ｙ_j)｝（12）（ただし、ｆ(ｄ・ｙ_j)＝−ｄ・ｙ_j＋ｄ²・ｙ_j ²・・・・（13）のように表される。

【００４９】ｆ(ｄ・ｙ_j)≪１のとき、区間ｉｊにおい
てｄの関数としてＥＬを与える曲線Ｃ_j≒ｙ_j ³・ｄ・
(ｄ−ｉ)の比例係数が存在し、上述した訂正方法は正し
いことが証明される。また、表Ｔ３中のｄの関数（さら
に具体的には、各値ｄ₁の関数として）として基本訂正
値ＣＢ_l、ならびに表Ｔ４のＸ_jの関数としてスケール
係数Ｈ_jを保持することが可能である。

【００５０】基本曲線ＣＢを構成するために用いられる
基準区間において、ｉＢ＝Ｘ_jb〔ただし、Ｘ_jb＋ｉは２
^m個の小区間に分割される〕、ｄ₁を表すｄの値のｍ個
の上位ビット（即ち、Ｄのｎ個の上位ビットに続くｍ個
のビット）表Ｔ３をアドレス指定するのにように機能す
る。

【００５１】最終的な誤差は、区間 0.5から１に対する
近似値ｆ(ｄ・ｙ_j)＝ｃ^teによる誤差である。

【００５２】Ｈ_j＝Ｃ_j／Ｃ_jb ＝(ｙ_j ³／ｙ_jb ³)×｛ｄ・(ｄ−ｉ)｝／［｛ｄ・(ｄ−ｉ)｝×｛１＋ｆ_j(ｄ)｝／｛１＋ｆ_jb(ｄ)｝（14）（ただし、ｄ＝ｉ）と仮定する。

【００５３】Ｈ_jがｄとは無関係で、ｙ_jだけに応じて
変化するものとすると、ｆ_j(Ｄ)はｆ_jb(ｄ)にほぼ等し
くなければならない。このとき、式（13）は、１＋ｆ(ｄ)＝１−ｄ・ｙ＋ｄ²・ｙ²・・・＝１／（１＋ｄ・ｙ）（15）のように表されるので、Ｈ_j＝ (ｙ_j ³／ｙ_jb ³)×｛(１＋ｄ・ｙ_jb）／（１＋ｄ・ｙ_j)｝Ｈ_j＝Ｋ×（ｙ_j／ｙ_jb)³ （16）従って、Ｋ＝（１＋ｄ・ｙ_j)／（１＋ｄ・ｙ_jb）） ≒（１＋ｄ・ｙ_jb）×（１−ｙ_j) Ｋ≒１−｛ｄ・(ｙ_j−ｙ_jb)｝（17）（ただし、ｄの上限はｉに等しく、（ｙ_j−ｙ_jb）の上
限は１に等しく、訂正の計算用の単位に対してｄ・(ｙ_j
−ｙ_jb)の上限＝ｉ＝２^-nである。これはＥＬＭＡＸ＝
２^-(2n-1)との組合せで、比例係数Ｈ_jを適用すること
により得られるＩ₂について３ｎ−１ビットの精度を与
える。

【００５４】等式(16)から、Ｈ_j＝(ｙ_j／ｙ_jb)³＝(ｘ_jb
／ｘ_j)³ということができる。

【００５５】さらに、Ｃ（Ｘ_jl）に等しい近似一定値の
幅ｉ×２^-mのｄの周囲のサブセグメント全体について、
使用による別の誤差の原因がある。この結果生じた最大
誤差は、Ｃ０ 0.5;（0.5 ＋２^-m-n）の第１サブセグメ
ント（ｊ＝０およびｌ＝０）に対応し、Ｃ０（ 0.5＋２
^-m-n）＝８×２^-m-n×２^-n＝２^-(2n+m-3)に等しい。

【００５６】従って、表３の精度（２ｎ＋ｍ−３）が、
比例係数を用いて得られる精度（３ｎ−１）と少なくと
もほぼ同じ大きさであることが重要である。これはｍ≧
ｎ＋２について確認される。

【００５７】このように、相補訂正により、ｍをｎ＋２
以上に選択すると、ｎ個のビットの追加精度を得ること
が可能になる。

【００５８】例として、本発明の計算方法により、ニュ
ートンの反復法を使用することなく、ｎ＝８およびｍ＝
10の値で単精度浮動小数点形式の24ビットの仮数の逆数
を得ることが可能となる。この場合、Ｉｏは、ｎ＝８個
の有効ビットで表Ｔ１から得られ、Ｉ１は２ｎ−１＝15
個の有効ビットで得られ、Ｉ２は正規化に先立つ３ｎ−
１＝23個の有効ビットで得られ、従って、正規化後の24
番目のビットに１つの誤差が考えられる。

【００５９】以上までの説明において、Ｉ₀＝１／
Ｘ_j、即ち、問題の区間ｉｊの下限Ｘ_jに基づき、この
場合負の一定符号を持つ誤差を常に参照にしてきた。符
号付誤差と共に作動することにより、絶対値の半分最大
誤差を減らすことができる。従って、線形近似により、
Ｉ１について２ｎ個の有効ビットを得ることが可能にな
る。１つの符号ビットを適応させるため、表Ｔ２は若干
修正される。しかし、Ｔ２の要素Ｇ₀の最上位ビットは
構成によりゼロであることを考慮して、上記符号ビット
のためのスペースはＴ２に容易に見出される。

【００６０】寸法形状の観点から、弦Ｙ_jＹ'_jに対応す
る図３の直線Ｄ_j（Ｘ）は、｜ＥＭＡＸ_j｜／２に等しい
値だけ図面の鉛直方向に下方にＤＳ_j（Ｘ）中へと並進
移動させる。この場合、線形近似の出発値はＩｏ＝ＩＳ
ｏ（Ｘ_j）＝（１／Ｘ_j）−｜ＥＭＡＸ_j｜／２となる。

【００６１】同様に、様々な曲線Ｃ_jを鉛直方向の並進
運動により変形させ、図２に示した符号付曲線ＣＳ_jを
与える。このような構成では、曲線ＣＳ_jの中央軸は軸
ＯＸと一致する。この修正により、相補訂正後の１つ以
上の追加有効ビットをさらに得ることができる。再び与
えられた値を用いて、得られた結果は25個の有効ビット
であり、これらは単精度浮動小数点形式計算に使用する
ことができる。値ｎ＝９およびｍ＝11で、符号付訂正を
用いて、Ｉ₁が２ｎ＝18個の有効ビットで、またＩ₂が
３ｎ＋１＝28個の有効ビットで得られる。次にＩ₂の値
をニュートンの方法による反復の出発値ＩＮＯとして使
用する場合には、第１反復において、56個の有効ビット
を持つ結果ＩＮ１が得られ、これは倍精度浮動小数点形
式（56ビット仮数）中の数の逆数を計算するのに充分で
ある。

【００６２】本発明に従う逆数計算装置の実施例図４は、前述の方法を実施するための本発明に従う装置
の実施例を示す。このような装置は、通常の２進デジタ
ルコンピュータの処理ユニットあるいはプロセッサに組
み込まれている。図４に示されてはいないが、この装置
には、浮動小数点形式の数を処理する回路、ならびに固
定小数点形式の数を処理する回路の両方に使用すること
ができる通常の正規化回路が付属している。特に、基数
２の正規化回路は、数Ｄの第１最上位ビットとして逆数
（または仮数）が求められる数の第１ビット（その値は
１である）を位置付けるのに必要なシフトを実施し、指
数部の対応する修正を行う。逆数計算の最終的結果は、
後の使用のために適したフォーマット中で再び正規化し
てもよい。

【００６３】従って、この装置は、入力レジスタＲＤ
（12）を備え、入力レジスタは３つのフィールド：Ｄの
ｎ個の上位ビットを持つフィールドＸ_j、次のｍ個のビ
ットを持つフィールドＤＬ、ならびにｇ個の保護ビット
を持つフィールドＱに分割される。Ｂのフォーマットが
Ｉ₂のフォーマットより大きい場合には、Ｄの最下位ビ
ットはＩ２のために使用しないが、その代わり、最終回
のニュートン反復に使用する。

【００６４】本発明に従う装置は、ＶＬＳＩにより容易
に集積可能に設計される。特に、これはプログラム可能
な読取り専用メモリ（ＰＲＯＭｓ）の形態で作成される
四つの表Ｔ１〜Ｔ４を含む。特に、表Ｔ１（14）、Ｔ２
（16）およびＴ４（20）は、Ｄのｎ個の上位ビットを基
にしてアドレス指定される。実際には、これら表のエン
トリ数は、Ｘ_jの位２〜ｎの位置のビットだけを考慮に
入れて２^n-1に減らすことができる。

【００６５】その出力で逆数表Ｔ１は値Ｉｏを提供し、
その寸法は検索される最終精度に必要な寸法より大き
い。従って、表Ｔ１の寸法は((ｎ＋ｍ＋ｇ）×２^n-1)で
ある。

【００６６】偏差表Ｔ２は出力値Ｇｏを提供し、これは
符号付でも符号付でなくてもよく、線形近似を計算する
のに用いる。Ｇｏの寸法は、検索される精度に必要な寸
法より大きいので、表Ｔ２は理論寸法((ｎ＋ｍ＋ｇ）×
２^n-1)である。実際には、Ｔ２に入力された逆数偏差の
値は、Ｇｏのｎ個の上位ビットがゼロである、もしくは
符号を表すような値である。すなわち、Ｇｏが符号であ
るならば、符号に従って０または１となる符号を表す１
ビットの除く全ビットがゼロである。従って、構成によ
り、Ｔ２の寸法を縮小し、Ｄのフォーマットの特徴に合
わせて、Ｇｏの再フォーマット形成および再フレーム付
けが可能なＴ２の出力回路を提供することができる。

【００６７】その出力で、スケール表Ｔ４は寸法がほぼ
ｎ個のビットのスケール係数Ｈｊの値を提供し、上の記
載に従う最終精度を保証する（式（17）から引き出され
た結論を参照）。表Ｔ４は寸法（ｎ×２^n-1)である。

【００６８】訂正表Ｔ３（18）はフィールドＤＬのｍ個
のビットに基づいてアドレス指定され、従って２^m個の
エントリを備える。その出力で、表Ｔ３は、ｍがｎ＋２
以上に選択されたとき、寸法が約ｎビットの基本訂正係
数ＣＢｌの値を提供する。

【００６９】表の正確な寸法は、上に与えた基本値に基
づき、それぞれの応用例に応じて定義されるが、これら
の値は、保護ビットの数を減らすことに価値があると証
明される限り、シミュレーションによる最適化が可能で
あることに留意すべきである。いくつかの場合には、Ｒ
ＤのフィールドＱの保護ビットの数ｇは、出力Ｉｏ、Ｓ
₁およびＣ_jlについて選択されるものとは異なることも
ある（ここでは、保護ビットのビット数は便宜性からｇ
に等しく選択した）。

【００７０】さらに、本発明に従う装置は、２つの乗算
回路Ｍ１(22)およびＭ２(24)を備え、３つの入力Ｉ₀、
Ｓ₁およびＣ_jlと１つの出力を備える加算手段が、図４
に示したように配置される２つの加算回路Ａ１(26)およ
びＡ２(28)により構成される。しかし、本発明の範囲を
越えることなく、２つの加算器Ａ１およびＡ２の代わり
に、３つの入力を備える単一加算回路（図示せず）を使
用してもよい。

【００７１】乗算器Ｍ１は線形近似による値Ｉ₁の計算
に導入すべき訂正を計算するのに使用する。Ｍ１の２つ
のオペランドは、Ｔ２の出力値Ｇ₀と、最寄りのεへの
すなわちε以下の誤差をもった移動ｄ＝Ｄ−Ｘ_jを表す
Ｄの（ｍ＋ｇ）個の最下位ビットである。再び、Ｇ₀の
（ｍ＋ｇ）個の最下位ビットだけを用いて、乗算器の寸
法を((ｍ＋ｇ）×（ｍ＋ｇ))とすることもできる。この
乗算器は、乗算演算器の仮数のものであれば有利であ
る。乗算器Ｍ１の出力値Ｓ１は適切にフレーム付けさ
れ、ｎ＋ｍ＋ｇビットに切り捨てられた後、加算器Ａ１
の２つの入力の１つに与えられる。加算器Ａ１の他方の
入力は表Ｔ１により提供された値Ｉ₀を受ける。Ｇ
₀（およびＳ₁）が符号付の値で表される場合、加算器
Ａ１は加算器／減算器タイプを選択する。

【００７２】乗算器Ｍ２は訂正係数Ｃ_jlを計算するのに
使用される。上の説明に従い、この乗算器の寸法は小さ
い（ｎ×ｎ）。Ｍ２の２つのオペランドは、表４の出力
値Ｈ_j、ならびに表Ｔ３の出力値ＣＢｌにより構成され
る。表Ｔ３に記憶されている値が符号付でない場合に
は、同じことが乗算器Ｍ２の出力値Ｃ_jlにも言える。こ
の出力値Ｃ_jlは、加算器Ａ２に適切にロードできるよう
に、切り捨てられ、ｎ＋ｍ＋ｇにフレーム付けされる。
その結果、加算器Ａ２のオペランドはＣ_jlおよびＩ₁で
あり、後者は乗算器Ｍ１から送られる。符号付された、
あるいは場合によって符号付されていない加算器Ａ２
は、最大３ｎ−１有効ビット（あるいは、符号付された
近似値を計算する場合には最大３ｎ＋１有効ビット）を
持つｎ＋ｍ＋ｇビットのフォーマット中で、値Ｉ₂をそ
の出力に送る。

【００７３】最後に、装置は、Ｉ２に基づき少なくとも
１つのニュトン反復を実施するためのハードウエア手段
を含む。この反復は、特定回路の数を減らすためのプロ
グラミングにより行うことができる。この場合、コンピ
ュータの特殊性に応じて異なる基数（例えば、基数16）
への正規化操作がＡ２の出力でＩ２の値について行われ
る。他方で、この操作は、ニュートン反復が特殊なマイ
クロプログラム回路により為された場合（図１に示す場
合のように）には必要ではない。

【００７４】以上の説明から、単精度浮動小数点形式の
仮数の逆数は、ニュートンの方法（これは乗算器の大寸
法の補助セットを必要とする）を使用することなく、小
寸法の追加表（Ｔ３およびＴ４）を加えるだけで計算す
ることができる。さらに、主要乗算器Ｍ１が、ウォレス
(Wallace) の木として知られる構造に配置された加算器
を備える場合には、加算器Ａ１およびＡ２はこの構造に
容易に集積することができる。最後に、２つの乗算器Ｍ
１およびＭ２は独立して、しかも同時に作動することに
留意されたい。これは、分割操作が行われる速度のため
に科学用電子計算機では重要な事項である。

【図面の簡単な説明】

【図１】本発明の方法の機能を概略的に説明するための
図である。

【図２】区間〔0.5;１〕の曲線Ｙ（Ｘ）＝１／Ｘ、Ｃｊ
およびＣＳｊを概略的に示す図である。

【図３】区間ｉｊ＝〔Ｘｊ，((Ｘｊ）＋ｉ）〕での図１
の曲線Ｙ（Ｘ）およびＣｊを拡大して概略的に示す図で
ある。

【図４】デジタルコンピュータで本発明の方法を実施す
るための装置を概略的に示す図である。

【符号の説明】

12 入力レジスタ 14 逆数表Ｔ１ 16 偏差表Ｔ２ 18 訂正表Ｔ３ 20 スケール表Ｔ４ 22 乗算回路Ｍ１ 24 乗算回路Ｍ２ 26 加算回路Ａ１ 28 加算回路Ａ２

Claims

【特許請求の範囲】

【請求項１】ａ）与えられた数Ｄを２進数に変換し且つ正規化し、ｂ）入力値Ｘ_j＝１／２＋（ｊ×２^-n）（ただし、ｊは
０から２^n-1−１までの整数）に対応する数Ｄのｎ個の
上位ビットに基づいて、数Ｄの逆数の第１の近似値Ｉｏ
を逆数表Ｔ１中で検索し、ｃ）値Ｄをその区間内に含む区間ｉｊ＝〔Ｘ_j，Ｘ_j＋
ｉ〕（但しｉ＝２^-n）での逆数偏差勾配Ｇ_O＝ΔＩ_O／ｉ
を偏差表Ｔ２で検索し、ｄ）線形近似により、アルゴリズムＩ₁＝Ｉ₀＋（ｄ×
Ｇ₀）（但し、ｄ＝Ｄ−Ｘ_jで、Ｇ₀は代数値として入
力される）を用いて第２の値Ｉ₁を決定し、ｅ）基本区間ｉ_B＝〔Ｘ_jB，Ｘ_jB＋ｉ〕での偏差Ｅ＝Ｉ
−Ｉ₁を表す、符号付あるいは符号付でない、予め設定
した基本訂正値ＣＢ_lをｄに基づいて訂正表Ｔ３で検索
し、ｆ）Ｘ_jに基づいてスケールファクタＨ_jをスケール表
Ｔ４で検索し、ｇ）訂正値Ｃ_jl＝ＣＢ_l×Ｈ_jを決定し、ｈ）第３の近似値Ｉ₂＝Ｉ₁＋Ｃ_jlを決定する各操作を
含むことを特徴とする数Ｄの逆数Ｉを計算する方法。
【請求項２】ｋ番目の反復が、アルゴリズム：ＩＮ_k＝（ＩＮ_k-1−１）×｛２−（Ｄ×ＩＮ_k-1）｝（ただし、ＩＮ₀＝Ｉ₂）により与えられるニュートン
の反復法を用いる演算を含むことを特徴とする請求項１
記載の方法。
【請求項３】逆数偏差勾配Ｇｏが負で、式：Ｇ₀＝｛Ｉ₀ (Ｘ_j＋ｉ）−Ｉ₀ (Ｘ_j) ｝／ｉにより与えられることを特徴とする請求項１および２の
いずれか１項に記載の製造方法。
【請求項４】Ｉ₀が、式：Ｉ₀＝ｙ_j＝１／Ｘ_jにより
与えられることを特徴とする請求項１〜３のいずれか１
項に記載の方法。
【請求項５】Ｉ₀が、式：ＩＳ₀（Ｘ_j）＝（１／
Ｘ_j）−（ＥＭＡＸ_j／２）（ただし、ＥＭＡＸ_jは、曲線Ｙ（Ｘ）＝１／Ｘと、区
間ｉｊ＝〔Ｘ_j，Ｘ_j＋１〕での曲線Ｙ（Ｘ）の弦Ｄ_j
（Ｘ）との間の最大偏差の絶対値を表す）により与えら
れることを特徴とする請求項１〜３のいずれか１項に記
載の方法。
【請求項６】上記訂正表Ｔ３のエントリが、数Ｄのｎ個
の上位ビットに続くｍ個のビットに基づいて行われ、
（ｌ×２^-m-n）≦ｄ＜（ｌ＋１）×２^-m-n（ただし、ｌ
は０〜２^m−１の整数である）の場合、ＣＢ_l＝Ｉ｛Ｘ
_jb＋（ｌ×２^-m-n）｝−Ｉ_l｛Ｘ_jb＋（ｌ×２^-m-n）｝
であることを特徴とする請求項１〜５のいずれか１項に
記載の方法。
【請求項７】Ｈ_jが、式：Ｈ_j＝（Ｘ_jb／Ｘ_j)³により
与えられることを特徴とする請求項１〜６のいずれか１
項に記載の方法。
【請求項８】ｎおよびｍの値が、近似値Ｉ₂におけるＮ
個の有効ビット（例えば、Ｎ＝32）を有する数の逆数を
計算するために選択されることを特徴とする請求項１〜
７のいずれか１項に記載の方法。
【請求項９】ｎおよびｍの値が、単一のニュートン法で
の反復ＩＮ₁でのＮ’個の有効ビット（例えば、Ｎ＝6
4）を有するで数の逆数を計算するために選択されるこ
とを特徴とする請求項２〜７のいずれか１項に記載の方
法。
【請求項10】符号付き浮動小数点形式の数の仮数の逆数
を計算するために使用されることを特徴とする請求項１
〜９のいずれか１項に記載の方法。
【請求項11】請求項１〜10のいずれか１項に記載の方法
を実施するためのデジタルコンピュータであって、その
プロセッサの少なくとも１つに、数Ｄの２進数への変換し且つ正規化するための手段と、数Ｄのｎ個の上位ビットに応じてアドレス指定され、出
力Ｉ₀を与える逆数表Ｔ１と、数Ｄのｎ個の上位ビットに応じてアドレス指定され、出
力Ｇ₀を与える偏差勾配表Ｔ２と、乗数入力に数Ｄのｎ個の上位ビットに続く少なくともｍ
個のビットを受け、被乗数入力にＧ₀を受けて、出力Ｓ
₁を与える第１乗算回路Ｍ１と、数Ｄのｎ個の上位ビットに続くｍビットに応じてアドレ
ス指定され、出力ＣＢ_lを与える訂正表Ｔ３と、数Ｄのｎ個の上位ビットに応じてアドレス指定され、出
力Ｈ_jを与えるスケール表Ｔ４と、入力にＣＢ_lとＨ_jを受け、出力Ｃ_jlを与える第２乗算
回路Ｍ２と、Ｉ₀、Ｓ₁およびＣ_jlを受ける３つの入力を備え、出力
Ｉ₂を与える加算手段（Ａ１、Ａ２）とを含むことを特
徴とするデジタルコンピュータ。
【請求項12】値Ｉ₂に基づいて、ニュートン法によりプ
ログラムされた反復処理を実施するためのハードウエア
およびソフトウエアを含むことを特徴とする請求項11記
載のコンピュータ。
【請求項13】上記表Ｔ２、乗算器Ｍ１および加算手段Ａ
１、Ａ２が符号付オペランドで動作することを特徴とす
る請求項１〜12のいずれか１項に記載のコンピュータ。
【請求項14】寸法Ｉ₀、Ｇ₀、Ｓ₁、Ｉ₁およびＩ
₂が、ｎ＋ｍ＋ｇ（ただしｇ≧０）に等しいことを特徴
とする請求項11〜13のいずれか１項に記載のコンピュー
タ。
【請求項15】上記表Ｔ３が、２^m（ただし、ｍ≧ｎ＋
２）個のエントリを含むことを特徴とする請求項11〜13
のいずれか１項に記載のコンピュータ。