Knuth's power tree: Difference between revisions
Added Perl
(Added Sidef) |
(Added Perl) |
||
Line 334:
<lang J> 90j83 ": (x:1.1) usepath 81
2253.24023604401248793730853803334956796672985248117050381481057734540658419009864481100</lang>
=={{header|Perl}}==
<lang perl>use Memoize;
memoize('path');
sub path {
my ($n, $p, $lvl) = @_;
$p ||= {1 => 0};
$lvl ||= [[1]];
return () if ($n == 0);
until (exists $p->{$n}) {
my @q;
foreach my $x (@{$lvl->[0]}) {
foreach my $y (path($x, $p, $lvl)) {
my $z = $x + $y;
last if exists($p->{$z});
$p->{$z} = $x;
push @q, $z;
}
}
$lvl->[0] = \@q;
}
(path($p->{$n}), $n);
}
sub tree_pow {
my ($x, $n) = @_;
my %r = (0 => 1, 1 => $x);
my $p = 0;
foreach my $i (path($n)) {
$r{$i} = $r{$i - $p} * $r{$p};
$p = $i;
}
$r{$n};
}
sub show_pow {
my ($x, $n) = @_;
my $fmt = "%d: %s\n" . ("%g^%s = %f", "%s^%s = %s")[$x == int($x)] . "\n";
printf($fmt, $n, "(" . join(" ", path($n)) . ")", $x, $n, tree_pow($x, $n));
}
show_pow(2, $_) for 0 .. 17;
show_pow(1.1, 81);
{
use bigint (try => 'GMP');
show_pow(3, 191);
}</lang>
{{out}}
<pre style="height:32ex;overflow:scroll">
0: ()
2^0 = 1
1: (1)
2^1 = 2
2: (1 2)
2^2 = 4
3: (1 2 3)
2^3 = 8
4: (1 2 4)
2^4 = 16
5: (1 2 4 5)
2^5 = 32
6: (1 2 4 6)
2^6 = 64
7: (1 2 4 6 7)
2^7 = 128
8: (1 2 4 8)
2^8 = 256
9: (1 2 4 8 9)
2^9 = 512
10: (1 2 4 8 10)
2^10 = 1024
11: (1 2 4 8 10 11)
2^11 = 2048
12: (1 2 4 8 12)
2^12 = 4096
13: (1 2 4 8 12 13)
2^13 = 8192
14: (1 2 4 8 12 14)
2^14 = 16384
15: (1 2 4 8 12 14 15)
2^15 = 32768
16: (1 2 4 8 16)
2^16 = 65536
17: (1 2 4 8 16 17)
2^17 = 131072
81: (1 2 4 8 16 32 64 80 81)
1.1^81 = 2253.240236
191: (1 2 4 8 16 32 64 128 160 176 184 188 190 191)
3^191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347
</pre>
=={{header|Python}}==
| |||