追記：多倍長整数演算

大学 programing C/C++

多倍長演算の場合キャリーを考える必要があって、一桁mビットだと乗算のキャリーが最大mビットだから、普通はunsigned short型(2バイト)配列で整数値を表し計算途中はunsigned int(4バイト)型配列を使えば良い。
んで、もし基数を負数にするとしたら一桁mビットに対してキャリーが最大2mビット生じてしまう事に気付いた(もしかしたら2mビット以上かな？)。そうするとunsigned char(1バイト)配列で整数値を表し(-256進数)、計算途中はunsigned int型配列を使わなければならない。必ず１バイトは無駄にメモリを確保することになるし、ループ回数が約２倍。いくらなんでもコストが大きすぎるな〜面白いネタだと思ったけど。

  • DFTを使って高速に多倍長演算する方法もあるらしい。おもしろいけどDFTなんてすっかり忘れてしまった。てかあと１週間でレポート仕上げるのが大変そう。
  • 多倍長演算で表現テンプレート(式テンプレート)使えないのかな。ググってみたところ見当たらない。d = a*b*cをd = a; d *= b; d *= c; みたいにするだけだから出来そうな気がするけどなぁ。(ていうかレポートはCで書くのか...)

普通にやるのが一番良い気がしてきた(笑)