DanceDanceRevolution A20 段位認定進捗状況

段位認定モードといえば beatmaniaIIDX がその走りであるが, 現在稼働している DanceDanceRevolution A20にも実装されている. もっとも, 私にとっては皆伝はおろか六段すら相当に遠い存在ではあるのだが...

稼働時から少しずつ実力を伸ばしていき, 漸くSingle Play の五段合格にこぎつけることができた. もっとも, いわゆる捨てノーツがそれなりにあるのでスコアはひどいことになっているが.

Double Play についてはもっと体力をつけてから挑戦したい. 四段を取れたのも正直に言って奇跡的なもので, 意識した捨てノーツがないにもかかわらずこの結果なのでより精進したい.

DanceDanceRevolution A20 SP五段 747680
DanceDanceRevolution A20 DP四段 749820

実用数学技能検定1級合格!

9回目の受験にして漸く実用数学技能検定1級に合格することができました!

初めて挑戦したのは6年前. 直前に受験した準1級を満点で合格したのだから1級も何とかなるだろうと思ってチャレンジして, その結果が惨敗だったときの悔しさを胸に, 続けて2回受験するもまるで歯が立たず...

転居で環境が変わったところで気軽に受験できなくなった(個人受験会場が近くになかった)ために諦めていたところ, 次の転居ではまた個人受験会場が近くなったことから再起を決意.

昨年から受験をしたもののやはり合格には届かなかったが, 解法が全く思い浮かばないということがなくなったので、もう少しで手が届くという感触は得ていた。

それでも, 前回の結果が逆ボーダー (1次が4.5/7 (合格ライン 5/7), 2次が (2.3/4 (合格ライン 2.5/4)) だったときは心が折れかけた...

が, ここまでできているのだから何とかなると気合を入れ直したところ, 今度こそ合格ラインを超えることができたのである.

実用数学技能検定1級合格証
2019年10月27日実施第344回実用数学技能検定1級の合格証

連分数を処理する数式処理ソフトウェア

記事の都合上, 解釈が面倒な数式を書くので, 同じ式を表現した WolframAlpha へのリンクを設定しています.

連分数とは、分数の分母にさらに分数が含まれるような数値表現である.

例えば, 1+2/(3+4/(5+6/7))というようなものである.

特に、分子の部分がすべて 1 になっているような連分数のことを正則連分数といい, 単に連分数といった時には正則連分数であることを暗黙で示していることがある.

正則連分数について, a0+1/(a1+1/(a2+1/a3)) を [a0; a1, a2, a3] と表現する. 各 ai は正の整数 (a0 は0や負の値を含めた整数) である.

ある実数を(正則)連分数に変換することを連分数展開というが, 有理数ならば有限項の連分数で, 無理数ならば無限項の連分数で表現されることがわかっている.例えば, 355/113=[3; 7, 16], π=[3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, 15, 3, 13, 1, ...] となる.

無理数を分数(整数比)で近似する場合, 連分数展開を途中で打ち切って真分数や仮分数に戻すという手段が使われる。 そうして現れる分子や分母の値は, それ以下の整数を用いたあらゆる整数比(分数)よりもよりよい近似となることが知られている.

実際に, 例に挙げた 355/113=[3; 7, 16]=[3; 7, 15, 1] は 355 以下の整数を用いた分数の中で最良の円周率の近似である.

さて, 正則連分数展開は次の手順で行われる.

  1. 正則連分数展開を行いたい数を ω0 とし, n を 0 とする.
  2. ωn の整数部分を an とする.
  3. ωn の小数部分が 0 に等しい場合は, ak (kn+1) は存在しない, すなわち, 連分数表現は an の項で打ち切る.
  4. ωn+1ωn=an+1/ωn+1 を満たすように定める.
  5. n に 1 を加えて2番目の手続きに戻る.

この作業を行う数式処理ソフトををいくつか紹介する.

連分数近似を実装している数式処理ソフトの紹介

キログラムの定義が変わった日

2018年11月16日にキログラムの定義を変更することが CGPM (国際度量衡総会)で可決され, 本日2019年5月20日により全世界的に施行されることとなった.

いままでのキログラムの定義は次のように物質に依存する定義であった。

  • 水1リットルの重量
  • 大気圧下で氷が溶けつつある温度における水1リットルの重量
  • 最大密度(液温摂氏4度)における蒸留水1立方デシメートル(1リットル)の質量
  • アルシーブ原器 (有体に言うと白金塊) の質量
  • IPK (国際キログラム原器: 白金とイリジウムの合金)の質量

水はいろんなものを自然に溶かし込むし、金属も徐々にいろんなものを吸着して変質するので不変で安定したものというにははばかられた.

それでもIPKは誤差1億分の5という精度ではあったが, 近年の科学技術の発達により, これでも精度は足りないという状況であった.

今回の改訂は, 特殊相対性理論から得られた式 E=mc2 と光子エネルギーの式 E=hν から m=hν/c2 を得るので, 今までは実験値であったプランク定数を真の意味で定数とすることにより キログラムが定義されるということになる。

ただ, この定義に至る裏側で, 日本やドイツを中心とする科学者たちは (IPKと比べれば)手軽に作成できる原器を作り, その精度を裏付ける役割を担った. その原器はケイ素(シリコン)結晶である. このあたりの話は産業技術総合研究所のウェブサイトが詳しい.

常用対数の近似計算と10の自然対数の近似計算

非常に大きな数を扱うための概念として対数を高校数学で学習する. 例えば, 210 は 103 とほぼ等しい. 10 の累乗に値を換算したときの指数に相当する数を, その元の数の常用対数 をとった値というのである. これを式で表したものが log10210≈3 という関係である.

なお, 3dB(decibel( で 2 倍という関係はこの対数計算から得られるのである.

これを一般化すると, 1 ではない正の実数 a, 任意の実数 r について対数(logarithm(を次のように定義するということである。

ar=R ⇔ logaR=r

a=10 のときは常用対数, a=e (e: ネイピア数) のときは自然対数, a=2 のときは二進対数と特別に呼ばれる.

logaR という表記であるが, 文脈から明らかな場合は a はしばしば省略される.

ここでよく話題になる話として, 様々な整数の常用対数をとるといくらになるのか? というものがある. いくつかの整数に対して, その概算値を出してみよう.

log(1) は正確に 0 である. なぜならば, すべての 0 ではない実数 R について R0=1 が成り立つからである.

log(2) は冒頭で話題にした 210≈103 の関係から 10log(2)≈3 ⇔ log(2)≈0.3 となる. 厳密には 210>103 であるから log(2)>0.3 である. 上からの評価もしたい. 1000<1024<1250 の関係を使うと. 常用対数をとると 3<10log(2)<=4-3log(2) となるから log(2)<4/13<0.3077 が得られるが、 ちょっとこれではおおざっぱすぎる. ここは天下り的ではあるが, 293<1028 という関係を使う. すると, log(2)<28/93<0.3011 を得る.

log(3) についてもここでは近似値を求めることになる. 80<81 より 1+3log(2)<4log(3) から log(3)>19/40=0.475 という評価ができる. また, 20000>19683=39 ⇔ 4+log(2)>9log(3) から log(3)<4/9+log(2)/9=400/837<0.4779

これらの値を用いて log(4)=2log(2), log(5)=1-log(2), log(6)=log(2)+log(3), log(8)=3log(2), log(9)=2log(3) が概算できる.

1桁の整数の残り log(7) は様々な近似が検討されている. 例えば, 48<49<50 ⇔ 4log(2)+log(3)<2log(7)<2-log(2) より 67/80=0.8375<log(7)<17/20=0.85 という簡易的な評価がある. もうちょっと精度を上げるならば 74=2401>2400 ⇔ 4log(7)>2+3log(2)+log(3) より log(7)>27/32=0.84375, 48×1024/1000>49 ⇔ 14log(2)+log(3)-3>2log(7) より log(7)<1417/1674<0.8465 さらには, 106<22×366×73 と 210×78<310×105 を評価すれば小数第3位まで確定できる.

最後に loge(10) を評価する. そうすると, 自然対数と常用対数の変換に必要な定数が得られるのである. ただ, こちらについては積分計算により求めるのが一般的だろう. 12(1/x)dx=loge(2) という関係があるからだ. 被積分関数は積分区間内において凸関数なので、台形近似では収束がちょっと遅い. シンプソンの公式なら劇的に早く収束する. 具体的には (1/(6n))(1+2Σj=1n-11/(1+2j/(2n))+4Σj=1n(1/(1+(2j-1)/(2n)))+1/2) これを必要な精度まで計算して log10(2) で割ると loge(10) が得られる. シンプソンの公式は4次収束なので、n=2 でも3桁の精度は出る. loge(2)≈0.693 なので loge(10) は 2.25 から 2.31 の範囲にあるといえる.

おまけ: 連分数による近似

2019年になりました

今年もよろしくお願いいたします.

昨年の積み残しがあるので今年は何とかクリアしたいです. 何とか次のものは達成したいところ.

  • 数学検定1級合格
  • 統計検定1級合格
  • TOEICで人並みの点数を取れるようになるか英検準1級をとれるように頑張る
  • 5kmを40分以内に走り切れる体力を取り戻す

学習の成果はこのブログにもちょっとずつ載せていきますので, 小難しい記事が増えるかもしれません...

今後ともよろしくお願いいたします.

ユークリッドの互除法

世界最古に発見されたアルゴリズムのひとつとして知られるユークリッドの互除法は, 歴史上の価値のみならず, 公約数という素因数が絡む計算を素因数分解せずに効率的に求めることができるという点で非常に有用な手法となっています.

ユークリッドの互除法とは, 2つの0ではない整数a, b に対して, 次の手続を繰り返すことで ab の最大公約数を求めることができます.

  1. b=0 ならば a が求めるべき最大公約数である. アルゴリズムはここで終了する.
  2. c≡a (mod b) を計算し, ab を代入, bc を代入する.
  3. 最初に戻る.

ラメの定理により, アルゴリズムの繰り返し回数は a, b のうち小さい方の 10 進桁数を d とすれば, 高々 5d 回となることが知られており, 5d 回程度の繰り返しが発生する例はフィボナッチ数列(最初の2項を1としたもの)の隣接2項を対象とした場合が知られています.

もしも, これを素因数分解で解決しようとすると, a, b のうち小さい方の正の平方根の数だけ「試しに割り算して割り切れるかを確かめる」作業が必要となります。

つまり, abのもとで割算の回数を比較すると, ユークリッドの互除法ならば 2.2log(b), 素因数分解するなら √b と見積もることができます. b が大きい場合, どちらの方が効率がいいのかは明らかです.

この方法を拡張すると不定方程式 ax+by=gcd(a,b) の整数解を導出することができます. これが拡張されたユークリッドの互除法です. 拡張されたユークリッドの互除法の手順は次のとおりです.

  1. r0=a, s0=1, t0=0, r1=b, s1=0, t0=1, i=1 とする.
  2. ri+1=ri-1-qiri を 0≤ri+1≤abs(ri), qi は整数となるように定める.
  3. si+1=si-1-qisi, ti+1=ti-1-qiti とする.
  4. ri+1=0 の場合は x=si, y=ti であるので計算を終了する. ri+1≠0 の場合は次の項目に進む.
  5. i に 1 を加えて 2. の項目へ戻る.

ユークリッドの互除法の使用例

モジュラ逆数について

個人的メモ

m における整数 a のモジュラ逆数 a-1 (mod m) とは, aa-1≡1 (mod m) を満たす a-1x (mod m) なる整数 x の合同類である.

m における整数 a のモジュラ逆数が存在するための必要十分条件は gcd(m, a)=1 である.

a-1 (mod m) を求める最も汎用的な方法は拡張されたユークリッドの互除法を用いることである. つまり, a, m が所与であるもとでの ax-qm=gcd(a,m)=1 を満たす xa-1 (mod m) である.

他にも, オイラーのトーシェント関数を用いて a-1aφ(m)-1 (mod m) としたり, カーマイケル関数を用いて a-1aλ(m)-1 (mod m) と求める方法があるが, これは m を因数分解する必要があるので効率的な導出方法ではない. これらの特殊形として, m が素数 p であった場合は, a-1ap-2 (mod p) とすることができる.

具体例

合同式に関する諸性質

個人的なメモ

  • フェルマーの小定理とは次の関係を言う: 素数 pp とは互いに素な整数 a について ap-1≡1 (mod p) が成り立つ.
  • 数論におけるオイラーの定理とは次の関係を言う: 任意の正の整数 nn とは互いに素な整数 a について aφ(n)≡1 (mod n) が成り立つ.
    • φ(n) はオイラーのトーシェント関数であり、これは n 以下の n とは互いに素な正の整数の数となる。
    • nk=1mpkbk と素因数分解できたならば, φ(n)=nΠk=1m(1-1/pk)
  • カーマイケルの定理とは次の関係を言う: φ(n) は am≡1(mod n) を満たす最小の m であるとは限らない.
    最小の m はカーマイケル関数λ(n)で与えられる.

    • カーマイケル関数は次のように再帰的に定義される.
      • λ(2e)=1 (e=1), 2 (e=2), 2e-2 (e≧3)
      • 奇素数 p について λ(pe)=pe-1(p-1)
      • nk=1mpkbk と素因数分解できたならば λ(n)=lcm(λ(p1b1),...,λ(pmbm)). ただし, lcm は引数たちの最小公倍数(least common multiple)を表す。

    n≡1 (mod λ(n)) を満たすような n をカーマイケル数という.

以上によれば, 2n≡1 (mod 15) を満たす n は, フェルマーの小定理では導出できない (n=3×5)が,
オイラーの定理によれば n=8 のときに成立することが分かり, カーマイケルの定理によれば, 最小の整数 n は 4 である.

統計検定準1級に合格しました

2018年6月に実施された統計検定の準1級に合格しました。

2018年6月実施分統計検定試験結果通知書
2018年6月実施分統計検定試験結果通知書

統計検定準1級合格証
統計検定合格証準1級

創設時の2011年のときは1級から4級までの4段階だったところ, 2015年から準1級が新設され, その初回に受験はしていたのですが当時は力が及ばなかっただけに感動も一入です.

準1級は5者択一マーク式(今回は24問)と記述試験(今回は数値のみの回答2問5か所, 小論述問題2問5項目, 論述試験1問)からなっているところ,
数値回答は致命的間違いがあって半分落とし、小論述問題は1問が空白、論述試験も 2 割 (さすがに空白はまずいと思いひねり出したものが1つ当たった)が
マーク式は 8 割方正解できたので、滑り込みで合格ラインに乗っかったというところでした。

統計検定は正確なボーダーラインと配点を公表していないので, 受験直後は完答できた人以外は合格発表までやきもきさせられるのですよね... 他の試験 (例えば, 情報処理技術者試験や放射線取扱主任者試験 (第1種及び第2種) は 6 割という情報を公表しているので, 統計検定もおそらくそれに倣っている (大学でも「可」の評価が出る) とは思いますが.

次は数学検定1級の再チャレンジです. 試験日は2018年7月22日(もうすぐ!)です.