アルゴリズム百選 - ユークリッドの互除法 : 404 Blog Not Found
2007年12月11日16:30 カテゴリアルゴリズム百選Math アルゴリズム百選 - ユークリッドの互除法 今回は、ユークリッドの互除法を取り上げます。 ユークリッドの互除法とは何か。小学校の時に実は習っているはずですが、忘れている方は思い出してみてください。最大公約数(Greatest Common Divisor)を確実に計算する方法です。古代から有名なこのアルゴリズムは、かつては"The Algorithm"といえばこれをさすほど有名なアルゴリズムです。 それは、コードではなく普通の言葉でも簡単に書くことが出来ます。gcd(m, n)を出すには、 mをnで割り、余りがrだとする 余りrが0なら、nがGCD。 そうでなければ、nとrのGCDを求める 互い違いに割っていくので、互除法というわけです。 function gcd(m, n){ if (m < n) return gcd(
アルゴリズム百選 - ベキ乗はO(1)でOK? : 404 Blog Not Found
2007年12月04日23:00 カテゴリアルゴリズム百選Math アルゴリズム百選 - ベキ乗はO(1)でOK? これ、Hyukiさんをはじめ多くの方が疑問に思っていらっしゃるようなので、いまのうちに答えておきましょう。blogで書く以上、書く順番は順不同で構わないのですし。 アルゴリズム百選 - フィボナッチ数列にO()を学ぶ - www.textfile.org フィボナッチ数列の一般項を求める式を使ったときってO(1)って言えるのだろうか？まずは、論より証拠、というわけで実測値をご覧下さい。Cでフィボナッチ数をO(n)アルゴリズムと公式を使ってそれぞれ100万回計算した時にかかった時間をプロットしたものです。最適化をかけていないものと-O3で最適化をかけたものと双方を計測しています。fib(73)まで計算したのは、doubleで整数で保っておける限界がそこまでだったので。ソースは本
404 Blog Not Found:アルゴリズム百選 - 二分探索(binary search)
2007年12月04日08:30 カテゴリアルゴリズム百選Math アルゴリズム百選 - 二分探索(binary search) 今回は二分探索を取り上げます。 検索:コンピューターの最もよくある利用法 「二分探索って何?」「ググレカス」と言われないためにこの記事は存在するのですが、Webの検索に限らず、「目的のデータを見つけて取り出す」というのは、およそコンピューターの利用法で最もポピュラーなものです。 配列:コンピューターがデータを扱う根本的な方法 そのデータはコンピューターのなかでどう置かれているかというと、非常に単純です。デジタル化されたデータ=数値が一定間隔で並んでいるだけです。こういうデータ構造を、配列(array)といい、この数値一個一個のことを要素(element)と言います。 現代のコンピューターでは、最小要素はバイト(byte)と呼ばれています。このバイトの中には0と1
宴会ネタ - 揚げ足取り数列 : 404 Blog Not Found
2007年12月03日18:15 カテゴリMath翻訳/紹介 宴会ネタ - 揚げ足取り数列 もう師走ではないか。宴会の季節ではないか。 というわけで宴会でほろ酔い加減の時に使えそうな数学ネタを。 Q. ...に続く数字を答えなさい。 1, 2, 3, 4... 答えは5ではありません。29です。その次は?126です。 でたらめを言っているのではありません。きちんと単純な規則に則っているのです。 その規則とは? a(n) = (n - 1)(n - 2)(n - 3)(n - 4) + n でした。 (n - 1)(n - 2)(n - 3)(n - 4)があるおかげで、n = 1,2,3,4に関しては、a(n) = n になります。しかしそれ以外に関しては、落とし穴になる、というわけです。(n - 1)(n - 2) ... (n - k)の部分を変えれば、任意の数字を落とし穴に出来るとい
アルゴリズム百選 - フィボナッチ数列にO()を学ぶ : 404 Blog Not Found
2007年11月28日18:00 カテゴリアルゴリズム百選Math アルゴリズム百選 - フィボナッチ数列にO()を学ぶ 404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10、これほどの反響になるとは。200ブクマぐらいは予想していたが、もいくとは。 とりあえず、本の仮題を「アルゴリズム百選」として、「アマグラマーのすすめ」と同じように本blogに草稿を書いていくことにする。「メインページ」の「アルゴリズム大募集! C&R研究所 - トップページ」の方も適宜更新していくが、「その場で動かせるコードサンプル」はここでないと書けないので。 ただし、「アマグラマーのすすめ」よりは書き方は順不同になるはず。それでも序文相当のことは「チラ見」ならぬ「チラ書き」しておいた方がいいだろう。というわけで、序文に変えて紹介するのが、本Entry。 ヒントとな
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
一年以上かけて読(める|むべき)一冊 - 書評 - A New Kind of Science : 404 Blog Not Found
2007年11月13日04:00 カテゴリ書評/画評/品評Math 一年以上かけて読(める|むべき)一冊 - 書評 - A New Kind of Science The 2,3 turing machineが出たときに紹介しようと思っていたらなんだかんだで後回しになってしまった。 A New Kind of Science Stephen Wolfram 私はこれまで全てのページに少なくとも3度以上目を通した。 が、とても「読了」(read)したとは言えない。せいぜい「目を通した」(browse)したといったところか。 それでも紹介せずにはいられない魅力がこの本にはある。 本書"A New Kind of Science"は、超天才Stephen Wolframの単著。いや、涼宮ハルヒが超天才なら、こちらはもう神としかいいようがない。 といっても、知名度ではいまいちかも知れない。少なくと
数苦を経て数楽へ - 書評 - 数学する精神 : 404 Blog Not Found
2007年11月03日01:00 カテゴリ書評/画評/品評Math 数苦を経て数楽へ - 書評 - 数学する精神 数学は、コーヒーのようなものなのかも知れない。 数学する精神 加藤文元 その苦みが味わえるようになって、やっと楽しめるようになるという点において。 本書「数学する精神」は、数学者が数学するときの気持ちを、読者に読ませるようにというより、著者が書きたいように書いた本。書きたいように書く妨げにならないための配慮か、本書は数式も遠慮なく登場し、それを無理なく登場させられるように横書きになっている。 p. 10 この本は一般向けにわかりやすく数学を解説した本というよりは、むしろ「数学」そのものについての本であり、数学についての筆者の個人的な思想や信条(そして心情も!)を率直に告白した本である。 目次 はじめに 第1部 人間と数学 第1章 計算できる記号 第2章 ウサギとカメ 第3章 ビ
perl - behind the 2,3 turing machine : 404 Blog Not Found
2007年10月27日16:15 カテゴリMathLightweight Languages perl - behind the 2,3 turing machine 日本でもWiredが取り上げて知られるようになった2,3 Turing Machineですが、 Wolfram Blog: The Prize Is Won; The Simplest Universal Turing Machine Is Proved WIRED VISION / 「ウルフラム氏のチューリングマシン」を20歳の学生が証明 この証明に、Perlが使われていますというお話。 http://www.wolframscience.com/prizes/tm23/TM23Proof.pdf - 証明のPDF I have written several Perl programs, to demonstrate t
全ての奇数は素数であることの証明いろいろ : 404 Blog Not Found
2007年10月09日04:00 カテゴリ1st Day of AprilMath 全ての奇数は素数であることの証明いろいろ まだwww(ワワワじゃないぞwww)もない頃、rec.humorとかでさんざん使われたネタだけど、ぐぐると数学者、物理学者、工学者バージョンぐらいしか見当たらなくて寂しいので。 以下、弾脳内学者の意見も踏まえて。 数学者 3は、素数である。 5は、素数である。 7は、素数である。 ∴数学的帰納法により、全ての奇数は素数であることが証明された。 物理学者 1は特異点。 3は、素数。 5は、素数。 7は、素数。 9は計測誤差。 すべての奇数は素数であることが観測により実証された。 ソフトウェア工学者 #define is_prime(n) ((n) & 1) 保守議員 「賛成の諸君の起立を求めます」「『すべての奇数は素数である』法案は賛成多数により可決されました」 革新
書評 - 非線形科学 : 404 Blog Not Found
2007年10月07日00:00 カテゴリ書評/画評/品評SciTech 書評 - 非線形科学 すっかり書評が遅くなってしまったのも、待ち時間が長いAmazonのせいにしとくか。 非線形科学 蔵本由紀 私は2週間待たされた。そして、それだけの価値がある一冊だった。 本書「非線形科学」は、文字通り、「線形」に「非ず」に振る舞う諸現象を科学で扱うことにかけて説いた一般書。フラクタル、カオス、そしてネットワーク....この広大な分野は、その小さな枝一本を取り上げても新書一冊分の分量があるほど豊穣な領域であるが、それだけに、一冊で紹介するには相当な力量がいる。著者は、まさにそれをやってのけた。しかも、新書で。 目次 まえがき プロローグ 第一章 崩壊と想像 第二章 力学的自然像 第三章 パターン形成 第四章 リズムと動機 第五章 カオスの世界 第六章 ゆらぐ自然 エピローグ 参考文献 さくいん こ
書評 - √2の不思議 : 404 Blog Not Found
2007年10月05日03:45 カテゴリ書評/画評/品評Math 書評 - √2の不思議 献本も多いせいか、近頃数学本を紹介していないので、久々に。 √2の不思議 足立恒雄 ああ、簡単に出来ることを、なぜ出来るのかを考え抜くのはなんと難しいのだろう。 本書「√2の不思議」は、内容は難しいとは言えないのに、要約するのが実に難しい本。ここは著者に語ってもらうことにしよう。 P. 007 しかし私は、数学が役に立つかどうかといったけちな効用論を超えて、「人間が人間であるのは数学を持ったからであるというところまで踏み込んで主張したい。「文明は道具の使用とともに始まった」というような即物的な主張を、私は採らない。 本書は、それを一冊かけて主張したものだといっていいだろう。 目次 - 筑摩書房 √２の不思議 / 足立 恒雄 著より 第１章 人間の条件は数学することである―「数」の発見 ０の発明 「意
算数 - 8のふしぎ : 404 Blog Not Found
2007年09月25日21:45 カテゴリMath 算数 - 8のふしぎ 142857.comのおかげで、7が注目されていますが、8にも注目ということで軽く一本。 既出かと思ったのけど、検索で引っかからなかったので。 1 * 8 + 1 = 12 * 8 + 2 = 123 * 8 + 3 = 1234 * 8 + 4 = 12345 * 8 + 5 = 123456 * 8 + 6 = 1234567 * 8 + 7 = 12345678 * 8 + 8 = 123456789 * 8 + 9 = 類似の9でかけるというのは、 123456789 で紹介されてました。 Dan the Number Juggler 「Math」カテゴリの最新記事
perl - $scalarの中身が数値か否かを判定する : 404 Blog Not Found
2007年09月21日00:45 カテゴリLightweight Languages perl - $scalarの中身が数値か否かを判定する 詳しくはCookbookの2.1を参照してもらうとして、これは以外とよく出てくる設問なので。 Perl Cookbook (English) Christiansen / Torkington [邦訳: Perlクックブック] Kazuho@Cybozu Labs: MySQL の高速化プチBKところで、実数の場合はどうすればいいんでしょうね。 Scalar::Util::looks_like_number() Perl 5.8.1以降であれば、第一選択はこれです。第一引数の結果が数値か否かを、Perl APIに直接問い合わせるので高速です。ベンチマークを最後に示しますが、真偽ともに正規表現と比較して250倍高速です。 Regexp::Common
CO2削減に最も有効な方法 : 404 Blog Not Found
2007年07月07日23:00 カテゴリMath CO2削減に最も有効な方法 以下の文の間違いを見つけよ。 MORI LOG ACADEMY: 温暖化解決に最も有効な方法 「食料品が５％値上がりしました。さて、消費者はどうしたら良いでしょうか？」という問いに対する、最も素直な答は、「食べる量を５％減らせば良い」である。設問をもう少しいじるとわかりやすいかも知れない。 体重が５割増えた人は、元の体重に戻すのに今の体重を何割減量すればよいか？ 答えは、1/3、すなわち三割三分(二桁精度で)。1/2ではない。以下、一般化した場合をJavaScriptで表現してみた。 %増えたものを元に戻すのに必要な削減率は% ちょっと計算してみればわかるが、増えたものを元に戻すための削減率は、増える前と比較した場合の増加率より必ず小さくなる。ゆえに、増加させるための手間も減少させる手間も同じように増減率と比例
書評 - 数学ガール : 404 Blog Not Found
2007年07月09日00:00 カテゴリ書評/画評/品評Math 書評 - 数学ガール 怪書に快書。奇書だがきしょくない。 数学ガール 結城浩 初掲載2007.07.07;週明けまで更新 ライトノベルならぬ、ライトサンコーショ? 今年、いやここ数年読んだ中で、最も書評しがたい一冊でもある。 本書「数学ガール」は、まぎれもない一般向け数学書でありながら、同時にロマンスでもある。文庫化するなら、コバルト文庫が一番似合ってそうな数学書というのは、他にないだろう。 まずは数学的に、数学書としての本書とラブコメとしての本書を分けて考えてみる。まずは数学書の方。 目次 数学ガール | 数学 | サイエンス | サイエンス・テクノロジー・メディカル | ライブドア ブックスより追補 プロローグ 第1章 数列とパターン 第2章 数式という名のラブレター 第3章 ωのワルツ 第4章 フィボナッチ数列と母関
無限は君が思っているほど大きいとは限らない : 404 Blog Not Found
2007年06月27日13:00 カテゴリValue 2.0Math 無限は君が思っているほど大きいとは限らない この「可能無限」という言葉は、120% Fasionable Nonsenseだと考えている。それも、人畜無害なものではなく、「水からの伝言」なみかそれ以上に危険な。 My Life Between Silicon Valley and Japan - フューチャリスト宣言や茂木さんのことやはてなのことなどを酔っ払いながら書いてみる 茂木さんが最初に「自分が書いた文章」を披露しながら、「自分は可能無限の世界を愛していて、人間の有限性というのを受け入れることが未だにできずにいる。だから物事を決められないのが自分の欠点なんだ。弱さなんだ。そういう秘密を頭に浮かべながら、この文章書きました」みたいな話をしていた。茂木は可能無限を以下のように定義している。 フューチャリスト宣言 p.1
404 Blog Not Found:グラフィックに役立つ数学的事実
2007年06月20日10:30 カテゴリ翻訳/紹介Math グラフィックに役立つ数学的事実 del.icio.us経由。 Handy Mathematics Facts for Graphics 単なる翻訳ではなく、もう少し使いやすくしてみた。 定数 実際にJavaScriptに計算させています。 √2 = sqrt(2) = Φ = (sqrt(5) + 1)/2 = 黄金比の長い方。短い方は小文字のφをあてることが多い。φ = 1/Φ = Φ - 1 = √3 = sqrt(3) = e = exp(1) = π = 4 * atan2(1,1) = ファイゲンバウム定数 詳しくは Feigenbaum Constant -- from Wolfram MathWorld Feigenbaum constants - Wikipedia, the free encyclopedia
√2√2√2... : 404 Blog Not Found
2007年06月13日19:30 カテゴリMath √2√2√2... 見る可算、じゃなかったミルカさん、仮定しなくてもとけまっせ。 [結] 2007年6月 - 結城浩の日記:ルートの無限入れ子クイズ ミルカさん「先生、この数式の値が《ある正の値に収束する》ことは仮定してもいいんですか？」 ヒント。 以下の値は? ∛4∛4∛4... ついでにこれも。 ∜8∜8∜8... [結] 2007年6月 - 結城浩の日記彼「数列の極限値を求める問題とみなす。一般項の形を考えて、その極限を調べる。…だから、定式化するとこうかな」 この彼の定式化をさらに進めると、わかりやすいかな。 数列〈an〉が、 a1 = a1/r, a2 = (a * a1/r)1/r, a3 = (a * ((a * a1/r)1/r))1/r で与えられているとき、limn → ∞anを求めよ。 ただし、r > 1, a >
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
紹介 - なぜ0で割ってはいけないのか？ : 404 Blog Not Found