それでも TeX で素因数分解したい人のための何か

2012/12/01 〜 2012/12/25

TeX & LaTeX Advent Calendar

〜TeX で騒げ、TeX で笑え〜

こちらは平常運航。

*  *  *

以前に「普通の言語から変換して TeX プログラムを作る」という方法論について解説した。今日からは、具体的な変換の例をいくつか見ていくことにする。最初の例は「素因数分解」である。

Lua で「素因数分解」してみた

元となる Lua のプログラムは次の通り。factorize(n) で n の素因数分解を表示する。test_factorize() はテスト用の関数で、2 から 100 までの素因数分解を表示する。((なお、io.write() は、print() と異なり、出力に改行文字を付けない。))

-- factorize0.lua
-- [変数一覧]
-- 真偽値値: fac_head, fac_stop
-- 整数値: nn, n, k, e, q, r

--(公開) test_factorize()
-- 2から100までの素因数分解を出力する.
function test_factorize()
  for nn = 2, 100 do
    io.write(nn.." = ")
    factorize(nn)
    io.write("\n")
  end
end

--(公開) factorize(整数n)
-- nを素因数分解した式を出力する.
function factorize(_1)
  -- n : 未分解の整数
  -- k : 試行する除数
  -- fac_head : 未出力の状態か？
  -- fac_stop : 停止するか？
  n = _1; fac_head = true
  fac_try(2)
  k = 3; fac_stop = false
  while not fac_stop do
    fac_try(k)
    k = k + 2
  end
  if n > 1 then
    fac_out(n, 1)
  end
end

-- int_divide(整数x,整数y)
-- xをyで整除した時の商と余りを返す.
function int_divide(_1, _2)
  return math.floor(_1 / _2), _1 % _2
end

-- fac_try(整数x)
-- 除数xにおける試行.
function fac_try(_1)
  -- e : 指数
  -- q : 整除の商
  -- r : 整除の余り
  e = 0
  while true do
    q, r = int_divide(n, _1)
    if r == 0 then
      n = q; e = e + 1
    else break
    end
  end
  fac_out(_1, e)
  -- 未分解の数(n)が現在の除数より小さい場合は
  -- nは素数または1であり分解は完了している
  if n < _1 then
    fac_stop = true
  end
end

-- fac_out(整数p,整数e)
-- 素因数pの項を出力する. eは指数.
function fac_out(_1, _2)
  -- 指数0は出力しない
  if _2 == 0 then return end
  -- 先頭以外では「x」を出力
  if fac_head then fac_head = false
  else io.write(" x ")
  end
  -- eが1なら「p」、それ以外は「p^e」と出力
  io.write(_1)
  if _2 > 1 then io.write("^".._2) end
end

-- メイン
test_factorize()

ただし、この最初の段階で、幾つかの「変換」を済ませた形で記述している。

• ローカル変数を使わず、グローバル変数のみを用いている。
• 関数の引数は _1、_2、……の名前にしている。
• 整除の商と余りは TeX では同時に得られる。それを見越して、「商と余りを返す関数」int_divide() を用意している。

プログラムの出力（test_factorize() の出力）は次の通り。

2 = 2
3 = 3
4 = 2^2
5 = 5
6 = 2 x 3
……(92行省略)……
99 = 3^2 x 11
100 = 2^2 x 5^2

これを、TeX に直す直前の形に変換したのが次のプログラム。

-- factorize0.lua
-- [変数一覧]
-- 真偽値値: fac_head, fac_stop
-- 整数値: nn, n, k, e, q, r

--(公開) test_factorize()
function test_factorize()
  nn = 1
  while nn < 100 do
    nn = nn + 1
    io.write(tostring(nn).." = ")
    factorize(nn)
    io.write("\n")
  end
end

--(公開) factorize(整数n)
function factorize(_1)
  n = _1; fac_head = true
  fac_try(2)
  k = 3; fac_stop = false
  while (fac_stop and 1 or 0) == 0 do -- (*1)
    fac_try(k)
    k = k + 2
  end
  if n > 1 then
    fac_out(n, 1)
  end
end

-- int_divide(整数x,整数y)
function int_divide(_1, _2)
  -- (*2) q = 商, r = 余り とする
  q = _1; q = math.floor(q / _2)
  r = -q; r = r * _2; r = r + _1
end

-- fac_try(整数x)
-- 除数xにおける試行.
function fac_try(_1)
  e = 0; r = 0
  while r == 0 do -- (*3) 少し細工する
    int_divide(n, _1) -- q, r に返る
    if r == 0 then
      n = q; e = e + 1
    end
  end
  fac_out(_1, e)
  if n < _1 then
    fac_stop = true
  end
end

-- fac_out(整数p,整数e)
function fac_out(_1, _2)
  if _2 > 0 then
    if fac_head then fac_head = false
    else io.write(" x ")
    end
    io.write(tostring(_1))
    if _2 > 1 then io.write("^"..tostring(_2)) end
  end
end

-- メイン
test_factorize()

もちろん、出力は元の factorize0.lua と同じである。次の点を改修している。

• for 文を while 文に直した。
• break の除去を行った。
• 関数を手続きに変換した。
• (*1) の行に奇妙な式がある。この while 文の条件部は元々は not fac_stop であったが、TeX では（\@whilenum だけを使うという前提では）条件部には整数の式を書く必要がある。従って、三項演算子((c and t or f は Lua で三項演算子を模倣するためのイディオム。C 言語での c ? t : f に相当する。))を用いて真偽値を整数値（0 か 1）に変換した上で 0 との等式比較としている。
• (*2) で関数を手続きに変換する際、「実際の実行での値の格納先である q, r に直接代入する」という方式を用いた。
• (*3) のループは元々は「r == 0 でない」という条件で末尾で抜け出す。これを「r == 0」の条件の whlie ループ（先頭判定）に変えるとともに、初回にループに入ることを保証するために予め r = 0 の代入を行った。

TeX で「素因数分解」してみた

そして最終的に TeX（on LaTeX）のプログラムに変換したのがこれ。パッケージ名は tcfactorize、名前空間は tcfr、そして公開命令は \factorize と \testfactorize である。

% tcfactorize.sty
\NeedsTeXFormat{LaTeX2e}
\ProvidesPackage{tcfactorize}

%% 変数定義
%(真偽値)
\newif\iftcfr@fac@head
\newif\iftcfr@fac@stop
%(整数値)
\newcount\tcfr@nn
\newcount\tcfr@n
\newcount\tcfr@k
\newcount\tcfr@e
\newcount\tcfr@q
\newcount\tcfr@r

%%(公開) \testfactorize
\newcommand*{\testfactorize}{%
  \par\noindent
  \tcfr@nn=1
  \@whilenum\tcfr@nn<100 \do{%
    \advance\tcfr@nn 1
    $\makebox[2em][r]{\the\tcfr@nn}=% 左辺を2em幅で出力
    \factorize{\tcfr@nn}$%
    \ifnum\tcfr@nn<100 \\\fi % 最後以外では改行
  }%
  \par
}
%%(公開) \factorize{整数n}
\newcommand*{\factorize}[1]{%
  \tcfr@n=#1\relax \tcfr@fac@headtrue
  \tcfr@fac@try{2}%
  \tcfr@k=3 \tcfr@fac@stopfalse
  \@whilenum \iftcfr@fac@stop1 \else0 \fi=0 \do{%
    \tcfr@fac@try{\tcfr@k}%
    \advance\tcfr@k 2
  }%
  \ifnum \tcfr@n>1
    \tcfr@fac@out{\tcfr@n}{1}%
  \fi
}

%% \tcfr@int@divide{整数x}{整数y}
\def\tcfr@int@divide#1#2{%
  \tcfr@q=#1\relax \divide\tcfr@q#2\relax
  \tcfr@r=-\tcfr@q \multiply\tcfr@r#2\relax \advance\tcfr@r#1\relax
}

%% \tcfr@fac@try{整数x}
\def\tcfr@fac@try#1{%
  \tcfr@e=0 \tcfr@r=0
  \@whilenum \tcfr@r=0 \do{%
    \tcfr@int@divide{\tcfr@n}{#1}%
    \ifnum \tcfr@r=0
      \tcfr@n=\tcfr@q \advance\tcfr@e 1
    \fi
  }%
  \tcfr@fac@out{#1}{\tcfr@e}%
  \ifnum \tcfr@n<#1\relax
    \tcfr@fac@stoptrue
  \fi
}

%% \tcfr@fac@out{整数p}{整数e}
\def\tcfr@fac@out#1#2{%
  \ifnum #2>0
    \iftcfr@fac@head \tcfr@fac@headfalse
    \else \times
    \fi
    \number#1\relax
    \ifnum #2>1 ^{\number#2}\fi
  \fi
}

\endinput

• 折角 TeX で実行しているのだから、出力はしょぼい ASCII 文字列でなく格好良い TeX の数式組版で出力した。\factorize は数式の LaTeX テキストを出力するが、それ自身は数式モードへの切り替えを行わない（だから数式モードで実行する必要がある）ことに注意。
• 真偽値の変数は TeX ではスイッチ（\newif で定義される if-トークン）で表される。if aaa then ... end は \ifxx@aaa ... \fi と書ける。三項演算子も TeX の if 文で書けて、例えば (fac_stop) ? 1 : 0*1は \iftcfr@fac@stop 1 \else 0 \fi*2 と置き換えられる。

テスト用の LaTeX 文書と、その組版結果を掲載する。

\documentclass[a4paper]{article}
\usepackage{tcfactorize}
\begin{document}
\testfactorize
\end{document}