mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-09-29, 15:38   #1
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2·193 Posts
Default 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?
Greenbank is offline   Reply With Quote
Old 2005-09-29, 16:57   #2
Greenbank
 
Greenbank's Avatar
 
Jul 2005

18216 Posts
Default

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.
Greenbank is offline   Reply With Quote
Old 2005-09-29, 17:20   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

164448 Posts
Thumbs up

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-09-29, 18:22   #4
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2·193 Posts
Default

Thank you. I shall grab my colleagues copy of Knuth and be enlightened.
Greenbank is offline   Reply With Quote
Old 2005-09-29, 19:32   #5
Citrix
 
Citrix's Avatar
 
Jun 2003

22×397 Posts
Default

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
Citrix is offline   Reply With Quote
Old 2005-09-30, 10:20   #6
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2×193 Posts
Default

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.
Greenbank is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Question on modular exponentiation? ramshanker Math 2 2015-10-31 15:28
Exponentiation w/ independent variable Unregistered Homework Help 4 2010-08-04 06:38
Optimum LL settings+hardware for i5/i7 hj47 Hardware 58 2009-12-12 12:23
Optimum amount of RAM for P-1 testing dave_0273 Data 3 2003-11-01 17:07
Multiple systems/multiple CPUs. Best configuration? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔