The Beauty of Bézier Curves
Bézier curves - how do they do? They're used for animation, text rendering, and all sorts of curved shapes! But how do they actually work? well, like, that's what the video is about, so, watch it to find out etc!! • Lots of love to 💛 Jazz "queenjazz" Mickle for making the music ❱ https://queenjazz.bandcamp.com/ 💙 Grant "3Blue1Brown" Sanderson for pushing me to finally do this ❱ https://youtub
Speeding up `atan2f` by 50x
2021-08-16 Speeding up atan2f by 50x \mathrm{atan2} is an important but slow trigonometric function. However, if we’re working with batches of points and willing to live with tiny errors, we can produce an \mathrm{atan2} approximation which is 50 times faster than the standard version provided by glibc. Perhaps more impressively, the approximation produces a result every 2 clock cycles. This is ac
Introduction to Locality-Sensitive Hashing
Tyler Neylon — (Got a machine learning project? Email me: tyler@unboxresearch.com) [Formats: html | pdf | kindle pdf] Locality-sensitive hashing (LSH) is a set of techniques that dramatically speed up search-for-neighbors or near-duplication detection on data. These techniques can be used, for example, to filter out duplicates of scraped web pages at an impressive speed, or to perform near-constan
超高速！多倍長整数の計算手法【後編：N! の計算から円周率 100 万桁の挑戦まで】 - Qiita
4-1. N! の高速な計算 $N! = 1 \times 2 \times 3 \times 4 \times \cdots \times N$ を計算してみましょう。 $N!$ は場合の数を求める問題でよく出てきて、こんな感じのものが求まります。 $1, 2, ..., N$ が書かれたトランプのカードが 1 枚ずつあるとき、これを一列に並べる順番は何通りあるか？ 例えば、$N = 13$ の場合 $13! = 6,227,020,800$ 通り、のように計算できます。 また、$N!$ は二項係数 $_NC_K$ を求めるのにも使われます。 $N!$ が求まれば、$_NC_K = N! \div K! \div (N-K)!$ で掛け算・割り算するだけで計算できますね。 $N$ 個の区別できるボールから $K$ 個を選ぶ方法は何通りか？ これが $_NC_K$ になります。例えば、$N
超高速！多倍長整数の計算手法【前編：大きな数の四則計算を圧倒的な速度で！】 - Qiita
1. はじめに ～メインを読むための準備～ まず、大きな数の計算の話をする前に、少しコンピューターと計算回数について話しましょうか。 コンピューターは、現代ではソフトウェアやアプリケーションの開発に使われていますが、これには重要な背景があります。これは「計算がめっちゃ速いこと」です！人間なんかと比べたら、圧倒的な計算スピードを誇ります。 1-1. 人間の計算速度はどのくらい？ まず人間はどのくらいの速度で計算できるでしょうか？速い人も遅い人もいると思います。 例えば、$628 \times 463$ の計算を、今やってみましょう。10 秒以内で計算できたらかなり速い方でしょう。この計算では、次のように「単純計算」を合計 28 回もしていることになります。 9 回の 1 桁 × 1 桁の掛け算 6 回の 1 桁 × 1 桁の足し算 13 回の繰り上がり計算 もし $628 × 463$ が
数学オリンピックの問題にプログラミングで挑戦！ ～数え上げから幾何問題まで～ - Qiita
1. はじめに はじめまして！高校 2 年生の square1001 です。 私は主に「競技プログラミング」に取り組んでいます。情報オリンピックの世界大会の日本代表になったり、TopCoder や AtCoder などのプログラミングコンテストにも出場したりしています。コンテストに出場するだけでなく、問題の作成も積極的にやっています。 ところで、みなさんは、「日本数学オリンピック」という大会を知っていますか？これは、日本全国の高校生以下を対象にした、数学の問題解決能力を競う、全国的にとても有名な大会です。本記事では、日本数学オリンピックの予選で出題される問題を、難しい数学的知識や数学的考察を使わずに、「コンピューターの高い計算能力」と「アルゴリズムの力」でチャレンジしてみます！ 導入 - コンピューターが世界を変えた！ プログラミングを実務などでやっている方の中には、「システムやアプリケー
[多項式・形式的べき級数]（１）数え上げとの対応付け | maspyのHP
概要 ある種の数え上げの計算は、多項式・形式的べき級数に対する計算と結び付けることができます。数え上げの問題を、多項式・形式的べき級数に対する計算と読み替えて、代数的な式変形により答を得る手法が、競技プログラミングにおいても注目され始めているようです。 さまざまな問題を文字式の問題に翻訳できるようになっておけば、文字式に対して理解を深めるだけで、幅広い問題に対する解決力を同時に伸ばしてしまうことができます。また、中高数学の学習で学んだ文字式や関数の式変形に対する能力が利用できることも魅力になると思います。 ここでは、数え上げの対象を多項式・形式的べき級数の問題に対応させる練習をしていきましょう。（逆に言うと、対応させた先の「多項式・形式的べき級数の問題を解く」方法の説明は、この記事では扱いません。） 多項式への言い換えは、経験がないうちは、唐突に感じてしまうことがあると思いますが、頻出のパ
![[多項式・形式的べき級数]（１）数え上げとの対応付け | maspyのHP](https://cdn-ak-scissors.b.st-hatena.com/image/square/d3b83cb0b151f85f4ab582d54745629884ec04db/height=288;version=1;width=512/https%3A%2F%2Fmaspypy.com%2Fwp-content%2Fuploads%2F2023%2F01%2F5Dth6Yjz_400x400.jpg)
「ループ・再帰・gotoを使わず1から100までの数値を印字する」Conner Davis 氏の回答の考察 - Qiita
2019年6月に以下の記事が投稿されました。 ループ、再帰、gotoを使わずに1から100までを印字するC++プログラムは書けますか？に対するIchi Kanayaさんの回答 - Quora 英語版の記事「How to print 1 to 100 in C++ without a loop, goto or recursion - Quora」から興味深い回答を抜き出して、それにランク付けをしながら和訳してくださっている記事です。 初級や中級は「まぁあるよね（C++知らないけれど……）」という感じですが、 上級とされた「マイクロソフト社のデータサイエンティスト Conner Davis 氏」の回答が面白かった ので、ご紹介を兼ねてその発想の源泉を推測してみることにしました。 Conner Davis 氏の回答 以下に Conner Davis 氏の回答の和訳を引用します。 マイクロソフト
ハルヒ問題（最小超置換問題）の紹介 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに 皆さんこんにちは、「データ構造とアルゴリズムAdvent Calendar」の作成者、文字列大好き文字列初心者の@kgotoです。 一昨年と去年は「文字列アルゴリズムAdvent Calendar」を作り、去年は念願の完走をしました。有り難いことに反響も大きかったです！ 今年は「データ構造とアルゴリズム」と対象を広げて、一瞬でカレンダーの枠が埋まるのでは！？とドキドキしていたのですが、蓋を開けてみるとなんとまだ11日も空きがあります！！ ちょっと寂しいですね。。。 もちろん無理に参加してくれとは言いませんが、この記事を読んでち
K問題：Black and White Boxes - tshitaの備忘録Ⅱ
1. 概要 これは Competitive Programming （その2） Advent Calendar 2016 - Adventar の22日目の記事です． 今年のACM-ICPC 2016アジア地区つくば大会のK問題で組合せゲーム理論に関する問題が出題されました．この問題を通して組合せゲーム理論の紹介をします (考察が中途半端になってしまいました)． 2017年1月5日に追記・修正しました． 解説等は公開されています． 問題 ： Problem K : Black and White Boxes 判定データ ： http://icpc.iisf.or.jp/past-icpc/regional2016/judge-data/K/ 講評 ： http://icpc.iisf.or.jp/past-icpc/comments/2016.pdf#page=5 講評スライド ： htt
Google Chromeが採用した、擬似乱数生成アルゴリズム「xorshift」の数理
2015年12月17日、Google Chrome の JavaScript エンジン（処理系）である V8 の公式ブログにて、 JavaScript の標準的な乱数生成APIである Math.random() の背後で使われているアルゴリズムの変更がアナウンスされました。 Math.random() 関数は JavaScript を利用する際には比較的よく使われる関数ですので、親しみのある方も多いのではないかと思います。 新たなバグの発見や、従来より優秀なアルゴリズムの発見によってアルゴリズムが変更されること自体はそれほど珍しくはないものの、 技術的には枯れていると思われる Math.random() のような基本的な処理の背後のアルゴリズムが変更されたことに驚きを感じる方も少なくないかと思いますが、 それ以上に注目すべきはその変更後のアルゴリズムです。 実際に採用されたアルゴリズムの原
Fast Approximate Logarithms, Part I: The Basics
Performance profiling of some of the eBay code base showed the logarithm (log) function to be consuming more CPU than expected. The implementation of log in modern math libraries is an ingenious wonder, efficiently computing a value that is correct down to the last bit. But for many applications, you’d be perfectly happy with an approximate logarithm, accurate to (say) 10 bits, especially if it we
A New Provable Factoring Algorithm
Factoring, factoring, the whole day through, keeps on my mind—apologies to Hoagy Carmichael and Stuart Gorrell Michael Rubinstein is an expert on number theory, who is on the faculty of the University of Waterloo. He is one of the organizers of a 61-birthday symposium being held December 15–19 in Princeton for my friend and former colleague, Peter Sarnak. I guess it is a matter of taste for a numb
nCr mod mの求め方 - uwicoder
これはCompetitive Programming Advent Calendar Div2012に投稿された記事のようです。 今年ははてなではなくatwiki(こちら)のほうでやります。はてなはTeXが汚かったりソースコードの折りたたみができない等色々アレなので・・。 さて、今回は数え上げ・数学ゲーの常連、Combinationの剰余の計算について書きます。正確にはBinomial Coefficient(2項係数)ですね。ここでは1秒以下で求められることを目安に制約をつけてそれぞれについて解説します。 TeX的に楽な式で書きたいとおもいます。 0o_ ※一応Javaコードを添えてはいますが、完全なものとは限らないので、全部欲しい場合は関数名から察するか@uwitenpenにmentionください。 mがsqaurefree(4以上の平方数で割り切れない)のとき mを素因数分解して素数
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
組み合わせ最適化問題に対する実用的なアルゴリズムとその応用 - Speaker Deck
http://akira.ruc.dk/~keld/teaching/algoritmedesign_f05/Artikler/05/Manber88.pdf