雑記帳: 3月 2016

2016年3月16日水曜日

$\mathrm\TeX$配列を使って素数リストをひたすら生成

前回配列が扱えるようになったので満を持して素数探索プログラムを書こう。これならただ計算してるだけよりわざわざ$\mathrm\TeX$で書く意義がありそうな気がするよ！素数リスト使って問題作るとか！

とりあえず高速化とかほとんど考えないでnまでの素数を列挙するマクロを作ってみる

\def\PrimeCount#1{%
\NewArray{primes} \PushArray{primes}{2}% 配列primes生成、2をpush(=要素として加える)
\newcount\@judnum \@judnum=3\relax% カウンタ\@judnumを生成、3を代入
\newcount\@aryind% カウンタ\@aryindを生成　※余計にカウンタを生成し過ぎないようループの前で生成する
\@whilenum\@judnum<#1\relax \do{% \@judnumが引数nを超えないときループ
\@aryind=0\relax%
\LengthofArray[\arylen]{primes}% primesの長さを\arylenに格納　※\arylenはカウンタではなく制御綴。
\@tempcntb=0\relax% \@tempcntbを、\@judnumが素数か判別するboolean変数として使用　
\@whilenum\@aryind<\arylen\relax \do{% \@judnumが素数かどうか判別するループ
\GetArray[\ttt]{primes}{\the\@aryind}% 素数リストを順に調べていく　\tttにprimesを格納
\@tempcnta=\@judnum% 計算のため\@tempcntaに値をコピー
\surplus\@tempcnta\ttt\relax% 以前作った\surplusで\@tempcnta % \tttを計算
\ifnum\@tempcnta=\z@% 割り切れたなら\@tempcndb=1にする&　\@aryindを増やしてloopを終わらせる
\@tempcntb1\relax%
\advance\@aryind\arylen%
\fi%
\increment\@aryind%
}%
\ifnum\@tempcntb=\z@ \PushArray*{primes}{\the\@judnum} \fi% ↑で\@tempcndb=1になっていなければ素数
\advance\@judnum2% 偶数は飛ばす
}%
[\ShowArray{primes}]%
}%

配列TLArrayパッケージの仕様は作者のブログで確認してもらうとして、カウンタの宣言がループの外になっているのは、ループの中でカウンタを作るとループを繰り返す毎にカウンタを使用してしまうからである。$\mathrm\TeX$のカウンタは最大256個、$\mathrm\LaTeX$のオプションを使っても数万個しか使えない。もともとペーシ数とか数えるのに使う機能だしシカタナイネ
　ここで問題になるのは以前作った\surplusがカウンタを3つも使っている上に一番激しいループの中にいることだ。
　ひとまず引数をわざわざ新しいカウンタで受けている部分は激しくもったいないので引数を直接使うとして、それでも一つはカウンタが必要にになる。

\def\surplus#1#2{%
\newcount\t \t=#1\relax%
\divide#1#2 \multiply#1#2 \advance\t-#1%
#1=\t\relax%
}

これを使うとn=800くらいが限界になる。

(No room for a new \count はカウンタがもう作れないというエラー)

4桁も無い素数リストなどショボいにも程が有るのでもう少し改善を試みる。

　本体の\PrimeCountと同様カウンタを"外で"作ってしまえばいい、つまりJavaでいうクラス変数みたいな感じにすればよろしい。Javaでもストリームリーダーとかを作りすぎてメモリを浪費しないようにクラスで宣言することがある。
　流石に \t とかいう適当な名前だとスコープが広がってどっかで名前が被りそうな気がするので名前を複雑にして

\newcount\suptmp
\def\surplus#1#2{%
\suptmp=#1\relax%
\divide#1#2 \multiply#1#2 \advance\suptmp-#1%
#1=\suptmp\relax%
}

こうすればn=1000でも10000でも動くようになる。

　さて、ここからは高速化を図る。素数以外の数では割っていないのでこれでもかなり速めだが、
nの約数pは$\sqrt n$ までに現れなければそれと対になる$\frac{n}{p}$も無いからそれより先を計算しても割り切れることはないはずである。
というわけで$\sqrt n$までで計算を止めたいが剰余すらなかった$\mathrm\TeX$に平方根計算などど言う高級なものがあるわけもなく、ニュートン法やら二分探索やらを使ったらできるんだろうが今回は$p^2$がnを超えないという条件を使う。(またpのためにカウンタを用意しなければいけないが)

\newcount\@tespow

を4行目の後、

\@tespow=\ttt \multiply\@tespow\ttt\relax
\ifnum\@tespow>\@judnum \advance\@aryind\arylen\relax \fi

を11行目の後におけばループはpが$\sqrt n$を超えたところでbreakされる。

結果はn=10000の時
元の関数が11秒
改良した物が1.7秒
だった($\mathrm\TeX$では計時機能が分単位なのでストップウォッチで計ることになったが)
めっちゃ速くなったなびっくり

おかげでn=100000でも数十秒でできた。
24ページに渡る素数リストもできたし時間をかければいくらでも増やせそうなので今回は満足。

-2019-03-12: $\TeX$を$\mathrm\TeX$に変更

$\mathrm\TeX$にも配列

　$\mathrm\TeX$には配列が無い。組版処理言語なのだからそんなもの無くて当然である。むしろチューリング完全になってることの方が変態的なのだ。
しかし名前参照=「文字列データを用いて、その文字列と同じ名前をもつ変数を参照する」機能(よくわからん)というモノがあるらしくこれを使って配列を実装してくれていた人が居た。

http://0-chromosome.hatenablog.jp/entry/2015/12/07/000000

この人によると「擬似的な」配列らしいがともかく1次元配列として使う分にはそう変わらないらしいので問題ない。ここで$\mathrm\TeX$プログラミングにおける著しく面倒くさいポイントがクリア出来る。

　習うより慣れろということで、まずはこのTLarrayパッケージの配列の挙動を掴むために↑のサイトの説明を見ながらスタック処理をやってみる。
スタック処理というのは値を順に格納していき、値を取り出すときは逆に最後に入れた物から順に取り出していく、という操作である。

\makeatletter
\def\countup#1{
\NewArray{test}
\@tempcnta=1\relax
\newcounter{cnt}
\@whilenum\@tempcnta<#1\relax\do{
\@tempcntb=\@tempcnta \multiply\@tempcntb5
\PushArray{test}{\the\@tempcntb}
\advance\@tempcnta1
}
\advance\@tempcnta-1
\@whilenum\@tempcnta>\m@ne\relax\do{
\PopArray{test}\par
\advance\@tempcnta-1
}
\DestructArray{test}
}
\makeatother
\begin{document}
\countup{6}
\end{document}

　※サイトでカウンタはなるべく作らないで標準で用意されている\@tempcnta,\@tempcntbを使ったほうが良いとか\loop～\ifnum-\repeatの代わりに\@whilenum-\do{～}が示されていたので、
今回からなるべく従い、@を含む制御綴を使う関係上\makeatletter～\makeatotherを使っている。@のカテゴリコードはその他なので通常は制御綴には使えないが文字に変更することで使えるようになる。$\mathrm\TeX$のシステムの大事な所は不用意に書き換えれらないように@を含んだものが多い

　適当にステップ数の5倍を格納して、そのあと逆に取り出していくので出力は

25
20
15
10
5

みたいになるはず。ところが、

????

何故か最後の数字ばっかり出力される。

ありがたいことに配列の中身を列挙する\ShowArray{}コマンドが用意されているので8行目のあとに

　[ \ShowArray{test} ]\par

を追加して実行すると

、とおそらく\@tempcntbが変動するに連れて配列の中身も全部書き換わってしまっている。配列にカウンタそのものが格納されているようだ。

　\theを外すとか\relaxをつけるとか$\mathrm\LaTeX$版のカウンタ\newcounter{count}を使ってみるとかいろいろやったがやはりエラーになるかカウンタ自体が格納されてしまう。

　パッケージの中身を直接読める程の技能は私にはないしどうしようかと思い悩んだ末、作者に直接聞いてみようかと思ったら仕様書的なものがパッケージに添付されていることに気がついた。

　いろいろ読んでいくと

ここで \PushArray 命令は⟨値⟩を展開せずに配列に追加するが，後ろに * をつけて \PushArray* とすると ⟨値⟩を完全展開したものを配列に追加することができる．

とあった。これじゃん。3時間も悩んでいた自分がバカみたいだ。

　8行目を　\PushArray*{test}{\the\@tempcntb}　に書き換えると

期待通りの出力になった。

　これでカウンタと変数が普通のプログラミング言語と同じような計算ができるようになった。

　次は前回やろうとしていた高速で素数を求めるプログラムについて。→次回

-2019-03-12: $\TeX$を$\mathrm\TeX$に変更

2016年3月12日土曜日

$\mathrm\TeX$マクロ累乗、階乗、素数判定関数

剰余演算子のついでによくプログラミングで聞かれる数学的関数を幾つか実装してみた。

まず累乗

\def\powercalc#1#2{
\newcount\t \t=#1 \relax%
\newcount\step \step=1 \relax%
\loop%
\multiply\t#1 \relax%
\increment\step \relax%
\ifnum \step<\q \repeat%
#1=\t \relax%
}

t=#1を#2回掛けるだけの簡単なお仕事。(これじゃ指数部が負や小数の時は対応できないって？そもそもカウンタは整数値しか扱えないからいいのだ。)
\loopの扱いなどについてはキヨシ関数の記事を参照。
ちなみに#○は引数。

次が階乗。

\def\function#1{
\newcount\t \t=1 \relax%
\newcount\step \step=1 \relax%
\loop%
\multiply\t\step \relax%
\increment\step \relax%
\ifnum\step<#1 \repeat%
#1=\t \relax%
}

1から#1まで掛けるだけの簡単なお仕事。累乗とあんまり変わらない。

最後が素数判定。

\def\ifprime#1{ %素数なら0,合成数なら1をjudgeに格納
\ifnum #1<2 %
%1
\else%
\newcount\judge \judge=0 \relax%
\newcount\step \step=2 \relax%
\newcount\max \max=#1 \decrement\max \relax%
\loop%
\newcount\temp \temp=#1 \relax%
\surplus\temp\step \relax%
\ifnum \temp<1 \judge=1 \fi%
\increment\step \relax%
\ifnum \step<\max \repeat%
%\the\judge
\fi%
}

本当はtrueとかfalseとかを返せるようにしたかったのだが引数のカウンタに上書きする以外の戻り値の返し方がわかんなかったので仕方なく素数なら0,合成数なら1をjudgeに格納することにした。
Java風に言うとvoidにしてグローバル変数に格納して返す、みたいな？(適当)
3行目と14行目をコメントから外せばdviに0か1を書き出すようになる。

さて、実行。

\documentclass{article}
\def\surplus#1#2{%
\newcount\n \newcount\m \newcount\t%
\n=#1 \m=#2 \t=\n \relax%
\divide \n by \m%
\multiply \n by \m%
\advance \t by -\n%
#1=\t\relax%
}
\def\minus#1#2{ \advance #1 by -#2 \relax}
\def\increment#1{ \advance #1 by 1 \relax}
\def\decrement#1{ \advance #1 by -1 \relax}
\def\powercalc#1#2{
\newcount\t \t=#1 \relax%
\newcount\step \step=1 \relax%
\loop%
\multiply\t#1 \relax%
\increment\step \relax%
\ifnum \step<\q \repeat%
#1=\t \relax%
}
\def\function#1{
\newcount\t \t=1 \relax%
\newcount\step \step=1 \relax%
\loop%
\multiply\t\step \relax%
\increment\step \relax%
\ifnum\step<#1 \repeat%
#1=\t \relax%
}
\def\ifprime#1{ %素数なら0,合成数なら1をjudgeに格納
\ifnum #1<2 %
%1
\else%
\newcount\judge \judge=0 \relax%
\newcount\step \step=2 \relax%
\newcount\max \max=#1 \decrement\max \relax%
\loop%
\newcount\temp \temp=#1 \relax%
\surplus\temp\step \relax%
\ifnum \temp<1 \judge=1 \fi%
\increment\step \relax%
\ifnum \step<\max \repeat%
%\the\judge
\fi%
}
\begin{document}
\newcount\p \newcount\q
\p=5 \q=3
\powercalc\p\q
$5^3= \the\t $
\p=5
\function\p
$5!= \the\p $
\ifprime{51}
if $51$ is prime number? \ifnum \judge<1 Yes. \else No. \fi
\ifprime{53}
if $53$ is prime number? \ifnum \judge<1 Yes. \else No. \fi
\end{document}

コメントアウトを手作業で赤くするのが疲れてきたのでやめた。

ちなみに各行の最後がコメントアウトしてあったりちょいちょい数値の後に\relaxが入ってるのはバグ防止。どっかで読んだ。

前回作った剰余演算子とインクリメント、デクリメント、減算演算子も冒頭で記述してあるが今回はインクリメントくらいしか使っていない。

累乗、階乗は戻り値がカウンタに格納されて帰ってくるので第一オペランドはカウンタでないといけない。累乗の第二オペランドと素数判定は数値でもカウンタでもいい(はず)。
55行目で5^3、60行目で5!、62,65行目で51と53が素数かどうか判定している。\ifnumで入れた数値が素数かどうか(\judgeが0かどうか)の判定でYes.かNo.か分岐。

実行結果はこう

上手いこと行った。

2ケタ以上の数は{ }で括らないといけないのでカウンタのほうが楽そう。どうせ使うのはマクロの中だろうし。

配列がないので素数のリスト化とかはできず速度のこととか全く考えてないから大きい数だととてもつらい予感がする。ただベンチマークしようにも時間取得が分単位とかだから結構大変かも。
とりあえず平方根関数を使ってStep数を減らすのが当面の課題か。(でも一から実装すると平方根って2分探索とか始まったりしてやばそう。)
いつか配列を使って素数リストを書き出せるマクロでも作りたい。頑張れば連想配列のようなものができるらしいし。

-2019-03-12: $\TeX$を$\mathrm\TeX$に変更

$\mathrm\TeX$カウンタ剰余演算子の実装

$\mathrm\TeX$のカウンタは四則演算はできるらしいが剰余演算子は無いっぽいので実装してみた。
ついでによくプログラミングで聞かれる数学的関数を幾つか実装してみた。→次の記事

まず$\mathrm\TeX$のカウンタの演算子は加、乗除(と代入文)ができる。
詳しくはこちら http://www.geocities.co.jp/HeartLand-Poplar/1240/latex/value.html

加減乗除を組み合わせ剰余演算子のマクロを作る。

\def\surplus#1#2{%
\newcount\n \newcount\m \newcount\t
\n=#1 \m=#2 \t=\n%
\divide \n by \m%
\multiply \n by \m%
\advance \t by -\n%
#1=\t\relax%
}

\surplusは二項演算子で#1％#2を計算する
計算式は、n=#1,m=#2として
　n-(n/m)*m
除算\divideは切り捨てて整数値を返す(そもそもカウンタは整数値しか扱わない)のでこれであまりが計算できる。
カウンタ用演算子は多項演算とかいう高度なことはできないしカウンタの値を変更してしまい元の値は保持できないのでtにmの値をバックアップして順次計算していく。
ちなみに演算子には引き算がないがカウンタや数値の前に"-"をつけるだけで簡単に符号反転できるので加算\advanceで計算できる。

カウンタの演算子は
　\operator operand1 by operand2
の形(operandはカウンタ又は数値)か
　\operatoroperand1operand2
で実行できる。わざわざbyやスペースを入れた方が数値を扱うときは見やすかもしれない。

さて、剰余演算子ができたので実行してみるが、参考ページに$\mathrm\LaTeX$はカウンタのインクリメントがあるのに$\mathrm\TeX$には無いということだったのでインクリメント、デクリメントを実装した。($\mathrm\LaTeX$のカウンタは$\mathrm\TeX$のと形式が違うため直接適用できない)
また形式が他と違って加算と符号反転の組み合わせになるのがなんか嫌だったので減算演算子もついでに書いておいた。

\documentclass{article}
\def\surplus#1#2{%略記
\newcount\n \newcount\m \newcount\t
\n=#1 \m=#2 \t=\n%
\divide\n\m%
\multiply\n\m%
\minus\t\n%
#1=\t\relax% %戻り値
}
\def\surplus#1#2{%
\newcount\n \newcount\m \newcount\t
\n=#1 \m=#2 \t=\n%
\divide \n by \m%
\multiply \n by \m%
\advance \t by -\n%
#1=\t\relax%
}
\def\minus#1#2{
\advance #1 by -#2
}
\def\increment#1{
\advance #1 by 1
}
\def\decrement#1{
\advance #1 by -1
}
\begin{document}
\newcount\p \p=101 \newcount\q \q=13
\surplus\p\q
\the\p
\increment\p
\the\p
\minus\p\q
\the\p
\end{document}

33,36,40行目でそれぞれ　101/13, (101/13=)10++, (10++=)11-13を計算している。
実行結果は

上手いこと行った。
ちなみに3～10行と12～19行で略記版とフルテクスト版で\surplusを宣言しているが$\mathrm\LaTeX$の\newcommandでは名前が被るとエラーになるのと違い、\defは上書きされるのでこのドキュメントでは後者が生きている。

キヨシ関数で乱数を\ifoddにかけて場合分けをする操作があったが剰余演算子ができたのでもっと場合分けが増やせるようになった。
この関数は引数のカウンタの数値を上書きしてしまうため単に場合分けに使うだけなら次の記事のifprime関数のように別のカウンタに格納したものを呼び出すようにした方がいいかもしれない。

次の記事で一応ここで作ったインクリメントが活躍している。（ただ普通に+1するのとあんまり変わんないけど）

-2019-03-12: $\TeX$を$\mathrm\TeX$に変更

2016年3月11日金曜日

キヨシ関数のはなし

一部で話題のキヨシ関数をTeXで実装してみたので覚えも兼ねて記事にしてみます
カウンタとかif文やらloop文やらのいい練習になったと思う
↓コレ

Javaの講義、試験が「自作関数を作り記述しなさい」って問題だったから
「ズン」「ドコ」のいずれかをランダムで出力し続けて「ズン」「ズン」「ズン」「ズン」「ドコ」の配列が出たら「キ・ヨ・シ！」って出力した後終了って関数作ったら満点で単位貰ってた
— てくも (@kumiromilk) 2016年3月9日

ソースがこちら

1 \documentclass{article}
2 \usepackage{lcg}
3 \newcount\rnd \newcount\KYScountZ \newcount\KYScountD
4 \def\Kiyoshi{%
5 \rnd=\the\time \KYScountZ=0 \KYScountD=0%
6 \loop%
7 \chgrand[seed=\rnd] \rand \rnd=\arabic{rand} %乱数
8 \ifodd\rnd %奇数の時
9 ズン\par%
10 \advance\KYScountZ1\relax%
11 \else %偶数の時
12 ドコ\par%
13 \ifnum\KYScountZ>3\relax%%ズン×4以上の時
14 キ・ヨ・シ！\par%
15 \advance\KYScountD1\relax%
16 \else %%ズンリセット
17 \KYScountZ=0\relax%
18 \fi
19 \fi
20 \advance\rnd1\relax%
21 \ifnum\KYScountD<1 \repeat
22 }
23 \begin{document}
24 \Kiyoshi
25 \end{document}

で、アルゴリズムと行数を合わせてJavaで書いたのがこれ↓

1 import java.io.*;
2 import java.util.Random; public class Main {
3 static long rnd, KYScountZ, KYScountD;
4 static void kiyoshi(){
5 rnd=System.currentTimeMillis(); KYScountZ=0; KYScountD=0;
6 do{
7 Random r = new Random(rnd); rnd=r.nextLong();
8 if(rnd%2==1){
9 System.out.println("ズン");
10 KYScountZ++;
11 }else{
12 System.out.println("ドコ");
13 if(KYScountZ>=4){
14 System.out.println("キ・ヨ・シ！");
15 KYScountD++;
16 }else{
17 KYScountZ=0;
18 }
19 }
20 rnd++;
21 }while(KYScountD<1);
22 }
23 public static void main(String[] args) throws Exception {
24 kiyoshi();
25 } }

大体そのまま移植したのでJava分かる人なら何やってるかわかると思う。ただclassの開始終わりが邪魔だったくらい。printlnの改行とかも\parが対応してる。
TeXで変数に当たるのがカウンタというもので、7 3 行目で生成、各所で代入文とかインクリメントとかやってる。
7行目は乱数生成してるんだけどseed=\rndとして乱数を作った、というとこしかわからん
　※追記 \arabic{～} というのはLaTeX式のカウンタの数値を展開するやつらしい
繰り返し文は言語機能ではなくマクロ。\loop～\if―\repeatが\ifーが成立している間～を展開するというもの

何度見ても\fi (endif的なもの)のネーミングセンスはイカしてると思う

実行結果はこう

Javaの方は乱数の具合がこの方法だと偏るのかやたらドコが多くなかなかループが終わらない…

本当は各行について何やってるかの説明を書いたりしたのだが操作ミスって全部消えたので心が折れた。

以下参考サイト
TeX loop文の解説 http://d.hatena.ne.jp/zrbabbler/20110828/1314537300
TeX 乱数のあ使い方 http://blog.livedoor.jp/cielo_cielo/archives/54462128.html
Java seedを使ったjava.util.Randomの用法 http://npnl.hatenablog.jp/entry/20090116/1232120896

登録: 投稿 (Atom)

雑記帳

2016年3月16日水曜日

\(\mathrm\TeX\)配列を使って素数リストをひたすら生成

\(\mathrm\TeX\)にも配列

2016年3月12日土曜日

\(\mathrm\TeX\)マクロ累乗、階乗、素数判定関数

\(\mathrm\TeX\)カウンタ剰余演算子の実装

2016年3月11日金曜日

キヨシ関数のはなし

2016年3月16日水曜日

\(\mathrm\TeX\)配列を使って素数リストをひたすら生成

\(\mathrm\TeX\)にも配列

2016年3月12日土曜日

\(\mathrm\TeX\)マクロ 累乗、階乗、素数判定関数

\(\mathrm\TeX\)カウンタ剰余演算子の実装

2016年3月11日金曜日

キヨシ関数のはなし

\(\mathrm\TeX\)マクロ累乗、階乗、素数判定関数