|
Dc (UNIX)
dc (desk calculator; 卓上計算機の意) は、任意精度の演算をサポートする、クロスプラットフォームな逆ポーランド記法の計算機ユーティリティである[1]。ロバート・モリスがベル研究所にいる間に開発されたこのソフトウェアは、最も古い Unix ユーティリティのひとつで[2]、これは C 言語の発明よりも前のことである。同世代の他のユーティリティのように一連の強力な機能を持っているが、その構文は簡潔である[3][4]。伝統的に、中間記法の計算機ユーティリティである bc は dc をバックエンドプロセスとして利用していた。 ここでは、言語の一般的な傾向を示すためにいくつかの例を紹介している。完全なコマンドと構文については、それぞれの実装による man ページを参照されたい。 歴史dc は現存する Unix 言語の中で最も古いものである。ベル研究所に PDP-11 が導入されたときには、アセンブラよりも先に、(B 言語で書かれた) dc がそのマシンで動く最初の言語なった[5]。ケン・トンプソンは、dc がこのマシンで書かれた最初のプログラムだとも発言している[2]。 基本的な演算dc で を計算するには次のように実行する (空白文字のほとんどは省略可能): $ cat << EOF > cal.txt
4 5 *
p
EOF
$ dc cal.txt
20
$
次のコマンドを使用して結果を得ることもできる: $ echo "4 5 * p" | dc
あるいは: $ dc -
4 5*pq
20
$ dc
4 5 *
p
20
q
$ dc -e '4 5 * p'
これらの動作は「4 と 5 をスタックにプッシュし、乗算演算子 ( 演算の精度 (演算で有効とする小数点以下の桁数) を変更するには 2 3 / p
5 k 2 3 / p 次の dc コマンドは を計算する ( 12 _3 4 ^ + 11 / v 22 - p その他にも、スタックの先頭 2 つの要素の順を入れ替える 入出力
前述したとおり、 dc はまた、入力と出力に利用する基数を任意に設定できる。 以下に示すのは 16 進数の入力を 2 進数に変換する例である: $ echo 16i2o DEADBEEF p | dc
11011110101011011011111011101111
言語の特徴的な機能dc は、上で述べた基本的な演算やスタック操作に加えて、マクロ、条件分岐、演算結果の一時保存などの機能を備えている。 レジスタdc におけるレジスタは、マクロや条件式の基本となる仕組みである。それぞれのレジスタは 1 文字の名前を持っている。レジスタを利用して値を保存したりスタックに取り出したりすることができる。 3 sc 4 lc * p レジスタをスタックとして利用することもできる。メインのスタックとレジスタのスタックとの間でプッシュ・ポップするには 文字列dc では また、dc では マクロdc ではレジスタやスタックに数値だけでなく、文字列を格納できるようにすることでマクロ機能を実現している。文字列は表示するだけでなく、それ自身を dc コマンドとして実行することもできる。以下に示すのは 1 を加算して 2 を掛けるマクロをレジスタ m に格納する例である: [1 + 2 *] sm そして次のようにマクロを呼び出す ( 3 lm x p 条件分岐マクロの仕組みを利用して条件分岐を行うことができる。 [[Equal]p]sm 5 =m その他にも、 ループdc でループそのものを行う方法はないが、マクロを再帰的に実行することで再現できる。スタックの先頭の要素の階乗を求めるには次のようにする: # F(x): return x! # if x-1 > 1 # return x * F(x-1) # otherwise # return x [d1-d1<F*]dsFxp
例スタック全体の合計これはレジスタ a に格納されたマクロを再帰的に呼び出してスタック全体の合計を計算する。マクロの動作は、まずスタックの先頭 2 を足し合わせ ( 1 2 4 8 16 100 # 加算したい数をスタックに積む 0d[+z1<a]dsaxp # すべて加算して表示 実行結果は ファイル中の dc コマンドの合計ファイルの各行に記述された dc コマンドを実行し、その合計値を計算する。単なる数値は dc コマンドとして有効であるので、行ごとに記述された数値の合計を得ることもできる。 これも上の例と同様にレジスタ a に格納されたマクロを再帰的に呼び出して合計を計算している。 $ cat file | dc -e '0d[?+z1<a]dsaxp'
$ { echo "5"; echo "7"; } | dc -e '0d[?+z1<a]dsaxp'
この結果は $ { echo "3 5 *"; echo "4 3 *"; echo "5dd++"; } | dc -e '0d[?+z1<a]dsaxp'
この結果は より この手法を利用することの長所は、dc の演算は無限精度であるので、 AWK などの簡明な手法を用いる場合に起こりうるオーバーフローや精度落ちが発生しないことである。 対して短所もあり、空行 (技術的には要素をプッシュしない行) に遭遇するとループが停止すること、負値の符号 を dc の負符号 単位変換以下に示すのは、ワンライナーで書かれた較的簡単な単位変換プログラムの例である: $ dc -e '[[Enter a number (metres), or 0 to exit]psj]sh[q]sz[lhx?d0=z10k39.370079*.5+0k12~1/rn[ feet ]Pn[ inches]P10Pdx]dx'
この例はメートルで表された距離をフィートとインチに変換する。ユーザに入力を促し、適切な形式で変換結果を出力し、別の数値を変換するためにループしている。 最大公約数以下に示すのは互除法を利用して最大公約数を求める例である: $ dc -e '??[dSarLa%d0<a]dsax+p' # 最短実装
$ dc -e '[a=]P?[b=]P?[dSarLa%d0<a]dsax+[GCD:]Pp' # 読みやすくしたもの
階乗入力された値 の階乗 を計算する: $ dc -e '?[q]sQ[d1=Qd1-lFx*]dsFxp'
Quinedc にも quine が存在する。 $ dc -e '[91Pn[dx]93Pn]dx'
$ dc -e '[91PP93P[dx]P]dx'
すべての素数を求める$ echo '2p3p[dl!d2+s!%0=@l!l^!<#]s#[s/0ds^]s@[p]s&[ddvs^3s!l#x0<&2+l.x]ds.x' | dc
このプログラムは Michel Charpentier によって書かれた、すべての素数を表示するプログラムである。このプログラムは次のように短縮でき、恐らくこれが最短であると思われる。 $ echo '2p3p[dl!d2+s!%0=@l!l^!<#]s#[0*ds^]s@[p]s&[ddvs^3s!l#x0<&2+l.x]ds.x' | dc
素因数分解これもまた Michel Charpentier によって書かれた[6]: $ dc -e '[n=]P?[p]s2[lip/dli%0=1dvsr]s12sid2%0=13sidvsr[dli%0=1lrli2+dsi!>.]ds.xd1<2'
短くすると: $ dc -e "[n=]P?[lfp/dlf%0=Fdvsr]sF[dsf]sJdvsr2sf[dlf%0=Flfdd2%+1+sflr<Jd1<M]dsMx"
より高速なものでは (200 bit の数 で試すなら $ dc -e "[n=]P?[lfp/dlf% 0=Fdvsr]sFdvsr2sfd2%0=F3sfd3%0=F5sf[dlf%0=Flfd4+sflr>M]sN[dlf%0=Flfd2+sflr>N]dsMx[p]sMd1<M"
これを更に高速化するには、定数へのアクセスをレジスタへのアクセスに置き換える: $ dc -e "[n=]P?[lfp/dlf%l0=Fdvsr]sF2s2dvsr2sf4s4d2%0=F3sfd3%0=F5sf[dlf%l0=Flfdl4+sflr>M]sN[dlf%l0=Flfdl2+sflr>N]dsMx[p]sMd1<M"
Diffie–Hellman 鍵交換より複雑な例では、Perl スクリプトに組み込まれている Diffie–Hellman 鍵交換がある。これは ITAR 議論のときにサイファーパンクたちの間で人気であった。このスクリプトは Unix ライクな OS にはどこにでもある Perl と dc だけで実行できる[7]: #!/usr/bin/perl -- -export-a-crypto-system-sig Diffie-Hellman-2-lines
($g, $e, $m) = @ARGV, $m || die "$0 gen exp mod\n";
print `echo "16dio1[d2%Sa2/d0<X+d*La1=z\U$m%0]SX$e"[$g*]\EszlXx+p | dc`
これのコメント付きのバージョンは少しわかりやすく、ループや条件分岐、マクロから脱出するための #!/usr/bin/perl
my ($g, $e, $m) = map { "\U$_" } @ARGV;
die "$0 gen exp mod\n" unless $m;
print `echo $g $e $m | dc -e '
# Hex input and output
16dio
# Read m, e and g from stdin on one line
?SmSeSg
# Function z: return g * top of stack
[lg*]sz
# Function Q: remove the top of the stack and return 1
[sb1q]sQ
# Function X(e): recursively compute g^e % m
# It is the same as Sm^Lm%, but handles arbitrarily large exponents.
# Stack at entry: e
# Stack at exit: g^e % m
# Since e may be very large, this uses the property that g^e % m ==
# if( e == 0 )
# return 1
# x = (g^(e/2)) ^ 2
# if( e % 2 == 1 )
# x *= g
# return x %
[
d 0=Q # return 1 if e==0 (otherwise, stack: e)
d 2% Sa # Store e%2 in a (stack: e)
2/ # compute e/2
lXx # call X(e/2)
d* # compute X(e/2)^2
La1=z # multiply by g if e%2==1
lm % # compute (g^e) % m
] SX
le # Load e from the register
lXx # compute g^e % m
p # Print the result
'`;
関連項目脚注・出典
外部リンク
|
