optimum multiple exponentiation 'problem'

[Greenbank]

Here's an interesting problem that I'm trying to solve and produce the optimum solution, with an efficient algorithm.

It concerns creating multiple exponentions of a certain value with the minimal computational power.

You are given a value x and a set of required powers n.
So you need to compute x^n for each member of n.

i.e. n = { 2, 3, 4, 5, 6 }

There are two operations available. sqr(x) and mul( x_i, x_j ).

For the sake of this problem consider sqr() slightly faster than mul( ) but only just.

If S is the number of sqr() operations and M is the number of mul() operations then solutions are first ranked on S+M (the lower the better), and if several solutions have this same lowest score then the one(s) with minimal M (and maximum S) will be considered the fastest.

A divide operation does exist but it is too computationally expensive to use.

Imagine the following powers of x are required:-

n = { 2, 4, 5 }

The obivous answer is to perform these operations:-

x_2 = sqr( x )
x_4 = sqr( x_2 )
x_5 = mul( x_4, x )

2 sqr() and 1 mul().

But now consider the following powers of x:-

n = {2, 3, 4, 17 }

The most optimal solution is this:-

x_2 = sqr( x )
x_4 = sqr( x_2 )
x_8 = sqr( x_4 )
x_16 = sqr( x_8 )
x_3 = mul( x_2, x )
x_17 = mul( x_16, x )

4 sqr and 2 mul operations.

However, consider this set:-

n = {2, 4, 5, 10}

My original algorithm would calculate the powers x_i where i = 2^n and i < n_max. So, for this case, it would do:-

x_2 = sqr( x )
x_4 = sqr( x_2 )
x_8 = sqr( x_4 )
x_5 = mul( x_4, x )
x_10 = mul( x_8, x_2 )

3 sqr() and 2 mul() operations.

However, the most optimal solution is this:-

x_2 = sqr( x )
x_4 = sqr( x_2 )
x_5 = mul( x_4, x )
x_10 = sqr( x_5 )

3 sqr() and only 1 mul().

For:-

n = { 2, 3, 15 }

x_2 = sqr( x )
x_4 = sqr( x_2 )
x_8 = sqr( x_4 )
x_3 = mul( x_2, x )
x_7 = mul( x_4, x_3 )
x_15 = mul( x_8, x_7 )

3 sqr(), 3 mul()

but it could be done in:-

n = { 2, 3, 15 }

x_2 = sqr( x )
x_3 = mul( x_2, x )
x_6 = sqr( x_3 )
x_12 = sqr( x_6 )
x_15 = mul( x_12, x_3 )

3 sqr(), 2 mul().

Is this problem better known by another name (that I can go and read up on it) or know of a clever algorithm for solving it.

I'm trying to map it to a minimal-cost graph coverage problem but it doesn't quite fit.

Any ideas?

[Greenbank]

OK, problem slightly reduced.

for each even n required, if n/2 is required then obtain x_n by sqr( x_(n/2) ).

However this still leaves lots of n's, to give you an idea of the scale/bounds:-

The largest set of n has 9109 values and n_max = 10079.
There are two other sets, one containing 2006 values and another containing 8924 values.

I'm beginning to think that this is a rather complex problem and I might have to settle for a quick to compute but not optimal solution.

[R.D. Silverman]

Originally Posted by Greenbank

OK, problem slightly reduced.

for each even n required, if n/2 is required then obtain x_n by sqr( x_(n/2) ).

However this still leaves lots of n's, to give you an idea of the scale/bounds:-

The largest set of n has 9109 values and n_max = 10079.
There are two other sets, one containing 2006 values and another containing 8924 values.

I'm beginning to think that this is a rather complex problem and I might have to settle for a quick to compute but not optimal solution.

Look up (not surprisingly) Knuth Vol 2. See the section on 'addition chains".

Finding your minimal chain is known to be NP-Complete.

[Greenbank]

Thank you. I shall grab my colleagues copy of Knuth and be enlightened.

[Citrix]

What is the longest addition chain consisting only of primes or 2^n*p, assuming 1 and 2 are primes, since the term must start with 1 and 2 is the second term?

Citrix

[Greenbank]

After a bit more testing it turns out that this is unnecessary in this circumstance.

Two reasons:

1. The base I'm using is 2.
2. It's also modulo arithmetic.

It's actually quicker to use addition and then a conditional subtraction of the modulus and iterate from n_0 to n_max.

If the base were not an integer, or sufficiently high then addition/conditional subtraction would become slower than sqr[mod]() mul[mod]().

Interesting problem though. Thanks for the reference. Section 4.6.3 in Knuth (Vol II) IIRC.