Hatena::ブログ(Diary)

ptoolisの日記

2018-01-26 動的計画法、モジュラ計算、再帰の関数

最近コードフオースのの問題を解くために三つのテーマがある苦しい所を見ています。 A dynamic programming approach mapping the number of bits set in a number to its transforms to 1, the computation of a quotient mod m, and the ability to obtain recursive behavior without exhausting the stack are concerns. 再帰の数が多くてスタック空間が足りない心配があるがもっと効果的なアルゴリズムを考えられません。それ以外、モジュラに関わる割る処分がちょっと手数になる。The modular division operation requires the modular multiplicative inverse, which can be output by the extended Euclidean algorithm. This algorithm outputs gcd(a,b), which in this case will be the divisor k and the modular operand m. However, it also outputs x and y such that ax+by=gcd. As k and m are relatively prime, this simplifies to kx+ym = 1. Then, taking both sides mod m yields kx mod m + ym mod m = 1 (mod m). bm mod m is trivially 0. Thus, the equation is simply kx=1 mod m, so, given x from the algorithm, the modular multiplicative inverse of k is known. Then, to find (a/k)%m, take (a*x)%m.

参照

以下のサイトの説明に詳細が書かれています。

https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/

https://www.geeksforgeeks.org/modular-division/

The intuition behind the algorithm is a pair of recurrence relations and induction.

デバッグ用のログからのユークリッド計算の例を貼り付けます。calling exteuc on 8, 1000000007

extEuc end, retV 1, a 8, b 1000000007, x 125000001, y -1, rdr 0, quot 7

exteuc outputs jmodinv 125000001

calling exteuc on 9, 1000000007

extEuc end, retV 1, a 9, b 1000000007, x 111111112, y -1, rdr 0, quot 8

exteuc outputs jmodinv 111111112

もう一つの難しいところがあった。001の場合に一ビットがありますが変換の数がゼロだからこのケースを変換一の合計から引くのが必要です。

2017-10-28

クレジット・デフォルト・スワップの値

04:15

最近ブリゴ氏とアルフォンセィの論文

を読んでいるけどよく分からない。the author's discuss a Poisson process for defaults and then bring up a variable "uppercase gamma", which seems to represent the number of defaults up to t. However, exp(-(G(u)-G(t))) seems to be used as both the probability and discount factor, and accounts for cases where the default time tai occurs after u.

2017-10-07

ペアトレードの変動性

01:22

最近コッフマン氏のトレーディング戦略の本を読んでいます。しかしターゲット変動性のところはよく分からない。

2017-09-29

確率微分方程式とオプション値計算

05:44

最近確立過程とSDEを学びながら停止時間と到達時間の計算式を見ています。難しい所は複数ありますが特に偏微分方程式の作り方とコロモゴロフの前向きと後ろ向き方程式の使い方が問題点だった。それ以外はPx,0(tau>T)=x/sqrt(2*pi*T)はよく分からない。N(0) = 1/2 and N'(0) = 1/sqrt(2pi). Here, though, it would seem that the derivative element of N'(0) is not the time derivative but the position derivative. In addition, there seems to be no relationship between the N(0), N'(0), and Px,t(tau>T)=1-2N(-x/sqrt(T-t)). Actually, though, the argument inside the normal CDF goes to 0 as T->infinity. たぶん微分に間違いが入っている。N'(0) = 1/sqrt(2*pi*T). Thus, the x/sqrt(2*pi*T) value is likely the one term Taylor series about x.

2017-09-18

コンスタント・マチュリティ・スワップ・スプレッド

01:03

最近長期間と短期間のスワップ金利の差を表すCMS スプレッドを学んでいます。