目次
初めに
前置き
どうも、いなえのまきです。
この記事はCCS Advent Calendar 2017の6日目として書かれた記事です。
前日の記事 by ユーマ
次の人→珈琲王子
どうも今年は裏アドベントカレンダーなるものもあるらしいので気になる方はそちらも是非。
去年はCCS Advent Calenter 2016にも参加しました。記事はこちら
動機
さて、別に何をやるとも決めていなかったので、「コンピュータ上での文字周りのことについて勉強してまとめて、それを記事にしてあげるかなあ」くらいのノリでアドベントカレンダーに参加してしまったのですが、思ったよりもやることがあったのと、少し調べてみると結構な分量と労力になりそうな事がわかったので、文字周りの話は余裕がある時にまた記事をあげることにして断念しました。
そこで、何か楽に書けるふさわしい題材がないかと思った時に、過去に楽しそうと思って書いてみた多倍長整数のコードを思い出した感じです。
多倍長整数自体は結構色々なライブラリで実装されてたり、言語によってはデフォルトでサポートされてたりするそうなので、そもそも自分で作る意味がない(車輪の再発明)なわけなんですが、面白そうなので作ってみたという経緯があります。その為、新規性はないです(1年ぶり2回目)が、個性を出せるように頑張ってみたのでどうぞ。
多倍長整数
多倍長整数って？
Wikipediaを見ると、
任意精度演算とは、数値の精度を必要ならいくらでも伸ばしたりできるような演算システム（実際上は利用可能なメモリ容量に制限されるが）による演算である。
とした上で、
という風に書かれています。
何となくイメージはつかめるかと思いますが、こちらのサイトにあるように
多倍長整数とは、コンピュータに巨大な整数を扱わせるための仕組みである。
こういったものです。
Cなんかでいうint型なんかは扱える数の大きさに定められた制限があります。これはハード側で高速に演算等を行う為らしいのですが、そのせいでその制限以上の大きさの値を扱うことが出来ず困る場面もあります。これを解決する為に用いられるのが多倍長整数といったものです。多倍長整数は、制限なく大きな整数を扱うことを可能にしてくれるのです(実際にはメモリの容量等ハードの制限はありますが)。
よくある方針
ここやここやここやここ当たりを見てる感じ、基本方針としては、整数の配列やリスト等を用意してやって、それらを1つの数として扱うアルゴリズムを実装していく感じが多いみたいですね。
どうやったの？
以前僕が書いたものも内部的にはこれに結構近い感じのものだったのですが、少し特色付けたいなと思って僕が目指したのが、std::stringを使って多倍長整数を実装するという方法です。
何故これにしたかというと、
- std::stringが勝手に長さを調整してくれるので、メモリの確保や解放の処理を自分で書かなくていいので楽な上メンテナンスしなくていいから
- いくら大きな値を扱えるようにしてもBigInt a=9999999999999999999999;みたいに書くと定数が大きすぎるとして怒られてしまうが、BigInt a="9999999999999999999999";という風に書けるようにすればこの問題は解決する。その上で内部で数字を文字列で持てば、初期化や代入周りの処理が超楽に書ける
- str_var[i]とすることでi番目のcharを取り出せるので、n桁目を取得するのが楽*1
みたいな目論見はあったわけですが、正直一桁あたりにchar分の1バイト使ってるのでとてもメモリが無駄になる上に、高速な計算も特に思いついていたわけではなかったので、正直な所演算子オーバーロードを手で書いて覚える練習がしたかったみたいな色合いが強かったです。内心実用には耐えないだろうなあとか思いながらも楽しそうだからというだけで書いてました、ハイ。
ただ、インターフェースを綺麗にするというか、ユーザーが違和感なく使えるようなクラスを考えるのって難しいんだなあとか、あっちを立てるとこっちが立てるでどうにもならんなあというところとかが出てきて、ライブラリ開発者様等の神の凄さを実感して、そこは勉強になりました。
実装
全体の方針
最終目標は、std::string型で保持している整数(以下文字列整数)を持つ自作クラスを、int型と同じ使用感で使えることになります。
そのためにまず、文字列整数をint型と同様に扱えるようにすることを考えます。
そのためにまず文字列整数同士の加算と減算、比較をする関数を用意します。そしてその必要最低限の関数を使って演算子をオーバーロードしていきます。
その他雑記
注意すべきは内部処理でint型に変換してしまうと、実質精度がint型と同じなってしまう点に気をつけることです。
演算子オーバーロードでは、他のオーバーロードを出来る限り内部で呼ぶ形にすることでDRY原則に従い、メンテナンスのコストを下げようとしたのですが、加算と減算は場所によってはその場で定義してしまってます(別の演算子呼ぶより早いかな？とか思ったので。もしかしたらコンパイラが最適化してくれるから気にしなくていい系案件かもしれませんが…)。よって少し統一感の無いコードになってます。
あと、char型の数字(文字の内部的な数値ということではなく'1'とかのこと)を単純にint型にするのが地味にどうしようか迷いました。
加えて、実は
BigInt x = BigInt(0) +"2";
みたいな記法を許せるように「BigIntとstd::stringの+演算子」もオーバーロードしてたんですが、intへのキャストを暗黙のキャストも許可して定義した(これはintと同じく自然に使えるようにするため)影響でBigInt(0)が暗黙にint型にキャストされた場合というのも考えないといけなくなってしまい、組み込み演算である「integerとpointer-to-objectとの+演算」とどちらの演算子を使っているのかというのがコンパイラが判断できずエラーを吐くという結果になったので、これについては断念しました。
もう後は見ておくれ
正直そんなに語る所もない内容なのでソースコードだけ貼っつけとくので後はご自由に御覧ください(丸投げ)
多倍長整数はbigintやbignumといったような名前にする慣習があるらしいのですが、なんかそこまで言うのがおこがましい感じがしたのでちょいデカ目のintくらいのつもりでlonger_intという名前にしました。
何か不足している所や間違っている所があったら教えてください。
以下ソースへのリンク
*1:だと思っていたがそうでもなかった
