Search on the blog

2014年3月2日日曜日

tetrationとiterated logarithm


 tetrationとiterated logarithm。
それぞれ演算の種類です。見たことはありましたが、理解が曖昧だったので調べてみました。

tetrationとは?
na = 1 if n = 0
na = a^((n-1)a) if n > 0

で定義される演算です。

02 = 1
12 = 2^(02) = 2
22 = 2^(12) = 4
32 = 2^(22) = 16
42 = 2^(32) = 65536
52 = 2^(42) = 2^65536
......

のようになり、ものすごい早さで増加する関数です。

a * n = a + a + a + a + ....というように掛け算は足し算に分解できます。
同様に、
a ^ n = a * a * a * a * ... というようにべき乗は掛け算に分解できます。

tetrationの場合は、
na = a^(a^(a^(a^....)))というようにべき乗に分解できます。 例えば42 = 2^(2^(2^2)) = 2^(2^4) = 2 ^ 16 = 65536というふうになります。

iterated logarithmとは?
iterated logarithmとは以下のように定義される関数です。

log*(n) = 0 if n <= 1
log*(n) = 1 + log*(log(n)) if n > 1

log*()は一般に"log star"と読みます。

例えば底を2とすると、
log*(1) = 0
log*(2) = 1 + log*(log(2)) = 1 + log*(1) = 1
log*(4) = 1+ log*(log(4)) = 1 + log*(2) = 2
log*(16) = 1 + log*(log(16)) = 1 + log*(4) = 3
log*(65536) = 1 + log*(log(65536)) = 1 + log*(16) = 4
log*(2^65536) = 1 + log*(log(2^65536)) = 1 + log*(65536) = 5

となります。ちょうどtetrationの逆関数のような関係(※)にあり、ものすごく増加の遅い関数です。

※厳密にはtetrationの逆関数はsuper-logarithmです。
正の実数nに対して、super-logarithmとiterated logarithmには
log*n = ceil(slog(n))
という関係が成り立ちます。

0 件のコメント:

コメントを投稿