JP2583599B2

JP2583599B2 - ２進整数乗算処理方法

Info

Publication number: JP2583599B2
Application number: JP1033927A
Authority: JP
Inventors: 孝則寺田
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1989-02-14
Filing date: 1989-02-14
Publication date: 1997-02-19
Anticipated expiration: 2012-02-19
Also published as: JPH02212927A

Description

【発明の詳細な説明】〔概要〕計算機が持つ乗算命令実行機構で扱う２進整数の長さ
の２倍の長さを持つ被乗数および乗数の乗算を行う２進
整数乗算処理方法に関し， FORTRANプログラム等における63ビット整数型の乗算
を，浮動小数点命令を使用しないで実現する手段を提供
することを目的とし，被乗数Ｘおよび乗数Ｙのそれぞれについて，上位ｎビ
ットと下位ｎビットとに分割して，各々ｎビットのレジ
スタに割り当てる処理過程と,nビットのレジスタに割り
当てた被乗数Ｘおよび乗数Ｙのそれぞれについて，上位
ｎビットを左に１ビット分シフトするとともに，下位ｎ
ビットの最上位ビットを，上位ｎビットの最下位ビット
に繰り入れる処理過程と，被乗数Ｘの上位ｎビットおよ
び乗数Ｙの上位ｎビットの値により，場合分けを行い，
オーバフローの検出を行うとともに，オーバフローとな
らない場合に，各ｎビットのデータ間の演算により，被
乗数Ｘと乗数Ｙとの2nビットの範囲内で表される積を計
算する処理過程とを備えるように構成する。

〔産業上の利用分野〕

本発明は，計算機が持つ乗算命令実行機構で扱う２進
整数の長さの２倍の長さを持つ被乗数および乗数の乗算
を行う２進整数乗算処理方法に関する。

計算機による科学技術計算や事務処理計算では，乗算
が頻繁に用いられる。計算機で扱う数値の中で最も単純
な形式は,2進整数であるが，乗算の対象となる２進整数
で表される被乗数，乗数について，桁数を増やすことが
望まれる。

〔従来の技術〕

従来,1語32ビットの計算機などによって実行されるFO
RTRANプログラムでは,31ビット整数型どうしの乗算が可
能であるが,63ビット整数型の乗算は実行できなかっ
た。

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

従来,FORTRANプログラム等では,63ビット整数型の乗
算ができなかったため，そのような乗算を行う場合に
は，例えば整数型の数値を浮動小数点に変換し，浮動小
数点命令を使用して乗算を行った後，結果について整数
型に型変換を行うというような処理が必要になるという
問題があった。そのため，処理手続きが煩雑で，処理も
遅くなるという問題があった。

本発明は上記問題点の解決を図り,FORTRANプログラム
等における63ビット整数型の乗算を，浮動小数点命令を
使用しないで実現する手段を提供することを目的として
いる。

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

第１図は本発明の構成例を示す。

第１図において,10はCPUおよびメモリ等からなる計算
機,P1ないしP3は計算機10による乗算のための処理過程,
Xは被乗数,Yは乗数,R1ないしR4はレジスタを表す。

計算機10は,nビットのデータを保持する複数のレジス
タR1〜R4を持ち，これらのレジスタに設定された２進整
数の乗算命令実行機構を有する。

それぞれ2nビットの範囲内で表される２進整数である
被乗数Ｘおよび乗数Ｙの乗算を行う場合，次のような処
理過程P1〜P3によって，乗算を実行する。

処理過程P1では，被乗数Ｘを，上位ｎビットのX1と，
下位ｎビットのX2とに分け，それぞれレジスタR1,レジ
スタR2に設定する。また，乗数Ｙを，上位ｎビットのY1
と，下位ｎビットのY2とに分け，それぞれレジスタR3,
レジスタR4に設定する。

処理過程P2では，レジスタR1,レジスタR2に割り当て
た被乗数Ｘについて，上位ｎビットを左に１ビット分シ
フトするとともに，下位ｎビットの最上位ビットを，上
位ｎビットの最下位ビットに繰り入れる処理を行う。同
様に，レジスタR3,レジスタR4に割り当てた乗数Ｙにつ
いて，上位ｎビットを左に１ビット分シフトするととも
に，下位ｎビットの最上位ビットを，上位ｎビットの最
下位ビットに繰り入れる処理を行う。

次に，処理過程P3では，被乗数Ｘの上位ｎビットX1お
よび乗数Ｙの上位ｎビットY2の値により，場合分けを行
い，オーバフローの検出を行うとともに，オーバフロー
とならない場合に，上記各ｎビットのデータ間の演算に
より，被乗数Ｘと乗数Ｙとの積を計算する。

〔作用〕

本発明では,1語がｎビットの計算機10により,2nビッ
トの範囲内で表される被乗数X,乗数Ｙについての乗算を
行うにあたって，まず，処理過程P1により，それぞれｎ
ビットに分割する。

このｎビット間で，そのまま乗算命令を実行すると，
下位ｎビットの先頭ビットが符号ビットとして扱われる
ため，このビットがたまたま“1"であるとすると，部分
的に負の数の計算が行われることになる。そこで，処理
過程P2により，この下位ｎビットの先頭ビットを，上位
ｎビットの最下位ビットに繰り入れ，下位ｎビットの先
頭ビットを０とする。上位ｎビットの元の値は,1ビット
ずつ左側へシフトする。

次に，処理過程P3では，乗算結果が2nビット（実質の
有効桁としては,2n−１ビット）の範囲内で表されるよ
うに，オーバフローの検査を行い，各ｎビットの積およ
び和を計算して，求めるべき計算結果を得る。

〔実施例〕

第２図は本発明の一実施例についての適用システムの
例，第３図は本発明の一実施例による処理の例，第４図
は本発明の一実施例処理フローを示す。

本発明は，例えば第２図に示すようなシステムにおい
て実施される。第２図において,20はFORTRAN言語で記述
されたプログラムをコンパイルした結果のFORTRANオブ
ジェクトプログラム,21はパラメータリスト,22はライブ
ラリとして提供される63ビット乗算関数ルーチンを表
す。

従来,FORTRAN言語によるプログラムでは,63ビット整
数型どうしの乗算はできず，仕様制限になっていた。本
実施例では,63ビット整数型の乗算を行う場合,FORTRAN
オブジェクトプログラム20は，それぞれ63ビット整数型
の被乗数X,乗数Ｙおよび結果域からなるパラメータリス
ト21を作成し，あらかじめ用意された63ビット乗算関数
ルーチン22を呼び出す。

63ビット乗算関数ルーチン22は，第１図に示すような
処理過程により,63ビット整数型の乗算を実行する。そ
して，乗算結果をパラメータリスト21の結果域に設定し
て，呼び出し元のFORTRANオブジェクトプログラム20に
復帰する。

例えば，第３図（ａ）に示すように,FORTRANオブジェ
クトプログラム20において，「Ｉ＝2147483648＊２」の乗算を行うとする。

FORTRANオブジェクトプログラム20は，第３図（ｂ）
に示すようなパラメータリスト21を作成し，その先頭ア
ドレスを所定のレジスタRegに設定して,63ビット乗算関
数ルーチン22を呼び出す。

63ビット乗算関数ルーチン22は，第３図（ｃ），
（ｄ）に示すように，被乗数X,乗数Ｙを，それぞれ32ビ
ットのX1,X2およびY1,Y2に分割し,X2,Y2の先頭ビット
を，それぞれX1,Y1に繰り入れる処理を行う。なお，第
３図（ｃ），（ｄ）では，数値を16進数字で表してい
る。この例における10進数字表現の「2147483648」は2
³¹であり,32ビット＋32ビットの16進数字表現では，「0
0000000」「80000000」と表される。

演算の原理は，以下のとおりである。

Ｚ＝Ｘ・Ｙを考える。ここで,X≧0,Y≧０とする。

Ｘ＝X1・2³¹＋X2,Y＝Y1・2³¹＋Y2 （０≦X2,Y2≦2³¹）とすると，Ｚ＝Ｘ・Ｙ＝X1・Y1・2⁶²＋（X1・Y2＋X2・Y1）×2³¹＋X2・Y2 となる。ここで， X1・Y1≧０ X1・Y2＋X2・Y1≧０ X2・Y2≧０であるから，Ｚ≦2⁶³となるためには， X1・Y1≦２でなければならない。

これを満たす組（X1,Y1）によって，以下の組み合わ
せになる。

この場合分けによる処理は，以下のとおりになる。

ｉ）X1＝0,Y1＝０の場合これは,Z＝X2・Y2を計算すればよい。

ii）X1＝Y1＝１の場合Ｚ＝2⁶²＋（X2＋Y2）2³¹＋X2・Y2であるから，Ｚ≦2⁶³は，（X2＋Y2）2³¹＋X2・Y2≦2⁶² ……（１）と同値である。

X2＜2³¹,Y2＜2³¹から， X2＋Y2＜2³²,X2・Y2＜2⁶²であるから，（１）式の左辺
の計算において，論理加算命令で桁溢れ（オーバフロ
ー）が起こることはない。

従って，（１）式が成立することと,X,Yで桁溢れが起
きないことは同値であり，（１）式で等号が成立してよ
いのは,X・Ｙ＜０の場合だけである。

iii）（X1＝０かつＹ≠０）または（X1≠０かつY1＝０）の場合 X1≠０かつY1＝０と仮定しても一般性は失われない。
このとき，Ｚ＝X1・Y2・2³¹＋X2・Y2となる。

Ｚ≦2⁶³は， X1・Y2・2³¹＋X2・Y2≦2⁶³ ……（２）と同値になる。従って,X1・Y2の計算で，上位４バイト
（32ビット）が０でなければ，桁溢れとなる。

iv）（X1＝２かつY1＝１）または（X1＝１かつY1＝２）の場合この場合,X1・Y2＋X2・Y1＝０かつX2・Y2＝０から,X2
＝Y2＝０であり，かつＸ・Ｙ＜０でなければ桁溢れにな
る。

ｖ）X1≧２かつY1≧の場合 X1・Y1・2⁶³≧2⁶⁵であるので，桁溢れとなる。

以上の演算の原理を利用して,63ビット整数型の乗算
およびオーバフローの検出を，第４図に示す処理〜
のように行う。以下，第４図に示す処理〜に従って
説明する。

被乗数Ｘおよび乗数Ｙを，それぞれ上位・下位の32
ビットずつに分割し，その分割したX1,X2およびY1,Y2を
それぞれレジスタに設定する。

Ｘが負数ならば，符号を反転して正数にする。この
処理は以下のように行う。

X1＜０なら,Xに−X1−１を入れる。

さらに,X2が最小値でないなら,X2に−X2を入れる。Ｘ
の符号を反転したことを記憶しておく。

Ｙについても同様に，負数ならば，符号を反転して正
数にする。

次に,X2の先頭ビットX1に繰り入れる処理を行う。
この処理は以下のように行う。

X1とX2を合わせて左に１ビットシフトする。

X2だけを右に１ビットシフトする。

Y2の先頭ビットについても，同様にY1の最下位ビット
に繰り入れる処理を行う。

X1とY1の値により，処理ｉ〜処理ｖの場合分けを行
う。

前述した演算の原理に従って，各場合分けに応じた
オーバフロー検出を行い，オーバフローが起きない場合
に,32ビットの乗算と論理和の各演算により，積（Ｚ）
を計算する。なお,X,Yが負数ならば，符号反転により，
正数に直して計算を行っているので，最後に元のX,Yの
どちらか一方だけが負数である場合に，積Ｚの符号を反
転して,Zを負数で表す。

〔発明の効果〕

以上説明したように，本発明によれば，例えば１語が
32ビットの計算機上で,63ビット整数型の乗算を浮動小
数点命令を使用しないで実現できるようになり，応用プ
ログラムにおける計算精度を向上させるとともに，処理
負担を軽減することが可能になる。

【図面の簡単な説明】

第１図は本発明の構成例第２図は本発明の一実施例についての適用システムの
例，第３図は本発明の一実施例による処理の例，第４図は本発明の一実施例処理フローを示す。図中,10は計算機,P1〜P3は処理過程,R1〜R4はレジスタ,
Xは被乗数,Yは乗数を表す。

Claims

(57)【特許請求の範囲】

【請求項１】ｎビットのデータを保持する複数のレジス
タを備えるとともに,nビットの２進整数による被乗数と
ｎビットの２進整数による乗数との乗算命令実行機構を
有する計算機を用いて，それぞれ2nビットの範囲内で表
される２進整数である被乗数Ｘおよび乗数Ｙの乗算を行
い,2nビット範囲内で表される積を算出する２進整数乗
算処理方法であって，被乗数Ｘおよび乗数Ｙのそれぞれについて，上位ｎビッ
トと下位ｎビットとに分割して，各々上記ｎビットのレ
ジスタに割り当てる処理過程（P1）と，上記ｎビットのレジスタに割り当てた被乗数Ｘおよび乗
数Ｙのそれぞれについて，上位ｎビットを左に１ビット
分シフトするとともに，下位ｎビットの最上位ビット
を，上位ｎビットの最下位ビットに繰り入れ，下位ｎビ
ットの最上位ビットのビット値を０とする処理過程（P
2）と，上記ビットシフト処理後の被乗数Ｘおよび乗数Ｙの上位
ｎビットをX1,Y1,下位ｎビットをX2,Y2としたとき，被
乗数Ｘの上位ｎビットX1および乗数Ｙの上位ｎビットY1
の値による場合分けに応じて， X1＝０かつY1＝０の場合，上記乗算命令実行機構を用
いて,Z＝X2・Y2に相当する演算を行い， X1＝１かつY1＝１の場合，オーバフローの検出を行う
とともに，オーバフローとならないときに，上記乗算命
令実行機構を用いて,Z＝2^2n-2＋（X2＋Y2）2^n-1＋X2・Y
2に相当する演算を行い， X1≠０かつY1＝０の場合，オーバフローの検出を行う
とともに，オーバフローとならないときに，上記乗算命
令実行機構を用いて,Z＝X1・Y2・2^n-1＋X2・Y2に相当す
る演算を行い， X1＝０かつY1≠０の場合，オーバフローの検出を行う
とともに，オーバフローとならないときに，上記乗算命
令実行機構を用いて,Z＝X2・Y1・2^n-1＋X2・Y2に相当す
る演算を行い，その他の場合に，オーバフローによるエラー処理また
はＺ＝負の最小値とする処理を行い，被乗数Ｘと乗数Ｙとの2nビットの範囲内で表される積を
算出する処理過程（P3）とを備えたことを特徴とする２
進整数乗算処理方法。