Knuth's power tree: Difference between revisions
Content added Content deleted
m (Normalised orthography) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 450: | Line 450: | ||
191: [1, 2, 4, 8, 16, 32, 64, 128, 160, 176, 184, 188, 190, 191] |
191: [1, 2, 4, 8, 16, 32, 64, 128, 160, 176, 184, 188, 190, 191] |
||
3 ^ 191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347</pre> |
3 ^ 191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347</pre> |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
Line 1,128: | Line 1,125: | ||
191: (1 2 4 8 16 32 64 128 160 176 184 188 190 191) |
191: (1 2 4 8 16 32 64 128 160 176 184 188 190 191) |
||
3^191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347 |
3^191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347 |
||
</pre> |
|||
=={{header|Perl 6}}== |
|||
Paths are random. It is possible replace <code>.pick(*)</code> with <code>.reverse</code> if you want paths as in Perl, or remove it for Python paths. |
|||
<lang perl6>use v6; |
|||
sub power-path ($n ) { |
|||
state @unused_nodes = (2,); |
|||
state @power-tree = (False,0,1); |
|||
until @power-tree[$n].defined { |
|||
my $node = @unused_nodes.shift; |
|||
for $node X+ power-path($node).pick(*) { |
|||
next if @power-tree[$_].defined; |
|||
@unused_nodes.push($_); |
|||
@power-tree[$_]= $node; |
|||
} |
|||
} |
|||
( $n, { @power-tree[$_] } ...^ 0 ).reverse; |
|||
} |
|||
multi power ( $, 0 ) { 1 }; |
|||
multi power ( $n, $exponent ) { |
|||
state %p; |
|||
my %r = %p{$n} // ( 0 => 1, 1 => $n ) ; |
|||
for power-path( $exponent ).rotor( 2 => -1 ) -> ( $p, $c ) { |
|||
%r{ $c } = %r{ $p } * %r{ $c - $p } |
|||
} |
|||
%p{$n} := %r ; |
|||
%r{ $exponent } |
|||
} |
|||
say 'Power paths: ', pairs map *.&power-path, ^18; |
|||
say '2 ** key = value: ', pairs map { 2.&power($_) }, ^18; |
|||
say 'Path for 191: ', power-path 191; |
|||
say '3 ** 191 = ', power 3, 191; |
|||
say 'Path for 81: ', power-path 81; |
|||
say '1.1 ** 81 = ', power 1.1, 81; |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
Power paths: (0 => () 1 => (1) 2 => (1 2) 3 => (1 2 3) 4 => (1 2 4) 5 => (1 2 3 5) 6 => (1 2 3 6) 7 => (1 2 3 6 7) 8 => (1 2 4 8) 9 => (1 2 3 6 9) 10 => (1 2 3 5 10) 11 => (1 2 3 6 9 11) 12 => (1 2 3 6 12) 13 => (1 2 3 6 12 13) 14 => (1 2 3 6 12 14) 15 => (1 2 3 6 9 15) 16 => (1 2 4 8 16) 17 => (1 2 4 8 16 17)) |
|||
2 ** key = value: (0 => 1 1 => 2 2 => 4 3 => 8 4 => 16 5 => 32 6 => 64 7 => 128 8 => 256 9 => 512 10 => 1024 11 => 2048 12 => 4096 13 => 8192 14 => 16384 15 => 32768 16 => 65536 17 => 131072) |
|||
Path for 191: (1 2 3 6 9 18 27 54 108 162 189 191) |
|||
3 ** 191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347 |
|||
Path for 81: (1 2 3 6 9 18 27 54 81) |
|||
1.1 ** 81 = 2253.24023604401 |
|||
</pre> |
</pre> |
||
Line 1,403: | Line 1,348: | ||
81: (1 2 3 5 10 20 40 41 81) |
81: (1 2 3 5 10 20 40 41 81) |
||
1.1^81 = 2253.2402360440283</pre> |
1.1^81 = 2253.2402360440283</pre> |
||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
Paths are random. It is possible replace <code>.pick(*)</code> with <code>.reverse</code> if you want paths as in Perl, or remove it for Python paths. |
|||
<lang perl6>use v6; |
|||
sub power-path ($n ) { |
|||
state @unused_nodes = (2,); |
|||
state @power-tree = (False,0,1); |
|||
until @power-tree[$n].defined { |
|||
my $node = @unused_nodes.shift; |
|||
for $node X+ power-path($node).pick(*) { |
|||
next if @power-tree[$_].defined; |
|||
@unused_nodes.push($_); |
|||
@power-tree[$_]= $node; |
|||
} |
|||
} |
|||
( $n, { @power-tree[$_] } ...^ 0 ).reverse; |
|||
} |
|||
multi power ( $, 0 ) { 1 }; |
|||
multi power ( $n, $exponent ) { |
|||
state %p; |
|||
my %r = %p{$n} // ( 0 => 1, 1 => $n ) ; |
|||
for power-path( $exponent ).rotor( 2 => -1 ) -> ( $p, $c ) { |
|||
%r{ $c } = %r{ $p } * %r{ $c - $p } |
|||
} |
|||
%p{$n} := %r ; |
|||
%r{ $exponent } |
|||
} |
|||
say 'Power paths: ', pairs map *.&power-path, ^18; |
|||
say '2 ** key = value: ', pairs map { 2.&power($_) }, ^18; |
|||
say 'Path for 191: ', power-path 191; |
|||
say '3 ** 191 = ', power 3, 191; |
|||
say 'Path for 81: ', power-path 81; |
|||
say '1.1 ** 81 = ', power 1.1, 81; |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
Power paths: (0 => () 1 => (1) 2 => (1 2) 3 => (1 2 3) 4 => (1 2 4) 5 => (1 2 3 5) 6 => (1 2 3 6) 7 => (1 2 3 6 7) 8 => (1 2 4 8) 9 => (1 2 3 6 9) 10 => (1 2 3 5 10) 11 => (1 2 3 6 9 11) 12 => (1 2 3 6 12) 13 => (1 2 3 6 12 13) 14 => (1 2 3 6 12 14) 15 => (1 2 3 6 9 15) 16 => (1 2 4 8 16) 17 => (1 2 4 8 16 17)) |
|||
2 ** key = value: (0 => 1 1 => 2 2 => 4 3 => 8 4 => 16 5 => 32 6 => 64 7 => 128 8 => 256 9 => 512 10 => 1024 11 => 2048 12 => 4096 13 => 8192 14 => 16384 15 => 32768 16 => 65536 17 => 131072) |
|||
Path for 191: (1 2 3 6 9 18 27 54 108 162 189 191) |
|||
3 ** 191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347 |
|||
Path for 81: (1 2 3 6 9 18 27 54 81) |
|||
1.1 ** 81 = 2253.24023604401 |
|||
</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |