Julia の素数周りの実装 - Qiita
概要 Julia には，素数周りの関数が標準で組み込まれています．その実装にどんなアルゴリズムが採用されているのか調べてみました． いきなりまとめですが，Julia の素数周りのアルゴリズムでは， 素数生成: Atkin の篩 Wheel factorization を使った Eratosthenes の篩 [更新] 素数判定: Miller-Rabin 素数判定法 素因数分解: 試し割り法 + Pollard-Brent Rho 法 が採用されています．以下，それぞれについて軽く紹介します．ちなみに，この記事では，アルゴリズムの詳細や，計算量の説明はしません．誰かの Julia のコードを調査するとかっかかりにでもなったら幸いです． この記事は，2015-07-13 時点での コード をもとに書きました．動作確認にも，b2528a6e66 の Nightly ビルドを使っています． 素数
素数候補を効率よく絞りこむ「Wheel factorization」について調べたこと - Line 1: Error: Invalid Blog('by Esehara' )
今日の料理 サーモン漬け丼 概要 素数リストの求め方に関しては、前回アトキンのふるいを紹介した。この他にもWheel factorizationという方法がある。調べてみたところ、直接的な日本語の紹介が乏しいので、実装したついでに、調べた範囲のことについてメモをしておく。 はじめに 素数リストを求める方法にも様々あって、前回はアトキンのふるいを紹介したのだが、論文を読めばわかるように、確かに高速なのかもしれないが、あまり直感的とは言いがたい側面がある。 そんな中、アトキンのふるいに関して調べていた最中にJulia の素数周りの実装 - Qiitaという記事を見つけた。これによれば、「Wheel factorizationを使った Eratosthenesのふるい」にアルゴリズムを変更したことが書いてある。しかし、このWheel factorizationの日本語情報を探してみたのだが、自分
プログラミングコンテストでの動的計画法
2. はじめに • 「動的計画法」は英語で 「Dynamic Programming」 と言います． • 略して「DP」とよく呼ばれます． • スライドでも以後使います． 4. ナップサック問題とは？ • n 個の品物がある • 品物 i は重さ wi, 価値 vi • 重さの合計が U を超えないように選ぶ – 1 つの品物は 1 つまで • この時の価値の合計の最大値は？ 品物 1 品物 2 品物 n 重さ w1 重さ w2 ・・・ 重さ wn 価値 v1 価値 v2 価値 vn 5. ナップサック問題の例 品物 1 品物 2 品物 3 品物 4 U=5 w1 = 2 w2 = 1 w3 = 3 w4 = 2 v1 = 3 v2 = 2 v3 = 4 v4 = 2 品物 1 品物 2 品物 3 品物 4 答え 7 w1 = 2 w2 = 1 w3 = 3 w4 = 2 v1 = 3 v
Evolutionary algorithms and analog electronic circuits
I've been working for a while on a program that automatically generates analog electronic circuits using evolutionary algorithms. It's still very much a work in progress, but I've used it to generate some useful circuits. Current workings of the program is as follows: Programmer decides a goal function, possible constraints, simulation type(AC, DC, Transient), number of nodes and types and values
Neural networks and deep learning
Neural Networks and Deep Learning What this book is about On the exercises and problems Using neural nets to recognize handwritten digits How the backpropagation algorithm works Improving the way neural networks learn A visual proof that neural nets can compute any function Why are deep neural networks hard to train? Deep learning Appendix: Is there a simple algorithm for intelligence? Acknowledge
Redis new data structure: the HyperLogLog - <antirez>
Generally speaking, I love randomized algorithms, but there is one I love particularly since even after you understand how it works, it still remains magical from a programmer point of view. It accomplishes something that is almost illogical given how little it asks for in terms of time or space. This algorithm is called HyperLogLog, and today it is introduced as a new data structure for Redis. Co
GitHub - BonzaiThePenguin/WikiSort: Fast and stable sort algorithm that uses O(1) memory. Public domain.
WikiSort is an implementation of "block merge sort", which is a stable merge sort based on the work described in "Ratio based stable in-place merging", by Pok-Son Kim and Arne Kutzner [PDF]. It's generally as fast as a standard merge sort while using O(1) memory, and can be modified to use additional memory optionally provided to it which can further improve its speed. C, C++, and Java versions ar
SIGHT & LIGHT - How to create 2D visibility/shadow effects for your game
Hello! Today, I will show you how to make something like this: (move your mouse around in the box below) This effect is used in my open-source indie game, Nothing To Hide. It's also found in many other 2D games, like Monaco, Gish, and if this tutorial does its job... maybe your next game! I will show the steps & mistakes I personally made while learning how to create this effect. First, some boile
Core algorithms deployed
Algorithms that are the main driver behind a system are, in my opinion, easier to find in non-algorithms courses for the same reason theorems with immediate applications are easier to find in applied mathematics rather than pure mathematics courses. It is rare for a practical problem to have the exact structure of the abstract problem in a lecture. To be argumentative, I see no reason why fashiona
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
微分積分
Raft:Understandable Distributed Consensus
[PDF] Top 10 algorithms in data mining
New algorithm can dramatically streamline solutions to the ‘max flow’ problem | MIT News