20050929, 15:38  #1 
Jul 2005
2×193 Posts 
optimum multiple exponentiation 'problem'
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 minimalcost graph coverage problem but it doesn't quite fit. Any ideas? 
20050929, 16:57  #2 
Jul 2005
2·193 Posts 
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. 
20050929, 17:20  #3  
Nov 2003
2^{2}×5×373 Posts 
Quote:
Finding your minimal chain is known to be NPComplete. 

20050929, 18:22  #4 
Jul 2005
2×193 Posts 
Thank you. I shall grab my colleagues copy of Knuth and be enlightened.

20050929, 19:32  #5 
Jun 2003
3×23^{2} Posts 
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 
20050930, 10:20  #6 
Jul 2005
2·193 Posts 
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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Question on modular exponentiation?  ramshanker  Math  2  20151031 15:28 
Exponentiation w/ independent variable  Unregistered  Homework Help  4  20100804 06:38 
Optimum LL settings+hardware for i5/i7  hj47  Hardware  58  20091212 12:23 
Optimum amount of RAM for P1 testing  dave_0273  Data  3  20031101 17:07 
Multiple systems/multiple CPUs. Best configuration?  BillW  Software  1  20030121 20:11 