mersenneforum.org > Math optimum multiple exponentiation 'problem'
 Register FAQ Search Today's Posts Mark Forums Read

 2005-09-29, 15:38 #1 Greenbank     Jul 2005 6028 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 minimal-cost graph coverage problem but it doesn't quite fit. Any ideas?
 2005-09-29, 16:57 #2 Greenbank     Jul 2005 38610 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.
2005-09-29, 17:20   #3
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 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.

 2005-09-29, 18:22 #4 Greenbank     Jul 2005 2·193 Posts Thank you. I shall grab my colleagues copy of Knuth and be enlightened.
 2005-09-29, 19:32 #5 Citrix     Jun 2003 3×232 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
 2005-09-30, 10:20 #6 Greenbank     Jul 2005 1100000102 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post ramshanker Math 2 2015-10-31 15:28 Unregistered Homework Help 4 2010-08-04 06:38 hj47 Hardware 58 2009-12-12 12:23 dave_0273 Data 3 2003-11-01 17:07 BillW Software 1 2003-01-21 20:11

All times are UTC. The time now is 13:52.

Sat May 28 13:52:34 UTC 2022 up 44 days, 11:53, 0 users, load averages: 1.25, 1.36, 1.48