(57)【特許請求の範囲】
【請求項１】
所定精度の引数に対して適用されると当該所定精度の結果を返す関数fの適用が、当該所定精度の引数を参照して第１の演算列に含まれる演算を順に実行することによって計算され、漸化式
xi+1 = f(xi)  (i≧0)
を当該所定精度の数に対して用いると乱数列x0，x1，x2，…が得られる関数fに対応付けられる乱数列生成装置であって、
当該所定精度の初期値x0を取得する初期値取得部、
ビット列
b0，b1，b2，…
を取得するビット列取得部、
前記取得されまたはすでに計算された当該所定精度の数xi  (i≧0)を参照して第２の演算列に含まれる演算を順に実行することによって得られる結果を計算して、これを当該所定精度の次項xi+1とする次項計算部、
前記取得されまたは前記計算された当該所定精度の数
x0，x1，x2，…
を乱数列として出力する乱数列出力部
を備え、
前記次項計算部は、当該第２の演算列として、当該第１の演算列に含まれる演算のいずれか１つ以上の後に、前記取得されたビット列を順に参照して当該ビットの値に応じて当該演算の結果を修正する演算を挿入した演算列を用いる
ことを特徴とするもの。
【請求項２】
所定精度の引数に対して適用されると当該所定精度の結果を返す関数fの適用が、当該所定精度の引数を参照して第１の演算列に含まれる演算を順に実行することによって計算され、漸化式
xi+1 = f(xi) (i≧0)
を当該所定精度の数に対して用いると乱数列x0，x1，x2，…が得られる関数fに対応付けられる乱数列生成装置であって、
当該所定精度の初期値x0を取得する初期値取得部、
ビット列
b0，b1，b2，…
を取得するビット列取得部、
前記取得されまたはすでに計算された当該所定精度の数xi (i≧0)を参照して第２の演算列に含まれる演算を順に実行することによって得られる結果を計算して、これを当該所定精度の次項xi+1とする次項計算部、
前記取得されまたは前記計算された当該所定精度の数
x0，x1，x2，…
を乱数列として出力する乱数列出力部
を備え、
前記次項計算部は、当該第２の演算列として、当該第１の演算列に含まれる演算のいずれか２つ以上の後に、前記取得されたビット列を順に参照して当該ビットの値に応じて当該演算の結果を修正する演算を挿入した演算列を用いる
ことを特徴とするもの。
【請求項３】
所定精度の引数に対して適用されると当該所定精度の結果を返す関数fの適用が、当該所定精度の引数を参照して第１の演算列に含まれる演算を順に実行することによって計算され、漸化式
xi+1 = f(xi) (i≧0)
を当該所定精度の数に対して用いると乱数列x0，x1，x2，…が得られる関数fに対応付けられる乱数列生成装置であって、
当該所定精度の初期値x0を取得する初期値取得部、
ビット列
b0，b1，b2，…
を取得するビット列取得部、
前記取得されまたはすでに計算された当該所定精度の数xi (i≧0)を参照して第２の演算列に含まれる演算を順に実行することによって得られる結果を計算して、これを当該所定精度の次項xi+1とする次項計算部、
前記取得されまたは前記計算された当該所定精度の数
x0，x1，x2，…
を乱数列として出力する乱数列出力部
を備え、
前記次項計算部は、当該第２の演算列として、当該第１の演算列に含まれる演算のいずれか１つ以上の後に、前記取得されたビット列を順に参照して当該ビットの値が所定の値である場合、当該演算の結果を所定精度のビット列で表現した場合の所定位置のビットの値を反転して当該演算の結果を修正する演算を少なくとも１つ挿入した演算列を用いる
ことを特徴とするもの。
【請求項４】
所定精度の引数に対して適用されると当該所定精度の結果を返す関数fの適用が、当該所定精度の引数を参照して第１の演算列に含まれる演算を順に実行することによって計算され、漸化式
xi+1 = f(xi) (i≧0)
を当該所定精度の数に対して用いると乱数列x0，x1，x2，…が得られる関数fに対応付けられる乱数列生成装置であって、
当該所定精度の初期値x0を取得する初期値取得部、
ビット列
b0，b1，b2，…
を取得するビット列取得部、
前記取得されまたはすでに計算された当該所定精度の数xi (i≧0)を参照して第２の演算列に含まれる演算を順に実行することによって得られる結果を計算して、これを当該所定精度の次項xi+1とする次項計算部、
前記取得されまたは前記計算された当該所定精度の数
x0，x1，x2，…
を乱数列として出力する乱数列出力部
を備え、
前記次項計算部は、当該第２の演算列として、当該第１の演算列に含まれる演算のいずれか１つ以上の後に、前記取得されたビット列を順に参照して当該ビットの値に応じて当該ビットの値が所定の値である場合、当該演算の結果を所定精度のビット列で表現した値に、所定の整数値（所定位置のビットの値を１とし、その他の位置のビットが０である整数値を含む。）を加算もしくは減算して当該演算の結果を修正する演算を少なくとも１つ挿入した演算列を用いる
ことを特徴とするもの。
【請求項５】
請求項３または４に記載の乱数列生成装置であって、
当該所定位置のビットは、当該演算の結果を当該所定精度のビット列で表現した場合の最下位ビットに相当する
ことを特徴とするもの。
【請求項６】
請求項３または４に記載の乱数列生成装置であって、
当該所定の値は１である
ことを特徴とするもの。
【請求項７】
請求項１から６のいずれか１項に記載の乱数列生成装置であって、
当該第１の演算列に含まれる演算は、前回の計算の結果の取得、当該取得された計算の結果およびそれまでの演算の結果に対する加減算ならびに乗算を含む
ことを特徴とするもの。
【請求項８】
請求項１から７のいずれか１項に記載の乱数列生成装置であって、
当該関数fは、2以上の整数aに対して
Ta(cosθ) = T(cos aθ)
により定義されるチェビシェフ多項式のいずれかにより、
f(x) = Ta(x)
と定義される
ことを特徴とするもの。
【請求項９】
請求項１から７のいずれか１項に記載の乱数列生成装置であって、
当該関数fは、当該所定精度で固定小数点表現された値に対して適用され、2以上の整数Nに対して、当該固定小数点表現された値を整数値と解釈した場合に、整数演算により
f(x) = 2x(x+1) mod 2N
と定義される
ことを特徴とするもの。
【請求項１０】
所定精度の引数に対して適用されると当該所定精度の結果を返す関数fの適用が、当該所定精度の引数を参照して第１の演算列に含まれる演算を順に実行することによって計算され、漸化式
xi+1 = f(xi)  (i≧0)
を当該所定精度の数に対して用いると乱数列x0，x1，x2，…が得られる関数fに対応付けられ、初期値取得部、ビット列取得部、次項計算部、乱数列出力部を備える乱数列出力装置にて実行される乱数列生成方法であって、
前記初期値取得部が、当該所定精度の初期値x0を取得する初期値取得工程、
前記ビット列取得部が、ビット列
b0，b1，b2，…
を取得するビット列取得工程、
前記次項計算部が、前記取得されまたはすでに計算された当該所定精度の数xi  (i≧0)を参照して第２の演算列に含まれる演算を順に実行することによって得られる結果を計算して、これを当該所定精度の次項xi+1とする次項計算工程、
前記乱数列出力部が、前記取得されまたは前記計算された当該所定精度の数
x0，x1，x2，…
を乱数列として出力する乱数列出力工程
を備え、
前記次項計算工程では、当該第２の演算列として、当該第１の演算列に含まれる演算のいずれか１つ以上の後に、前記取得されたビット列を順に参照して当該ビットの値に応じて当該演算の結果を修正する演算を挿入した演算列を用いる
ことを特徴とする方法。
【請求項１１】
所定精度の引数に対して適用されると当該所定精度の結果を返す関数fの適用が、当該所定精度の引数を参照して第１の演算列に含まれる演算を順に実行することによって計算され、漸化式
xi+1 = f(xi) (i≧0)
を当該所定精度の数に対して用いると乱数列x0，x1，x2，…が得られる関数fに対応付けられ、初期値取得部、ビット列取得部、次項計算部、乱数列出力部を備える乱数列出力装置にて実行される乱数列生成方法であって、
前記初期値取得部が、当該所定精度の初期値x0を取得する初期値取得工程、
前記ビット列取得部が、ビット列
b0，b1，b2，…
を取得するビット列取得工程、
前記次項計算部が、前記取得されまたはすでに計算された当該所定精度の数xi (i≧0)を参照して第２の演算列に含まれる演算を順に実行することによって得られる結果を計算して、これを当該所定精度の次項xi+1とする次項計算工程、
前記乱数列出力部が、前記取得されまたは前記計算された当該所定精度の数
x0，x1，x2，…
を乱数列として出力する乱数列出力工程
を備え、
前記次項計算工程では、当該第２の演算列として、当該第１の演算列に含まれる演算のいずれか２つ以上の後に、前記取得されたビット列を順に参照して当該ビットの値に応じて当該演算の結果を修正する演算を挿入した演算列を用いる
ことを特徴とする方法。
【請求項１２】
所定精度の引数に対して適用されると当該所定精度の結果を返す関数fの適用が、当該所定精度の引数を参照して第１の演算列に含まれる演算を順に実行することによって計算され、漸化式
xi+1 = f(xi) (i≧0)
を当該所定精度の数に対して用いると乱数列x0，x1，x2，…が得られる関数fに対応付けられ、初期値取得部、ビット列取得部、次項計算部、乱数列出力部を備える乱数列出力装置にて実行される乱数列生成方法であって、
前記初期値取得部が、当該所定精度の初期値x0を取得する初期値取得工程、
前記ビット列取得部が、ビット列
b0，b1，b2，…
を取得するビット列取得工程、
前記次項計算部が、前記取得されまたはすでに計算された当該所定精度の数xi (i≧0)を参照して第２の演算列に含まれる演算を順に実行することによって得られる結果を計算して、これを当該所定精度の次項xi+1とする次項計算工程、
前記乱数列出力部が、前記取得されまたは前記計算された当該所定精度の数
x0，x1，x2，…
を乱数列として出力する乱数列出力工程
を備え、
前記次項計算工程では、当該第２の演算列として、当該第１の演算列に含まれる演算のいずれか１つ以上の後に、前記取得されたビット列を順に参照して当該ビットの値が所定の値である場合、当該演算の結果を所定精度のビット列で表現した場合の所定位置のビットの値を反転して当該演算の結果を修正する演算を少なくとも１つ挿入した演算列を用いる
ことを特徴とする方法。
【請求項１３】
所定精度の引数に対して適用されると当該所定精度の結果を返す関数fの適用が、当該所定精度の引数を参照して第１の演算列に含まれる演算を順に実行することによって計算され、漸化式
xi+1 = f(xi) (i≧0)
を当該所定精度の数に対して用いると乱数列x0，x1，x2，…が得られる関数fに対応付けられ、初期値取得部、ビット列取得部、次項計算部、乱数列出力部を備える乱数列出力装置にて実行される乱数列生成方法であって、
前記初期値取得部が、当該所定精度の初期値x0を取得する初期値取得工程、
前記ビット列取得部が、ビット列
b0，b1，b2，…
を取得するビット列取得工程、
前記次項計算部が、前記取得されまたはすでに計算された当該所定精度の数xi (i≧0)を参照して第２の演算列に含まれる演算を順に実行することによって得られる結果を計算して、これを当該所定精度の次項xi+1とする次項計算工程、
前記乱数列出力部が、前記取得されまたは前記計算された当該所定精度の数
x0，x1，x2，…
を乱数列として出力する乱数列出力工程
を備え、
前記次項計算工程では、当該第２の演算列として、当該第１の演算列に含まれる演算のいずれか１つ以上の後に、前記取得されたビット列を順に参照して当該ビットの値が所定の値である場合、当該演算の結果を所定精度のビット列で表現した値に、所定の整数値（所定位置のビットの値を１とし、その他の位置のビットが０である整数値を含む。）を加算もしくは減算して修正する演算を挿入した演算列を用いる
ことを特徴とする方法。
【請求項１４】
請求項１２または１３に記載の乱数列生成方法であって、
当該所定位置のビットは、当該演算の結果を当該所定精度のビット列で表現した場合の最下位ビットに相当する
ことを特徴とする方法。
【請求項１５】
請求項１２または１３に記載の乱数列生成方法であって、
当該所定の値は１である
ことを特徴とする方法。
【請求項１６】
請求項１０から１５のいずれか１項に記載の乱数列生成方法であって、
当該複数の演算は、前回の計算の結果の取得、当該取得された計算の結果およびそれまでの演算の結果に対する加減算ならびに乗算を含む
ことを特徴とする方法。
【請求項１７】
請求項１０から１６のいずれか１項に記載の乱数列生成方法であって、
当該関数fは、2以上の整数aに対して
Ta(cosθ) = T(cos aθ)
により定義されるチェビシェフ多項式のいずれかにより、
f(x) = Ta(x)
と定義される
ことを特徴とする方法。
【請求項１８】
請求項１０から１６のいずれか１項に記載の乱数列生成方法であって、
当該関数fは、当該所定精度で固定小数点表現された値に対して適用され、2以上の整数Nに対して、当該固定小数点表現された値を整数値と解釈した場合に、整数演算により
f(x) = 2x(x+1) mod 2N
と定義される
ことを特徴とする方法。
【請求項１９】
請求項１から９のいずれか１項に記載の乱数列生成装置であって、
前記取得されるビット列は、乱数ビット列である
ことを特徴とするもの。
【請求項２０】
請求項１０から１８のいずれか１項に記載の乱数列生成方法であって、
前記取得されるビット列は、乱数ビット列である
ことを特徴とする方法。
【請求項２１】
コンピュータを、請求項１から９または１９のいずれか１項に記載の乱数列生成装置として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、乱数列生成装置、乱数列生成方法、ならびに、これらをコンピュータ上にて実現するプログラムに関する。
【０００２】
【従来の技術】
従来から、漸化式を用いて乱数を発生させる手法が良く知られている。すなわち、初項x0を与えた場合に、所定の関数fを用いて、整数i  (i≧0)に対して順次漸化式
xi+1 = f(xi)
を計算することにより、数列
x0，x1，x2，…
を得て、これを乱数として扱う、というものである。
【０００３】
漸化式で用いる関数fとしては、たとえば、線形合同法、Knuthの方法、Ｍ系列、Wichmann-Hillの方法などが知られており、ある数を乗算した結果を他の数で除算した余りを用いるなどの手法が広く使われている。このほか、発明者が種々の手法を提案しているカオス乱数の分野では、関数fとしてチェビシェフ多項式を用いる場合の乱数列の性質についても研究が進められており、無限精度で計算を行った場合には、乱数列に周期がなくなる、という特徴がある。
【０００４】
【発明が解決しようとする課題】
しかしながら、従来から知られている手法やカオス乱数の手法も含め、このような漸化式の計算を実際にコンピュータで行うと、生成される数値に偏りが生じてしまうことが多い。この偏りには、得られる乱数列の数値上の偏りのほか、当該乱数列に含まれる数値のそれぞれを、所定桁数の２進数で表現した場合、各桁についての「０」と「１」の出現頻度の偏りなどがある。
【０００５】
そこで、精度が制限された数値計算においても、従来と同じ漸化式を利用した場合であっても、生成される乱数が上記のような意味で偏りの少ないものとできる手法が強く望まれている。
【０００６】
本発明は、このような課題を解決するものであって、乱数列生成装置、乱数列生成方法、ならびに、これらをコンピュータ上にて実現するプログラムを提供することを目的とする。
【０００７】
【課題を解決するための手段】
以上の目的を達成するため、本発明の原理にしたがって、下記の発明を開示する。
【０００８】
本発明の第１の観点に係る乱数列生成装置は、複数の演算により表現される関数fを用いた漸化式
xi+1 = f(xi)  (i≧0)
を所定精度の数において用いて、乱数列x0，x1，x2，…を発生させ、初期値取得部と、ビット列取得部と、次項計算部と、乱数列出力部と、を備え、以下のように構成する。
【０００９】
すなわち、初期値取得部は、当該所定精度の初期値x0を取得する。
【００１０】
一方、ビット列取得部は、ビット列
b0，b1，b2，…
を取得する。
【００１１】
さらに、次項計算部は、取得されまたはすでに計算された当該所定精度の数xi  (i≧0)に、当該複数の演算を施して当該関数fを適用して、当該所定精度の次項xi+1を計算する。
【００１２】
そして、乱数列出力部は、取得されまたは計算された当該所定精度の数
x0，x1，x2，…
を乱数列として出力する。
【００１３】
一方、次項計算部は、当該複数の演算のいずれか１つ以上の後において、取得されたビット列を順に参照し、当該ビットの値に応じて当該演算の結果を修正して、当該関数fを適用する。
【００１４】
また、本発明の乱数列生成装置は、次項計算部において、「当該複数の演算のいずれか１つ以上の後」にかえて「当該複数の演算のいずれか２つ以上の後」とするように構成することができる。
【００１５】
また、本発明の乱数列生成装置において、次項計算部による当該演算の結果の修正のいずれかは、「当該ビットの値が所定の値である場合、当該演算の結果を所定精度のビット列で表現した場合の所定位置のビットの値を反転する」ことであるように構成することができる。
【００１６】
また、本発明の乱数列生成装置において、次項計算部による当該演算の結果の修正のいずれかは、「当該ビットの値が所定の値である場合、当該演算の結果を所定精度のビット列で表現した値に、所定の整数値（所定位置のビットの値を１とし、その他の位置のビットが０である整数値を含む。）を加算もしくは減算する」ことであるように構成することができる。
【００１７】
また、本発明の乱数列生成装置において、当該所定位置のビットは、当該演算の結果を当該所定精度のビット列で表現した場合の最下位ビットに相当するように構成することができる。
【００１８】
また、本発明の乱数列生成装置において、「当該ビットの値が所定の値である場合」は、「当該ビットの値が１である場合」であるように構成することができる。
【００１９】
また、本発明の乱数列生成装置において、当該複数の演算は、前回の計算の結果の取得、当該取得された計算の結果およびそれまでの演算の結果に対する加減算ならびに乗算を含むように構成することができる。
【００２０】
また、本発明の乱数列生成装置において、当該関数fは、2以上の整数aに対して
Ta(cosθ) = T(cos aθ)
により定義されるチェビシェフ多項式のいずれかにより、
f(x) = Ta(x)
と定義されるように構成することができる。
【００２１】
また、本発明の乱数列生成装置において、当該関数fは、当該所定精度で固定小数点表現された値に対して適用され、2以上の整数Nに対して、当該固定小数点表現された値を整数値と解釈した場合に、整数演算により
f(x) = 2x(x+1) mod 2N
と定義されるように構成することができる。
【００２２】
本発明のその他の観点に係る乱数列生成方法は、複数の演算により表現される関数fを用いた漸化式
xi+1 = f(xi)  (i≧0)
を所定精度の数において用いて、乱数列x0，x1，x2，…を発生させ、初期値取得工程と、ビット列取得工程と、次項計算工程と、乱数列出力工程と、を備え、以下のように構成する。
【００２３】
すなわち、初期値取得工程では、当該所定精度の初期値x0を取得する。
【００２４】
一方、ビット列取得工程では、ビット列
b0，b1，b2，…
を取得する。
【００２５】
さらに、次項計算工程は、取得されまたはすでに計算された当該所定精度の数xi  (i≧0)に、当該複数の演算を施して当該関数fを適用して、当該所定精度の次項xi+1を計算する。
【００２６】
そして、乱数列出力工程は、取得されまたは計算された当該所定精度の数
x0，x1，x2，…
を乱数列として出力する。
【００２７】
一方、次項計算工程では、当該複数の演算のいずれか１つ以上の後において、取得されたビット列を順に参照し、当該ビットの値に応じて当該演算の結果を修正して、当該関数fを適用する。
【００２８】
また、本発明の乱数列生成方法は、次項計算工程において、「当該複数の演算のいずれか１つ以上の後」にかえて「当該複数の演算のいずれか２つ以上の後」とするように構成することができる。
【００２９】
また、本発明の乱数列生成方法において、次項計算工程における当該演算の結果の修正のいずれかは、「当該ビットの値が所定の値である場合、当該演算の結果を所定精度のビット列で表現した場合の所定位置のビットの値を反転する」ことであるように構成することができる。
【００３０】
また、本発明の乱数列生成方法において、次項計算工程における当該演算の結果の修正のいずれかは、「当該ビットの値が所定の値である場合、当該演算の結果を所定精度のビット列で表現した値に、所定の整数値（所定位置のビットの値を１とし、その他の位置のビットが０である整数値を含む。）を加算もしくは減算する」ことであるように構成することができる。
【００３１】
また、本発明の乱数列生成方法において、当該所定位置のビットは、当該演算の結果を当該所定精度のビット列で表現した場合の最下位ビットに相当するように構成することができる。
【００３２】
また、本発明の乱数列生成方法において、「当該ビットの値が所定の値である場合」は、「当該ビットの値が１である場合」であるように構成することができる。
【００３３】
また、本発明の乱数列生成方法において、当該複数の演算は、前回の計算の結果の取得、当該取得された計算の結果およびそれまでの演算の結果に対する加減算ならびに乗算を含むように構成することができる。
【００３４】
また、本発明の乱数列生成方法において、当該関数fは、2以上の整数aに対して
Ta(cosθ) = T(cos aθ)
により定義されるチェビシェフ多項式のいずれかにより、
f(x) = Ta(x)
と定義されるように構成することができる。
【００３５】
また、本発明の乱数列生成方法において、当該関数fは、当該所定精度で固定小数点表現された値に対して適用され、2以上の整数Nに対して、当該固定小数点表現された値を整数値と解釈した場合に、整数演算により
f(x) = 2x(x+1) mod 2N
と定義されるように構成することができる。
【００３６】
本発明のその他の観点に係るプログラムは、コンピュータを、上記の乱数列生成装置として機能させ、または、コンピュータに、上記の乱数列生成方法を実行させるように構成する。
【００３７】
また、当該プログラムは、コンピュータ読取可能な情報記録媒体（コンパクトディスク、フレキスブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、または、半導体メモリを含む。）に記録することができる。
【００３８】
本発明の情報記録媒体に記録されたプログラムを、記憶装置、計算装置、出力装置、通信装置などを備える汎用コンピュータ、携帯電話機、ＰＨＳ装置、ゲーム装置などの携帯端末、並列計算機などの情報処理装置、ＤＳＰ（Digital Signal Processor）、ＦＰＧＡ（Field Programmable Gate Array）などで実行することにより、上記の乱数列生成装置や乱数列生成方法を実現することができる。
【００３９】
また、これらの装置とは独立して、コンピュータ通信網を介して本発明のプログラムそのものを配布、販売したり、当該プログラムを記録した情報記録媒体を商品流通過程において配布、販売することができる。
【００４０】
【発明の実施の形態】
以下に本発明の実施形態を説明する。なお、以下にあげる実施形態は、説明のためのものであり、本発明の範囲を制限するものではない。したがって、当業者であれば、これらの各要素または全要素を、これと均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も、本発明の範囲に含まれる。
【００４１】
（第１の実施の形態）
図１は、本発明の第１の実施の形態に係る乱数列生成装置の概要構成を示す模式図（データフロー図）である。図２は、当該乱数列生成装置において実行される乱数列生成方法の制御の流れを示すフローチャートである。以下、これらの図を参照して説明する。なお、本実施形態では、理解を容易にするため、チェビシェフ多項式を用いたカオス乱数生成の手法に本発明の原理を適用した場合を例にあげて説明するが、他の乱数生成の手法にも、本発明を適用することができる。
【００４２】
乱数列生成装置１０１は、複数の演算により表現される関数fを用いた漸化式
xi+1 = f(xi)  (i≧0)
を所定精度の数において用いて、乱数列x0，x1，x2，…を発生させる。
【００４３】
本実施形態では、関数fとして、チェビシェフ多項式を用いる。図３は、チェビシェフ多項式を表したグラフである。チェビシェフ多項式は、整数aを次数とするとき、
T(a,cosθ)=cos(aθ)
のように、余弦関数の加法定理により定義することができる。一方、以下のように、有理多項式で直接表現することもできる。
T(0,x) = 1
T(1,x) = x
T(2,x) = 2x2-1
T(3,x) = 4x3-3x
【００４４】
チェビシェフ多項式y = T(a,x)は、いずれも、開区間-1<x<1を開区間-1<y<1に写像する有理写像である。
【００４５】
本図には、次数２から５のチェビシェフ多項式が、y = T(2,x)，y = T(3,x)，y = T(4,x)，y = T(5,x)の形式でグラフ表示されている。横軸がｘ軸、縦軸がｙ軸である。
【００４６】
以下では、理解を容易にするため、２次のチェビシェフ多項式により、f(x) = T(2,x)として説明するが、２以上の次数のチェビシェフ多項式であれば、同様に本発明の原理を適用することができる。
【００４７】
この場合、関数fは
f(x) = 2x2-1
と定義されることになるが、この関数は、以下のような演算に分解することができる。すなわち、
（１）値xを取得する。
（２）値xを自乗する。
（３）その結果を２倍する。
（４）その結果から１を減算する。
【００４８】
本発明では、このような演算から１つ以上、好ましくは２つ以上を選択して、その演算の後に、別途得られたビット乱数列によりハーネシングを行う。以下では、上記演算の（１）（２）（４）の後に、ハーネシングを行うものとして、説明を行う。
【００４９】
さて、本実施形態の乱数列生成装置１０１は、初期値取得部１０２と、ビット列取得部１０３と、次項計算部１０４と、乱数列出力部１０５と、を備える。
【００５０】
まず、初期値取得部１０２は、当該所定精度の初期値x0を取得して、これを、コンピュータ内の所定精度の固定小数点表現変数vに格納する（ステップＳ２０１）。変数vは、コンピュータのＲＡＭ（Random Access Memory）上に領域を用意してもよいし、ＣＰＵ（Central Processing Unit）内のレジスタを利用してもよい。
【００５１】
ついで、乱数列出力部１０５は、変数vに格納された値を乱数列の項として出力する（ステップＳ２０２）。以降に説明するように、ステップＳ２０２は、繰り返し実行されるので、乱数列
x0，x1，x2，…
が１回の繰り返しで１つづつ出力されることになる。
【００５２】
さらに、次項計算部１０４は、変数vに対して以下のステップＳ２０１〜Ｓ２１１により、当該関数fを適用して、当該次項を計算し、その値を変数vに格納する。以下、詳細に述べる。
【００５３】
ここで、ビット列取得部１０３は、ビット列
b0，b1，b2，…
を受け付ける。このビット列は、あらかじめ用意しておいてもよいし、別の乱数生成装置によって生成させてもよい。また、十分に長いランダムなビット列をあらかじめ用意しておき、これから巡回的に順次各桁のビットを取得するのでもよい。本実施形態では、周期が225-1のゴールド符号を３種類（１回の繰り返しにおけるハーネシングの回数と同じ数）だけ用意して、これらの先頭から順番に１ビットづつ取り出して並べたものを、このビット列として用いる。
【００５４】
ステップＳ２０２についで、ビット列取得部１０３は、次のビット値を取得する。すなわち、それまでにこのビット列の
b0，b1，…，bi-1
が使われていた場合は、ビット値biを取得する（ステップＳ２０３）。以下に述べるように、本実施形態では、１回の繰り返しでビット列からビット値を３個消費するので、初めてステップＳ２０３を実行する際はiは0であり、以降は、繰り返しが進むごとに３づつ増えていくことになる。
【００５５】
そして、固定小数点表現された変数vを整数と見て、これに対して当該ビット値bi（整数の０か１）との排他的論理和（exclusive or；ｘｏｒ）をとり、その結果を変数vに格納する。すなわち、変数vを整数と見て、ビット値biが１である場合は、その最下位ビットを反転させる（ステップＳ２０４）。以下では単にこの処理を「ｘｏｒをとる」という。これは、上記演算（１）の後にハーネシングを行うことに相当する。
【００５６】
さらに、変数vに変数vの値を乗算して、結果を変数vに格納する（ステップＳ２０５）。
【００５７】
ついで、ビット列取得部１０３は、次のビット値bi+1を取得する（ステップＳ２０６）。
【００５８】
そして、変数vとビット値bi+1とのｘｏｒをとって、上記演算（２）の後のハーネシングを行う（ステップＳ２０７）。
【００５９】
さらに、変数vの値を２倍して、結果を変数vに格納する（ステップＳ２０８）。
【００６０】
そして、変数vから１を減算して、結果を変数vに格納する（ステップＳ２０９）。
【００６１】
ついで、ビット列取得部１０３は、次のビット値bi+2を取得する（ステップＳ２１０）。
【００６２】
変数vとビット値bi+2とのｘｏｒをとって、上記演算（４）の後のハーネシングを行い（ステップＳ２１１）、ステップＳ２０２に戻る。
【００６３】
このように、本実施形態では、別途用意された乱数ビット列
b0，b1，b2，…
により、関数fの適用に必要な演算で得られた結果の最下位ビットをハーネシングにより修正して、生成される乱数列の偏りを減らす。
【００６４】
さて、チェビシェフ多項式を用いる場合には、初期値として-1<x0<1を採用した場合には、値域と定義域がいずれも開区間(-1,1)となるから、固定小数点表現で演算を行うのに適している。以下、上記の２次のチェビシェフ多項式で、１６ビット固定小数点表現を採用した場合の演算について詳細に説明する。
【００６５】
まず、演算は、上記のように４段階に分けることができる。１６ビット固定小数点表現で開区間(-1,1)を表現する場合は、最上位ビットは符号ビットとするのが一般的である。0xを十六進数を表す接頭辞とすると、以下のような対応関係が成り立つ。
0x0000は、実数値0に相当する。
0x7fffは、実数値1よりも小さい、この固定小数点表現で表現可能な最大数に相当する。
0x8000は、実数値-1に相当する。
0xffffは、この固定小数点表現で表現可能な０に最も近い負の数に相当する。
【００６６】
そこで、上記の演算のそれぞれに対応させて説明する。
（１）値xを取得する。これは、変数vに格納された１６ビットの値をそのまま用いることとなる。
（２）値xを自乗する。これは、変数vに格納されたものを１６ビットの整数とみて、１６ビット同士の整数の乗算を行うことと等価である。結果は３２ビットとなるので、結果の上位１６ビットを変数vに格納する。
（３）その結果を２倍する。これは、左への１ビットシフト演算で表現できる。
（４）その結果から１を減算する。これは、上記のように、変数vを整数値とみて、0x7fffを減算することと等価である。
【００６７】
このほか、以下のような計算を行ってもよい。
（１）値xを取得する。変数vに格納された１６ビットの値を１６ビットレジスタに格納する。
（２）値xを自乗する。上記の１６ビットレジスタの値を自身と乗算して、結果を３２ビットレジスタに得る。
（３）その結果を２倍する。上記の３２ビットレジスタを左へ１ビットシフトする。
（４）その結果から１を減算する。上記の３２ビットレジスタから、３２ビットの1に相当する値0x7fffffffを減算する。
（５）さらに、結果を１６ビットに戻すため、上記の３２ビットレジスタの上位１６ビットで表現される値を変数vに格納する。
【００６８】
このように、チェビシェフ多項式の計算は、ＣＰＵで高速に実行できる整数演算に帰着させることができるため、これとｘｏｒを用いれば、高速な乱数生成が可能となる。
【００６９】
（その他の実施形態）
上記実施形態では、ビット列から得たビット値と、変数vの最下位ビットとの排他的論理和をとることにより、ビット値が１の場合に変数vの最下位ビットを反転することとしていたが、排他的論理和のかわりに、以下のような演算を用いることができる。
（１）ビット値が１の場合は、変数vに「最下位ビットが１でそのほかのビットが０である値」を加算する。すなわち、変数vを整数値とみて、得られたビット値をそのまま加算する。
（２）ビット値が１の場合は、変数vから「最下位ビットが１でそのほかのビットが０である値」を減算する。すなわち、変数vを整数値とみて、得られたビット値をそのまま減算する。
【００７０】
また、最下位ビットではなくて、その他のビット位置を採用してもよい。たとえば、最下位よりも１つ桁が上のビット位置を採用してもよい。
【００７１】
また、各ハーネシングごとに、上記の手法のいずれかを選択し、ハーネシングごとに異なる手法を採用することもできる。
【００７２】
さらに、所定精度で固定小数点表現された値に対して適用される関数fとして、2以上の整数Nに対して、当該固定小数点表現された値を整数値と解釈した場合に、整数演算により
f(x) = 2x(x+1) mod 2N
と定義されるものを採用することもできる。これは、チェビシェフ多項式の実数計算に相当する整数による演算である。
【００７３】
このほか、固定小数点表現ではなく、浮動小数点表現を用いて、仮数部の所定位置のビット（たとえば、仮数部の最下位ビット）に対して、上記ｘｏｒをとるなどの処理をする態様も採用でき、これも本発明の範囲に含まれる。
【００７４】
なお、上記のように、周期225-1のゴールド符号を３種類用いて、３回のハーネシングのうち２回は最下位ビットのｘｏｒ、１回は最下位ビットの加算を行ったところ、生成される乱数列の分布がチェビシェフ多項式による力学系で表現される分布と一致するほか、当該値の各ビット位置に0と1が出現する頻度がほぼ等しくなり、FIPS140-1と呼ばれる乱数の性質を調べるテストをパスするなど、良好な乱数を得ることができた。
【００７５】
【発明の効果】
以上説明したように、本発明によれば、乱数列生成装置、乱数列生成方法、ならびに、これらをコンピュータ上にて実現するプログラムを提供することができる。
【図面の簡単な説明】
【図１】  本発明の乱数列生成装置の実施例の概要構成を示す模式図である。
【図２】  当該実施例にて実行される乱数列発生方法の処理の流れを示すフローチャートである。
【図３】  チェビシェフ写像の概要を示すグラフである。
【符号の説明】
１０１  乱数列生成装置
１０２  初期値取得部
１０３  ビット列取得部
１０４  次項計算部
１０５  乱数列出力部
【図１】
0003656057.tif 000002
【図２】
0003656057.tif 000003
【図３】
0003656057.tif 000004