高速逆平方根(fast inverse square root)のアルゴリズム解説 - 滴了庵日録
高速逆平方根とは？ C言語のコード 検証 アルゴリズムの要点 [1] 逆平方根の計算を対数・指数の計算に置き換える [2] 浮動小数点型の内部表現を利用した対数・指数の近似計算 [2.1] 対数の近似 [2.2] σの最適値 [2.3] 整数型での解釈 [2.4] 逆平方根の計算とマジックナンバー0x5F3759DF [3] ニュートン法による収束で精度アップ 感想 高速逆平方根とは？ 高速逆平方根(fast inverse square root)とは、平方根の逆数 を高速に計算するアルゴリズムです。平方根の逆数は逆平方根とも呼ばれます。逆平方根はベクトルの正規化などに用いられるので、これを高速に計算できるアルゴリズムには大きなご利益があります。 参照： Fast inverse square root - Wikipedia C言語のコード 高速逆平方根の関数を示します。0x5F375
数値計算の研究をしている学生が"数値計算に潜むとんでもないリスク"について話してみる - Qiita
筆者は「精度保証付き数値計算」という分野で研究をしている大学院生です． 「数値計算は分かるけど」「精度保証付き数値計算？ナニソレ？」という方がほとんどだと思います． 「精度保証付き数値計算」の研究自体は30年ほど前から盛んに行われていますが，世間に浸透しているとは言えない状況です． 自分の研究分野が世間に知られていないのは何か少し寂しい感じがするので「精度保証付き数値計算」を少しでも広めるべく記事を投稿することにしました．(シリーズ化するかも知れません) 本日は「精度保証付き数値計算」というワードだけでも覚えていただければ幸いです． 今回は"数値計算に潜むとんでもないリスク"に関してカジュアルにお話します． そして筆者の研究分野である「精度保証付き数値計算」の必要性を知ってもらえればなと思います． この記事を読み終える頃には計算機を信頼できなくなっているかも知れません(笑) ※不安を煽るこ
微分動作の問題点と不完全微分 - とりあえずフィードバック制御
時間遅れしかないプロセスにとって、未来を予測し位相を進めてくれる微分動作は良心である。単にノイズに弱いからと言って、微分時間を小さく設定したり、PI制御しか使わないのはもったいないです。今回は、PID制御をより実践的に使うための要素技術の一つである不完全微分について解説します。 キーワード：PID制御、微分動作、不完全微分 はじめに PID制御における微分動作は、温度制御のような応答が遅いプロセスの改善に役立つ。一方で、流量や圧力関係の制御では、ポンプや弁の動作に起因した脈動や乱流で制御量が振動的になってしまうことから、微分動作がそれを増幅し、過大な操作量で制御系を不安定にしたりする。そればかりか、過大なアクチュエータの動作は設備の劣化にもつながる。他にも良くない影響として、非常に大きくなった操作量が有効な操作範囲を超えたり、パルス状になった操作量ではアクチュエータがそもそも動作できなかっ
ECMAScriptの浮動小数点数の丸め仕様がスゴい - hnwの日記
ECMAScriptの浮動小数点数の丸め関数である Number.prototype.toFixed() について調べてみたところ、浮動小数点数をわかっている人が作った硬派な仕様だと感じたので、解説してみます。 浮動小数点数の丸めの善し悪しについて 私はプログラミング言語の浮動小数点数の丸め処理に興味があり、過去に関連記事を30本以上書いています。こうした活動から得られた知見として、良い丸め関数には次のような性質があると考えています。 仕様がシンプルで直感的であること 仕様が抜け漏れなく文書化されていること バグを作り込みにくい仕様であること どれも良い関数の一般論のような話ですが、丸め処理に限って言えば簡単な話ではありません。そもそも浮動小数点数の性質が人の直感に反するため利用者にとっても実装者にとっても罠が多く、結果として上の条件を満たせないことが多いのです（私が面白いと感じるポイント
計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。今回は計算量オーダーの求め方について書きます。 0. はじめに 世の中の様々なシステムやソフトウェアはアルゴリズムによって支えられています。Qiita Contribution ランキング作成のために用いるソートアルゴリズムのような単純なものから、カーナビに使われている Dijkstra 法、流行中のディープラーニングに用いられている確率的勾配降下法など、様々な場面でアルゴリズムが活躍しています。アルゴリズムとはどんなものかについて具体的に知りたい方には以下の記事が参考になると思います: アルゴリズムとは何か ～ 文系理系問わず楽しめる精選 6 問 ～ アルゴリズムを学ぶと $O(n^2)$ や $O(n\log{n})$ や $O(2^n)$ といった計算量オーダーの概念が登場します。こうした記法を見ると
Pythonでの数値計算ライブラリNumPy徹底入門
NumPyは、多次元配列を扱う数値演算ライブラリです。機械学習だけでなく画像処理、音声処理などコンピュータサイエンスをするならNumPyを学んでおくことで、あなたの日々の研究や開発の基礎力は格段にアップするはずです。 プログラミングの初心者から、Webエンジニア、これから研究する人など、初学者にも分かりやすく優しく説明することを心がけて必要な知識が身につくように解説しています。 腰を据えて学習する時間と余裕のある方は、Step1から順に進めていくことで、苦手意識のあった方でも一通り読み終わる頃には理解できなかったPythonとNumPyのソースコードがスラスラと読めるようになるはずです。 上級者の方は、分からない記事だけ読むだけでも、力になると思われます。あなたのプログラミング能力を向上する手助けになることをお約束します。このサイトを通して、コンピュータサイエンスに入門しましょう。 Ste
円周率の16進数表現100億桁目を求めてみた！ ― 円周率の世界記録をどのように検証するか ― - プログラムモグモグ
あなたは円周率を何桁言えますか。3.14159…という、あの数字です。 円周率の小数部分は無限に続き、循環することもありません。 古来より、数学者は円周率の値を様々な幾何学的な近似や公式を用いて計算してきました。 その桁数は計算機の発明により飛躍的に伸び、収束の速い公式の発見や効率の良いアルゴリズムの発明などによって加速してきました *1。 5年前、私がまだ学生だった頃、円周率1億桁の計算に挑んだことがありました。 私にとって高精度計算の初めての挑戦で、様々な試行錯誤で苦労したのをよく覚えています。 itchyny.hatenablog.com 2017年現在、円周率計算の世界記録は22兆桁です。 円周率計算の歴史をご覧いただくとよく分かると思いますが、近年の円周率計算の世界記録からは次のような特徴が読み取れます。 2002年に1兆を超え、最新の記録 (2016年) は22兆桁 (10進数
Webプログラマと数学の接点、その入り口
フロントエンドのパラダイムを参考にバックエンド開発を再考する / TypeScript による GraphQL バックエンド開発
暗号文のままで計算しよう - 準同型暗号入門 -
2. • 準同型暗号とは何か • 加法準同型暗号のデモ • 楕円ElGamal暗号 • 完全準同型暗号 • その原理の雰囲気の紹介 • 『クラウドを支えるこれからの暗号技術』 • 公開鍵暗号の最先端応用技術・理論 • 準同型暗号が載ってる和書は現時点で本書のみ • 数学成分高め • https://herumi.github.io/ango/ 概要 2/39 3. • 光成滋生（@herumi） • @IT連載記事「クラウド時代の暗号化技術論」 • http://www.atmarkit.co.jp/ait/series/1990/ • CODE BLUE2015 • Excelのパスワード暗号化にあったバグの話 • http://www.slideshare.net/herumi/ms-office-54510219 • 属性ベース暗号の実装でIEEE trans. on Compute
暗号と数学はどういう関係があるの？
答え：暗号は「数学的問題」に基づいています TLSにも使われている公開鍵暗号では、公開鍵と秘密鍵のペアを作成して使用する。ペアの片方で暗号化したデータは、対となる鍵でしか復号できない。公開鍵と秘密鍵の数学的な関係はわかっているのに、公開鍵からは秘密鍵を求めらない──。このような巧みさを実現できるのは、「公開鍵から秘密鍵を求めることは困難で、秘密鍵と公開鍵を生成するのは容易」という、非常に都合のよい一方向性を備えた数学理論（数学的問題）を基にしているからだ。 現在使用されている公開鍵暗号は、「素因数分解問題」「離散対数問題」「楕円曲線上の離散対数問題」のいずれかに基づいている（図9）。素因数分解問題は、桁数の大きな合成数▼を素因数分解する問題だ。RSAなどがこれに基づいている。2つの素数 p 、q を作った人は、その積 n を容易に求められるが、n から p と q それぞれを求めるのは困難
リードソロモン符号の技術解説 株式会社シグリード(SIGLEAD Inc.)
リードソロモン符号の訂正能力tは、式3-1で表わされる。但し、nは符号シンボル数、kは情報シンボル数である。 【式3-1】 n-kは冗長シンボル数を表すことから、4シンボルの誤りを訂正するには8シンボルの冗長シンボル、8シンボルの誤りを訂正するには16シンボルの冗長シンボルを付加すればよいことが分かる。このことから、リードソロモン符号の最小距離dminは式3-2で表すことができる。 【式3-2】 シングルトンの限界式は、最小距離が“冗長シンボル数+1”以下にしかならないことを意味している。式3-2と式3-3から、リードソロモン符号の最小距離はn-k+1となる。従って、リードソロモン符号はシングルトンの限界式を等号で満たし、この意味においても非常に良好な符号であるといえる。 リードソロモン符号の誤り訂正はシンボル単位で行われることに注意が必要である。n=15、k=11、t=2のGF（2^4）
Hash Function
ハッシュ関数 ハッシュ関数とは ハッシュ関数（暗号学的ハッシュ関数）は，入力データに対して暗号変換に似た処理(攪拌処理)を繰り返し施すことにより一定長(128～512ビット程度)のデータになるように入力データを圧縮する関数である． メッセージダイジェストやフィンガープリントとも呼ばれる． ハッシュ値の計算は比較的単純であり，共通鍵暗号に比べて処理が数十～数百倍以上も速い．このため，ハッシュ関数は以下に示すように情報セキュリティシステムの各所で用いられている． コンピュータのハードディスク上に生のパスワー ドを保存する場合，そのままでは危険なため，パスワードのハッシュ値を保存する． ログイン時のパスワードからハッシュ関数によりハッシュ値を計算し保存されている値と比較する． 乱数データを生成するために，幾つかの初期データをハッシュ関数に入力しデータを攪拌する． ディジタル署名を生成する際の前処
機械学習を初めて勉強する人におすすめの入門書 - old school magic
概要 私が機械学習の勉強を始めた頃、何から手を付ければ良いのかよく分からず、とても悩んだ覚えがあります。同じような悩みを抱えている方の参考になればと思い、自分が勉強していった方法を記事にしたいと思います。 目標としては、機械学習全般について、コンパクトなイメージを持てるようになることです。 そのためにも、簡単な本から始めて、少しずつ難しい本に挑戦して行きましょう。 入門書 何はともあれ、まずは機械学習のイメージを掴むことが大切です。 最初の一冊には、フリーソフトでつくる音声認識システムがおすすめします。 フリーソフトでつくる音声認識システム - パターン認識・機械学習の初歩から対話システムまで 作者: 荒木雅弘出版社/メーカー: 森北出版発売日: 2007/10/17メディア: 単行本（ソフトカバー）購入: 45人 クリック: 519回この商品を含むブログ (38件) を見るレビュー :
Bitcoinは計算量理論から見て「無限連鎖講」である
「ビットコイン（Bitcoin）」はデータ交換の仕組みであり、決済や蓄財など貨幣であるかのように使われています。このため、IT（情報技術）、ビジネス、経済、社会といった様々な面から論じる必要があります。『ビットコイン・ホットトピックス』欄には、多様な論点の記事を掲載していきます。今回は京都大学の安岡孝一准教授に、計算量理論の立場から寄稿していただきました。（日経コンピュータ編集部） 「Mt.GOX」の破綻（関連記事）によって一躍有名になった感のあるBitcoin（ビットコイン）だが、この期に及んでも、いまだBitcoinを信奉している人々がいて、正直なところ理解に苦しむ。遠慮会釈なく言わせてもらえば、Bitcoinはデジタルマネーとしての設計が極めて悪質で、計算量理論から見て無限連鎖講となっている。別の言い方をすれば、ネズミ講である。 Bitcoinの設計上、新規に発行された通貨を誰が受け
見落としがちな整数関連の脆弱性（後編）
見落としがちな整数関連の脆弱性（後編）：もいちど知りたい、セキュアコーディングの基本（5）（1/2 ページ） 前回に続き、バグの中でも大きな割合を占める整数の取り扱いに関する脆弱性について解説します。今回取り上げるのは「切り捨て」「符号拡張／ゼロ拡張」についてです。 「Coverity Scan レポート」にみる整数関連のバグ 初めに、脆弱性に関する最近のトピックスとして「Coverity Scanレポート」を紹介したいと思います。 2013年5月7日、静的解析ツールベンダの米Coverityは、2012年度版「Coverity Scan レポート」を公開しました。 Coverityは、自社のコード解析ツールを使ってオープンソースソフトウェア（OSS）を解析し、解析結果を無償で開発者に提供することを通じて、OSSコミュニティのコード品質向上に寄与する「Coverity Scan」プロジェク
論理的に考えることの強力さを一生忘れなくさせる世界一くだらない問題
学校で教える内容を増やすとか減らすとかいう話を聞くと、思い出すことがある。 学校の授業で聞いたことで、今も覚えていることといえば、どれも余計なことばかりだ。 人間が不真面目にできているせいかもしれないが、意思伝達から冗長さや不要なものを除いていくと、いつしか何も伝わらなくなってしまうんじゃないかと思ってしまう。 以下で紹介するのも、むかし雑談のように聞いて、今も忘れがたく頭の片すみにあるバカ話である。 この主張を調査によって検証するためには、髪の毛の数を数えるという手間のかかる作業を、膨大な人数分繰り返すことが必要である。 ほとんどの人にとっては不可能であり、また可能な者がいたとしても、この主張の成否を知ることにはあまりにメリットがないので、調査が実施される見込みはほとんどない。 ではこの件は、人類にとって永遠に謎のままなのかといえば、そうではない。 我々は思考の力によって結論を得ることが
hnwの日記 - PHPの奇妙なround関数
(2012/11/01追記) 4年ほど前の記事「PHP5.3.0alpha3のround関数の実装がPHP5.2.6と変わった - hnwの日記」でお伝えした通り、PHP 5.3.0から別の実装が採用されており、本ページで指摘しているような挙動のPHPは既に絶滅危惧種です。念のため。 さて、プログラミングの話題もたまには書いてみます。今回はPHPのround関数の挙動が変だ！という話題です。 round()は浮動小数点数を四捨五入する関数で、大抵の言語に同じ名前で実装されているかと思います。ではPHPのround関数の何が問題なのか、ちょっと試してみましょう。 $ uname -sro Linux 2.6.9-42.0.10.plus.c4smp GNU/Linux $ php --version PHP 5.1.6 (cli) (built: Feb 23 2007 06:56:38)
統計数理研究所 Random Number Generator
こちらでは、定まった形式の乱数データをすぐに取得頂けます。乱数データは30分おきに新しいものに更新されています。 個数は全て100個で、1個ごとに改行されて出力されています。（改行コードはWindows(CRLF)です）
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Hatena ID
人を動かすデザイン力 | キャリワカ：仕事術 | nikkei BPnet 〈日経BPネット〉
