JPH07248902A - 浮動小数点演算装置とその誤差補正方法および線形計画問題最適化装置とその最適解の求解方法 - Google Patents

Abstract

(57)【要約】 【目的】 浮動小数点演算装置とその誤差補正方法およ
びその浮動小数点演算装置を備えた線形計画問題最適化
装置とその最適解の求解方法に関し，演算結果の誤差の
影響が後続の演算に影響しないようにすることを目的と
する。 【構成】 正規化浮動小数点数の指数保持部Ａ(10)と，
演算結果の正規化浮動小数点数の指数保持部Ｂ(13)と，
演算結果を補正するかしないかの判定基準の閾値を保持
する閾値保持部(11)と，演算前の該指数と演算後の該指
数の比較結果と該閾値を比較し，演算結果の補正を行う
かあるいは行わないかを判定する指数比較部(12)と，指
数比較部(12)の比較結果に基づいて演算結果を補正する
演算結果変更部(14)とを備え，演算前の該指数と該演算
後の該指数の比較結果が該閾値より大きい場合には，演
算結果を０に補正する構成を持つ。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は，浮動小数点演算装置と
その誤差補正方法およびその浮動小数点演算装置を備え
た線形計画問題最適化装置とその最適解の求解方法に関
する。

【０００２】コンピュータにより浮動小数点演算を行う
場合には，計算桁が有限であることに起因する誤差を生
じる場合がある。特に線形計画問題最適化装置では，最
適解を得るまでに膨大な量の浮動小数点演算を必要とす
るので，その過程で上記の数値誤差が累積され，そのた
め，掃き出し回数の増加等で計算時間が長くなったり，
無限ループを生じ最適解に収束しないことがしばしば起
こる（掃き出しについては後述する）。

【０００３】

【従来の技術】従来はそのような誤差に基づく障害を回
避するため，掃き出し点を選択する場合にできるだけ誤
差を発生させない掃き出し点を選択するようにしてい
た。また，誤差が発生した場合には，ある定められた値
以下の小さな値は０とするように，決められた小さな値
（トレランス値）を境にまるめ処理補正を行う程度であ
った。

【０００４】図７，図８により，シンプレックス法によ
る線形計画問題の最適解の求め方について説明する。線
形計画問題は，図７ (a)に示す，制約条件，，，
において，目的関数のｚを最大にする解，ｘ₁ ，ｘ
₂ ，・・・，ｘ_k を求める問題である。

【０００５】ここで，図７ (b)に示すように，スラック
変数を導入して標準形の連立方程式とする（スラック変
数については例題を参照）。このとき，ｄ₁ ≧０ ，ｄ
₂ ≧０，・・・，ｄ_m ≧０とする。

【０００６】シンプレックス法は，このとき図７ (c)に
示すように，ｘ₁ ，ｘ₂ ，・・・，ｘ_n の係数および定
数項の作る行列に次の操作を行って最適解を求める方法
である。

【０００７】ステップ１ c₁ ， c₂ ，・・・，ｃ_n の
中で負の成分がなければ_, それはすでに最適解であり_,
処理を終了する。負の成分があれば_, その絶対値が最大
なものをとる。それをｃ_s とする。

【０００８】ステップ２ 第ｓ列中，ａ_is＞０となるａ
_isをすべて求める。 ステップ３ ステップ２で求めたａ_isについてｄ_i ／ａ
_isを計算し，最小のものをとる。最小のものが２つ以上
あるときはいずれでも良い。それをａ_rsとする。

【０００９】ステップ４ ａ_rsをピボットとするピボッ
ト変形を行いステップ１に戻る（ピボット変形について
は例題参照）。 図８により，上記の方法について，例題により説明す
る。

【００１０】図８ (a)のの制約条件を元に，目的関数
を最大とするｘ，ｙを求める。問題式 (a)に対してス
ラック変数（ｘ₃ ，ｘ₄ ）を導入して，標準形とし，ｚ
も変数にして図８ (b)の連立方程式を得る。

【００１１】そこで，ｘ₁ ，ｘ₂ ，ｘ₃ ，ｘ₄ の係数お
よび定数項からなる行列を作る（図８ (c)）。図８ (c)
の行列に対してステップ１を実行する。

【００１２】ｃ_s は（３，２）成分の c₂ ＝−４であ
る。ステップ２で求める第２列中正であるものは，ａ₁₂
＝１とａ₂₂＝３である。ステップ３で，２０／１＝２０
と３２／３＝１０．６６・・・を比較する。３２／３の
方が小さいのでａ_rs＝ａ₂₂をピボットとする。

【００１３】ステップ４でａ₂₂をピボットとしてピボッ
ト変形を行うことにより図８ (d)の行列を得る（ピボッ
ト変形は (d)のようにピボットとした要素ａ₂₂のある列
において，ピボットとした要素を１とし，他は０とする
変形である。この処理を掃き出しと称する）。

【００１４】ここで，ステップ１に戻る。 c₁ ＝−１／
３が負の項であるので，ステップ２へ進む。ａ₁₁＝４／
３＞０，ａ₂₁＝２／３＞０である。ステップ３で，（２
８／３）／（４／３）＝２８／４＝７，（３２／３）／
（２／３）＝３２／２＝１６である。７の方が小さいの
で，ａ_rs＝ａ₁₁＝４／３をピボットとする。

【００１５】ステップ４で，ａ₁₁をピボットとしてピボ
ット変形を行い，図８ (e)の行列を得る（掃き出しをす
る）。ステップ１にもどる。 c₁ ≧０，・・・， c₄ ≧
０，即ち全部非負なので終了する。

【００１６】ｘ₃ ＝０，ｘ₄ ＝０として，図８ (f)を最
適解とする。このとき目的関数ｚの値はｚ＝４５であっ
て，最大である（上記において，シンプレックス方の説
明は，紀伊國屋書店発行，伊藤 昇，岩井 齋良，岩堀
長慶，上林 達治，関野 薫，高橋 秀一著，「経済
系・工学系のための行列とその応用」を参照した）。

【００１７】図９は従来の線形計画問題最適化装置で使
用される浮動小数点演算装置の加減算処理のフローチャ
ートを示す。図示の番号に従って説明する。

【００１８】Ｓ１ 正規化された浮動小数点データを入
力する。 Ｓ２ 加算もしくは減算をする。 Ｓ３ 小さな値についてまるめ処理をする。

【００１９】Ｓ４ 演算結果を出力する。

【００２０】

【発明が解決しようとする課題】上記のように，変数が
多い場合は，線形計画問題の最適解を求めるためには，
膨大な数の演算処理を行わなければならない。そのた
め，コンピュータの桁の精度が有限であることに起因す
る誤差が累積され，掃き出し回数の増加，処理がループ
して最適解に収束しない等を生じる場合があった。

【００２１】誤差の影響について，図１０により説明す
る。図１０は浮動小数点演算における誤差の問題点の説
明図である。図１０ (a)は浮動小数点演算における正規
化の説明図である。

【００２２】浮動小数点演算では，数値は全て正規化し
て，有効数字を小数点以下第１位から始まるように仮数
部と指数部に分けて表すようにする。例えば，有効数字
４桁の１２３４は０．１２３４×１０⁴ とし，符号部を
正負の符号，指数部を１０⁴ の指数４，仮数部を仮数１
２３４として表す。

【００２３】次に図１０により，浮動小数点演算によ
り，Ａ−Ｂ＝Ｃ，Ｃ×１０００＝Ｄを計算する場合の誤
差について説明する。Ｂは他の演算処理により求められ
るものとする。

【００２４】Ｂは正規化されて，Ｂ＝０．４×１０が正
しい値であるが，Ｂの算出処理において誤差を生じ，正
規化して０．３９９９９９９９×１０が求められたもの
とする。

【００２５】図１０において， Ａのデータ入力をする。そして，に正規化された
浮動小数点数Ａが入力される。

【００２６】 Ｂの算出処理がなされる。そして，
に正規化された浮動小数点数Ｂが入力される。Ｂは０．
４×１０が正しい値（望まれる値）であるが，演算誤差
のために，０．３９９９９９９９×１０が算出され，
に入力される。

【００２７】において，Ｃ＝Ａ−Ｂが算出され，正規
化されて，Ｃ＝０．１×１０^-6が求められる。望まれる
正しいＣの値は，Ｃ＝０．４×１０−０．４×１０＝０
であるが，Ｂの算出処理の誤差のため，Ｃ＝０．１×
１０^-6が算出される。

【００２８】でＣ×１０００＝Ｄの処理がなされる。
の演算結果Ｃにより，Ｄ＝０．１×１０^-3が求めら
れ，で出力される。のＢの算出処理でＢが正しく求
められていれば，Ｄ＝０であるはずであるが，誤差を生
じているためでＢの誤差が拡大されて出力される。

【００２９】本発明は，浮動小数点演算において，演算
結果の誤差の影響が後続の演算に影響しないようにし，
特に，線形計画問題に適用して有効な浮動小数点演算装
置と誤差補正方法およびその線形計画問題最適化装置と
その最適解の求解方法を提供することを目的とする。

【００３０】

【課題を解決するための手段】浮動小数点（特に，倍精
度の浮動小数点）加減算では，演算結果が演算前の数値
と比較して非常に小さい値（０に近い値）となる場合が
ある。例えば，演算前の指数部の値が１０（データ値が
１０桁）から０（データ値が１桁）に変化するような場
合である。これは，コンピュータの演算桁が有限である
ことに基づく誤差により生じたものである場合が多く，
本来は等しいはずの２数が，誤差により非常に小さい値
を生じたものであり，正しくは０であるものと考えられ
る。

【００３１】本発明は，このように加減算の前後で，指
数部の値が大きく変化して，小さい値を生じた場合は演
算結果を０とするようにした。この処理を相対誤差補正
と称する。

【００３２】図１は本発明の基本構成を示す。図１にお
いて，１は浮動小数点演算装置である。

【００３３】２は演算データ入力部であって，正規化デ
ータを入力するものである。３は演算データ保持部であ
って，正規化された入力データを符号部，指数部，仮数
部に分けて保持するものである。

【００３４】４は演算部であって，加減算をするもので
ある。５は正規化処理部である。６は演算結果保持部で
ある。

【００３５】７は相対誤差補正部であって，演算の前後
の指数部の変化を判定し，変化の程度に従って演算結果
を補正するものである。８は演算結果出力部である。

【００３６】１０は指数保持部Ａであって，入力された
演算データの指数部の値を保持するものである。１１は
閾値保持部であって，演算結果を変更するかしないかを
判定するための閾値を保持するものである。

【００３７】１２は指数比較部であって，演算前の入力
データの指数部と演算結果の指数部を比較するものであ
る。１３は指数保持部Ｂであって，演算結果の指数部の
値を保持するものである。

【００３８】１４は演算結果変更部であって，演算結果
を補正するものである。

【００３９】

【作用】図２を参照し，図１の本発明の基本構成の動作
を説明する。図２は本発明の基本構成の動作例を示す。

【００４０】演算データ入力部２は正規化された演算デ
ータを入力する。図２の場合，Ａ＝０．４×１０であ
り，Ｂ＝０．３９９９９９９９×１０が入力される。演
算データ保持部３はそれぞれの入力データを符号部，指
数部，仮数部に分けて保持する。演算部４はＡ，Ｂを減
算し，正規化処理部５は正規化処理をし，演算結果保持
部６は正規化した演算結果０．１×１０^-6を符号部，指
数部，仮数部に分けて保持する（指数部の表し方は説明
の都合上便宜的に図示のように表したものである）。

【００４１】一方，指数保持部Ａ(10)は，演算データ保
持部３に保持されているデータの指数部（値０１）を取
り出し保持する。また，指数保持部Ｂ(13)は演算結果保
持部６に保持されている指数部の値（−６）を取り出し
て保持する。そして，指数比較部１２は例えば，指数保
持部Ａ(10)の取り出した指数と，指数保持部Ｂ(13)の取
り出した指数の差をとり，閾値保持部１１に保持されて
いる値５と比較する。そして，指数部の差が閾値より大
きい場合には，演算結果変更部１４に演算結果の補正を
指示する。図の場合指数の差が７であり，閾値が５であ
るので，演算結果変更部１４に演算結果の補正を指示す
る。

【００４２】演算結果変更部１４は，指数比較部１２の
指示に従い，補正指示があれば演算結果保持部６に保持
されている演算結果を０に変更し，０を出力する。変更
指示がなければ，演算結果保持部６に保持している値を
出力する。

【００４３】本発明は，演算結果の値が大きい値でも，
指数部の値が大きく変化して得られたものであって本来
０であるべきものである場合には，そのことを判定し，
０に正しく補正する。

【００４４】従って，本発明によれば，線形計画問題最
適化装置のような多次元の連立方程式の解をもとめるよ
うな演算処理に対して正確な演算処理を行うことができ
るようになる。

【００４５】

【実施例】図３は本発明の浮動小数点演算装置を備えた
線形計画問題最適化装置の構成実施例を示す。

【００４６】図３において，２０は線形計画問題最適化
装置であって，シンプレックス法により線形計画問題の
最適解を求める線形計画問題最適解求解手段と，本発明
の相対誤差補正部をもつ浮動小数点演算装置を備えたも
のである。

【００４７】２１はＣＰＵである。２２は主記憶であ
る。２３は入力手段であって，演算データ，制約条件，
目的関数等を入力するものである。

【００４８】２４は出力手段であって，演算結果を出力
するディスプレイ，印刷装置等である。２５は浮動小数
点演算装置である。

【００４９】２６は乗除算部であって，乗算もしくは除
算を行うものである。２７は加減算部であって，加算も
しくは減算をするものである。２８は相対誤差補正部で
あって，前述のものである。

【００５０】３０は線形計画問題最適解求解手段であっ
て，シンプレックス法により線形計画問題の最適解を求
めるものである。３１はステップ１である（前記参
照）。

【００５１】３２はステップ２である（前記参照）。３
３はステップ３である（前記参照）。３４はステップ４
であって，掃き出し処理を行うものである（前記参
照）。

【００５２】３５は制約条件である。３６は目的関数で
ある。３７は演算データである。

【００５３】図３の構成において，線形計画問題最適解
求解手段３０は，浮動小数点演算装置２５を使用して，
制約条件３５と演算データ３７に基づいてステップ１(3
1)，ステップ２(32)ステップ３(32)，ステップ４(34)に
従って目的関数３６の最適解を求める。浮動小数点演算
装置２５においては，相対誤差補正部２８は，加減算処
理の演算結果について，前述の相対誤差を判定し，補正
が必要であれば，演算結果を０に補正し，浮動小数点演
算を行う。

【００５４】図４は本発明の浮動小数点演算装置の実施
例のフローチャートである。図４は倍精度の浮動小数点
演算装置の場合の動作である。 Ｓ１ 倍精度浮動小数点数の加減算処理を開始する。

【００５５】Ｓ２ 倍精度浮動小数点数の指数部を取り
出す（指数部の値をｍとする。演算データが２数以上あ
る場合には，そのいずれでも良い）。 Ｓ３ 倍精度浮動小数点数の加算または減算を行う。

【００５６】Ｓ４ 倍精度浮動小数点数の指数部を取り
出す（取り出した値をｎとする）。 Ｓ５ ｍ−ｎを求め，ｍ−ｎとある値（閾値）と比較す
る。ｍ−ｎ≧ある値であればＳ６に進み，ｍ−ｎ＜ある
値であれば，処理を終了する。

【００５７】Ｓ６ 演算前の指数と演算後の指数の差ｍ
−ｎがある値より大きいので，演算結果ＣをＣ＝０．０
とする。 図５により，本発明の浮動小数点演算装置の実施例を説
明する。

【００５８】図５は本発明の浮動小数点演算装置により
連立方程式を解く場合の例である。図５において，各浮
動小数はＣ言語の関数ｐｒｉｎｔｆ（“％ｅ”，浮動小
数変数名）で出力させた値である。浮動小数点数は３２
ビットで宣言してあるものとする。相対誤差補正で用い
る判定値（閾値）は５とする。

【００５９】(a)の連立方程式を解くものとする。(a)の
(2) 式の右辺の値は０．１を１００回加算処理して得ら
れたものである。計算方法は次のとおりである。

【００６０】ｉｎｔ ｉ； ｆｌｏａｔ ｒｈｓ２＝０．０； ｆｏｒ（ｉ＝１；ｉ＜＝１００；ｉ＋＋） ｒｈｓ２＋＝０．０１； 正しい演算結果は１であるが，演算誤差のため図示のよ
うに，９．９９９９９３ｅ−０１となったものである
（ｅ−０１は１０^-1を表す）。

【００６１】(a)式について掃き出し計算を行い，解く
と (b)式が得られる。そこで， (a)式を解くのに本発明
の相対誤差補正を行いながら解くと次のようになる。

【００６２】(c)式において（ (c)式は (a)式に同じで
ある），下線の部分について掃き出しをする。そこで，
(2) −(1) を計算すると右辺の計算は (d)になる。ここ
で， (d)の演算結果に対して相対誤差補正を行う。

【００６３】(2) 式の右辺９．９９９９９３ｅ−０１の
指数部を取り出すとｍ＝−１である。（あるいは(1) 式
の右辺１．００００００ｅ＋００の指数部を取り出して
ｍ＝０でも良い）。計算後の値の−６．５５６５１１ｅ
−０７の指数部を取り出すとｎ＝−７である。次にそれ
ぞれの指数部の差を求めると，ｍ−ｎ＝−１−（−７）
＝６である（あるいはｍ−ｎ＝０−（−７）＝７）。

【００６４】この値を判定値（閾値）と比較すると５よ
りも大きい。そのため， (d)式の右辺の値を誤差補正し
て０とし， (f)式を得る。その結果，正しい (g)式が得
られる。

【００６５】次に， (g)式のｙについて掃き出しを行
う。即ち， (g)式の(1) −(2) ’／２．０００００ｅ＋
００を計算すると，(h) 式が得られる。

【００６６】従って，相対誤差補正を行うことにより正
しい式が得られる（ (b)式の(2) ”の右辺の値が正しい
値に補正されている）。図６は本発明の効果の測定結果
を示す。

【００６７】図６は，シンプレックス法により，マトリ
ックスの大きさが数十×数十〜数千×数千の８１個の線
形計画問題最適化のための例題に対して，本発明の方法
と従来の方法とで掃き出し回数と掃き出し時間を求めた
ものである。改善率は改善量を相対誤差補正なしの量
（従来の方法による量）で本発明の方法による場合を割
ったものである。

【００６８】掃き出し回数および掃き出し時間が，本発
明の方法により改善されることが示されている。

【００６９】

【発明の効果】本発明は，演算結果の値が大きい値で
も，指数部の値が大きく変化して得られたものであって
本来０であるべきものである場合には，そのことを判定
し，０に正しく補正するので，従来，行われていたよう
な，演算結果が，あらかじめ定められた小さな値を基準
に補正するのでなく，演算の前後の値の大きさの変化に
より誤差の補正をするので，確実な誤差の補正を行うこ
とができるようになる。そのため，本発明によれば，線
形計画問題最適化装置のような多次元の連立方程式の解
をもとめるような演算処理に対して正確な演算処理を行
うことができるようになるとともに，演算速度も高速化
される。

【図面の簡単な説明】

【図１】本発明の基本構成を示す図である。

【図２】本発明の基本構成の動作例を示す図である。

【図３】本発明の浮動小数点演算装置を備えた線形計画
問題最適化装置の構成実施例を示す。

【図４】本発明の浮動小数点演算装置の実施例のフロー
チャートを示す図である。

【図５】本発明の実施例を示す図である。

【図６】本発明の効果の測定結果を示す図である。

【図７】線形計画問題の最適解の求め方を示す図であ
る。

【図８】例題（シンプレックス法）を示す図である。

【図９】従来の線形計画問題最適化装置で使用される浮
動小数点演算装置の加減算処理のフローチャートを示す
図である。

【図１０】浮動少数点演算における誤差の問題点につい
ての説明図である。

【符号の説明】

１ ：浮動小数点演算装置 ２ ：演算データ入力部 ３ ：演算データ保持部 ４ ：演算部（加減算） ５ ：正規化処理部 ６ ：演算結果保持部 ７ ：相対誤差補正部 ８ ：演算結果出力部 １０：指数保持部Ａ １１：閾値保持部 １２：指数比較部 １３：指数保持部Ｂ １４：演算結果変更部

Claims (4)

【特許請求の範囲】
1. 【請求項１】 正規化浮動小数点数の加減算を行う浮動
   小数点演算装置において，入力された正規化浮動小数点
   数の指数保持部Ａ(10)と，演算結果の正規化浮動小数点
   数の指数保持部Ｂ(13)と，演算結果を補正するかしない
   かの判定基準の閾値を保持する閾値保持部(11)と，演算
   前の該指数と演算後の該指数の比較結果と該閾値を比較
   し，演算結果の補正を行うかあるいは行わないかを判定
   する指数比較部(12)と，指数比較部(12)の比較結果に基
   づいて演算結果を補正する演算結果変更部(14)とを備え
   た，ことを特徴とする浮動小数点演算装置。
2. 【請求項２】 正規化浮動小数点数の加減算を行う浮動
   小数点演算装置における誤差補正方法において，入力さ
   れた正規化浮動小数点数の指数と演算結果の正規化浮動
   小数点数の指数との比較結果と，あらかじめ定めた閾値
   との比較結果に基づいて，演算結果を補正することを特
   徴とする浮動小数点演算装置の誤差補正方法。
3. 【請求項３】 請求項１に記載の浮動小数点演算装置を
   備えた線形計画問題最適化装置において，制約条件と目
   的関数を保持し制約条件のもとに最適解を求める線形計
   画問題求解手段を備え，該線形計画問題求解手段により
   該浮動小数点演算装置(1) において浮動小数点演算をす
   ることにより最適解を求めることを特徴とする線形計画
   問題最適化装置。
4. 【請求項４】 請求項１に記載の浮動小数点演算装置
   (1) を備えた線形計画問題最適化装置における最適解の
   求解方法において，入力された浮動小数点数の指数部
   と，演算結果の正規化浮動小数点数の指数部とを比較
   し，該比較結果をあらかじめ定めた閾値と比較し，その
   結果に基づいて演算結果を補正しながら該最適解を求め
   ることを特徴とする線形計画問題最適化装置における最
   適解の求解方法。