2017-07-28

MathJaxの試し書き2

下記のお題で書く。積分や分数を含む式。

Q.169 ☆5
次の極限値を計算せよ。
Find the limiting value.pic.twitter.com/T9mOJmpvJN
— どちゃ楽数学bot (@so_easy_math) 2017年7月26日

十分大きな ${n}$ については ${-\frac{\pi}{n}\le \theta \le \frac{\pi}{n}}$ において

${ \displaystyle \frac{1-\frac{1}{2}(\frac{\pi}{n})^2}{\frac{\pi}{n}+\pi}\le\frac{\cos\theta}{\theta + \pi}\le\frac{1}{-\frac{\pi}{n}+\pi} }$

であるから

${ \displaystyle n \frac{2\pi}{n}\frac{1-\frac{1}{2}(\frac{\pi}{n})^2}{\frac{\pi}{n}+\pi}\le n\int^{\frac{\pi}{n}}_{-\frac{\pi}{n}}\frac{\cos\theta}{\theta + \pi}d\theta\le n\frac{2\pi}{n}\frac{1}{-\frac{\pi}{n}+\pi} }$

${ \displaystyle \lim_{n \to \infty} n \frac{2\pi}{n}\frac{1-\frac{1}{2}(\frac{\pi}{n})^2}{\frac{\pi}{n}+\pi} = \lim_{n \to \infty} n\frac{2\pi}{n}\frac{1}{-\frac{\pi}{n}+\pi} = 2 }$

より
${ \displaystyle \lim_{n \to \infty} n\int^{\frac{\pi}{n}}_{-\frac{\pi}{n}}\frac{\cos\theta}{\theta + \pi}d\theta = 2 }$

感想

ここまで来たら何で書いても多分しんどい。数学やってる人はえらい。

2017-07-26

MathJax記法の試し書き

はてながMathJaxに対応しているらしいので、試しに使用してみる。

題材は下記の問題の解答を書くこと、としてみる。

Q.127 ☆8 [高2鉄緑校内模試]
(a+b)(b+c)(c+a)=2^2016を満たす自然数の3つ組(a,b,c)は幾つあるか。
— どちゃ楽数学bot (@so_easy_math) 2017年7月25日

ここでは、 ${n\geq 3}$ に対して下記の一般解を求めることから始める。

${ \displaystyle (a+b)(b+c)(c+a) = 2^n }$

${ a \geq b \geq c}$ として一般性を損なわない。

右辺の素因数は2のべきなので、左辺の各項（？）は

${ \displaystyle a+b=2^k, b+c=2^l, c+a=2^m \tag{a} }$

と書くことができる。ここで ${ a,b,c}$ の大小関係から
${ \displaystyle k \geq m \geq l \tag{b} }$
が言える。

明らかに ${ a,b,c}$ いずれかに奇数があるとすると、他の2つも必ず奇数となる。逆に、いずれかに偶数があると、他の2つも必ず偶数となることが容易に言える。

上記から ${a-b}$ は常に偶数であり、この差を ${a-b=2d}$ と表すと、(a)の第一式から

${ \displaystyle a=2^{k-1}+d, b=2^{k-1}-d }$

と書ける。また、これを(a)の第二式、第三式に適用すると
${ \displaystyle 2^{k-1}-d+c=2^l, c+2^{k-1}+d=2^m }$
となり、
${ \displaystyle c=-2^{k-1}+2^{l-1}+2^{m-1} }$
となる。

(b)より、 ${c > 0}$ となるためには ${k = m }$ が必要。(a)とあわせると ${b = c}$ となる。

ここで奇数解の場合、 ${b + c = 2^l}$ となりうるのは ${b = c = 1}$ の時のみ。すなわち、 ${d=2^k-1}$ となり、解は

${ \displaystyle a=2^{k+1}-1, b=1, c=1(k\ge 0) \tag{c} }$
となる。

一方、偶数解においては ${n}$ に対する解 ${( a,b,c)}$ がある場合、 ${(n-3)}$
に対する解 ${ (a/2 , b/2 , c/2)}$ が必ず存在することが容易に確認できる。この関係を偶数解である限り繰り返したどることで、 ${n}$ に対する偶数解 ${( a , b , c)}$ に対して、 ${n-3*r}$ に対する奇数解 ${( a/2^r, b/2^r , c/2^r)}$ を得ることができる。逆にいうと、偶数解はある ${n_0}$ に対する奇数解 ${( a_0,b_0,c_0)}$ を用いて ${n_0+3*r}$ に対する解 ${(2^ra_0, 2^rb_0 , 2^rc_0)(r > 0)}$ と表すことができる。

前記の議論から、すべての解は奇数解 ${( a_0,b_0,c_0)}$ を用いて
${ \displaystyle (2^ra_0, 2^rb_0 , 2^rc_0)(r\ge 0) \tag{d} }$
と表すことができる。

(c)における奇数解の定式化と(d)における一般化を踏まえれば ${(k\ge 0,r\ge 0)}$ を用いて
${ \displaystyle a=2^r(2^{k+1}-1), b=2^r, c=2^r }$
により ${n\geq 3}$ におけるすべての解が得られることがわかる。なお、対応する ${n}$ は
${\displaystyle n=(r+k+1)+(r+k+1)+(r+1)=3r+2k+3 \tag{e} }$
であり、すべての ${ (k\ge 0,r\ge 0)}$ は異なる解を生成する。

原題は ${n=2016}$ の解の数を求めるのであるから、(e)より ${3r+2k+3=2016}$ を満たす ${ (k\ge 0,r\ge 0)}$ の組み合わせの個数を数えれば良い。

これに該当するのは ${(k=0,r=671),(k=3,r=669),...,(k=1005,r=1)}$ の計336個である。

感想

綺麗にかけるけど、MathJaxって表示遅いな、、、
タグはすべての環境で有効なんだろうか。不明。
細かいことだがインラインの数式の前後にスペースを入れるのを忘れてはいけない。HTMLそのものが西洋言語向けの文化に基づいちゃってるので仕方ない部分はあるんだろうなとは思うけどめんどくさい。
TeXをよく知らないからなんだろうけど、displaystyleを使うときに前後に改行を入れるかどうかで左寄せかセンター寄せかが変わる？そういうもんなのか？

2016-04-02

sh/bashのパイプ/リダイレクションの使い方

sh/bashのパイプ/リダイレクションの使い方についてよく使いがちなものを理解できるようにまとめておく。

モチベーション：挙動がよくわからない

シェルスクリプトに書かれているリダイレクションが理解できない。

これまで、運用とかしてこなかったので人の書いたスクリプトを読むこともなく生きてきて、シェルはtcshでできる部分でいいや、という感じで生きてきた。でも環境はいつもデフォルトで使っちゃう派なので何かしら自動化しようとするとsh/bashを使わないと色々めんどいことに気づいた。しかたがないのでいまさらながらリダイレクションの記法について学ぶことにしてみた。

自分の理解度テスト的に下記を上げてみたけど、こんな感じ。

cmd > file # わかる
cmd >& file # なんだっけ？
cmd1 | cmd2 # わかる 
cmd1 |& cmd2 # わかる気もする。でも自分で書くときはこれが出てこない。

cmd 2>&1 > /dev/null # えっ？

以下に大体の読み方の基本から順番に書いていく。

基本

sh/bashのリダイレクションは基本的に (ディスクリプタ)> (ファイル) の羅列の形式である。
たとえば、

cmd 1> file

だとディスクリプタ1の出力先をfileという名前のファイルに設定する、という意味になる。

基本的にディスクリプタの1は標準出力、2は標準エラー出力なので、下記は「標準出力の出力先をfile1に、標準エラー出力の出力先をfile2に設定する」という意味になる。

cmd 1> file1 2> file2

>の代わりに>>を使うとファイルに追記する意味になる。

cmd 1>> file1
cmd >> file1

パイプは標準出力の出力先を後続のコマンドの標準入力に設定することを意味する。
下記はcmd1の標準出力をcmd2の標準入力に設定する。

cmd1 | cmd2

パイプにはディスクリプタ番号は指定できない。常に標準出力を次のコマンドの標準入力につなぐ。

リダイレクションの省略形

リダイレクションのディスクリプタが省略された場合は1を意味する。
つまり、下記の2つは同じ。

cmd > file
cmd 1> file

ディスクリプタの複製

>& 記号を使ったディスクリプタの複製について説明するが、これは複製？よくわからないので複製というのは「そういう名前」だと思って深く考えないほうが読みやすいかもしれない。

a>&b はディスクリプタaの出力先をディスクリプタbと同じにすることを意味する。
下記は標準エラー出力を標準出力と同じターミナルに出力する。

cmd 2>&1

なお、ディスクリプタaは省略できてデフォルトは2である。bは省略不可。

つまり、下記も同じ意味になる。

cmd >&1

複数の記述がある場合の理解の仕方（これ重要）

基本パターン

複数の記述がある場合、基本的には左から解釈される。
この過程をこれから述べるように表の形式で理解していくと出力結果を考えやすい。

基本的に何もしなければ標準出力等の出力先は下記のように設定されている。

ディスクリプタ	出力先(当初)
1	標準出力（ターミナル）
2	標準エラー出力（ターミナル）

ファイルへのリダイレクションが追加されると

cmd 1> file1 2> file2

ディスクリプタ	出力先(当初)	1> file1 適用後	2> file2 適用後
1	標準出力（ターミナル）	file1	file1
2	標準エラー出力（ターミナル）	標準エラー出力（ターミナル）	file2

標準出力はfile1へ、標準エラー出力はfile2へ出ることになる。

複製を含む場合

複製を含む場合、上記で説明したように複製を「出力先を同じにする」と理解するのがポイントになる。

下記のような複製がなされた場合、複製は出力先を同じにするので下記のようになる。

cmd 2>&1

ディスクリプタ	出力先(当初)	2>&1適用後
1	標準出力（ターミナル）	標準出力（ターミナル）
2	標準エラー出力（ターミナル）	標準出力（ターミナル）

下記のように順序を逆にすると結果が変わる。

cmd 2>&1 1> file1

ディスクリプタ	出力先(当初)	2>&1適用後	1> file1 適用後
1	標準出力（ターミナル）	標準出力（ターミナル）	file1
2	標準エラー出力（ターミナル）	標準出力（ターミナル）	標準出力（ターミナル）

逆パターンだと

cmd 1> file1 2>&1

ディスクリプタ	出力先(当初)	1> file1 適用後	2>&1適用後
1	標準出力（ターミナル）	file1	file1
2	標準エラー出力（ターミナル）	標準エラー出力（ターミナル）	file1

ディスクリプタの数を増やしてみる。新しいディスクリプタ3にはデフォルトでは何も設定されていない。

cmd 2>&1 3>&2

ディスクリプタ	出力先(当初)	2>&1適用後	3>&2適用後
1	標準出力（ターミナル）	標準出力（ターミナル）	標準出力（ターミナル）
2	標準エラー出力（ターミナル）	標準出力（ターミナル）	標準出力（ターミナル）
3	未設定	未設定	標準出力（ターミナル）

逆にしてみると

cmd 3>&2 2>&1

ディスクリプタ	出力先(当初)	3>&2適用後	2>&1適用後
1	標準出力（ターミナル）	標準出力（ターミナル）	標準出力（ターミナル）
2	標準エラー出力（ターミナル）	標準エラー出力（ターミナル）	標準出力（ターミナル）
3	未設定	標準エラー出力（ターミナル）	標準エラー出力（ターミナル）

パイプを含む場合

パイプを含む場合、標準出力の当初値が変わる。

cmd1 | cmd2

ディスクリプタ	出力先(当初)
1	cmd2の標準入力
2	標準エラー出力（ターミナル）

複製と併用するとこんな感じになる。

cmd1 2>&1 | cmd2

ディスクリプタ	出力先(当初)	2>&1適用後
1	cmd2の標準入力	cmd2の標準入力
2	標準エラー出力（ターミナル）	cmd2の標準入力

この例は比較的記法の似た cmd 2>&1 1> file のパターンよりは cmd 1> file 2>&1 のパターンとの類似性を強く感じるものになっている。
よく「左から読め」と言われるのだけれども、パイプだけは右側に書かれているのに、一番左に書いたような挙動をするので非常にわかりにくい感じがする。

複製と他の構文をまとめた記法

複製には他の構文とまとめる記法がある。

ファイル出力とまとめて書くことができる。

cmd 2>& file

これは下記と同じ。

cmd 1> file 2>&1

パイプとまとめて書く記法がある。

cmd1 |& cmd2

これは下記と同じ。

cmd1 2>&1 | cmd2

復習

出だしにあったコマンド群

cmd > file # わかる
cmd >& file # なんだっけ？
cmd1 | cmd2 # わかる 
cmd1 |& cmd2 # わかる気もする。書けない。

cmd 2>&1 > /dev/null # えっ？

は下記であることがわかるようになります。

cmd > file # 標準出力をfileに設定
cmd >& file # 標準出力と標準エラー出力をfileに設定
cmd1 | cmd2 # 標準出力をcmd2の標準入力に 
cmd1 |& cmd2 # 標準出力と標準エラー出力をcmd2の標準入力に
cmd 2>&1 > /dev/null # 標準出力を/dev/nullに、標準エラー出力をターミナルに標準出力として出力

結論

大事なことを書きます。

ググるのもいいけど、man (1) bash 読め。全部書いてある。

その他

2年ぶりに書いた記事がこれかよ、と悲しんでいる。

2013-12-31

つらぽよいsecure boot

つらぽよAdvent Calendarにネタを提供したわけでも何でもないんだけど

自宅のデスクトップPCが壊れた。具体的に言うと、HDDがクラッシュした。
もうちょっと正確に言うと、動作真っ最中に子供がぶつかって倒してしまった。
昔のHDDと比べると、あのカツーン、って音がかなりささやかだけど、ありがちなあの音を立てて起動しない現象になった。

PC自体はLenovoのやっすいやつ(H520S)である。キーボードとか、スピーカーとか、こまいパーツコミコミで４万円とかしなかった。Core i5でWindows7が載ってた。

でも、我が家では結構ハイスペックマシンである。

どうしようか悩んだ。なぜか換装用のHDDはあった。SATA-II出だしの頃のやつで遅いけど、容量300Gとかあるので、デスクトップ機としては問題ない。Lenovoにはリカバリディスクを送ってくれるサービスがあるらしい。このHDDとリカバリディスクでハッピーになれそう。。。なわけなかった。7000円払う必要があるし、なによりLenovoの窓口自体が年末年始で休業中だ。

あー、じゃー、Linuxとかでいいじゃん。

Ubuntuのインストールディスクを手持ちのネットブックで焼いて、インストールしたら、無事インストールできた。さすが！余裕じゃないですか。いつもVMPlayerでやってるのと同じじゃん！

と思ってインストール後にPCを再起動したら、

 Error1962:No operating system found.

ありー、なんかやり方まずかったかな。。。。

起動ディスクを別途作って起動しようとしても、全然起動しない。

ググってみると
Amazon.com: Customer Reviews: Lenovo H520s Desktop

Linux起動がうまく行かない、というような阿鼻叫喚の嵐。

集めた情報をだいたいかいつまんでまとめてみると

一部のLenovoのUEFI系マシンはsecure bootという仕組みがあり、Windows8が立ち上がるにはこれが必要である。
上記の仕組みを持つハードウェア環境でUbuntuなどの非正規OSはsecure bootにより起動を阻害される。RHELやFedoraの一部は正規の認証を受けているものがあるが、それ以外はsecure bootをOFFにしないと起動しない。

なるほど、secure bootをOFFにする必要があるのね、、、どうりで立ち上がらなかったわけだ。

と思い、BIOSのメニューを探してみたが、

secure bootに関するメニューすらない。。。。

マジか、、、同じ機種名の中でもOFFにできないモデルっぽい。

それでも、secureのまま、dual bootに成功している例はあるらしい。でも、逆に言うとdual bootの例しかない。どうも、Windowsのローダーを踏み台にして立ち上がるのは可能だが、それ以外はダメ、という感じらしい。(多分。たぶんね。)

つまり、WindowsのEFIローダーを書いておいて、起動シーケンスを横から頂戴すればいいのね！？

…いや、それやったら普通にリカバリディスク注文するし！

まー、どうしようかさんざん悩んだ挙句、Ubuntuのインストールディスクが起動していたのを思い出した。外部ブートはできるけど、光学ドライブのISOイメージだけってことっぽいんだよな。。。USBからも立ち上がんなかったし。

で、試しに、UbuntuのインストールディスクのgrubからHDD上のgrub.cfgを読み込んでみると、嘘のようにすんなりインストール後のHDDからシステムが起動した。

そういうわけで、当面、光学ドライブを踏み台にして起動する方向になりそうです。
なんだか変な感じではあります。
現時点ではUbuntuのインストールディスクを使っていますが、めんどいしアホいので、そのうちもっと小さなisoイメージ作ろうかなと思っています。

他にいい方法ないのかな。

正直、secure bootなるものにこういう風にいじめられるとは、なにか数奇な関係があるのかもしれません。

2013-08-05

Evalモナドを使って無限リストの並列評価

http://partake.in/events/9f226986-2812-441d-98b7-1f5cca9be432 にオンライン参加してきたので、Evalモナドを使った並列評価を行なってみた。

コード

ナイーブな素数探索アルゴリズムです。指定された数以上の一定個数の素数を抽出します。

import Control.Parallel.Strategies

-- rseq first n elements in parallel, then next n..
parListWithN :: Int -> [a] -> Eval ()
parListWithN n l = do
    parSeqListPar $ take n l
    case drop n l of
      [] -> return ()
      _  -> parListWithN n $ drop n l

-- rseq in parallel for finite length list
parSeqListPar :: [a] -> Eval ()
parSeqListPar [] = return ()
parSeqListPar (hd:tl) = do
    rpar hd
    parSeqListPar tl
    rseq hd
    return ()

-- filter f l with parallel precalcuration for l
filterEval :: (a -> Bool) -> [a] -> [a]
filterEval f l = runEval $ do
    rpar $ runEval $ parListWithN 100 l
    return $ filter f l

-- prime testing
isPrime :: Integral b => b -> Bool
isPrime n = not $ or $ map ((==0).(n `mod`)) [2..(n-1)]

-- find 100 successive primes after 435300
main = print $ take 100 $ filterEvalN isPrime [435300..]

このコードの挙動のポイントはいくつかあります。

filterEval関数：並列処理のトリガーを引くコードを処理キューに積んで、全体評価を始めます。
parListWithN関数：最初のn個の処理を並列処理にかけ、完了したら次のn個、というようにEvalモナドの挙動を指示する関数です。

並列処理がしたければ、rparを使ってタスクを積んでいくだけの簡単なお仕事です。

でも、次のような問題点があります。

全体評価の関数と並列処理が完全に分離していて、コントロールされていない。スケジューリング状況によっては、並列処理だけが進行して、全体評価側にフィードバックされずに進む可能性がある。

Evalモナドはこの辺りのコントロールが難しい感触があります。この後の並列計算ではこの辺りが解消されるか、気になるところです。

実行方法

使用時はthreadedオプションを付けてコンパイルします。

ghc -threaded FindPrime.hs

実行時は並列コアを指定します。

./FinePrime +RTS -N -RTS

threadscopeの実行結果とか見たかったけど、メモってる時点で時間切れなのでまた手が開けばやります。。。

2013-04-25

モンゴメリ乗算の例

下記を参考に

モンゴメリ乗算 - Wikipediaを参考に、サンプルとして、モンゴメリ乗算の計算をしてみる。

`11*18(mod 169)`を計算する。

単純に、

11*18 = 198 = 1*169+29

で答えは`29`です。

これをあえてモンゴメリ乗算でやってみる。

モンゴメリ乗算は剰余算を減算回路の繰り返しなしに実現するテクニックです。剰余算、割り算が出てきますが、実際には2のべきしか使わないので、ビットマスクやシフト演算で高速にできるのが特徴。

`R`をひとつ決めると、サブの演算子を下記のようにとって

MR(x) = (x + (x*N' mod R)*N)/R
Ninv : N' * N = -1 (mod R) となる数
R2 = R*R mod N

a * b = MR(MR(MR(a*R2)*MR(b*R2)))

とかけます。`R2`求めるときに`mod N` やってるやん！

R:256

に設定すると、下記のように関連する数値が導出されます。

Ninv:103
R2:133

`A=MR(a*R2)` `B=MR(b*R2)`とすると

A=(a R2+(a R2 Ninv mod R)N)/R
 =(11*133+(11*133*103 mod 256)*169)/256
 =112
B=(18*133+(18*133*103 mod 256)*169)/256
 =45
AB=112*45=5040
MR(AB)=((AB)+(AB Ninv mod R)N)/N
      = 157
MR(MR(AB)=(157+((157*103)`mod`256)*169)`div`256
         =29

あー、戻ってきた！

モンゴメリ乗算処理のテストケースを作ってみたのだけどそのままブログに書いてみましたの巻。

2013-04-22

__builtin_ffsはどこへ行くのか？(続編)

GCのマークビット判定などに使用される__builtin_ffsというGCC コンパイラ拡張が気になったので「__builtin_ffsはどこへ行くのか？ - dec9ue's diary」って記事をちょっと前に書きました。

続編です。

さて、何の話だったかというと、__builtin_ffsとは

Other Builtins - Using the GNU Compiler Collection (GCC) http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Other-Builtins.html によると

Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.

ということで、ビットマップ何かを操作するときに使えるGCC拡張のようだ。

ということでした。

そして、今回は

でも、対象をもうちょっとモダンなアーキテクチャに変えちゃうかも。。。

の予告通り、armv7-aのアーキテクチャに変えてみました。

arm-linux-gnueabihf-gcc -O0 -S -std=gnu99 builtin_ffs_test.c

の結果：

test:
        @ args = 0, pretend = 0, frame = 8
        @ frame_needed = 1, uses_anonymous_args = 0
        @ link register save eliminated.
        push    {r7}
        sub     sp, sp, #12
        add     r7, sp, #0
        str     r0, [r7, #4]
        ldr     r3, [r7, #4]
        rbit    r3, r3
        clz     r3, r3
        ldr     r2, [r7, #4]
        cmp     r2, #0
        bne     .L2
        mov     r3, #-1
.L2:
        add     r3, r3, #1
        mov     r0, r3
        add     r7, r7, #12
        mov     sp, r7
        pop     {r7}
        bx      lr

ARMv7AのARMインストラクションセットにはclzという先行0ビット判定を行うインストラクションがあります。これ使っちゃえば楽勝じゃん？

本当にありがとうございました。

あ、でもちょっと気になるのは、このインストラクションの発行フローはclzとrbitの組み合わせがあれば使う価値があるのですが、これはARMv6T2以降のARM/32bitThumbで使えるはずです。じゃぁ、なんでCortex-M3向けのコードはあんなややこしいコードになってたのか。16bitThumbを使うことを優先したのかな？