(57)【要約】【課題】被除数が固定値で除数が等差数列と見なすことができる時の除算に於ける演算回数を少なくする。【解決手段】演算装置は、等差数列と見なせる数列Ｙの一つの要素である除数Ｙｉ（ｉは１以上の整数）に対して、商Ｘ／Ｙｉを生成し、商Ｘ／Ｙｉの近似値Ｚｉを生成する。演算装置は、商Ｘ／Ｙｊと商Ｘ／Ｙｋ（ｋ＜ｊ＜ｉ）を含む少なくとも２つの商が生成された場合は、該少なくとも２つの商を用いて近似値Ｚｉを生成し、該近似値Ｚｉを入力とする乗算型除算を行って商Ｘ／Ｙｉを生成する。【選択図】図１
2015197814.tif 000002
【特許請求の範囲】
【請求項１】
演算装置であって、
等差数列と見なせる数列Ｙの一つの要素である除数Ｙｉ（ｉは１以上の整数）に対して、商Ｘ／Ｙｉを生成する商生成手段と、
前記商Ｘ／Ｙｉの近似値Ｚｉを生成する商近似値生成手段と、を有し、
前記商近似値生成手段は、前記商生成手段により商Ｘ／Ｙｊと商Ｘ／Ｙｋ（ｋ＜ｊ＜ｉ）を含む少なくとも２つの商が生成された場合は、該少なくとも２つの前記商を用いて前記近似値Ｚｉを生成し、
前記商生成手段は、前記近似値Ｚｉを入力とする乗算型除算を行って前記商Ｘ／Ｙｉを生成することを特徴とする演算装置。
【請求項２】
前記商近似値生成手段は、少なくとも前記２つの商を用いて、
Ｚｉ＝（Ｘ／Ｙｊ）＋（（Ｘ／Ｙｊ）−（Ｘ／Ｙｋ））×（（ｉ−ｊ）／（ｊ−ｋ））
により前記近似値Ｚｉを算出することを特徴とする請求項１に記載の演算装置。
【請求項３】
前記商近似値生成手段の演算処理と商生成手段の演算処理と合計のレイテンシをｔ（ｔは２以上の整数）とし、ｊ＝ｉ−ｔ、ｋ＝ｊ−１のとき、
前記商近似値生成手段は、
Ｚｉ＝（Ｘ／Ｙｊ）＋ｔ×（（Ｘ／Ｙｊ）−（Ｘ／Ｙｋ））））
により前記近似値Ｚｉを算出することを特徴とする請求項１又は２に記載の演算装置。
【請求項４】
前記商近似値生成手段は、前記商生成手段により少なくとも２つの前記商が生成されていない場合は、少なくとも１つの所定の初期値を用いて前記近似値Ｚｉを生成することを特徴とする請求項１乃至３のいずれか１項に記載の演算装置。
【請求項５】
前記商近似値生成手段は、前記所定の初期値として商Ｘ／Ｙ１と商Ｘ／Ｙ２の近似値を用いて前記近似値Ｚｉを生成することを特徴とする請求項４に記載の演算装置。
【請求項６】
前記商近似値生成手段は、
前記商生成手段が生成した商を記憶する記憶手段と
前記記憶手段により記憶された商を用いて前記近似値Ｚｉを計算する近似値計算手段とを有することを特徴とする請求項１乃至５のいずれか１項に記載の演算装置。
【請求項７】
前記商生成手段は、前記近似値Ｚｉが所望の精度を満たすように、繰り返し処理を行うことを特徴とする請求項１乃至６のいずれか１項に記載の演算装置。
【請求項８】
Ｘは１であることを特徴とする請求項１乃至７のいずれか１項に記載の演算装置。
【請求項９】
演算方法であって、
等差数列と見なせる数列Ｙの一つの要素である除数Ｙｉ（ｉは１以上の整数）に対して、商Ｘ／Ｙｉを生成する商生成工程と、
前記商Ｘ／Ｙｉの近似値Ｚｉを生成する商近似値生成工程と、を有し、
前記商近似値生成工程では、前記商生成工程において商Ｘ／Ｙｊと商Ｘ／Ｙｋ（ｋ＜ｊ＜ｉ）を含む少なくとも２つの商が生成された場合は、該少なくとも２つの前記商を用いて前記近似値Ｚｉを生成し、
前記商生成工程では、前記近似値Ｚｉを入力とする乗算型除算を行って前記商Ｘ／Ｙｉを生成することを特徴とする演算方法。
【請求項１０】
請求項１乃至請求項８のいずれか１項に記載の演算装置としてコンピュータを機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、乗算型除算を用いた演算装置、演算方法、及びプログラムに関する。特に、被除数が固定値で除数が等差数列である除算、もしくは、近似的に被除数が固定値で除数が等差数列と見なすことができる時の除算を行う演算装置、演算方法、及びプログラムに関する。
【背景技術】
【０００２】
除算をソフトウェア、あるいはハードウェアで実現する方式として、減算シフト型除算、乗算型除算、表と演算を組み合わせる除算などが知られている（非特許文献１等）。
【０００３】
減算シフト型除算は、人が筆算で除算を行う場合と同様、減算とシフトの繰り返しにより除算を行う方法である。被除数をＸ、除数をＹとして、商Ｚを小数点以下ｎビット目まで求める時、減算シフト型除算は減算とシフトの回数がｎに比例する。基数を２とする減算シフト型除算では、商を１ビット求める毎に減算とシフトを行う。減算とシフト回数を減らす為に、ＳＲＴ法などでは高次基数が用いられる。しかしながら、基数を大きくすると商の選択が複雑になってしまうため、実用となる基数は２、４、８、１６程度になる。従って、３２ビット精度の除算を行う場合、基数２であれば商の選択は簡単であるが、３２回の減算とシフトが必要になり、基数１６であれば８回の商の選択と減算とシフトが必要になる。
【０００４】
乗算型除算は、乗算の繰り返しにより除算を行うもので、代表的な方法にＮｅｗｔｏｎ−Ｒａｐｈｓｏｎ法、Ｇｏｌｄｓｃｈｍｉｄｔ法がある。Ｎｅｗｔｏｎ−Ｒａｐｈｓｏｎ法は、１／Ｙの近似値をＵ０から始め、Ｕｉ＋１＝Ｕｉ×（２−Ｕｉ×Ｙ）の繰り返しにより１／Ｙを求める。Ｕｉ＋１を算出する際に乗算を２回行い、Ｕｉ＋１の精度（有効桁数）はＵｉの２倍になる。必要な精度の１／Ｙ（＝Ｕｉ）を求めた後、Ｘを乗じることでＸ／Ｙを求める。Ｇｏｌｄｓｃｈｍｉｄｔ法も、Ｕｉ＋１の計算式は異なるが、Ｎｅｗｔｏｎ−Ｒａｐｈｓｏｎ法と同じくＵｉ＋１を算出する際に乗算を２回行い、Ｕｉ＋１の精度（有効桁数）はＵｉの２倍になる。これらの乗算型除算は、１／Ｙの近似値の精度がｍビットの時、およそｃｅｉｌ（ｌｏｇ２（ｎ／ｍ））回の繰り返しが必要である（ｃｅｉｌ（ｘ）は天井関数であり、実数 x に対して x 以上の最小の整数を返す）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】高木直史“算術演算回路のアルゴリズム−３．除算回路のアルゴリズム”，情報処理，Ｖｏｌ．３７，Ｎｏ．３，ｐｐ．２８０−２８６（１９９６年３月）．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところで、画像に対する射影変換を以下の様に行ったとき、１画素毎に１／ｚｏ０の除算が必要になる。除算回数は画素数と同じであるため、画素数が多いときには除算回数も多くなってしまう。
ｆｏｒ（ｙｉ＝０；ｙｉ＜ｙｉｍａｘ；ｙｉ＋＋）｛
ｆｏｒ（ｘｉ＝０；ｘｉ＜ｘｉｍａｘ；ｘｉ＋＋）｛
ｘｏ０＝ｍ１１×ｘｉ＋ｍ１２×ｙｉ＋ｍ１３；
ｙｏ０＝ｍ２１×ｘｉ＋ｍ２２×ｙｉ＋ｍ２３；
ｚｏ０＝ｍ３１×ｘｉ＋ｍ３２×ｙｉ＋ｍ３３；
ｘｏ＝ｘｏ０×（１／ｚｏ０）；
ｙｏ＝ｙｏ０×（１／ｚｏ０）；
｝
｝
【０００７】
１／ｚｏ０の演算で例えば３２ビット精度が必要である時、先に示した減算シフト型除算では、基数２であれば商の選択は簡単であるが３２回の減算とシフトが必要になり、基数１６であれば８回の商の選択と減算とシフトが必要になる。どちらにしても演算回数が多い。一方、乗算型除算では、１／ｚｏ０の近似値の精度（有効桁数）が１６ビットで求めることができれば２回の乗算で結果を求めることができる。しかし、近似値を高い精度で求める必要があるため、近似値の算出の演算量、もしくはテーブルサイズが大きくなってしまう。乗算型除算で２回の繰り返しを行う時は、必要になる１／ｚｏ０の近似値の精度（有効桁数）を８ビットにすることができるが、繰り返しでの乗算が４回に増えてしまう。射影変換の最内ループはＺｏ０＝ｍ３１×ｘｉ＋Ｚｃ（Ｚｃは定数）であり、１／Ｚｏ０において、被除数が固定値、除数が等差数列になる。しかしながら、被除数が固定値、除数が等差数列とする除算で演算回数が少ないものはこれまで開示されていない。
【０００８】
本発明は上記課題を鑑みてなされたものであり、被除数が固定値で除数が等差数列と見なすことができる時の除算に於ける演算回数を少なくすることを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するための一手段として、本発明の演算装置は以下の構成を有する。すなわち、演算装置であって、等差数列と見なせる数列Ｙの一つの要素である除数Ｙｉ（ｉは１以上の整数）に対して、商Ｘ／Ｙｉを生成する商生成手段と、前記商Ｘ／Ｙｉの近似値Ｚｉを生成する商近似値生成手段と、を有し、前記商近似値生成手段は、前記商生成手段により商Ｘ／Ｙｊと商Ｘ／Ｙｋ（ｋ＜ｊ＜ｉ）を含む少なくとも２つの商が生成された場合は、該少なくとも２つの前記商を用いて前記近似値Ｚｉを生成し、前記商生成手段は、前記近似値Ｚｉを入力とする乗算型除算を行って前記商Ｘ／Ｙｉを生成することを特徴とする。
【発明の効果】
【００１０】
本発明では、被除数が固定値で等差数列を除数とする除算に於ける演算回数を少なくすることが可能となる。
【図面の簡単な説明】
【００１１】
【図１】実施形態に於ける除算装置全体の構成例を表す図。
【図２】実施形態に於ける商算出部の構成例を表す図。
【図３】実施形態に於ける処理をコンピュータに実行させるためのプログラムのフローチャート。
【発明を実施するための形態】
【００１２】
［第１実施形態］
第１実施形態として、１／Ｙｉの除算における商の近似値を求める際、過去に計算された２つの除算結果から１次式を用いて現在の被除数における商の近似値を算出する実施形態を説明する。しかし、商の近似値を算出する際に、近似精度を高めたり、計算量を削減するために用いる式を２次以上にしたり、区間分割を行い区間毎に異なる式を適用したり、非線形演算を行うことも、本実施形態から容易に変更することができる。また、本実施形態では直近の２つの除算結果を用いて商の近似値を算出しているが、３つ以上の除算結果を用いることで近似精度を高めることも、本実施形態から容易に変更することができる。また、本実施形態では、入力される除数は等差数列Ｙの要素であるＹｉで、被除数Ｘは一定である場合の例を説明する。
【００１３】
商の近似値を過去に計算された除算結果から十分な精度で求めることが可能であるならば、除数は必ずしも等差数列である必要はない。例えば、除数が等差数列からは微少な誤差を含む時でも等差数列とみなして本実施形態を適用することが可能である。また、他の形態としては、等差数列であれば連続する二つの除数Ｙｉ，Ｙｉ＋１に対して、Ｙｉ＋１−Ｙｉ＝ｋ（一定）であるが、Ｙｉ＋１−Ｙｉ＝ｋ×ｒｉ（ｋは一定、ｒｉはｉ毎に異なる整数）である場合も、本実施形態から容易に変更することが可能である。
【００１４】
また、本実施形態では、除算として商Ｘ／Ｙｉではなく商１／Ｙｉの計算を行う例を説明する。しかし、Ｘ／Ｙｉを計算する際にも本実施形態を適用することが可能である。例えば、後にＸを乗ずる方式や、乗算型除算でＸ／Ｙｉを計算する方式にも本実施形態を適用することが可能である。
【００１５】
図１に、本実施形態に於ける除算装置全体の構成例を示す。図１に示す除算装置は、商近似値生成部１０１と商生成部１０２からなる。商生成部１０２は除数Ｙｉ１２５と商の近似値Ｚｉ１２１を入力として、必要な精度の商を求め、商１／Ｙｉ１２２を出力する。本実施形態では、商生成部１０２の処理として、Ｎｅｗｔｏｎ−Ｒａｐｈｓｏｎ法を用いた以下の式によって１回の繰り返しを行う方法を例に挙げる。
１／Ｙｉ＝Ｚｉ×（２−Ｚｉ×Ｙｉ）
この演算により、商の精度（有効桁数）は入力された商の近似値Ｚｉの精度の２倍になる。従って、商近似値生成部１０１が出力する商の近似値Ｚｉ１２１は、商１／Ｙｉ１２２で必要な有効桁数の１／２の有効桁数であればよい。
【００１６】
なお、本実施形態では、Ｎｅｗｔｏｎ−Ｒａｐｈｓｏｎ法を用いて繰り返しは１回のみの例を示すが、近似値を入力として精度を高める除算方法であれば、Ｇｏｌｄｓｃｍｉｄｔ法などの他の演算方法も用いることができる。また、精度を高めるための演算の繰り返し回数は任意である。ハードウェアであれば、演算をマルチサイクルで実現することも、１サイクル毎に異なる演算が可能なパイプライン方式で実現することもできる。
【００１７】
図２に、本実施形態に於ける商近似値生成部１０１の構成例を示す。図２に示す商近似値生成部１０１は、商１の近似値出力部１１３と商２の近似値出力部１１４と商記憶部１１１と商近似値計算部１１２からなる。
【００１８】
商記憶部１１１は、商生成部１０２が出力する商１／Ｙｉ１２２を記憶する。ここでは、商記憶部１１１は２つの記憶をもち、商１／Ｙｊ１２３と商１／Ｙｋ１２４とを保持して出力している（ｊ＝ｉ−１、ｋ＝ｉ−２）。商生成部１０２が新しい商を出力すると、保持している商をそれぞれシフトして、１／Ｙｋには以前の１／Ｙｊ、１／Ｙｊには新しい商１／Ｙｉを記憶する。
【００１９】
商近似値計算部１１２は、商生成部１０２が出力した過去の除算結果を用いて、商１／Ｙｉ（Ｙｉは等差数列）の近似値である、商の近似値Ｚｉ１２１を算出して出力する（ｉは１以上の整数）。本実施形態では、１／Ｙｊ１２３と１／Ｙｋ１２４（但しｊ＝ｉ−１、ｋ＝ｉ−２）を入力として以下に示す一次式で算出する。
Ｚｉ＝（１／Ｙｉ−１）＋（（１／Ｙｉ−１）−（１／Ｙｉ−２））
＝（１／Ｙｊ）＋（（１／Ｙｊ）−（１／Ｙｋ））  但し、ｊ＝ｉ−１、ｋ＝ｉ−２
【００２０】
なお、商１／Ｙｉを求める際、商記憶部１１１に過去の除算結果が記憶されていない時には商の近似値Ｚｉの予測ができない。商記憶部１１１に過去の除算結果が記憶されていない時は、上記の式の場合では、ｉ＝１とｉ＝２の場合が該当する。この場合に商近似値計算部１１２が商の近似値Ｚｉ１２１を出力するため、所定の初期値として、商１の近似値出力部１１３と商２の近似値出力部１１４は、それぞれＹ１に対する商１（商１／Ｙ１）の近似値Ｚ１１２６とＹ２に対する商２（商１／Ｙ２）の近似値Ｚ２１２７を出力する。商近似値計算部１１２はｉ＝１とｉ＝２に対しては、上記の一次式ではなく、商１の近似値Ｚ１１２６、商２の近似値Ｚ２１２７を出力する。なお、商１の近似値Ｚ１１２６、商２の近似値Ｚ２１２７は、メモリ等に格納された予め決められた値や、除数Ｙｉ１２５に基づいて決められた値であってもよい。
【００２１】
［第２実施形態］
第１実施形態では、商近似値生成部１０１の演算処理と商生成部１０２の演算処理との合計のレイテンシが１である場合の実施形態を説明した。次に、第２実施形態として、商近似値生成部１０１と商生成部１０２との合計のレイテンシが２以上になる時の実施形態を示す。
【００２２】
商近似値生成部１０１と商生成部１０２とを実装する際、パイプライン方式のハードウェアで実装したり、ソフトウェアで実装する場合でも使用するプロセッサの演算処理のレイテンシが大きい場合には、合計のレイテンシが２以上になる。この様な場合、商近似値計算部１１２で使用可能な過去の除算結果は、レイテンシをｔとした時、Ｙｉ−ｔとなる。商記憶部１１１は、Ｙｉ−ｔとこれより前の演算結果Ｙｉ−ｔ−１とを記憶して出力する。商近似値計算部１１２ではこれらの過去の除算結果を用いて、以下の算出式で商の近似値Ｚｉ１２１を算出して出力する。
Ｚｉ＝（１／Ｙｉ−ｔ）＋ｔ・（（１／Ｙｉ−ｔ）−（１／Ｙｉ−ｔ−１））
＝（１／Ｙｊ）＋ｔ×（（１／Ｙｊ）−（１／Ｙｋ））  但しｊ＝ｉ−ｔ、ｋ＝ｉ−ｔ−１
【００２３】
第１実施形態の場合と同様に、商近似値計算部１１２は、商記憶部１１１に過去の除算結果が記憶されていない場合には上記の式を用いて商の近似値Ｚｉの予測することができない。すなわち、商近似値生成部１０１と商生成部１０２とのレイテンシの合計がｔ（ｔは２以上の整数）であるならば、１／Ｙｉ（ｉは１以上の整数）の近似値Ｚｉを求める際、ｉ＝１からｉ＝ｔまでは別の方法で算出する必要がある。例えば、商１の近似値出力部１１３と商２の近似値出力部１１４が出力する商１の近似値Ｚ１１２６と商２の近似値Ｚ２１２７とを用いて、以下の式で求めることができる。
Ｚｉ＝Ｚ２＋（ｉ−２）×（Ｚ２−Ｚ１）
【００２４】
［第３実施形態］
次に、第３実施形態として、さらに商近似値計算部１１２で任意の２つの過去の除算結果から商の近似値を算出する実施形態を示す。商近似値計算部１１２は、過去の除算結果である１／Ｙｊと１／Ｙｋから、１／Ｙｉの近似値Ｚｉを算出するものとする（ｉ＞ｊ＞ｋ）。商記憶部１１１は、１／Ｙｊと１／Ｙｋを記憶して出力する。商近似値計算部１１２ではこれらの過去の除算結果を用いて、以下の算出式で商の近似値Ｚｉ１２１を算出して出力する
Ｚｉ＝（１／Ｙｊ）＋（１／Ｙｊ−１／Ｙｋ）×（（ｉ−ｊ）／（ｊ−ｋ））
【００２５】
［第４実施形態］
次に、第４実施形態として、商記憶部１１１に過去の除算結果が記憶されていない場合に、商１の近似値出力部１１３の出力と商２の近似値出力部１１４の出力を用いない実施形態を説明する。商近似値生成部１０１と商生成部１０２との合計のレイテンシがｔで、１／Ｙｉ（ｉは１以上の整数）の近似値Ｚｉを求める際、商近似値計算部１１２はｉ＞ｔの時は過去の除算結果を用いて近似値Ｚｉをｍ桁以上の精度で出力する。ｉ≦ｔの時は過去の除算結果を用いないが、近似値Ｚｉの精度がｍ桁未満であるとする。この場合、商生成部１０２でｉ＞ｔの時よりも繰り返し回数を増やすようにする。例えば、ｉ≦ｔの時はＺｉの精度がｍ／２桁以上ｍ桁未満ならば繰り返し回数を１回増やせばよい。ｉ＞ｔの時の繰り返し回数が１回で十分な精度の出力が求められるのであれば、所望の精度を満たすために、繰り返し回数を以下の式のように２回行うようにする。
Ｕｉ＝Ｚｉ×（２−Ｚｉ×Ｙｉ）
１／Ｙｉ＝Ｕｉ×（２−Ｕｉ×Ｙｉ）
【００２６】
［第５実施形態］
第５実施形態として、１／Ｙｉの除算における商の近似値を求める際、過去に計算された２つの除算結果から１次式を用いて現在の被除数における商の近似値をプログラムにより算出する実施形態を説明する。
【００２７】
図３に本実施形態を説明する除算のフローチャートを示す。Ｓ３０１の商近似値生成は、ステップＳ３０３の商記憶で保持されている過去の除算結果を用いて等差数列となるＹｉ（ｉは１以上の整数）に対して１／Ｙｉの近似値である、商の近似値Ｚｉ１２１を算出して出力する。本実施形態では、Ｓ３０１の商近似値生成は、１／Ｙｊ１２３と１／Ｙｋ１２４（但しｊ＝ｉ−１，ｋ＝ｉ−２）を入力として以下に示す一次式で算出を行う。
Ｚｉ＝（１／Ｙｉ−１）＋（（１／Ｙｉ−１）−（１／Ｙｉ−２））
＝（１／Ｙｊ）＋（（１／Ｙｊ）−（１／Ｙｋ））  但し、ｊ＝ｉ−１，ｋ＝ｉ−２
【００２８】
Ｓ３０１の商近似値生成は、１／Ｙｉ（ｉは１以上の整数）を求める際、過去の除算結果が記憶されていない時には商の近似値の予測ができない。上記の式の場合ではｉ＝１とｉ＝２が該当する。Ｓ３０１の商近似値生成は、この時に商の近似値を出力するため、Ｙ１に対する商１の近似値Ｚ１１２６とＹ２に対する商２の近似値Ｚ２１２７とを保持している。ｉ＝１とｉ＝２に対しては、前記の一次式ではなく、商１の近似値Ｚ１１２６、商２の近似値Ｚ２１２７を出力する。
【００２９】
ステップＳ３０２の商算出は、除数Ｙｉ１２５と商の近似値Ｚｉ１２１を入力として、必要な精度の商を求め、商１／Ｙｉ１２２を出力する。ここではＮｅｗｔｏｎ−Ｒａｐｈｓｏｎ法で１回の繰り返しを行う方法を例に挙げる。
１／Ｙｉ＝Ｚｉ×（２−Ｚｉ×Ｙｉ）
この演算により、商の精度（有効桁数）は入力された商の近似値Ｚｉの精度の２倍になる。従って、商の近似値Ｚｉ１２１は商１／Ｙｉ１２２で必要な有効桁数の１／２の有効桁数であればよい。
【００３０】
本実施形態ではＮｅｗｔｏｎ−Ｒａｐｈｓｏｎ法で繰り返しは１回のみの例を示したが、近似値を入力として精度を高める除算方法であれば、Ｇｏｌｄｓｃｍｉｄｔ法などの他の演算方法も用いることができる。また、精度を高めるための演算の繰り返し回数は任意である。
【００３１】
ステップＳ３０３の商記憶は、ステップＳ３０２で出力された商１／Ｙｉ１２２を記憶する。本実施形態では、ステップＳ３０３の商記憶は、２つの記憶をもち１／Ｙｊ１２３と１／Ｙｋ１２４とを保持している（ｊ＝ｉ−１，ｋ＝ｉ−２）。ステップＳ１０２の商生成は、新しい商を出力すると、保持している商をそれぞれシフトして、１／Ｙｋには以前の１／Ｙｊ、１／Ｙｊには新しい商１／Ｙｉを記憶する。
【００３２】
［第６実施形態］
第５実施形態では１／Ｙｉ（ｉは１以上の整数）を求める際、１／Ｙｉ−１と１／Ｙｉ−２を用いる方法を説明した。次に、第６実施形態として１／Ｙｉ−ｔと１／Ｙｉ−ｔ−１（ｔは１以上の整数）から１／Ｙｉを求める方法を説明する。この実施形態は、プロセッサの演算器のレイテンシが大きい場合などに適用できる。
【００３３】
プロセッサの演算器のレイテンシが大きい場合、ステップＳ１１２で１／Ｙｉの商近似値計算を行う際、例えば一つ前の除算結果である１／Ｙｉ−１はステップＳ１０２の商生成あるいはステップＳ１１１の途中にあり、使用するとストールによる性能低下が起きる。このようなときは、ステップＳ１１２の商近似値計算で用いる算出式を変更する。
【００３４】
ステップＳ１１２の商近似値計算で、参照できるデータがステップＳ１１１の商記憶で記憶された１／Ｙｉ−ｔと１／Ｙｉ−ｔ−１とすると、以下の算出式で商の近似値Ｚｉ１２１を算出して出力する。
Ｚｉ＝（１／Ｙｉ−ｔ）＋ｔ×（（１／Ｙｉ−ｔ）−（１／Ｙｉ−ｔ−１））
＝（１／Ｙｊ）＋ｔ×（（１／Ｙｊ）−（１／Ｙｋ））  但しｊ＝ｉ−ｔ，ｋ＝ｉ−ｔ−１
先の場合と同様に、１／Ｙｉ（ｉは１以上の整数）の近似値Ｚｉを求める際、ｉ＝１からｉ＝ｔまでは別の方法で算出する必要がある。このときは、Ｙ１に対する商１の近似値Ｚ１１２６とＹ２に対する商２の近似値Ｚ２１２７とを用いて以下の式で求めることができる。
Ｚｉ＝Ｚ２＋（ｉ−２）×（Ｚ２−Ｚ１）
【００３５】
［第７実施形態］
次に、第７実施形態として、さらにステップＳ１１２の商近似値計算で任意の２つの過去の除算結果から商の近似値を算出する実施形態を示す。この実施形態は、プロセッサがＳＩＭＤ演算器を持つ場合などに適用できる。
【００３６】
ステップＳ１１２の商近似値計算で、参照できるデータがステップＳ１１１の商記憶で記憶された過去の除算結果が１／Ｙｊと１／Ｙｋ（ｉ＞ｊ＞ｋ，ｊとｋは整数）であるとする。ステップＳ１１２の商近似値計算ではこれらの過去の除算結果を用いて、以下の算出式で商の近似値Ｚｉ１２１を算出して出力する
Ｚｉ＝（１／Ｙｊ）＋（ｉ−ｊ）／（ｊ−ｋ）×（１／Ｙｊ−１／Ｙｋ）
【００３７】
［第８実施形態］
第６実施形態として、さらにステップＳ１１２の商近似値計算で過去の除算結果が記憶されていない時に商を算出する本発明の別の実施方法を説明する。ステップＳ１１２の商近似値計算で１／Ｙｉ（ｉは１以上の整数）の近似値Ｚｉを求める際、ｉ＞ｔの時は過去の除算結果を用いて近似値Ｚｉをｍ桁以上の精度で出力する。ｉ≦ｔの時は過去の除算結果を用いないが近似値Ｚｉの精度がｍ桁未満であるとする。この時はステップＳ１０２の商生成でｉ＞ｔの時よりも繰り返し回数を増やすようにする。例えば、ｉ≦ｔの時はＺｉの精度がｍ／２桁以上ｍ桁未満ならば繰り返し回数を１回増やせばよい。ｉ＞ｔの時の繰り返し回数が１回で十分な精度の出力が求められるのであれば、繰り返し回数を以下の式のように２回行うようにする。
Ｕｉ＝Ｚｉ×（２−Ｚｉ×Ｙｉ）
１／Ｙｉ＝Ｕｉ×（２−Ｕｉ×Ｙｉ）
【００３８】
以上の実施形態に於いて述べたように、本発明では被除数が固定値で等差数列を除数とする除算を行う際、過去の除算結果を用いて商の近似値を算出する。この商の近似値を用いて乗算型除算（例えばＮｅｗｔｏｎ−Ｒａｐｈｓｏｎ法）を行うことで除算結果の精度を高める。これにより、除算に於ける演算回数を少なくすると共に、乗算型除算の近似値を求めるためのテーブルを不要にすることができる。また、一般的には、被除数が固定値で、除数が等差数列と見なすことができる除算を乗算型除算で行う際に、演算回数を少なくすると共に乗算型除算の近似値を求めるためのテーブルを不要にすることができる。
【００３９】
なお、上述したように、Ｘ／Ｙｉを計算する際にも本実施形態を適用することが可能である。この場合、以上の実施形態において、商１／Ｙｊを商Ｘ／Ｙｊ、商１／Ｙｋを商Ｘ／Ｙｋ、商１／Ｙ１を商Ｘ／Ｙ１、商１／Ｙ２を商Ｘ／Ｙ２に置き換えればよい。
【００４０】
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【符号の説明】
【００４１】
１０１  商近似値生成部、１０２  商生成部、１１１  商記憶部、１１２  商近似値生成部、１１３  商１の近似値出力部、１１４  商２の近似値出力部
【図１】
2015197814.tif 000003
【図２】
2015197814.tif 000004
【図３】
2015197814.tif 000005