(57)【要約】【目的】ロジスティック写像の固定小数点乗算器の桁上げを逐次ビット操作に置き換え、擬似乱数を高速に生成し、複雑な組合せ問題の解決に必要な順列と組合せを取得する。【構成】カオスを生成するロジスティック写像の乗算ｘｔ（１−ｘｔ）は、整数ｘｔとその反転プラス１の補数の掛け算である。シフトした逐次加算において、加算をビット操作に置き換える。【選択図】　　　　図１
2004127210.tif 000002
【特許請求の範囲】
【請求項１】
ロジスティック写像の固定小数点乗算器ｘｔ（１−ｘｔ）において、逐次乗算過程にあらわれる桁上げ処理をビット操作により実行することを特徴とするロジスティック写像の固定小数点乗算器。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
ディジタルコンピュータがあらゆる多値の組合せである順列（重なりのない組合せ）と組合せ（重なりを許す組合せ）を自在に駆使して問題解決に当たるためには、汎用ＣＰＵのまわりにロジスティック写像の固定小数点乗算器がコプロセッサとして配置されたときである。
【０００２】
計算量が爆発的に増大する複雑な組合せ問題に、ディジタルコンピュータが無力であることは知られている。ディジタルコンピュータは逐次処理の順序マシンである。人類にとって膨大なソフトの資産を搭載したディジタルコンピュータは、もはや手放すことのできない産業を支える道具となっている。順序を公平に変えることができるカオスという現象を、産業技術としてディジタルコンピュータに付加できるのはロジスティック写像ｘｔ＋１＝４ｘｔ（１−ｘｔ）に当分は限られる。集積回路のハードウエア化が可能なカオス発生器はロジスティック写像ｃ＝４．０の場合に限られるからである。
【０００３】
【従来の技術】
ロジスティック写像ｃ＝４．０、すなわちｘｔ＋１＝４ｘｔ（１−ｘｔ）、ｘｔ＝ｘｔ＋１の写像がリヤプノフ指数λ＝１ｎ２＝０．６９３…のカオスを生成することは、既によく知られている。同相変換量子化Ｙｔ．ｎ＝［２／π・ａｒｃｓｉｎ（ｘｔ）１／２・２ｎ］が優れたカオスの観測手法であり、また優れた初期値の与え方であることも知られている。カオスという現象は、精度の高い計算問題（数値計算）の中で現れるから、矛盾するようではあるが、ディジタルコンピュータの限られた精度の計算能力に依存せざるをえない。すなわち、ＯＳ上では浮動小数点６４ビット倍精度、有効数字５２ビットの数値計算能力で制限をもうけてもやむをえない。
【０００４】
ディジタルコンピュータが論理処理を得意とし、数値演算を得意としないこともよく知られている。バイトや２バイトを単位としたデータ処理に都合がいいようにＯＳは提供されているが、ビット操作には時間はかかっても、あらゆる組合せのバイナリーデータを扱うときには、ビット操作は欠かすことができない。
【０００５】
浮動小数点６４ビット倍精度、有効数字５２ビットでロジスティック写像を繰り返し計算し、同相変換量子化ｎ＝１で得られる擬似乱数Ｙｔ，１が、公平な組合せと公平な順列を大量に生成し、複雑な組合せ問題の解決に有用であることは知られている。初期値から繰り返し再生できる擬似乱数Ｙｔ，１は有効な産業技術となりうる。同相変換量子化ｎ（ｎ≦２６）でえられるタイムシリーズＹｔ，ｎは、原理的にＹｔ，ｎと等価である。
【０００６】
【発明が解決しようとする課題】
ディジタルコンピュータのＯＳ上で、浮動小数点６４ビット倍精度、有効数字５２ビットでタイムシリーズＹｔ，１を計算したとき、２つの解決されねばならない課題があらわれる。１つはＯＳ上のプログラムでロジスティック写像を計算したとき、１回の写像の計算に１μｓぐらいを必要とする。すなわち、１００万個の擬似乱数の生成に１秒もかかってしまう。ディジタルコンピュータを人間が使うときの待ち時間、約１秒では、たいした問題解決ができないことを意味している。
【０００７】
擬似乱数が周期にはいったのでは、問題解決能力はなくなる。ロジスティック写像を限られた有効数字のもとで計算した場合、すべての可能な組合せの１／２乗程度で周期に入ってしまうことが知られている。有効数字５２ビットの場合、２２６〜１０８である。１６都市のＴＳＰ（ｔｒａｖｅｌｉｎｇ　ｓａｌｅｓｍａｎ　ｐｒｏｂｌｅｍ、巡回セールスマン問題）で４ビットコード１６種類の順列１６！＝２．０９×１０１３通りを必要とするが１０３の長さの擬似乱数から０〜１５の順列を取り出したのでは、問題解決には不足である。これが第２の問題である。
【０００８】
【課題を解決するための手段】
かかる課題を解決するためには、２つの手法が考えられる。まず生成速度を向上させるためには、ロジスティック写像専用計算チップを用意するとよい。ＯＳ上での演算が浮動小数点計算であったのに対し、専用ＬＳＩまたは専用ＦＰＧＡであれば固定小数点乗算器がよい。ロジスティック写像計算のコアであるｘｔ（１−ｘｔ）専用乗算器とする。
【０００９】
固定小数点乗算器の計算精度は、内部状態ｘｔのビット幅を長くするとよい。シミュレーションだけのためでなく、ディジタルコンピュータが備わっている環境では、ディジタルコンピュータ上での固定小数点演算も考慮に入れておく方がよい。ＯＳ上で固定小数点演算を行うと、遅いことは常識である。ある環境を有効に活用するためには大切な配慮である。
【００１０】
一般論として、数値計算をともなう問題解決をディジタルコンピュータに求めたとき、数値計算をビット操作の論理処理に置き換えられるものなら、置き換えてしまいたい。そのためには、数値処理の過程を逐次解析して、ビット操作による論理処理の方法を具体的に発見していかねばならない。本案はその具体例である。
【００１１】
【作用】
説明をわかりやすく、簡単にするために、内部状態ｘｔが１０ビットの２進コードで与えられるロジスティック写像ワンサイクルの計算過程を図１に示す。実用的には、５２ビット、６４ビット、１２８ビットが設計される。ブロック１は掛ける数ｘｔ１０ビットである。１０進数で７１４という整数である。ブロック２は掛けられる数（１−ｘｔ）である１−ｘｔはｘｔの反転プラス１すなわち補数である。整数で３１０を意味する。乗算結果ブロック１１は２２１、３４０である。
【００１２】
ブロック３はブロック１をブロック２の最下位１ビットの位置にシフトした値である。ブロック４はブロック１をブロック２の２番目の下位１ビットの位置にシフトした値である。ブロック３とブロック４は加算され、ブロック５が加算結果である。
【００１３】
ブロック３と４にまたがって点線の囲いで示した部分２０は、加算において桁上げが生じる部分である。桁上げをともなわない領域での加算のルールは、（００）は０、（０１）は１、（１０）は１をおろすビット操作である。桁上げ領域２０でのビット操作は下から、（１１）は０、（０１）は０、（１０）は０、ここではあらわれていないが（１１）があらわれたら１をおろす、（００）を見つけたら１をおろす。
【００１４】
最初の加算結果ブロック５に、次のブロック６をおろし、同様の加算のためのビット操作を行い、加算結果ブロック７がえられる。同様の操作をもう２回繰り返すと乗算結果のブロック１１がえられる。
【００１５】
ブロック１の１０ビットと、その補数プラス１のブロック２の１０ビットとの乗算結果はブロック１１に示すように２０ビットとなる。その先頭２ビットは常に００となっている。この００、２ビットを最下位に移動させることが、４倍算である。この４倍算を実行する必要はない。乗算結果が３ビット目からだということを知っておくだけで十分である。
【００１６】
フィードバックすべき内部状態ｘｔ＋１の１０ビットは、先頭３ビット目からの１０ビットである。乗算結果ブロック１１の２０ビットの中から、先頭３ビット目からの１０ビットすなわち整数８６４が次の写像の計算のためにブロック１に戻され、残りの１０ビットは捨てられる。
【００１７】
擬似乱数のタイムシリーズＹｔ，１は、乗算結果ブロック１１の先頭３ビット目の１ビットである。
【００１８】
汎用固定小数点乗算器が、計算能力すなわち計算精度を向上させようとして整数のビット幅を拡げたとき、困難に直面するのは、桁上げのレーシングである。図１の本案手法が桁上げのレーシングから解放されていることは明らかである。その理由は、補数の掛け算であること、逐次分解して桁上げをビット操作のルールに置き換えられているからである。
【００１９】
【実施例】
産業用のニーズは、５２ビット固定小数点乗算器のＦＰＧＡによる実現にある。浮動小数点６４ビット、有効数字５２ビットでの切り捨てモードでのシミュレーションが可能である、ということからきている。８万ゲート規模のＦＰＧＡで、１回の写像時間の平均５０ｎｓが実現できている。浮動小数点６４ビット倍精度、有効数字５２ビットのとき１回の写像時間が１μｓであるのに比べると高速化されているといえる。
【００２０】
一方、ＯＳ上の５２ビット固定小数点演算で桁上げ加算を行ったときには、１回の写像の計算に５０μｓは必要となる。本案のビット操作により実行すると、１回の写像時間を１０μｓにまで短くすることができる。
【００２１】
ＦＰＧＡで本案の固定小数点乗算器を実現する場合、ビット幅の拡張にともなってゲート数が２乗に比例して増大し、１回当たりの写像時間はビット幅に比例して大きくなる。最終的には、最小線幅の小さいウエハプロセス技術を駆使して計算精度を向上させ、１回当たりの写像に要する時間を短くする努力がなされる。
【００２２】
【発明の効果】
ロジスティック写像の固定小数点乗算器を、加算桁上げという数値計算処理を行うことなく、ルールにもとづくビット操作の論理判別だけで実行し、桁上げレーシングの問題を解決した。５２ビット固定小数点乗算器が生成する擬似乱数Ｙｔ，１を複数並列に動作させることにより、１６都市のＴＳＰの最短経路を求められる程度の問題解決能力に到達できている。
【図面の簡単な説明】
【図１】ロジスティック写像１０ビット固定小数点乗算器である。
【符号の説明】
１　掛ける数　　　ｘｔ（１０ビット）：７１４
2004127210.tif 000003
３〜１０　　乗算の途中経過
１１　　　　乗算結果（２０ビット）：２２１，３４０
２０〜２７　桁上げを必要とする領域
【図１】
2004127210.tif 000004