円周率世界記録と多数桁乗算方式 後 保範 (Ushiro Yasunori) (株) 日立製作所 エンタープライズサーバ事業部 早稲田大学 教育学部 数学専修 非常勤講師 1 目次 1. 2. 3. 4. 5. 6. 7. 8. はじめに 円周��
円周率世界記録と多数桁乗算方式 後 保範 (Ushiro Yasunori) (株) 日立製作所 エンタープライズサーバ事業部 早稲田大学 教育学部 数学専修 非常勤講師 1 目次 1. 2. 3. 4. 5. 6. 7. 8. はじめに 円周率計算公式 円周率世界記録の歴史 世界記録達成の概要 世界記録達成の工夫点 多数桁乗算方式 多数桁分割乗算 おわりに 2 1. はじめに •1998年にDRM法(分割有理数化法、 Divide and Rationalize Method)を考案 •DRM法で級数関数の計算量が O(n2)からO(n・log(n)2)∼O(n・log(n)3)に削減 メモリ量がこれまでのAGM法より大幅減 •1TBの計算機で1兆桁円周率の計算が可能 DRM法で円周率1兆桁計算の検討を開始 •2002年11月24日､1兆2411億桁の世界記録達成 3 1.1
画像の専門家も「魔法のようだ」と驚愕！ ピンぼけ写真を修復できるプログラムが開発される | ロケットニュース24
画像の専門家も「魔法のようだ」と驚愕！ ピンぼけ写真を修復できるプログラムが開発される 2012年10月26日 わーん、街で偶然アイドルを見かけたから急いでカメラのシャッター切ったら案の定ピンぼけして、どこかのおばちゃんみたいに見えるわーっ！ 街の名前が書かれた看板の字すらボケすぎて何がなんだかわからんわーっ！ これじゃ何の証拠にもならへんやーんっ!! そんなアナタの切実なお悩みが近々解消されるかもしれないから、ピンぼけデータもしっかり保存しておくといいかもしれぬぞ。 というのも、ピントや手ぶれなどでぼやけている写真を修復してくれるプログラム「SmartDeblur」がプログラマーVladimir Yuzhikov氏によって開発されたというのである。 例えばピンぼけした風景の元画像と、処理後の画像を見てみると、その差は歴然！ それまで何がなんだか区別できなかったボケボケの風景が、プログラム
セルオートマトンの歴史
セルオートマトンの歴史 セルオートマトンはもともと1940年代末に生物の自己複製機能を摸擬するために、数学者のウラムとフォン・ノイマンによって提案されたものです[Ne66]。ウラムはモンテカルロ法という計算機シミュレーション法を開発したことで知られています。また彼は水素爆弾の製造にもかかわりました。フォン・ノイマンは最も有名な数学者の一人で、ゲーム理論の創始者[Po92]、史上初の電子計算機の設計者として知られています。当時フォン・ノイマンは機械またはオートマトン（自動機械と訳される）が自分自身のレプリカを作ることができるかどうかについて研究していました。彼は、自己複製には機械自身が自分自身の設計図（ブループリント）を有しており、それを複製することができれば自分自身を複製できると結論づけました。無論、このブループリントは実際の生物でDNA（一部のウィルスではRNA）に対応します。ただし、こ
fisheye view の計算式とプログラム - まめめも
fisheye view とは、なんかインターフェイスの世界では常識っぽい、フォーカスとなる点を中心に座標をぐにょーんと引き延ばす方法です。日本語が不自由ですみません。要するにこういう変換です。 皇居あたりを中心に線路地図をぐにょーんと引き延ばしています。これを実装しようと思って計算式やサンプルプログラムを探したのですが、意外に情報が少なくて手間取りました。なので記録を残しておきます。 種類 参考文献 *1 を眺めたところ、cartesian fisheye と polar fisheye の二種類があるようです。左が cartesian で右が polar です。でもこの例だとほとんど区別が付かないですね。よく見ると端っこの方のつぶれ方が違います。 cartesian fisheye view フォーカスの座標を 、引き延ばしたい点の座標を 、壁の位置を とするとき ( になる) 、引き
A Very Brief Introduction to the Pi-Calculus (in Japanese)
π-calculus 超入門 π-calculus は、80 年代の終わりごろに Milner らによって提案された並行計算のモデルの一つです。そこでは、プロセスと呼ばれる複数の独立した主体が、通信チャネルと呼ばれるデータの通り道を介して値をやりとりしながら、計算を行っていきます。π-calculus にはいろいろな変種があるのですが、ここではとりあえず次のような構成要素からなるものを考えましょう。 new x . P 新しいチャネル x を作ってから、プロセス P を実行する (channel creation) x![v1, ..., vn] チャネル x に値 v1, ..., vn を送る (asynchronous output) x?[v1, ..., vn] . P チャネル x から値 v1, ..., vn を受け取って、P を実行する (input guard) P |
スペル修正プログラムはどう書くか
Peter Norvig / 青木靖 訳 先週、2人の友人(ディーンとビル)がそれぞれ別個にGoogleが極めて早く正確にスペル修正できるのには驚くばかりだと私に言った。たとえば speling のような語でGoogleを検索すると、0.1秒くらいで答えが返ってきて、もしかして: spelling じゃないかと言ってくる(YahooやMicrosoftのものにも同様の機能がある)。ディーンとビルが高い実績を持ったエンジニアであり数学者であることを思えば、スペル修正のような統計的言語処理についてもっと知っていて良さそうなものなのにと私は驚いた。しかし彼らは知らなかった。よく考えてみれば、 別に彼らが知っているべき理由はないのだった。 間違っていたのは彼らの知識ではなく、私の仮定の方だ。 このことについてちゃんとした説明を書いておけば、彼らばかりでなく多くの人に有益かもしれない。Googleの
Bayesian Sets - mots quotidiens.
Bayesian Sets (Ghahramani and Heller, NIPS 2005)は Google Sets と同じようなことをベイズ的に行うアルゴリズムです。 いくつかアイテムを入れると, それを「補完する」ようなアイテムを 返してくれます。 これは NIPS の accepted papers が出た去年の8月から気になっていて, 本会議ではオーラルの発表もあって大体のやっていることはわかった ものの, 何と(本会議の時も!)論文がなく, 直接Hellerに連絡して もらえるように頼んでいたところ, Online proceedings の締切りがあった 時に連絡があって, 読めるようになりました。(リンクは下のページ参照) 岡野原君に先に 紹介 されてしまいましたが, 以下は, 岡野原君が書いていない話。 Bayesian Sets は, アイテム集合 D に対して,
エブログ マルコフ連鎖で文章生成（JavaScript）
マルコフ連鎖で文章生成（JavaScript） マルコフ連鎖による文章生成。マルコフ連鎖と言っていいのかあまり自信はないのだが、とりあえず文章を作ってはいる感じ。 テキストエリアに入力された文章を解析して、その中の単語を使って、自動生成します。文章生成ボタンを何度か押すと文章が変わっていくと思います。 意味不明であったり、そのままの文、同じ文が続けて出たりはしてしまいますが。 メロスは激怒した。必ず、かの邪智暴虐（じゃちぼうぎゃく）の王を除かなければならぬと決意した。メロスには政治がわからぬ。メロスは、村の牧人である。笛を吹き、羊と遊んで暮して来た。けれども邪悪に対しては、人一倍に敏感であった。きょう未明メロスは村を出発し、野を越え山越え、十里はなれた此（こ）のシラクスの市にやって来た。 ここに文章が作成されます。 posted by knit at 19:45 | Comment(9)
SoftURR -- a preliminary software implementation of URR
SoftURR‐URRのソフトウェアによる実装の試み version 0.1 公開。 Project Page ソースコード softurr-0.1.tar.gz 1. SoftURRとは SoftURRは、URR(Universal Representation of Real numbers;万能数値表現法)の ソフトウェアによる実装です。 URRは、算術的に美しく、実用的にも優れた浮動小数点数の表現方法ですが、 ハードウェアで実現することが容易でなかったため、 IEEE 754のように広く用いられることはありませんでした。 SoftURRでは、"動く"URRをソフトウェア(x86の整数演算)で実装してみることで、 URRを実用化するときに必要となってくる知識や経験を蓄積し、 最終的には、(夢は大きく！)規格化に向けた提言を行うことを目標としています。 2. U
万能数値表現法 ＵＲＲ
━─────────────────────────────────── アセンブラ講座（番外編） 《万能数値表現法 ＵＲＲ》 鎌田 誠 ──────────────────────────────────── IEEE 754 で規格化されている浮動小数点数の表現方法は符号と指数部と仮数 部に整然と分けられていてわかりやすく、実装も容易なのですが、指数部と仮数 部を区切る位置を固定してしまったために、大きな数を扱いたい技術者には指数 部の範囲が狭すぎ、精度を要求する技術者には仮数部のビット数が少なすぎると いう問題点があります。 しかし、かつて日本人によって IEEE 754 よりも算術的に優れている浮動小数 点数の表現方法が考案されていたことを知る人はほとんどいないでしょう。その 数値表現法は考案された当時の技術では実装が困難だったために規格化されなか ったようですが、非常に興味深い数
個人情報を渡さなくても認証が可能な技術の実用化へ、NEC － ＠IT
2006/7/19 NECは7月18日、世界最小のデータ量・世界最小計算量のプライバシー保護型認証方式を体現する曲線を発見し、同認証方式が実用化可能であることを実証したと発表した。 同認証方式は、利用者が特定グループに所属していることの証明とプライバシー保護とを世界最小データ量・世界最小計算量で実現する認証方式。グループ署名（ある権限を持つグループに所属しているかどうかを認証する技術）と呼ばれる方式の一種。今回の成果で、プライバシー保護型認証方式が具体的なアルゴリズムとして完成したため、実用化フェイズへ移行、同社では今後2年以内のサービス・製品への搭載を目指し、研究開発を進めていく。 この認証方式は、名前やIDといった個人を特定する情報を用いずに、認証対象がグループに属しているかどうかを確認することができる。また、特定の管理者のみが、認証された個人が誰であったかを認証記録から特定することが
暗号実装の魅力を探る － ＠IT自分戦略研究所
いま、現場で求められているキャリアやスキルは、どんなものだろうか。本連載では、さまざまなITエンジニアに自身の体験談を聞いていく。その体験談の中から、読者のヒントになるようなキャリアやスキルが見つかることを願っている。 携帯電話やカーナビゲーションシステムの普及に伴い、いま組み込み系開発で活躍する技術者が増えている。さらに組み込み系機器では盤石なセキュリティを確保する必要性も高まっている。組み込み系と暗号の最先端を研究するエンジニアを追う。 ■昔から暗号はあった 今回のテーマとなる技術は暗号と組み込み系となるが、まずはその前に暗号のルーツをひもとくところから始めよう。エジプトの古代遺跡に記された象形文字、ヒエログリフを見たことがあるだろうか。紀元前1900年ごろの遺跡に、最古の暗号文が使われていた、といわれている。 紀元前5世紀の古代ギリシャのスパルタでは、革ひもと棒を使ったスキュタレー暗
プログラムの算術的計算法 - 檜山正幸のキマイラ飼育記 (はてなBlog)
あー、やっぱりな -- 連休で調子がくるって、まだ何かおかしいよ。 で、少し頭のトレーニングになる話でもしましょうか。 pが論理式で、Aが文とか文の並びだとして、if (p) {A;} else {A;}って書く人はあまりいませんよね、これは単にA;と書いても“同じ”だから。次の3つの表現も事実上“同じ”なのはわかるでしょう。 // その1 if (p) { ; } else { if (q) { A; } } // その2 if (!p) { if (q) { A; } } // その3 if (!p && q) {A;} 次の「その2」はなんだか無意味みたいですが、「その1」と“同じ”です。 // その1 while (p) {A;} // その2 if (p) { A; while (p) {A;} } さて、一般に2つのプログラムコードが“同じ”であることを判定するのは難しいことで
[ruby-list:16645] Re: Sieve of Eratosthenes (Re: [ruby-dev:6094])
Subject: [ruby-list:16645] Re: Sieve of Eratosthenes (Re: [ruby-dev:6094]) From: wakou@ i t r p Date: Thu, 9 Sep 1999 07:30:38 +0900 In-reply-to: 12994 青山です。 On Thu, 18 Mar 1999 17:21:54 +0900, Shin-ichiro Hara <sinara / blade.nagaokaut.ac.jp> wrote: > するとある程度 max が大きいと(稲葉1)の大体３倍のスピード > が出るようです。 ちょっと古い話しですが、NIFTY の方でこの話が出まして、少し手を加えた所、 max が大きい場合、さらに倍ぐらいになりました。これでほぼ awk, perl の 速度に追い付いたようです。 max =
permutation - 白のカピバラの逆極限 S.144-3
http://d.hatena.ne.jp/qqqlxl/20060624/p3 (□□-□)/(□□-□□)=15 なる小町算。 □には2,3,4,6,7,8,9が入る。 というのがあります。 これを C でキレイに組みたいのですが、どうやるんでしょう？ う〜ん。素直に再帰で書きますか。 #include <stdio.h> int data[7] = {2,3,4,6,7,8,9}; void swap(int *a, int *b) { int temp; temp=*a; *a=*b; *b=temp; } void rec(int* f, int n, void(*r)(int*)) { int i; if(n<=0) { r(f); return; } for(i=0;i<n;i++) { swap(f+i, f+n-1); rec(f,n-1,r); swap(f+i, f+
ハンデつきジャンケンとロバスト制御 - swk's log
* ハンデつきジャンケンとロバスト制御 [tech] 6 users A さんと B さんがジャンケンをします．ただし，A さんだけはグーとチョキしか出せないというハンデつきのルールだとします．あなたが B さんなら，何を出しますか? 東大の 原辰次 先生が，とある講演 の余談として話されたネタ． (実は講演会自体は自分の講義と重なって出席できなくて，この話はその夜の飲み会で聞いた) これを尋ねるとほとんどの人が「グーを出す」と答える．実は，これは必ずしも最適な解ではない．グーを出すのは「最悪でもあいこに抑えたい」という「ロバスト制御」であるというお話． グーが必ずしも最適ではないってのがどうにもピンと来なかったので，家に帰ってから酔っ払った頭で計算してみた．ゲーム理論は一般書を流し読みしたくらいの知識しかないので，何か間違ってたら教えてください． ジャンケンの勝敗による利得を，勝ち: +
辞書を使わずに同義語を解析する言語解析エンジン，Sematicsが発表
Sematicsは6月15日，言語解析エンジンの最新版「Perceptron Engine」を発表した。語句の辞書データを使わずに解析するため高速という。同社の従来エンジン「Automaton Parser」で実現していた形態素解析と構文解析に加え，文脈解析と意味解析の機能を備えた。 同社の言語解析エンジンの特徴は，語句の辞書データを用いずに解析を行うこと。辞書が必要ないため，高速に処理できるほか，フット・プリントをコンパクトにできる。「（パソコンを使って）1センテンスを1000分の2秒で解析できる。500センテンスの解析は1秒で済む」（代表取締役の吹谷和雄氏）という。 同社が開発した第1号のエンジンであるAutomaton Parserは，統計的確率論によって，形態素解析と構文解析を実行するソフトである。語句を分割した最小単位である形態素ごとに分けて品詞を付与し，文節の係り受けを解析する
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://homepage1.nifty.com/herumi/diary/1208.html
ログイン - 佐賀研究室ホームページ
https://www-imai.is.s.u-tokyo.ac.jp/~seta/paper/SIGAL84-8/cross_sum.pdf