1 chain with 3 bits set 4 chains with 4 bits set Notation: @(.) means 2^(.). p,q,r are free nonnegative integer variables. A,B,C,D are also free nonnegative integer variables. * in the index-list as a right sub_index indicates a doubling step. : is a delimiter in the sub-index to refine this sub-index by a further 'value'. Such a 'value' is in general a polynomial of degree 0 or 1 in one variable [i.e. an affine form with integer coefficients and dimension less or equal 1]. This 'value' indicates either in a doubling step how many doubling steps are here, or when using a doubling step in another index how many doubling steps are used there. If a doubling step is used with exactly as many doubling steps it was generated then this delimiter and 'value' is optional [E.g. It may be left out in the left sub-index for every star-chain]. In all two-power-sum representations the two-power-exponents are always strictly monotonic decreasing and >= 0. Shortest Addition Chains with 2 Small Steps 0 3* @(p)+@(q)+@(r) A=p, B=q, C=r 0 1 1( 0, *:A) @(A) 2( 1, 1:B) @(A)+@(B) 3( 2, 1:C) @(A)+@(B)+@(C) 1 4* @(p)+@(p-5)+@(p-6)+@(p-7) A=p-6 0 1 1( 0, *:A) @(A) 2( 1, 1:A-1) @(A)+@(A-1) 3( 2, 1 ) @(A+1)+@(A-1) 4( 3, *:3) @(A+4)+@(A+2) 5( 4, 3 ) @(A+4)+@(A+2)+@(A+1)+@(A-1) 6( 5, *:1) @(A+5)+@(A+3)+@(A+2)+@(A) 7( 6, 5 ) @(A+6)+@(A+1)+@(A)+@(A-1) 2 4* @(p)+@(p-3)+@(q)+@(q-1) A=p-3, C=q-1 0 1 1( 0, *:A) @(A) 2( 1, 1:A-1) @(A)+@(A-1) 3( 2, 1:C) @(A)+@(A-1)+@(C) 4( 3, 2 ) @(A+1)+@(A)+@(C) 5( 4, *:1) @(A+2)+@(A+1)+@(C+1) 6( 5, 4 ) @(A+3)+@(A)+@(C+1)+@(C) 3 4* @(p)+@(q)+@(r)+@(-p+q+r) A=q-1, B=-p+q+r, D=p-q-1 0 1 1( 0, *:A) @(A) 2( 1, 1:B) @(A)+@(B) 3( 2, 1 ) @(A+1)+@(B) 4( 3, *:D+1) @(A+D+2)+@(B+D+1) 5( 4, 3 ) @(A+D+2)+@(A+1)+@(B+D+1)+@(B) 4 4* @(p)+@(q)+@(r)+@(-p+q+r+1) A=r, B=-p+q+r+1, D=p-r-2 0 1 1( 0, *:A) @(A) 2( 1, 1:B) @(A)+@(B) 3( 2, 1 ) @(A+1)+@(B) 4( 3, *:D+1) @(A+D+2)+@(B+D+1) 5( 4, 2 ) @(A+D+2)+@(B+D+1)+@(A)+@(B)