最近の 45 度回転事情 - Lilliput Steps
こんばんは, kagamiz です! ちょうど 1 歳老けたところです :). この記事は Competitive Programming Advent Calendar 2014 の 21 日目の記事として書かれました. この記事では, 最近ぼくが見た範囲で出題された 45 度回転の問題を紹介していこうと思います.ちなみに僕の中の最近は過去 6 年くらいまで含むのでご注意下さい. 1. 45 度回転の幾何学的解釈 競技プログラミングで 45 度回転 というと, 入力として与えられた 2 次元平面の点 を ないし に変換する操作を指すことが多いです. 数学的な意味で, 点 を原点に対して 45 度回転するという操作は, 行列を用いて と表されるので, という操作は という位置ベクトルを, 倍して 45 度回転した位置に変換することを表しています. 勝手に大きさを 倍していいか心配になります
Gears – Bartosz Ciechanowski
I’ve always been fascinated by mechanical gears. There is something captivating about the way their teeth come together to create a fluid, unified motion: In this blog post I’d like to look at these simple machines up close. I’ll explain how gears affect the properties of rotational motion and how the shape of their teeth is way more sophisticated than it may initially seem. Movement is important
Floating Point Math
Floating Point Math Your language isn’t broken, it’s doing floating point math. Computers can only natively store integers, so they need some way of representing decimal numbers. This representation is not perfectly accurate. This is why, more often than not, 0.1 + 0.2 != 0.3. Why does this happen? It’s actually rather interesting. When you have a base-10 system (like ours), it can only express fr
「月を入力すると日を返す多項式」と中国剰余定理 - tsujimotterのノートブック
「月を入力すると日を返す多項式」の話が、Twitterのタイムライン上で話題になりました。 togetter.com どんな話題かというと、多項式 を以下のように定義したとき この に を代入すると、 となり、月を入力すると日を返す多項式になっています！すごい！ こんな多項式をいったいどうやって求めるんだろうかと、気になったかたはいるんじゃないかと思います。 これについては 中国剰余定理 が使えるということを、Iwao KIMURA ( @iwaokimura ) さんが、以下のツイートで教えてくださいました。 月を入力すると日を返す多項式．中国の剰余定理のいい例ですね．sagemathだとコマンド一発． pic.twitter.com/F15nosE2ia— Iwao KIMURA (@iwaokimura) 2018年10月21日 中国剰余定理は私の好きな定理の一つですが、このような応
珍しいSHA1ハッシュを追い求めて - プログラムモグモグ
「SHA1ハッシュってあるだろう？」 放課後、いつものように情報処理室に行くと、高山先輩が嬉しそうな顔でそう言った。 「ええ、SHA1、ありますね」 「SHA1って何桁か覚えているかい？」 「えっと…」 一年下の後輩、岡村が口を開いた。 「50桁くらいはありましたっけ…？」 先輩はパソコンに向かって何かを打ちはじめた。 現在、情報部の部員は三人しかいない。部長の高山先輩と、二年の自分と、後輩の岡村だ。いや、正確に言うと、先輩の学年にはもう少しいたのだが、もうほとんど部室に来ることはなくなってしまった。無理もない、この季節になると先輩たちは受験勉強で忙しくなる。 「例えば、こういうふうに… 適当なSHA1の長さを…」 echo -n | openssl sha1 | awk '{print length}' 部長だけは今も部活に来てこうやって色々なことを教えてくれている。本人曰く、普通に勉強
統計学入門−目次
最終更新日：2022年08月24日 前口上へ 第1章へ webmaster@snap-tck.com Copyleft (C) 2000 SNAP(Sugimoto Norio Art Production)
Swift - Introducing PONS = Protocol Oriented Number System - Qiita
まだ荒削りですが、お披露目してもいいところまで来たので。 https://github.com/dankogai/swift-pons 売り口上 これでSwiftでも GMPとか外部ライブラリなしで任意精度整数(BigInt)や任意精度分数(BigRat)や任意精度浮動小数点数(BigFloat)が使えるようになります。 外部依存がないので、Xcodeでなくてもswiftcがあれば使えます。もちろんOS XだけでなくてLinuxもサポート その任意精度数も、四則演算以外の演算を最初からサポートしています。整数は素数判定できますし、任意精度実数は<math.h>の関数を使えます。 これだけでもかなりハッピーになれます。 でも本当のウリは、そこじゃないんですよ… 承前: 古き良きCの時代 例えばman powとしてみます。こんな答えが返ってくるでしょう。 SYNOPSIS #include <
Google Chromeが採用した、擬似乱数生成アルゴリズム「xorshift」の数理
2015年12月17日、Google Chrome の JavaScript エンジン（処理系）である V8 の公式ブログにて、 JavaScript の標準的な乱数生成APIである Math.random() の背後で使われているアルゴリズムの変更がアナウンスされました。 Math.random() 関数は JavaScript を利用する際には比較的よく使われる関数ですので、親しみのある方も多いのではないかと思います。 新たなバグの発見や、従来より優秀なアルゴリズムの発見によってアルゴリズムが変更されること自体はそれほど珍しくはないものの、 技術的には枯れていると思われる Math.random() のような基本的な処理の背後のアルゴリズムが変更されたことに驚きを感じる方も少なくないかと思いますが、 それ以上に注目すべきはその変更後のアルゴリズムです。 実際に採用されたアルゴリズムの原
JP Morgan Chaseがデリバティブ専用スパコンをFPGAで作った話 #fpgax - スティルハウスの書庫の書庫
金融系でFPGAというとHFTへの応用が知られてるけど、この事例はリアルタイムトレードの話ではない。金融業務で必要とされるバッチ処理やHPC（High Performance Computing）でもFPGAが本格的に使われ始めてるという話だ。 元ネタは、2011年にJP Morgan Chaseの人がスタンフォード大学で講演した内容。このビデオを見ていたらとっっっても面白かったので、 #fpgax 第3回で使う資料として要点を訳し、俺のコメントや補足を追加してみた。 http://www.youtube.com/watch?v=9NqX1ETADn0 （スライドはこちら） なお、FPGAも金融も素人なので、勘違いや誤訳があるかもしれない。FPGAとは何かよく知らない人はこちらをどうぞ。 リーマン・ショック対策のスパコン開発 JP Morgan Chaseは、社債やモーゲージ（不動産を担保
いつからその方法で偏りのない乱数が得られると錯覚していた？ - アスペ日記
私はつい最近まで勘違いしていました。 ここのページに書いてあるような方法で、一様分布する整数が得られると。 int random(int n) { return (int)(( rand() / (RAND_MAX + 1.0) ) * n); } この方法、一見すると実に一様分布が得られそうに見えるんですよね。 どういう思考回路を通っているかというのを自己分析すると、次のような感じです。 1. rand() では 0〜RAND_MAX のランダムな整数が得られる。 2. それを RAND_MAX + 1 で割ると、[0, 1) に一様分布する実数が得られる。 3. [0, 1) の一様な実数を n 倍して小数点以下を切り捨てたら、0 から n-1 に一様分布する整数が得られる。 これの罠なところは、1 と（特に）3 が正しいというところだと思います。 ただ、2 がダウト。 思いっきりダウ
コンプガチャの数理 -コンプに必要な期待回数の計算方法について- - doryokujin's blog
目次 1. 『コンプガチャの数理 -コンプに必要な期待回数の計算方法について-』 2. 『「数学的ゲームデザイン」というアプローチ』 3. 『コンプガチャの数理 -ガイドラインに基づいたゲームデザイン その1-』 4. 『コンプガチャの数理 -ガイドラインに基づいたゲームデザイン その2-』 目的 コンプガチャのコンプに必要な回数を求める問題は「The Coupon Collector's Problem」と呼ばれる数学モデルの枠組みに沿った美しい問題である事を述べ，いくつかの有用な結果を示す。 ※ あくまで個人研究のつもりで書いたので，色々不備があるかもしれません。その際は一言頂けると助かります。 定義 コンプガチャ問題を Coupon Collector's Problem に準じた形で書くと以下の様になる： 「全部で n 種類のアイテムがあって，1つのガチャの中にアイテムが1つ入って
数学の歴史２万年＋αを２５０のマイルストーンでまとめてみた
数学の営みは、我々が想像する以上に古く長い。 先史時代の遺物にも、計数の概念や天体観測に基づいた測時法があったことを示すものが発見される。 今回は、可能な限り（というかやり過ぎなくらいに）遡り、専門研究から数学遊戯、ポピュラー文化まで渉猟し、数学の歴史を画するマイルストーン（画期的出来事）を見つけ出そうとするクリフォード・ピックオーバーのThe Math Bookが取り上げる項目を手掛かりに、人類（すらも踏み越えているのだが）の営む数学の歴史を振り返ってみる。 c. 150 Million B.C. 経路積分する蟻 Ant Odometer サハラサバクアリCataglyphis fortisは、経路積分によって巣からの位置を把握する。回り道をしながら食べ物に辿り着いても最短距離で巣へ戻る。風のために砂丘の高さが変わっても、登りのために増えた分を差し引いて、巣までの水平距離を間違うことがな
平方根を使わずに高速で２点間の距離を近似する - きしだのHatena
２点間の距離の計算では平方根が必要になりますが、平方根は少し重い計算です。ということで、平方根を使わず、掛け算・割り算・足し算と絶対値・最大・最小だけで距離を近似する方法についての記事を翻訳してみました。 flipcode - Fast Approximate Distance Functions (12:02 補足：おそらく今の標準的なCPUでやる意味はほとんどないと思います。近似のアプローチとして面白いというくらいの話。Z80でやりましょう) 距離関数高速近似 by Rafael Baptista (27 June 2003) ２点間のユークリッド距離を求める計算式は次のようになる。 二次元では次のようになる。 この関数の計算には、平方根が必要になる。これは最近のコンピュータでも高価な計算である。平方根は逐次近似によって求められる。つまり、コンピュータは平方根近似のループを行って、与え
ベイズ推定を知っているフリをするための知識
最近はベイジアンが増えてきて、実用分野での利用も進んでいるようだ。話題としては知っておきたいが、世間一般には理解に混乱を生んでいるようだ。 ベイズ推定は入門レベルの統計学の教科書ではオマケ的な扱いがされており、実際に伝統的な統計手法を拡張している面が強い。そういう意味では、誤解や混乱があっても仕方が無い。 利用する必要があるのか無いのか良く分からない点も多いのだが、知らないと告白するのも気恥ずかしいかも知れない。自分ではベイズ推定で分析を行わない人が、ベイズ信者と話をあわせるために最低限知っておくべき事をまとめてみた。 1. ベイズ推定とは何か？ ベイズ推定とは、ベイズの定理を応用した推定手法だ。端的に理解するためには、最尤法に事前確率を導入している事だけ覚えれば良い。これで哲学的議論を全て回避してベイズ推定を把握することができる。 下の(1)式ではπ（θ）が事前確率、π(θ|x)が事後確
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
望月新一＠数理研
やたらすごい素数 - INTEGERS
アンパンマン
SciPy — SciPy v0.14.0 Reference Guide
World of Mathematics – Mathigon
数学基本用語集 - 翻訳百景