NTT(数論変換)のやさしい解説 - Qiita
この記事は、高速フーリエ変換の1つのバリエーションである、Numeric Theory Translation(数論変換)の詳しい解説記事です。 あまりなかったので書きました。 数論変換にありがちな なんで$10^9 + 7$じゃダメなのか 原始根って何？ とかについてもこれを見ればわかります。 前提知識としては、Fast Fourier Translation(高速フーリエ変換)が必要です。 kaage大先生のQiita記事とかは中高生にもわかりやすく書かれています。 下に一応自分の勉強ノートを載せます。(上の記事の行間を埋めた感じです) では、数論変換について説明したいと思います。 高速フーリエ変換の弱点 高速フーリエ変換は正しいですが、弱点として精度が足りないというのがあります。 なぜならば、複素数の1の$2^m$乗根は計算上ではれっきとした64bit倍精度浮動小数点のdoubleの
プログラミング的ゾンビとプログラミングの学習について
背景 こちらのまとめを読んで、「数学的ゾンビ」と面白い考え方だなと思うので、プログラミング的ゾンビというのも考えられないかと考えてみた。そして、同時にプログラミングの理解だとかプログラミングの学習とか、そのところも同時に書いていければなーとかでいろいろ書いてみた。 プログラミング的ゾンビについて プログラミング的ゾンビとは？ プログラミング的ゾンビというものを考えたとき、それはどういうものか？考えてみると以下の2つの点があてはまれば、プログラミング的ゾンビだと言えるだろう。 プログラムを書けるように見える プログラムの内容や意味するところは分かっていない と考えたとき、どのような人がプログラミング的ゾンビだろうか？と思うわけで、具体例を示していこう。 プログラミング的ゾンビの具体例 こうしたとき、プログラミングゾンビの一番典型的なのが、誰かが書いたコードをひたすらコピペして作る人たちだ。そ
プログラミング教育での悪い癖 - ビスケット開発室.
先日，中学生にビスケットの授業をやったのですが，プログラミング教育の悪い癖が出てしまったので，ちょっと書いてみたいと思います． １回目は９０分でビスケットランドと感染やジャンケンなどをやりました．これはこれで定番な内容でそこそこ上手く行ったと思います．普段，幼稚園児を相手にしている反応の大きさと比べたら小さな反応でしたが． で，２回目で彼らにはもっと難しいことに挑戦してもらおうということで，倉庫番を作ってもらいました． 最近の人たちにはこのゲームはそんなに知られていないので，まずは簡単に説明してから，６名くらいのグループに１台，倉庫番が入ったタブレットを渡して遊んでもらいました． その後，ビスケットで倉庫番の作り方を説明して作ってもらいます．作り方の説明は一番遅い人に合わせてやっているので，すぐできてしまう人は暇なようで，たとえば，斜めに動けるようにするとか，いろいろと余計なものを作ってし
C++1zの言語拡張まとめ - Faith and Brave - C++で遊ぼう
2017年中に改訂される予定のC++14の次のバージョン、仮称C++1zの更新内容をまとめました。正式名称はISO/IEC 14882:2017、通称C++17になる予定です。 C++1zの概要 C++17は、C++11ほど大きな変更はありませんが、重要な言語機能(構造化束縛とか)や、広く適用できるライブラリ機能が多く入っています。ライブラリは、ファイルシステムが入るのが大きいですね。ようやく標準ライブラリのみで、ファイルサイズを取得したり、ファイルのコピーや移動などを扱えるようになります。 策定体制として、Study Group (SG)と呼ばれる専門家グループがたくさん作られ、そこで同時並行に議論、策定が進められていた仕様のうち、固まったものがいくつかC++1zで導入されます。 それぞれの専門家グループで考えられた仕様はTechnical Specification (TS)という単位
有理数同士の大小比較
JAG の ICPC 模擬地区予選 2015 の最中に, ジャッジルームで思いついたこと. イントロ 誤差を避けるために有理数を使うとき, オーバーフローするボトルネックは, 多くの場合, 有理数同士の大小比較になる. (逆に, 有理数同士の大小比較がボトルネックにならないときは, 別のテクニックで誤差を避けられることがある) そこで, 有理数の分母分子自体はオーバーフローしていないときに, 有理数同士の比較を, なるべくオーバーフローさせずに行う方法を見る. つまり, 次のような sgn 関数を作りたい. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39template<class Int> struct Fraction{
Rustは何が新しいのか（基本的な言語機能の紹介） - いもす研
Rust は、Firefox を開発する Mozilla が開発し、次世代ブラウザの開発に使っているプログラミング言語です。借用検査という概念を導入することによりメモリ安全およびデータ競合安全をコンパイラが保証する言語であり、2015年中頃の安定版のリリースあたりから次第に注目を集めるようになりました。 メモリ安全とは、メモリの範囲外アクセスや二重解放、ヌル参照、未初期化領域へのアクセスがない状態を表します。ただし、Rust の言うメモリ安全とは、メモリリークをしないことを保証するものではありません。 データ競合安全とは、あるひとつのオブジェクトに対しての読み込みおよび書き込みのが同時に起き結果が不定になる状態にならないことを表します。競合状態とは異なります。 無名関数という概念を様々な言語が次々と導入したように、プログラミング言語は相互に影響を及ぼし徐々に変化しています。Rust は「寿
Swiftのエラー4分類が素晴らしすぎるのでみんなに知ってほしい - Qiita
これは Swift Tweets の発表をまとめたものです（次回開催はこちら）。イベントのスポンサーとして Qiita に許可をいただいた上で投稿しています。 ありがとうございました！Q&Aは他の人の発表中でも構わないのでリプを飛ばして下さい。 続いては僕 @koher の発表で、タイトルは "Swiftのエラー4分類が素晴らしすぎるのでみんなに知ってほしい" です。 #swtws — koher (@koher) 2017年1月14日 第 1 部: Swift の 4 種類のエラーについて あまり知られてませんが、エラー処理について、 Swift 2.0 設計時に Core Team がまとめた "Error Handling Rationale and Proposal" というドキュメントがあります。このドキュメントは、僕が去年 try! Swift で発表した際にも参考文献にしまし
C++ Format
C++ Format: a small, safe and fast formatting library for C++.C++ Format (cppformat) is an open-source formatting library for C++. It can be used as a safe alternative to printf or as a fast alternative to IOStreams. Format API The replacement-based Format API provides a safe alternative to printf, sprintf and friends with comparable or better performance. The format string syntax is similar to th
Old New Thing: 超最新の実験的C++機能、オタマジャクシ演算子
この実験的オタマジャクシ演算子を有効にするには、C++ファイルの上部に以下のような行を追加しなければならない。 #define __ENABLE_EXPERIMENTAL_TADPOLE_OPERATORS 例えば、以下はオタマジャクシ演算子を使ったコードの例である。 #define __ENABLE_EXPERIMENTAL_TADPOLE_OPERATORS #include <ios> #include <iostream> #include <istream> int __cdecl main(int, char**) { int n = 3; std::cout << "3 + 1 = " << -~n << std::endl; std::cout << "(3 - 1) * (3 + 1) " << ~-n * -~n << std::endl; return 0; } この
Non-Uniform Random Variate Generation
Non-Uniform Random Variate Generation (originally published with Springer-Verlag, New York, 1986) Luc Devroye School of Computer Science McGill University Preface to the Web Edition When I wrote this book in 1986, I had to argue long and hard with Springer Verlag to publish it. They printed a small number of copies, and never bothered with a second printing, even though, surprisingly, there seemed
C++のコンパイルエラー爆発を競うコンテスト - Faith and Brave - C++で遊ぼう
Results of the Grand C++ Error Explosion Competition 少し前に、C++のコンパイルエラーの長さを競うコンテストが開催されていました。 受賞のカテゴリは2つあり、ひとつめは最小コードで最大のコンパイルエラーを出した人、もうひとつは芸術的な評価による受賞です。 最小コードで最大のコンパイルエラー この部門で優勝したのはEd Hanwayさんという方で、ソースコード量に対して59億倍のコンパイルエラーメッセージを出力したそうです。 それには、自身を2回インクルードするという手法が使われていたそうです。 #include ".//.//.//.//jeh.cpp" #include "jeh.cpp" 次点として、インクルードに後方参照を使用した、7億9千万倍のコンパイルエラーを出力するコード： #include "set>.cpp" #incl
モンテカルロ法で次元の呪いを体験する - ぷる日記
MCMC講義（伊庭幸人） 難易度 - YouTube を観ていたところ、「(モンテカルロ法で円周率を求めるのは高次元になるとうまく行かなくなるので)一度は必ずやってみるべし！」と言われたのでやってみました。(4:17～) もちろんSASで。 N次元単位超球の(超)体積 超球を包む1辺の長さが2の超立方体の(超)体積 円周率を求める コードをシンプルにするために球の中心を原点にとり、すべての次元に対して正の方向のみを考えます。すると、球内部の体積は、単位立方体の体積はとなります。 この立方体の中に一様ランダムに点を打っていったときに、点を打った数と球の中に点が入ったときの数の比率が立方体の体積に対する球内部の体積の比率に近くなることが期待できます。 式で書くと、 について整理すると となります。*1 コード %macro pi(dim=, rep=); data pi; do i = 1 t
Visual Studioではなく、Windows付属のcsc.exe だけでC#実行ファイルを作る - Qiita
PC遠隔操作事件で弁護士さんが容疑者にはC#を作成する環境（Visual Studio 2010）がなかったと主張( http://goo.gl/wJyOc ) をされています。 この事件の事実や行方、あるいは今の容疑者は真犯人なのかといった事柄とは別に、C#のそこの部分を自分の手で確認してみたくなったので、極簡単なコンパイルのテストをしてみました。 「まぁ、C#の世界はよくわからないけど、念のために今Framework\v4.0.30319のcsc.exeでコンパイルしてみたら、hello.exe の中にそのGeneratorバージョンを埋め込めたので、できることはできるのかなと思う。」http://goo.gl/wqlWg ということで、Visual Studio 2010なしでC#の実行ファイル作成をテストしてみたメモです。(参考：Windows にデフォルトでインストールされている
sprintf を最大10倍以上高速化するプリプロセッサ「qrintf」を作った
最近H2OというHTTPサーバを書いているのですが、プロファイルを取ってみるとsprintfが結構な時間を食っていて不満に感じていました。実際、sprintfは数値や文字列をフォーマットするのに十徳ナイフ的に便利なので、HTTPサーバに限らず良く使われる（そしてCPU時間を消費しがちな）関数です。 では、sprintfを最適化すれば、様々なプログラムが より高速に動作するようになるのではないでしょうか。ということで作ったのが、qrintfです。 qrintfは、Cプリプロセッサのラッパーとしてソースコードに含まれるsprintfの呼出フォーマットを解析し、フォーマットにあわせたコードに書き換えることで、sprintfを高速化します。 たとえば、以下のようなIPv4アドレスを文字列化するコード片を sprintf( buf, "%d.%d.%d.%d", (addr >> 24) & 0xf
1300 みたいなのを 1.3 K bytes みたいに整形するメソッドってどういう名前にすれば良いのか - おともだちティータイム
y***s: 英語にくわしいフバさんに質問なんですが y***s: 1300 みたいなのを 1.3 K bytes みたいなのに整形するメソッドってなんてメソッド名にすればいいんですか fuba: -h When used with the -l option, use unit suffixes: Byte, Kilobyte, Megabyte, Gigabyte, Terabyte and Petabyte in order to reduce the number of digits to three or less using base 2 for sizes. fuba: man ls にはこんなかんじでかいてる y***s: なるほど shunirr: human readable fuba: to_human_readable_string みたいなのだるそうではある sh
デザイナーのわたしがプログラミングの基礎をだいたい3日で覚えた1つの方法
works デザイナーのわたしがプログラミングの基礎をだいたい3日で覚えた1つの方法 Posted by Miki Ishijima on May 20, 2014. フルスタックエンジニア！フルスタックエンジニア！ 最近なんでもかんでも出来る人が求められていますね。Webデザイナーの人でも簡単なプログラムに触れる機会は以前より格段に増えています。 わたしもプログラムを覚えたいと思い、勉強していました。しかしそれは、禁煙と同じようなもので触ってはやめて、触ってはやめて、飽きてしまうの繰り返しでした。 身につかない原因 プログラムの勉強会や、本、ブログなどを読んでもなぜ身につかないのか。難しいというのは理由ではありません。 むしろ、基礎の「き」くらいであればコーディングと同じくらい簡単です。 わたしが一番の原因だと考えるのは作りたいものがないというコトです。 子供向けプログラム学習アプリケー
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Rust の最初のステップ - Training
http://minerva.cs.uec.ac.jp/curling/wiki.cgi?page=FrontPage
http://www2.econ.osaka-u.ac.jp/~tanizaki/cv/papers/gamma_j.pdf
「テクスチャの異方向フィルタリング」ってなに？ - 4gamer.net