素因数分解アルゴリズム(特にSQUFOF)のこと - 再帰の反復blog
主要な素因数分解アルゴリズム SQUFOFについて 目次 主要な素因数分解アルゴリズム 素因数の性質に依存するアルゴリズム(ρ法、p-1法、楕円曲線法) 素因数の性質に依存しないアルゴリズム(SQUFOF、二次ふるい法、一般数体ふるい法) SQUFOFについて 連分数をもちいた素因数分解 シャンクスの改良 アルゴリズムの説明 例 アルゴリズムの改良 Schemeによるプログラム例 主要な素因数分解アルゴリズム ここでいう素因数分解アルゴリズムは完全に素因数分解をするアルゴリズムではなく因数(約数)をひとつ見つけ出すアルゴリズムなので、完全な分解が必要なら再帰的に実行したり試し割り法と組み合わせる必要がある。 素因数の性質に依存するアルゴリズム(ρ法、p-1法、楕円曲線法) 都合のよい性質を持った素因数を含んでいる場合に成功するアルゴリズム。都合のよい素因数を含んでいる場合は、汎用のアルゴリ
Methods of computing square roots - Wikipedia
Methods of computing square roots are algorithms for approximating the non-negative square root of a positive real number . Since all square roots of natural numbers, other than of perfect squares, are irrational,[1] square roots can usually only be computed to some finite precision: these methods typically construct a series of increasingly accurate approximations. Most square root computation me
楕円曲線暗号アルゴリズムを理解する｜TechRacho by BPS株式会社
お久しぶりです。yoshiです。みなさん、夏を満喫していますか？ 私は溶けそうです。日本の夏はとってもあつい。 覚えている方がいるかどうかは分かりませんが、以前私はRSA公開鍵暗号アルゴリズムを理解するという記事を書きました。今回はその続編（？）です。 楕円曲線について 楕円曲線、という言葉を事前知識無しで見ると、 多分こんな画像が脳裏に浮かぶと思います。違います。 楕円曲線の楕円は楕円積分から現れた言葉で、楕円積分は文字通り楕円の弧長などを求める方法なので全くの無関係とは言えませんが、少なくとも楕円曲線と楕円は別の図形です。楕円のことは忘れましょう。 実際の楕円曲線は、例を示すと以下のような曲線です。 一般化すると (ただし または ) という式で表されるこのような曲線をワイエルシュトラス型楕円曲線と呼びます。ワイエルシュトラス型、と付いているのは他のパターンもあるからで、 こんな形の楕
ポインタを使用した2つの整数の記憶場所を交換するプログラムについて - プログラマ専用SNS ミクプラ
2つの整数の記憶場所を交換するにはどのようにすればよいのでしょうか？下は問題文です。 intへのポインタ引数xとyをもつswap関数を定義し，2つの整数の記憶場所を交換するプログラムを作成しなさい． void swap(int *x, int *y); /* ポインタ引数x, yが指す変数の値を入れ替える */ main関数では，scanf関数を使って2つの整数を入力し，swap関数を呼んでから2つの整数値を出力する． swap関数にはprintf, scanfを書いてはいけない．main関数にはif文を書いてはいけない．大域変数を使ってはいけない． 実行例 整数を2つ入力 7 -1 swap前：7 -1 swap後：-1 7 int main(void) { int a, b; printf("整数を2つ入力¥n"); scanf("%d %d", &a, &b); printf("sw
勾配降下法の最適化アルゴリズムを概観する | POSTD
(編注：2020/10/01、2016/07/29、いただいたフィードバックをもとに記事を修正いたしました。) 目次： さまざまな勾配降下法 バッチ勾配降下法 確率的勾配降下法 ミニバッチ勾配降下法 課題 勾配降下法を最適化するアルゴリズム Momentum(慣性) Nesterovの加速勾配降下法 Adagrad Adadelta RMSprop Adam アルゴリズムの可視化 どのオプティマイザを選ぶべき？ SGDの並列化と分散化 Hogwild! Downpour SGD SGDのための遅延耐性アルゴリズム TensorFlow Elastic Averaging SGD 最適化されたSGDに対する更なる戦略 シャッフル学習とカリキュラム学習 バッチ正規化 早期終了 勾配ノイズ 結論 参考文献 勾配降下法は、最適化のための最も知られたアルゴリズムの1つです。これまではニューラルネット
数理最適化を用いて広告オークション入札金額を自動で調整してみた - Speee DEVELOPER BLOG
こんにちは、UZOU事業部の久松 @hisao_00 です。 業務としては、ネイティブ広告配信アルゴリズムの調査、設計、プロトタイプ開発を行っています。 先日開催された、SpeeeKaigi#4にて「数理最適化を用いた広告オークション入札金額の最適化」について発表しました。 数学好きの方、アドテク界隈の方、ぜひ読んで頂ければ幸いです。 概要 制約つき非線形最適化問題を解くことで、広告主がメディアの配信枠に対して入札する金額を最適化するロジックを考え、シミュレーションしてみました。 背景 広告主はUZOUを通してメディアに配信されますが、広告主に継続して出稿してもらうためには、広告成果を合わせることが重要です。 広告成果とは Web広告の大多数は、パフォーマンス広告と呼ばれるもので、 健康食品や化粧品など、ネット上に配信された広告を導線として 商品の購入までを想定して配信されています。 その
第三回 物理と情報と幾何のインフォーマルかもな勉強会＠スマートニュース株式会社のまとめ - hiroki_f’s diary
第三回 物理と情報と幾何のインフォーマルかもな勉強会@スマートニュース株式会社 : ATNDをやりました。 発表者の方から資料を頂きましたので、資料を置きますね。 西尾さん@smartnewsのレポート 「建築とコンピュータ・グラフィクスにおける力学と幾何学のちょうど中間」三木優彰 非公開 「複雑流体の変分原理」深川宏樹 スライドはいずれ論文とともに公開予定です。 流体力学における変分原理の改良 - hiroki_fの日記 ライトニングトーク 「SmartNewsの裏側」浜本階生 非公開 「カーネル法を用いた点過程の解析」手塚太郎 正定値カーネルと再生核ヒルベルト空間について 「有限幾何と分割の組合せ論」山田紘頌 有限幾何と分割の組合せ論 「量子論理と射影幾何」古賀実 古賀さんの資料があるpage MinoruKoga 直リンク 第三回物理と情報と幾何の勉強会「量子論理と射影幾何」.pdf
"二分探索はX分探索において最強"の証明 - Qiita
0.背景 二分探索を初めて学習してから数年、今更二分探索を学習する機会があり、 「分割する個数を増やしても計算時間は二分探索より早くならないのか？」 という単純な疑問が浮かんだ。 サイズNの配列をx(>2)個の領域に分割すれば、計算時間はlogx N * １ループ当たりの比較回数となり、logx N < log2 Nなので、１ループ当たりの比較回数次第では早くならないか？と思ったからである。 しかしWebで検索してみたが、探索アルゴリズムの一環としてのX分探索に関する記事は(少なくとも日本語では)見つからなかった。 また「凸関数の極値を求める」という目的における三分探索や黄金比探索といった探索アルゴリズムがあることを知ったが、今回は二分探索と同様の目的における探索アルゴリズムを対象にするため、本稿では対象外とした。 参考 ・ 実数探索三種類解説 -nodchipの日記 ・ 三分探索と黄金分
Knuth multiplicative hash が最小完全ハッシュ関数であることの証明 | メルカリエンジニアリング
こんにちは！サーチチームの @metal_unk です。普段はサーバーサイドエンジニアとして、メルカリの検索を改善する仕事をしています。 メルカリには Be Professional Day という「普段できないことをやろう」をテーマとする日があり、その日は業務に直接関係のないことや、普段は手をつけられないリファクタリングなどがされます。Be Professional Day の様子はこちらで紹介されています。 tech.mercari.com わたしは今回の Be Professional Day で、Knuth multiplicative hash が最小完全ハッシュであることを証明しました。このブログはその証明についての記事です。 「普段できないことをやろう」という Be Professional Day では、証明もアリです。 Knuth multiplicative hash
カークマンの組分け
カークマンの組分け １５人を、３人ずつ、５班に分ける方法の数を求めることは、順列・組合せにおける標準的な 問題である。実際に、 ある。 ところで、上の問題に対して、１度同じ班になった人とは２度と同じ班にならないと仮定する ような場合の方が、実生活でよく直面する。 たとえば、６チームのリーグ戦（総当り戦）で、同時に３試合ずつ５回戦を行う場合とか．．．。 １８４７年に、Ｋｉｒｋｍａｎ（1806～1895）は、次のような問題を提出している。 （正式な名前は、「カークマンの女生徒の問題」という。女生徒というのは、問題に対して本 質的ではないと思うのだが、なぜか、カークマンは「女生徒」と限定している！？） １５人を、次のように班分けする。 １日目・・・１５人を、３人ずつ、５班に分ける。 ２日目・・・１５人を、３人ずつ、５班に分ける。ただし、１度同じ班になった人とは２度と同じ班 にならないものとする。
コンプガチャの確率マジックを中学生にも分かるように説明するよ
コンプガチャが話題になっています。 コンプガチャにハマりやすい理由として「最初は当たりやすいが、だんだん確率が低くなる」という指摘があります。 なぜ「確率が低くなる」という現象おきるのでしょうか。 この記事ではコンプガチャの裏側にある確率マジックを分かりやすく解説します。 サイコロの面を全部そろえるゲーム いちばん身近な確率といえばサイコロです。 サイコロを使ったこんなゲームを考えてみます。 サイコロ コンプのルールサイコロを 1 回振るには 10 円が必要。6 つの面をすべてを出せば、500ml のペットボトル飲料をプレゼント。 「サイコロの 6 つの面をすべてコンプしよう」というゲームなので、シンプルな「コンプガチャ」といえます。 このゲーム、あなたなら参加しますか？ 6 つの面を全部だせばよいので、運がよければ 6 回（60円）でペットボトルが手に入ります。なんだかお得そうです。 た
RubyからGoの関数をつかわなくても再帰をやめなくてもアルゴリズムを改善する→はやい - prime's diary
qiita.com mattn.kaoriya.net という記事を読んだのでアルゴリズムを改善して速くしました。 いわゆる行列累乗のテクニックを使うと（乗算部分を除けば）N番目のフィボナッチ数はで求まります。 実際にはフィボナッチ数は指数的に増大するので乗算にかかる時間が支配的になるのでもっと遅くなります(Karatsuba法なら、高速フーリエ変換を使えば)。 単純な足し算のループでは足し算の桁数を考えると なのでそれよりは随分と速くなります。 40番目ぐらいでは実行時間はほとんど0なので100万番目のフィボナッチ数を求めてみます。 こちらが元のソースコード def fib(n) f0, f1, v = 0, 1, 0 n.times do |x| if x <= 1 v = x else v = f0 + f1 f0, f1 = f1, v end end return f0 + f1
正月の酔っ払い物理学者が数学者の皮を被った天使に出会うお話 | カメリオ開発者ブログ
あけましておめでとうございます。白ヤギの物理担当、シバタアキラ(@punkphysicist)です。 皆様はどんなお正月を過ごされましたか？日本の正月といえば、おせち、日本酒、おばあちゃん、そしてパズル、ですよね。私の正月はそんな感じでした。お節をたらふく食べ、美味しいお酒でほろ酔い気分になっている私の横で、黙々とおばあちゃんがパズルをやっているのに気づいたのです。部屋中をフワフワしている私とは全く対照的に、微動だにせずパズルを続けるおばあちゃん。御年迎えられると辛抱強さが半端ない。 そんなおばあちゃんがやっていたのはかわいいチョコレートのピースとは裏腹にこんな挑発的な文言の書かれたパズルです（この記事はアフィリエイトではありませんが、写真をクリックすると買えます） 何時間たっても答えが出ないおばあちゃん、辛抱強さは人一倍強いですが、私も何とか助けてあげたいと思いトライ。しかし日本酒が・・
素因数分解のアルゴリズム 〜その1〜 - Mandy Code
突然ですが、 問: 1〜100000までの数の中で最も約数の多いものを求めよ こんな問題がTwitterに流れていたらしく、定番っぽい問題ですが面白かったので数種類のやり方で解いてみます。 ある和nの約数の個数は、その数を素因数分解したときの指数だけを取り出してそれぞれに1足したものを掛けあわせれば求まります。 例えば12 = 2^2 * 3^1 なので、(2 + 1) * (1 + 1) = 6個となります。 つまり素因数分解が出来ればこの問題は解ける！ そこで初回は力技で素因数分解をしてみます。 まずコードをバーンと #!/usr/bin/env perl use strict; use warnings; main(); sub main { my $ans = +{ number => 0, factors => 0, result => +{}, }; for my $num (
ユークリッドの互除法 - Wikipedia
252と105のためのユークリッドの互除法のアニメーション。 クロスバーは、最大公約数（GCD）である21の倍数を表す。 それぞれのステップにおいて、1つの番号がゼロになるまで、より少ない数はより大きな数から引かれる。 残りの数は、GCD。 ユークリッドの互除法（ユークリッドのごじょほう、英: Euclidean Algorithm）は、2 つの自然数の最大公約数を求める手法の一つである。 2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。 明示的に記述された最古のアルゴリズムと
random()とrandom()*random()はどっちがランダムか？ | TRIVIAL TECHNOLOGIES 4 @ats のイクメン日記
みんなのIoT/みんなのPythonの著者。二子玉近く160平米の庭付き一戸建てに嫁/息子/娘/わんこと暮らしてます。月間1000万PV/150万UUのWebサービス運営中。 みんなのブロックチェーンは，ブロックチェーンの入門書。暗号やハッシュなどを含め，基礎からブロックチェーンの仕組みを学べる書籍です。 いろんな方に「新しい技術を学ぶことの楽しさ」を感じ取ってくれたら著者として嬉しいです:-)。お金は技術的にどのように定義されるのか。 みんなのIoTは，モノのインターネットと呼ばれるIoTの入門書です。IoTの基本について，読者に寄り添って優しく解説しました。裏テーマは一番とっつきやすいPython入門書。サポートページはこちら みんなのPython 第四版は，より分かりやすい入門書を目指し，機械学習やデータサイエンスの章も追加して第三版を大幅に書き換えました。Python 3.6にも華
QuickDrawはどのように素早く円を描いていたのか？ - ザリガニが見ていた...。
かつてのMac OS9までの描画エンジンの主役はQuickDrawが担っていた。GUIなOSでは、文字も含めてすべてをグラフィックとして扱うので、画面に見えているすべてのもの*1はQuickDrawによって描かれていたことになる。描画エンジンは、GUIなOS開発の要となる技術である。その出来が、GUIなOS開発の成否を分けるとも言える。 そして、最初期のQuickDrawは、ビル・アトキンソンがたった一人で開発したそうである。 当時（25年以上前）のCPUは、動作クロックが8MHzという性能だった。（現在は2GHz=2000MHzかつ、複数コアが当たり前） そのような性能であっても、違和感なくマウスで操作できるOS環境にするために、斬新な発想や試行錯誤を重ね、相当な努力の末に開発されたのがLisaやMacintoshであった。 Amazon.co.jp： レボリューション・イン・ザ・バレー
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
数学好きから見た量子コンピュータ～57を因数分解した話～
GitHub - ssaunier/round_robin_tournament: 💎 Ruby gem for Round Robin Tournament scheduling
高速な倍精度指数関数expの実装
