 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 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 minimal-cost graph coverage problem but it doesn't quite fit. Any ideas?   2005-09-29, 16:57 #2 Greenbank   Jul 2005 18216 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

"Bob Silverman"
Nov 2003
North of Boston

164448 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 22×397 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 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 Show Printable Version Email this Page 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 12:30.

Wed Jul 6 12:30:37 UTC 2022 up 83 days, 10:31, 0 users, load averages: 1.29, 1.15, 1.23