none
オーバーフロー時に溢れたほう(正の数・負の数)の最大値を高速に代入したい RRS feed

  • 質問

  • C = A * B

    の際にオーバーフローする場合、

    正の数の方向に溢れるのであれば、そのデータ型のMaxValue

    負の数の方向に溢れるのであれば、そのデータ型のMinValue

    をCに代入したいのですが、どのような方法が考えられますでしょうか?

    できるだけ、高速に動作させたいと思っています。

    ご助言をいただけるとありがたいです。


    • 編集済み VB User1 2012年5月27日 10:37
    2012年5月27日 4:04

回答

  • VBに関してはあまりわからないのですが(C++使いなもので)十分言語を超えられる内容だと思いましたので

    「数十MB~数百MB」というサイズや、型のバリエーションとか「Double型の-1~1」とかを見てもしやと思ったのですが

    対象のデータとはWAVデータだったりしますか?(違ったらすみませんw)

    少なくとも私はWAVデータを扱うプログラムで全く同じ問題にぶち当たった事があります。


    その時は「プレビュー用は速度重視でいく」ために、VBでいうLong(64bit整数)をはじめとする、『C++などでいうfloat型(VBでいうSingle?)以外すべて』を除外するという手を採用しました。


    ・・・ちょっと回りくどい言い方でしたね。

    プレビュー用はSingle型限定にしたってことです。

    通常1.0f ~ -1.0fぐらいでやりとりされるようにしました。

    (さらに、多少大きくなっても仕様上問題がないので、何度も加算合成が必要な場合もすぐに絶対値1.0f以下に丸める必要がありません。)

    なお、64bit整数を再生できる環境、あるいは求められる場面はそう多くないと思ったので、64bit整数書き出しはまだ対応していません。対応する場合は、その時はプレビュー用ほど速度が求められない、という点があります。

    64bit整数以外ならVB User1さん自身が考えられているように、比較的簡単に出来ますよね?


    また、64bit整数でも色々と考えられる事があります。


    ・一度でも浮動小数演算が含まれるかどうか

    整数同士の演算であれば型が浮動小数でも整数でも桁あふれなどしない限り誤差はなしのはずです。

    C = A * B

    の場合ですが、掛ける倍率はつねに整数でしょうか?

    浮動小数と整数の演算を行う必要が一度でもあれば、誤差は元々存在し得るはずです。


    ・倍率変化(2の累乗以外で割ること)なしで、Doubleに直した場合

    Doubleが仮数部で扱える精度の範囲内で整数*整数をそのまま扱うとかの場合ならば

    そのまま演算出来ます。

    Longで考えると、かなり数が大きくなって来ないと、精度の問題が出ない、ということになります。

    しかし、「オーバーフローするなら丸めたい」ということならば

    それほど完璧に精度の限りを尽くさなければならない状況、でしょうか?

    (もし64bit整数で桁あふれする可能性がありながら完璧に誤差を0にしたい場合は、自分で、あるいは誰かが作った多倍長整数を使用することとなると思います。その場合は速度はもうちょい遅くなります。)

    ・上記私の方法のように、『速度』についてさらにより割り切れるように状況を限定出来ないか

    ・32bitCPUに対応する必要があるかどうか。(その場合は、64bit整数を扱う速度はもともとある程度遅くなります。のでもともとユーザーは速度が多少遅くなることを覚悟しなければなりません。)

    ・キャッシュの問題で、もともとデータ型のサイズが大きくかつ大量のデータ、にアクセスすると遅くなります。(単独の演算ではDoubleの方がSingleより速いCPUでも、かなり膨大な量でかつ同じ要素数なら、Singleの方がDoubleより速くなり得る、など)


    その上で

    ・波形同士の畳み込みみたいな事じゃなくて、一つの定数を全ての数値に対して掛けるだけ、という計算ですよね?

    そうであるならば

    ・64bit整数で扱うべき、最大値、あるいは最小値を、その定数で割った数をmax_, min_とすると、掛ける前の数値がmax_より大きければ上限に丸めるべきとなるし、min_未満なら下限に丸めるべきとなりますね。なので、定数を掛けるのであれば先にその二つを変数に保持しておけば、2回の比較を行う事で出来ると思います。

    (Azuleanさんのおっしゃっているのはこういう意味でしょうか?)

    <↑についてここから一応検証↓>

    最大値が仮に999(==1000-1)で倍率が25の場合。

    999を整数演算で25で割ると39。ここで、39まではOKとなる。

    つまり元の数が39ならば掛けた後は975となるのでオーバーフローしない。

    40ならば1000となり、演算後はオーバーフローする。よって999にセットする。

    上記は割り切れない場合ですが、一応割り切れる場合でも試してみましょう。

    最大値が仮に10000で倍率が10の場合。

    10000を10で割ると1000。ここで、1000まではOKとなる。

    つまり元の数が1000ならば掛けた後は10000となるのでオーバーフローしない。

    1001ならば10010となり、演算後はオーバーフローする。よって10000にセットする。

    ・・・問題ないですよね?

    </ここまで>



    前述したとおり、速度について64bit整数はある程度割り切る必要性があるうえで

    なおかつもし「その2回の比較」を行うことは「速度的に問題外だ」となる、ということでしたら、やっぱり佐祐理さんのご提案のように、アセンブリ言語の出番となる可能性が高いと思います。

    (Overflow FlagのチェックとかはC++とインラインアセンブラだけで出来るのかな?そこはまだ確かめてないです)

    • 編集済み mr.setup 2012年5月28日 9:51
    • 回答としてマーク VB User1 2012年5月28日 12:47
    2012年5月28日 5:34

すべての返信

  • なぜそのような処理を必要としているのでしょうか? 背景を教えてください。場合によってはもっと別の部分を高速化すればいい問題なのかもしれません。

    逆に数値計算がボトルネックとなるようなプログラムならVBよりも別の言語を選択することをお勧めします。

    • 回答の候補に設定 佐祐理 2012年5月29日 15:05
    2012年5月27日 13:17
  • コメントいただき、ありがとうございます。


    わかりやすくshort型で説明しますが、-32768~+32767のデータがあります。

    すでに存在しているデータにユーザーが設定した倍率を掛ける必要があります。

    ちなみにユーザーが指定する倍率は極端に大きな値にはなりません。

    オーバーフローが発生した場合は近い値(最大値[+32767]または最小値[-32768])にするというのが仕様なのです。

    Short型の場合はIntegerで格納しておけば大きほうにオーバーしているか小さい方にオーバーしているか判別できます。

    Integer型の場合はLongで格納しておけば同様に可能です。

    じゃあ、Longはどうすれば?という事なのです。

    >逆に数値計算がボトルネックとなるようなプログラムならVBよりも別の言語を選択することをお勧めします。

    例外が多くなると処理が遅くなることを危惧したためです。

    VBにはどのようにオーバーフローしたか判別する事はできないということなのでしょうか?

    もしくは数学的な観点から溢れることを知るすべはないものかと考えております。


    2012年5月27日 15:50
  • VBにはどのようにオーバーフローしたか判別する事はできないということなのでしょうか?

    たいていは例外で見るものじゃないかなぁと思います。
    ループ中に大量の例外が出る、マウス移動で例外が出る、画面の再描画で例外が出るということでなければ、そこまでクリティカルにならないと思いますが、大量のデータ相手なのでしょうか。

    もしくは数学的な観点から溢れることを知るすべはないものかと考えております。

    <ここから自信なし>最大値をかけ算の一方の値で割った結果、他方の値より小さい数値が得られるならオーバーフローしそうですが、整数演算で誤差を考えると、厳密な閾値にならない…ような気がする。</ここまで>

    なお、元の「数値計算がボトルネックになるようなプログラムなら VB よりも別の言語を選択することをお勧めします」は、例外云々より時間のかかる数値計算のロジックをマネージコードで書くぐらいなら、ネイティブコードで書いた方が速いと言うところからです。


    質問スレッドで解決した場合は、解決の参考になった投稿に対して「回答としてマーク」のボタンを押すことで、同じ問題に遭遇した別のユーザが役立つ投稿を見つけやすくなります。

    2012年5月27日 22:20
    モデレータ
  • いくつもアドバイスがあります。

    作成しているプログラムは大量に計算を行い、計算時間がクリティカルなものなのでしょうか? 繰り返しになりますが、クリティカルでなければ、例外処理を行ったとしても全体としてたいした遅延にはならないはずです。

    速度が重要なプログラムに於いては、アセンブリ言語を使用することになると思います。 x86プロセッサーにはOF; Overflow Flagというものがあり計算結果がオーバーフロー・アンダーフローしたかどうかを演算後に確認することができます。また、SSE2辺りの命令を使用するとオーバーフローした際にMaxValueに変換する機能もあります(たぶんw)。

    数学的な観点で言うと、Math.Log(x, 2)で、2進数におけるxの桁数を取得できます。そして、n進数におけるa桁 × b桁の演算結果は (a+b)桁になります。つまり桁数の合計が31以下ならばIntegerでオーバーフローしないと言えます。まぁこんなこと考えるよりDoubleを使った方が簡単かと。
    # 符号は考慮してません。Math.Log(x, 2)は正確には桁数ではないのでもう少しきちんと数える必要もあります。

    2012年5月27日 23:49
  • Azulenさま,佐祐理さま

    ありがとうございます。

    データ量にすると数十MB~数百MBとなるため,大量という部類に入ると思います。

    補足ですが,対象のデータ型はShort,Integer,Long,Single,Doubleの符号付きのみです。

    計算時間は実用上はVB.NETでもほとんど問題になりません。ただし,まれにオーバー(アンダー)フローだらけのデータを処理する可能性もあるため,速いに越したことはないという意味です。処理速度は現時点では最重要ではありません。

    他の言語で作成するべきなのかもしれませんが,VB以外はC#が読める程度ですので一(イチ)から勉強する必要があります。

    私のスキルや習得時間を考えると現実的ではありません。申し訳ありません。

    Double型の-1~1に変換して処理をした後戻すという方法が現実的かとは思いますが,一度Doubleに変換後に何も処理をせずに元の整数値に戻せなかったため(物凄く小さい誤差ですが),整数のまま処理できないかと考えたのです。私の中での最後の手段です(誤差を無視するという意味で)。

    お二方からの数学的なアドバイスもいただき,ありがとうございます。今はまだちんぷんかんぷんですが,じっくり考えてみます。

    2012年5月28日 3:53
  • VBに関してはあまりわからないのですが(C++使いなもので)十分言語を超えられる内容だと思いましたので

    「数十MB~数百MB」というサイズや、型のバリエーションとか「Double型の-1~1」とかを見てもしやと思ったのですが

    対象のデータとはWAVデータだったりしますか?(違ったらすみませんw)

    少なくとも私はWAVデータを扱うプログラムで全く同じ問題にぶち当たった事があります。


    その時は「プレビュー用は速度重視でいく」ために、VBでいうLong(64bit整数)をはじめとする、『C++などでいうfloat型(VBでいうSingle?)以外すべて』を除外するという手を採用しました。


    ・・・ちょっと回りくどい言い方でしたね。

    プレビュー用はSingle型限定にしたってことです。

    通常1.0f ~ -1.0fぐらいでやりとりされるようにしました。

    (さらに、多少大きくなっても仕様上問題がないので、何度も加算合成が必要な場合もすぐに絶対値1.0f以下に丸める必要がありません。)

    なお、64bit整数を再生できる環境、あるいは求められる場面はそう多くないと思ったので、64bit整数書き出しはまだ対応していません。対応する場合は、その時はプレビュー用ほど速度が求められない、という点があります。

    64bit整数以外ならVB User1さん自身が考えられているように、比較的簡単に出来ますよね?


    また、64bit整数でも色々と考えられる事があります。


    ・一度でも浮動小数演算が含まれるかどうか

    整数同士の演算であれば型が浮動小数でも整数でも桁あふれなどしない限り誤差はなしのはずです。

    C = A * B

    の場合ですが、掛ける倍率はつねに整数でしょうか?

    浮動小数と整数の演算を行う必要が一度でもあれば、誤差は元々存在し得るはずです。


    ・倍率変化(2の累乗以外で割ること)なしで、Doubleに直した場合

    Doubleが仮数部で扱える精度の範囲内で整数*整数をそのまま扱うとかの場合ならば

    そのまま演算出来ます。

    Longで考えると、かなり数が大きくなって来ないと、精度の問題が出ない、ということになります。

    しかし、「オーバーフローするなら丸めたい」ということならば

    それほど完璧に精度の限りを尽くさなければならない状況、でしょうか?

    (もし64bit整数で桁あふれする可能性がありながら完璧に誤差を0にしたい場合は、自分で、あるいは誰かが作った多倍長整数を使用することとなると思います。その場合は速度はもうちょい遅くなります。)

    ・上記私の方法のように、『速度』についてさらにより割り切れるように状況を限定出来ないか

    ・32bitCPUに対応する必要があるかどうか。(その場合は、64bit整数を扱う速度はもともとある程度遅くなります。のでもともとユーザーは速度が多少遅くなることを覚悟しなければなりません。)

    ・キャッシュの問題で、もともとデータ型のサイズが大きくかつ大量のデータ、にアクセスすると遅くなります。(単独の演算ではDoubleの方がSingleより速いCPUでも、かなり膨大な量でかつ同じ要素数なら、Singleの方がDoubleより速くなり得る、など)


    その上で

    ・波形同士の畳み込みみたいな事じゃなくて、一つの定数を全ての数値に対して掛けるだけ、という計算ですよね?

    そうであるならば

    ・64bit整数で扱うべき、最大値、あるいは最小値を、その定数で割った数をmax_, min_とすると、掛ける前の数値がmax_より大きければ上限に丸めるべきとなるし、min_未満なら下限に丸めるべきとなりますね。なので、定数を掛けるのであれば先にその二つを変数に保持しておけば、2回の比較を行う事で出来ると思います。

    (Azuleanさんのおっしゃっているのはこういう意味でしょうか?)

    <↑についてここから一応検証↓>

    最大値が仮に999(==1000-1)で倍率が25の場合。

    999を整数演算で25で割ると39。ここで、39まではOKとなる。

    つまり元の数が39ならば掛けた後は975となるのでオーバーフローしない。

    40ならば1000となり、演算後はオーバーフローする。よって999にセットする。

    上記は割り切れない場合ですが、一応割り切れる場合でも試してみましょう。

    最大値が仮に10000で倍率が10の場合。

    10000を10で割ると1000。ここで、1000まではOKとなる。

    つまり元の数が1000ならば掛けた後は10000となるのでオーバーフローしない。

    1001ならば10010となり、演算後はオーバーフローする。よって10000にセットする。

    ・・・問題ないですよね?

    </ここまで>



    前述したとおり、速度について64bit整数はある程度割り切る必要性があるうえで

    なおかつもし「その2回の比較」を行うことは「速度的に問題外だ」となる、ということでしたら、やっぱり佐祐理さんのご提案のように、アセンブリ言語の出番となる可能性が高いと思います。

    (Overflow FlagのチェックとかはC++とインラインアセンブラだけで出来るのかな?そこはまだ確かめてないです)

    • 編集済み mr.setup 2012年5月28日 9:51
    • 回答としてマーク VB User1 2012年5月28日 12:47
    2012年5月28日 5:34
  • mr.setupさま

    >・64bit整数で扱うべき、最大値、あるいは最小値を、その定数で割った数をmax_, min_とすると、~

    たいへんわかりやすい解説、ありがとうございます。この方法で解決できそうです。

    >C = A * B

    >の場合ですが、掛ける倍率はつねに整数でしょうか?

    >浮動小数と整数の演算を行う必要が一度でもあれば、誤差は元々存在し得るはずです。

    倍率は浮動小数である事が多いです。

    -1.0d~1.0dへの変換誤差・整数へ戻す際の誤差というのがどうにも気持ち悪くて、精神的によろしくないと思った次第です。

    技術的な根拠はありません。

    >対象のデータとはWAVデータだったりしますか?(違ったらすみませんw)

    すべてお見通しのようですね(笑) おっしゃるとおり、PCM形式のデータを対象としています。

    速度については恐らく問題ないと思いますので、このまま.NET Frameworkベースで開発するつもりです。

    Azuleanさま、佐祐理さま、mr.setupさま

    この度は貴重なご助言をいただきまして、誠にありがとうございました。

    2012年5月28日 12:47
  • やはりVBを使うべきではないように思います。

    速度を気にされているようですが、計算コストが全然理解できていないです。質問に「高速に」としか書かれていなかったので整数×整数と勝手に勘違いしていました。整数×整数は高速ですが、整数×浮動小数は低速です。

    更に浮動小数が絡んでくるとVBには別の問題が出てきます。VBの整数処理は銀行型丸めという特殊な処理がされています。これにより1.5を整数にすると2になり0.5を整数にすると1ではなく0になります。そもそも意図しない値になり得ますし、この処理のせいで「遅くなる」と言えます。(オーバーフローの処理速度が気になるレベルであれば)

    先のコメントでSSE2を紹介しましたが、これがまさに音声などマルチメディア処理のための命令で、データサイズにもよりますが、2個・4個・8個のデータを同時に計算するため、1つずつ計算するより2倍・4倍・8倍速くなります。そしてこの命令はVBからは使うことができません。

    速度を意識するのなら、速度差のわかる環境で開発すべきです。

    2012年5月28日 22:17
  • >おっしゃるとおり、PCM形式のデータを対象としています。

    そうですかw 

    ※この時点で、あとは自分で気になり次第気になった部分を実験したり調べていただく事で、まぁ細かいとこはいっかなと思ったのですが

    佐祐理さんが細かいところを穴埋めされる、という事でしたら、せっかくなので私もちょいちょい穴埋めさせてください。


    倍率は浮動小数である事が多いです。

    これは、場合により Long型 * Double型 が出現する、ってことですよね?

    そうなると、丸めや速度の事を一端置いといたとしても

    これを読むと

    Long 型 (Visual Basic)

    Long型がDouble型に変換された上で演算される、ということになるように読めます。


    VBのDoubleについて、細かい正確な仕様(バージョンといいますか)は存じていませんが

    倍精度浮動小数点数型 (Double) (Visual Basic)

    を見て


    IEEEと書いてあるので、少なくとも符号・指数部(2の何乗か)・仮数部(2進数)で表わされる仕様ではあるはずという感じを受けます。


    従って、単にLong→Doubleの変換がされた時点で

    すでに情報の欠落(誤差。Doubleの精度に下がる)を防げない、ということがあるはずです。
    仮にもしDecimal, で、倍率の小数もDecimalとしておけば

    演算中はその問題はないと思いますが、それもそれでかなり遅くなるのではないかという気がします。


    また、仮に最終的にLongで扱うようにするのであれば、一旦-1.0d~1.0dへ変換する必要はないはずです。

    Doubleは(仮数部の)精度はLongより劣りますが、表せる最大値はLongより遥かに大きいです。

    むしろそのまま計算する方が良さ気な感じがします。

    あと、以前触った感じで、SSE2は佐祐理さんのおっしゃるとおり、単純に速かったですね。

    ※もしさらに最強に速度をとるならGPU委託が良いのかもしれません。(CUDAとか)ただ、浮動小数のデフォルトの扱いが若干違ったような記憶があるので、そこでいいかどうかという問題はありますが。

    • 編集済み mr.setup 2012年5月28日 23:28
    2012年5月28日 23:20
  • 佐祐理さま、mr.setupさま

    残念ながら、VB以外の知識は極端にありません。学習のためのコストが大きくなり現実的ではないという事もご理解いただければ幸いです。

    また、速いに越したことはありませんが最重要ではないという位置づけです。

    VBで開発が完了し、将来的にもっと速くという欲望が出てきた場合には是非検討したいと思います。

    ただ、VBは銀行型丸め処理をする事を知ってはおりましたが、完全に失念しておりました。

    また、Long * Doubleが低速になってしまうことやLongがDoubleに変換された後計算されるなど、考えてもみませんでした。

    計算精度・速度ともにバランスを考えながら開発をするように心がけたいと思います。

    最後にひとつだけ。

    LongをDoubleにキャスト(-1~1ではない)して、そのまま、またLongに戻すということはどの程度の誤差が予想されるでしょうか?

    2012年5月29日 14:59
  • LongをDoubleにキャスト(-1~1ではない)して、そのまま、またLongに戻すということはどの程度の誤差が予想されるでしょうか?

    それは全くの『数値次第』であり、かつ『厳密にはVBのDoubleの仕様次第』でもありますね。

    ただ、予想としては

    例えば、演算前の数値はLongで、整数なので、この絶対値が1+2の52乗くらいより十分小さくて(?)倍率が整数になってて、演算後の数値もまた絶対値が1+2の52乗くらいより小さければ、誤差は0ですね。


    ただし、どれかが破れると一言では言えなくなります。

    ので、『最大誤差』で話をしますが

    おそらくこれは

    Long→Doubleの時点で

    Doubleの完璧な精度を比率上1とします。(わけわかめな言葉ですが「もっとも上質な精度」って感じです。うまく言えない)

    すると『仮数部の誤差』がおそらくだいたい2の-52乗として、Double同士の一回の乗算ですから

    『2の-52乗 * 2 以内』

    が足されそこからさらにDouble→Longなのでもう一回足され

    どんなにがんばっても合計『2の-52乗 * 4以内』ぐらいだと思います。(仮数部の誤差の最大値が)

    あとはどこまでこれが巨大かです。

    とはいえ、オーバーフロー判定を行うとすれば、演算結果がLongの最大値(最小値)を超える事がないとすれば

    「もっとも上質な精度」はLongの最大値(最小値)とおけるわけですから

    数値の上では、たぶん

    ±( 2の63乗*2の-52乗*4 ) = ±8192

    ぐらいに収まると思います。(PCMなら実際の数値じゃなくて最大値や最小値に対する比率の方が大事だと思いますが)

    途中の計算の根拠は、以前教えてgooというサイトでmaru_yoshi_さんと言う方と考えたものです。

    対数減衰を実現するときの具体的手法について

    まぁ、完全にあってるという保証はありませんw

    ただ少なくとも、よほど極端な数値を設定しない限り上記よりだいぶ少なくなる可能性が高いんではないかと思いますよ。

    それが大きいか小さいかはアプリの性質によるかもしれませんが。

    • 編集済み mr.setup 2012年5月29日 23:08
    2012年5月29日 15:21
  • 残念ながら、VB以外の知識は極端にありません。学習のためのコストが大きくなり現実的ではないという事もご理解いただければ幸いです。

    そのような状況が予想されたのでまず初めに「なぜそのような処理を必要としているのでしょうか? 背景を教えてください。場合によってはもっと別の部分を高速化すればいい問題なのかもしれません。」と質問しました。

    オーバーフロー処理よりも普段の演算の方がよほど時間を要しているでしょうし、その部分を高速化するためには知識が必要です。それが非現実的とのことなら諦めればいいと思います。

    もしVBの範囲で高速化したいということでしたら、所要時間を測定し、時間を要しているコードブロックを切り出して挙げてみてください。何かアドバイスできるかもしれません。

    2012年5月29日 22:15