Addition-chain exponentiation: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
| (6 intermediate revisions by 2 users not shown) | |||
Line 1,056:
Uses an iterator to generate A003313 (the first 100 values). Uses the Knuth path method for the larger integers. This gives a chain length of 18 for both 27182 and 31415.
<syntaxhighlight lang="julia">import Base.iterate
mutable struct AdditionChains{T}
Line 1,079 ⟶ 1,078:
function findchain!(acs::AdditionChains, n)
@assert n > 0
n == 1 && return [one(eltype(first(acs.chains)))]
idx = findfirst(a -> a[end] == n, acs.chains)
Line 1,132 ⟶ 1,131:
println("1.00002550055251^27182 = ", pow(1.00002550055251, expchains[27182]))
println("1.00002550055251^(27182 * 31415) = ", pow(BigFloat(pow(1.00002550055251, expchains[27182])), expchains[31415]))
println("(1.000025 + 0.000058i)^27182 = ", pow(Complex(1.000025, 0.000058), expchains[27182]))
println("(1.000022 + 0.000050i)^31415 = ", pow(Complex(1.000022, 0.000050), expchains[31415]))
x = sqrt(1/2)
matrixA = [x 0 x 0 0 0; 0 x 0 x 0 0; 0 x 0 -x 0 0; -x 0 x 0 0 0; 0 0 0 0 0 1; 0 0 0 0 1 0]
Line 1,168 ⟶ 1,167:
1.00002550055251^27182 = 1.9999999999792688
1.00002550055251^(27182 * 31415) = 7.199687435551025768365237017391630520475805934721292725697031724530209692195819e+9456
(1.000025 + 0.000058i)^27182 = -0.01128636963542673 + 1.9730308496660347im
(1.000022 + 0.000050i)^31415 = 0.00016144681325535107 + 1.9960329014194498im
matrix A ^ 27182 =
6×6 Matrix{Float64}:
Line 1,752 ⟶ 1,751:
--1.00003 ^ 27182 (20) = 1.9999999999727968238298855
--1.00003 ^ 27182 (19) = 1.9999999999727968238298527</pre>
=={{header|Python}}==
<syntaxhighlight lang="python">''' Rosetta Code task Addition-chain_exponentiation '''
from math import sqrt
from numpy import array
from mpmath import mpf
class AdditionChains:
''' two methods of calculating addition chains '''
def __init__(self):
''' memoization for knuth_path '''
self.chains, self.idx, self.pos = [[1]], 0, 0
self.pat, self.lvl = {1: 0}, [[1]]
def add_chain(self):
''' method 1: add chains depth then breadth first until done '''
newchain = self.chains[self.idx].copy()
newchain.append(self.chains[self.idx][-1] +
self.chains[self.idx][self.pos])
self.chains.append(newchain)
if self.pos == len(self.chains[self.idx])-1:
self.idx += 1
self.pos = 0
else:
self.pos += 1
return newchain
def find_chain(self, nexp):
''' method 1 interface: search for chain ending with n, adding more as needed '''
assert nexp > 0
if nexp == 1:
return [1]
chn = next((a for a in self.chains if a[-1] == nexp), None)
if chn is None:
while True:
chn = self.add_chain()
if chn[-1] == nexp:
break
return chn
def knuth_path(self, ngoal):
''' method 2: knuth method, uses memoization to search for a shorter chain '''
if ngoal < 1:
return []
while not ngoal in self.pat:
new_lvl = []
for i in self.lvl[0]:
for j in self.knuth_path(i):
if not i + j in self.pat:
self.pat[i + j] = i
new_lvl.append(i + j)
self.lvl[0] = new_lvl
returnpath = self.knuth_path(self.pat[ngoal])
returnpath.append(ngoal)
return returnpath
def cpow(xbase, chain):
''' raise xbase by an addition exponentiation chain for what becomes x**chain[-1] '''
pows, products = 0, {0: 1, 1: xbase}
for i in chain:
products[i] = products[pows] * products[i - pows]
pows = i
return products[chain[-1]]
if __name__ == '__main__':
# test both addition chain methods
acs = AdditionChains()
print('First one hundred addition chain lengths:')
for k in range(1, 101):
print(f'{len(acs.find_chain(k))-1:3}', end='\n'if k % 10 == 0 else '')
print('\nKnuth chains for addition chains of 31415 and 27182:')
chns = {m: acs.knuth_path(m) for m in [31415, 27182]}
for (num, cha) in chns.items():
print(f'Exponent: {num:10}\n Addition Chain: {cha[:-1]}')
print('\n1.00002206445416^31415 =', cpow(1.00002206445416, chns[31415]))
print('1.00002550055251^27182 =', cpow(1.00002550055251, chns[27182]))
print('1.000025 + 0.000058i)^27182 =',
cpow(complex(1.000025, 0.000058), chns[27182]))
print('1.000022 + 0.000050i)^31415 =',
cpow(complex(1.000022, 0.000050), chns[31415]))
sq05 = mpf(sqrt(0.5))
mat = array([[sq05, 0, sq05, 0, 0, 0], [0, sq05, 0, sq05, 0, 0], [0, sq05, 0, -sq05, 0, 0],
[-sq05, 0, sq05, 0, 0, 0], [0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 0]])
print('matrix A ^ 27182 =')
print(cpow(mat, chns[27182]))
print('matrix A ^ 31415 =')
print(cpow(mat, chns[31415]))
print('(matrix A ** 27182) ** 31415 =')
print(cpow(cpow(mat, chns[27182]), chns[31415]))
</syntaxhighlight>{{out}}
<pre>
First one hundred addition chain lengths:
0 1 2 2 3 3 4 3 4 4
5 4 5 5 5 4 5 5 6 5
6 6 6 5 6 6 6 6 7 6
7 5 6 6 7 6 7 7 7 6
7 7 7 7 7 7 8 6 7 7
7 7 8 7 8 7 8 8 8 7
8 8 8 6 7 7 8 7 8 8
9 7 8 8 8 8 8 8 9 7
8 8 8 8 8 8 9 8 9 8
9 8 9 9 9 7 8 8 8 8
Knuth chains for addition chains of 31415 and 27182:
Exponent: 31415
Addition Chain: [1, 2, 3, 5, 7, 14, 28, 56, 61, 122, 244, 488, 976, 1952, 3904, 7808, 15616, 15677, 31293]
Exponent: 27182
Addition Chain: [1, 2, 3, 5, 7, 14, 21, 35, 70, 140, 143, 283, 566, 849, 1698, 3396, 6792, 6799, 13591]
1.00002206445416^31415 = 1.9999999998924638
1.00002550055251^27182 = 1.9999999999792688
1.000025 + 0.000058i)^27182 = (-0.01128636963542673+1.9730308496660347j)
1.000022 + 0.000050i)^31415 = (0.00016144681325535107+1.9960329014194498j)
matrix A ^ 27182 =
[[mpf('5.0272320351359433e-4092') 0 mpf('5.0272320351359433e-4092') 0 0 0]
[0 mpf('5.0272320351359433e-4092') 0 mpf('5.0272320351359433e-4092') 0 0]
[0 mpf('5.0272320351359433e-4092') 0 mpf('5.0272320351359433e-4092') 0 0]
[mpf('5.0272320351359433e-4092') 0 mpf('5.0272320351359433e-4092') 0 0 0]
[0 0 0 0 0 1]
[0 0 0 0 1 0]]
matrix A ^ 31415 =
[[mpf('3.7268602513250562e-4729') 0 mpf('3.7268602513250562e-4729') 0 0 0]
[0 mpf('3.7268602513250562e-4729') 0 mpf('3.7268602513250562e-4729') 0 0]
[0 mpf('3.7268602513250562e-4729') 0 mpf('-3.7268602513250562e-4729') 0
0]
[mpf('-3.7268602513250562e-4729') 0 mpf('3.7268602513250562e-4729') 0 0
0]
[0 0 0 0 0 1]
[0 0 0 0 1 0]]
(matrix A ** 27182) ** 31415 =
[[mpf('1.77158544475749e-128528148') 0 mpf('1.77158544475749e-128528148')
0 0 0]
[0 mpf('1.77158544475749e-128528148') 0
mpf('1.77158544475749e-128528148') 0 0]
[0 mpf('1.77158544475749e-128528148') 0
mpf('1.77158544475749e-128528148') 0 0]
[mpf('1.77158544475749e-128528148') 0 mpf('1.77158544475749e-128528148')
0 0 0]
[0 0 0 0 0 1]
[0 0 0 0 1 0]]
</pre>
=={{header|Racket}}==
Line 1,813 ⟶ 1,962:
Multiplications: 21
</syntaxhighlight>
=={{header|Raku}}==
{{trans|Python}}
<syntaxhighlight lang="raku" line># 20230327 Raku programming solution
use Math::Matrix;
class AdditionChains { has ( $.idx, $.pos, @.chains, @.lvl, %.pat ) is rw;
method add_chain {
# method 1: add chains depth then breadth first until done
return gather given self {
take my $newchain = .chains[.idx].clone.append:
.chains[.idx][*-1] + .chains[.idx][.pos];
.chains.append: $newchain;
.pos == +.chains[.idx]-1 ?? ( .idx += 1 && .pos = 0 ) !! .pos += 1;
}
}
method find_chain(\nexp where nexp > 0) {
# method 1 interface: search for chain ending with n, adding more as needed
return ([1],) if nexp == 1;
my @chn = self.chains.grep: *.[*-1] == nexp // [];
unless @chn.Bool {
repeat { @chn = self.add_chain } until @chn[*-1][*-1] == nexp
}
return @chn
}
method knuth_path(\ngoal) {
# method 2: knuth method, uses memoization to search for a shorter chain
return [] if ngoal < 1;
until self.pat{ngoal}:exists {
self.lvl[0] = [ gather for self.lvl[0].Array -> \i {
for self.knuth_path(i).Array -> \j {
unless self.pat{i + j}:exists {
self.pat{i + j} = i and take i + j
}
}
} ]
}
return self.knuth_path(self.pat{ngoal}).append: ngoal
}
multi method cpow(\xbase, \chain) {
# raise xbase by an addition exponentiation chain for what becomes x**chain[-1]
my ($pows, %products) = 0, 1 => xbase;
%products{0} = xbase ~~ Math::Matrix
?? Math::Matrix.new([ [ 1 xx xbase.size[1] ] xx xbase.size[0] ]) !! 1;
for chain.Array -> \i {
%products{i} = %products{$pows} * %products{i - $pows};
$pows = i
}
return %products{ chain[*-1] }
}
}
my $chn = AdditionChains.new( idx => 0, pos => 0,
chains => ([1],), lvl => ([1],), pat => {1=>0} );
say 'First one hundred addition chain lengths:';
.Str.say for ( (1..100).map: { +$chn.find_chain($_)[0] - 1 } ).rotor: 10;
my %chns = (31415, 27182).map: { $_ => $chn.knuth_path: $_ };
say "\nKnuth chains for addition chains of 31415 and 27182:";
say "Exponent: $_\n Addition Chain: %chns{$_}[0..*-2]" for %chns.keys;
say '1.00002206445416^31415 = ', $chn.cpow(1.00002206445416, %chns{31415});
say '1.00002550055251^27182 = ', $chn.cpow(1.00002550055251, %chns{27182});
say '(1.000025 + 0.000058i)^27182 = ', $chn.cpow: 1.000025+0.000058i, %chns{27182};
say '(1.000022 + 0.000050i)^31415 = ', $chn.cpow: 1.000022+0.000050i, %chns{31415};
my \sq05 = 0.5.sqrt;
my \mat = Math::Matrix.new( [[sq05, 0, sq05, 0, 0, 0],
[ 0, sq05, 0, sq05, 0, 0],
[ 0, sq05, 0, -sq05, 0, 0],
[-sq05, 0, sq05, 0, 0, 0],
[ 0, 0, 0, 0, 0, 1],
[ 0, 0, 0, 0, 1, 0]] );
say 'matrix A ^ 27182 =';
say my $res27182 = $chn.cpow(mat, %chns{27182});
say 'matrix A ^ 31415 =';
say $chn.cpow(mat, %chns{31415});
say '(matrix A ** 27182) ** 31415 =';
say $chn.cpow($res27182, %chns{31415});
</syntaxhighlight>
{{out}}
<pre>First one hundred addition chain lengths:
0 1 2 2 3 3 4 3 4 4
5 4 5 5 5 4 5 5 6 5
6 6 6 5 6 6 6 6 7 6
7 5 6 6 7 6 7 7 7 6
7 7 7 7 7 7 8 6 7 7
7 7 8 7 8 7 8 8 8 7
8 8 8 6 7 7 8 7 8 8
9 7 8 8 8 8 8 8 9 7
8 8 8 8 8 8 9 8 9 8
9 8 9 9 9 7 8 8 8 8
Knuth chains for addition chains of 31415 and 27182:
Exponent: 27182
Addition Chain: 1 2 3 5 7 14 21 35 70 140 143 283 566 849 1698 3396 6792 6799 13591
Exponent: 31415
Addition Chain: 1 2 3 5 7 14 28 56 61 122 244 488 976 1952 3904 7808 15616 15677 31293
1.00002206445416^31415 = 1.9999999998924638
1.00002550055251^27182 = 1.999999999974053
(1.000025 + 0.000058i)^27182 = -0.01128636963542673+1.9730308496660347i
(1.000022 + 0.000050i)^31415 = 0.00016144681325535107+1.9960329014194498i
matrix A ^ 27182 =
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 1 0
matrix A ^ 31415 =
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 -0 0 0
-0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 1 0
(matrix A ** 27182) ** 31415 =
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 1 0</pre>
=={{header|Tcl}}==
Line 1,938 ⟶ 2,219:
{{libheader|Wren-fmt}}
This is very slow (12 mins 50 secs) compared to Go (25 seconds) but, given the amount of calculation involved, not too bad for the Wren interpreter.
<syntaxhighlight lang="
import "./fmt" for Fmt
var Save = Struct.create("Save", ["p", "i", "v"])
| |||