素因数分解

前回の AWK Users JP :: ハミングの問題の中で「素因数分解を用いて解けると思った」と書いたので、素因数分解をやってみます。

これにもアルゴリズムがあり、C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー) (単行本)に掲載されています。

#! /usr/bin/gawk -f
# factorize.awk
# Ref. 「C言語による最新アルゴリズム事典」(ISBN-10: 4874084141) P.154

BEGIN {
    if (__test__) {
        for (i = 1; i <= 10; i++) {
            print i " = " factorize(i);
        }
    }
}

# factorize():  素因数分解を行い、その数式を返す
#   in:     数値
#   out:    素因数分解を行った結果の数式
function factorize(num,     d, q, factorize_str) {
    while (num >= 4 && num % 2 == 0) {
        factorize_str = "2 * ";
        num /= 2;
    }
    d = 3;
    q = num / d;
    while (q >= d) {
        if (num % d == 0) {
            factorize_str = factorize_str d " * ";
            num = q;
        } else {
            d +=2;
        }
        q = num / d;
    }
    factorize_str = factorize_str num;
    return factorize_str;
}

実際に実行してみましょう。

$ nawk -f factorize.awk -v __test__=1
1 = 1
2 = 2
3 = 3
4 = 2 * 2
5 = 5
6 = 2 * 3
7 = 7
8 = 2 * 2
9 = 3 * 3
10 = 2 * 5

このように計算されます。

さて、少しテストのことを考えてみます。 テストは重要であると言われていますが、これは awk でも他の言語でも同じです。 では、awk はどのようにしてテストを行うのが良いかという問題に対しては gawk のソースコードの中の test/Makefile が良い例になります。

非常にクラシックな方法ですが、Makefile の中にテストを行う手順を記述しておくことでテストを行います。

#! /usr/bin/make

AWK                     = /usr/local/bin/nawk
PROG_NAME               = factorize

TEST_FLAG               = -v __test__=1

CMP                     = /usr/bin/cmp

AWK_PROG                = $(PROG_NAME).awk
IN_FILE                 = $(PROG_NAME).in
OK_FILE                 = $(PROG_NAME).ok

check: $(PROG_NAME)

$(PROG_NAME):

	@echo $@
	@$(AWK) $(TEST_FLAG) -f $(AWK_PROG) > _$@
	@-$(CMP) $(OK_FILE) _$@ && rm -f _$@

	@make pass_fail

pass_fail:

	@COUNT=`ls _* 2> /dev/null | wc -l`;\
	if test $$COUNT = 0 ;\
	then echo ALL TEST PASSED ;\
	else echo $$COUNT TEST FAILED ;\
	fi

このような Makefile を用意します。 あらかじめ準備しておいた解答ファイル (この場合、拡張子を .ok にしています) と実際の出力が同じかどうかを cmp コマンドで検査して、異なる場合には出力ファイル名の先頭にアンダースコアを付けるというものです。

例えば、以下のような解答ファイル (factorize.ok) を用意します。

1 = 1
2 = 2
3 = 3
4 = 2 * 2
5 = 5
6 = 2 * 3
7 = 7
8 = 2 * 2
9 = 3 * 3
10 = 2 * 5

そこで、make check を実行します。

$ make check
factorize
make[1]: Entering directory `/home/hi_saito/work/awk/factorize'
ALL TEST PASSED
make[1]: Leaving directory `/home/hi_saito/work/awk/factorize'

このようにすることでチェックを行うことができます。 特に awk にはバリアントが多いため、どの awk を使うかを変数 (AWK) として保持しておくと make 実行時に変更ができるため便利です。

$ make check AWK='busybox awk'
factorize
make[1]: Entering directory `/home/hi_saito/work/awk/factorize'
ALL TEST PASSED
make[1]: Leaving directory `/home/hi_saito/work/awk/factorize'

今どき make コマンドは流行らないのかもしれませんが、最低限の使い方を知っておくと便利です。

tag_nawk.pngtag_nawk.pngtag_nawk.pngtag_nawk.png