Addition-chain exponentiation: Difference between revisions

=={{header|J}}==

<lang j>vars=: 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'

mul=: '+/ .*'

eq=: '=:'

b2e=:3 :0 NB. express binary chain as equation

(|.x{.~##:y) b2e y

:

b=. }.#: y

v=. (-#b) {. x

({.x),eq,(,(mul,~])"0 |.b#v), ([,eq,])/(],mul,])"0 v

)

addch=:3 :0

p=. q: y

N=: +/n=. #@#:"0 p

assert N <: 1+#vars NB. enough variables?

v=. (|.N{.vars) <@(' ',])/.~ (+/\n) I. 1+i.N

3}.;v b2e&.> p

)</lang>

This implementation finds an expression which calculates the given exponent. <code>b2e</code> finds the binary chain expression for that exponent. <code>addch</code> finds the addition chain expression.

This implementation of addch uses binary chain for each prime factor of the exponent and combines them.

Example use:

<lang j> mul=: '*'

addch 15

C*C*C =:A*B*B=:A*A

addch 31415

L*M*M=:L*L =:G*I*J*K*K*K=:J*J=:I*I=:H*H=:G*G =:A*B*C*F*F*F=:E*E=:D*D=:C*C=:B*B=:A*A

addch 27182

N*N =:A*B*C*E*I*K*M*M*M=:L*L=:K*K=:J*J=:I*I=:H*H=:G*G=:F*F=:E*E=:D*D=:C*C=:B*B=:A*A

addch 27182*31415

a*a =:Y*Z*Z=:Y*Y =:T*V*W*X*X*X=:W*W=:V*V=:U*U=:T*T =:N*O*P*S*S*S=:R*R=:Q*Q=:P*P=:O*O=:N*N =:A*B*C*E*I*K*M*M*M=:L*L=:K*K=:J*J=:I*I=:H*H=:G*G=:F*F=:E*E=:D*D=:C*C=:B*B=:A*A</lang>

I tried to compute the expression given by addch 31415 using matrix multiplication as my multiplier, and using

<lang j>A=: ".;._2]0 :0

4 _3 4r3 _1r4

_13r3 19r4 _7r3 11r24

3r2 _2 7r6 _1r4

_1r6 1r4 _1r6 1r24

)</lang>

However, I ran out of memory needed to represent the arbitrary precision intermediate results.

When I use floating point values instead of arbitrary precision, the result I got was:

<lang j> mul=: +/ .*

do addch 31415

_ __ _ __

__ _ __ _

_ __ _ __

__ _ __ _</lang>

Here a single underline represents floating point infinity and a double underline represents negative floating point infinity.

So I have elected to not try to compute the other requested results.

That said, note that this approach exceeds the values given in the A003313 by 1 in 22 cases, when considering the first 100 values in the sequence.