割り算の計算量 - あざらしとペンギンの問答
足し算、引き算、掛け算と来たら、残る四則演算は割り算です。 割り算においてこれまでと違うことは、何と言っても「割り切れない」場合が存在することでしょう。他の四則演算はすべて整数の範囲で閉じている*1のですが、整数同士の割り算では結果が整数とならない場合が存在します。 そこで、今回は割り算を小学校で習ったように、割り切れないときは余りを出す、という形で行うこととします。つまり、除算と剰余算を同時に行うというわけです。入力として2つの非負整数 を受け取り、計算の結果としては の商 と余り の組 を出します。これらが満たす関係は です。 が割り切れるということは、 となることに他なりません。 結果として小数を出す割り算もこれに当てはめて行うことができます。例えば、分数 の小数第4位までの値を第5位を四捨五入して得る計算は、次のように実現できます。まず分子に欲しい位と同じ4個の0を足して を計算し
算術演算の計算量 - あざらしとペンギンの問答
気がつけば大晦日。明日はもう2014年です。このブログを始めて1年も過ぎました。記事が充実しないのは筆者の怠慢の致すところであります。 久々の更新で一体何を書くのかといえば、大分放置していた計算量の定義です。誕生日のパラドックスを素因数分解に応用しよう！と言ったのはいつの話でしたかね？今回の話からやっと続きに入れます。まずは、最も基本的な算術演算である四則演算（加減乗除）の計算量を考えます。 結論を先に書いておきます。 2つの数 がそれぞれ位取り記数法（基数は2以上で任意に固定）の 桁で入力として与えられるとき、四則演算の結果を同じ記数法で出力するときの（最悪時）計算量は 足し算 ： 引き算 ： 掛け算 ： 割り算 ： （） 特に、上で および割り算で とすると 足し算 ： 引き算 ： 掛け算 ： 割り算 ： となります。これらのうち、掛け算と割り算はより小さいオーダーで計算することができ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
アリスとボブは妥協する - あざらしとペンギンの問答
