3 の 333 乗を計算する

3の33乗はどうやって計算すべきか? - ザリガニが見ていた...。 にインスパイヤされて、3 の 333 乗を計算してみます。

最近の LL は 3 の 333 乗が計算できるらしいのですが、awk では計算できません。

$ python -c 'print 3**333'
7609880231320598097204258672650327807278963563720778651170100370357916\
3143930619961304414564937852255793535157094995201000183376930256653178\
6879537190794573523

$ perl -Mbignum -e 'print 3**333,"\n"'
7609880231320598097204258672650327807278963563720778651170100370357916\
3143930619961304414564937852255793535157094995201000183376930256653178\
6879537190794573523

$ ruby -e 'puts 3**333'
7609880231320598097204258672650327807278963563720778651170100370357916\
3143930619961304414564937852255793535157094995201000183376930256653178\
6879537190794573523

$ awk 'BEGIN {print 3 ^ 333}'
7.60988e+158

そこで、加算と乗算と乗算のみですが、多倍長整数計算のようなものを作ってみます。 数として計算するとダメなので、文字列に分解して桁ごとに計算しています。

#! /usr/local/bin/nawk -f
# arith.awk
# 多倍長整数計算
# usage: nawk -f arith.awk

BEGIN {
    print "多倍長整数計算: 3 ^ 33 = " arith_pow(3, 33);
    print "標準計算:       3 ^ 33 = " 3 ^ 33;

    print "多倍長整数計算: 3 ^ 333 = " arith_pow(3, 333);
    print "標準計算:       3 ^ 333 = " 3 ^ 333;
}

## arith_pow():     多倍長整数の乗算
##  in:     数値 num1, num2
##  out:    num1 ^ num2
function arith_pow(num1, num2,
                    mul_ans, i) {
    mul_ans = num1;

    for (i = 1; i < num2; i++) {
        mul_ans = arith_mul(mul_ans, num1);
    }

    return mul_ans;
}

## arith_mul():     多倍長整数の掛け算
##  in:     数値 num1, num2
##  out:    num1 * num2
function arith_mul(num1, num2,
                    add_ans, i) {

    add_ans = num1;

    for (i = 1; i < num2; i++) {
        add_ans = arith_add(add_ans, num1);
    }

    return add_ans;
}

## arith_add():     多倍長整数の足し算
##  in:     数値 num1, num2
##  out:    num1 + num2
function arith_add(num1, num2,
    num_arr1, arr1, num_arr2, arr2, larger, arr_new, plus, i, ret_val) {

    num_arr1 = split(reverse(num1), arr1, "");
    num_arr2 = split(reverse(num2), arr2, "");

    larger = (num_arr1 >= num_arr2) ? num_arr1 : num_arr2;

    for (i = 1; i <= larger; i++) {
        arr_new[i] = arr1[i] + arr2[i] + plus[i];
        if (arr_new[i] >= 10) {
            arr_new[i] = arr_new[i] % 10;
            arr_new[i + 1] = 1;
            plus[i + 1] = 1;
        }
    }

    for (i = plus[larger + 1] ? larger + 1 : larger; i > 0; i--) {
        ret_val = ret_val arr_new[i];
    }

    return ret_val;
}

## reverse():   文字列を逆にする
##  in:     文字列 num
##  out:    文字列 num を逆にしたもの
function reverse(num,    i, ret_val) {
    for (i = length(num); i > 0; i--) {
        ret_val = ret_val substr(num, i, 1);
    }

    return ret_val;
}

関数名を見て気が付かれた方もいると思いますが、awk で多倍長整数計算をしていた人がいらっしゃって Arithmetica としてリリースされています。 AWK のリンク先が切れてしまっていますが、Arithmetica からダウンロードできます。

復活してくださることを期待して、とりあえず、実行してみます。

$ gawk -f arith.awk
多倍長整数計算: 3 ^ 33 = 5559060566555523
標準計算:       3 ^ 33 = 5559060566555523
多倍長整数計算: 3 ^ 333 = 760988023132059809720425867265032780727896356372077865117010037035791631439306199613044145649378522557935351570949952010001833769302566531786879537190794573523
標準計算:       3 ^ 333 = 7.60988e+158

アルゴリズムによる最適化などを行っていないため、非常に遅いのですが、ちゃんと 3 の 333 乗を計算することができました。

Arithmetica の DL 先 (2011/10/30)

Arithmetica の DL 先を教えていただきました。 以下の URL になります。

  • http://homepage3.nifty.com/text/download/arith_h.lzh

tag_nawk.png tag_nawk.png tag_nawk.png tag_nawk.png