読者です 読者をやめる 読者になる 読者になる

あざらしとペンギンの問題

主に漫画、数値計算、幾何計算、TCS、一鰭旅、水族館、鰭脚類のことを書きます。

割り算を使わずに割り算をする

妙なタイトルですが、今回は次のような問題を考えます。割り算を計算をするために電卓を使いたい。しかし、電卓を持ってきたところ、割り算のボタンが故障していて使えないことが判った。他のボタンは問題なく機能しているが、割り算だけは使えない。なんと…

Toom-Cook法:掛け算の数が減るカラクリ

今回は、Karatsuba法をダシにして、「高みの見物で構造が見えてくる」というお話をします。最初の高速乗算アルゴリズムであるKaratsuba法は、それだけ見ると天下り的に上手いことやって式を作ったように思えます。あるいは実際そうだったのかもしれません。…

掛け算の計算量

前回の足し算の計算量に続いて、今回は掛け算の計算量について見ることにします。掛け算(および割り算)において一つ重要なことは、筆算よりもオーダーの意味で(定数倍を超えて)速い計算方法が存在することです。一方で、足し算(および引き算)の場合は…

オーダーのすゝめ

前回の計算量の議論の問題点として、数字の見方(基数)を自由に変えられるとした場合、計算量が一定しないことを最後に述べました。それは例えば計算量がCPUに依存するということであり、計算量を理論的に抽象化して議論する場合の妨げとなります。そこで、…

算術演算の計算量

気がつけば大晦日。明日はもう2014年です。このブログを始めて1年も過ぎました。記事が充実しないのは筆者の怠慢の致すところであります。久々の更新で一体何を書くのかといえば、大分放置していた計算量の定義です。誕生日のパラドックスを素因数分解に応用…