20090725, 05:07  #1 
Jul 2009
37_{8} Posts 
Best practices in addition chains
What's the current standard algorithm for optimizing addition chains?
This is of course to minimize the number of multiplications needed to compute powers. I'd love to find a decent heuristic that doesn't have to be completely optimal, but is better than the doubleandaddifodd standard binary method. Ie, for 15, I'd like to get a 6long chain like 1 2 3 6 12 15 which is better than the binary method which computes the 7long 1 2 3 4 7 8 15 Knuth's 4.6.3 survey is fun but not too practical. Currently I'm computing short chains by a pretty simple heuristic.. kind of a poor man's broken dynamic program. If N is prime, I return the shorter of the binary chain, 1+chain(N1), or 1+chain(N2). if N is factorable into pq, I return the shortest of the binary chain, or chain(p)+chain(q) for all possible pq. That heuristic certainly isn't optimal but it seems OK for medium sized n up to 2^32 or so. But surely there's some better methods. There's explicit tables here. But I'm hoping for a nice little function I can call to get "pretty likely optimal" results. Huge bonus points if someone did some template metaprogramming in C++ to do this right at runtime! 
20090725, 07:38  #2 
Oct 2007
152_{8} Posts 
If your objective is not to find the absolute best chain, there are a lot of improvements that can be done to the binary method. Bernstein has a survey with focus on exponentiation applications at:
http://cr.yp.to/papers/pippenger.pdf 
20090725, 11:43  #3 
Tribal Bullet
Oct 2004
6731_{8} Posts 
GMPECM uses Montgomery's PRAC algorithm. His experiments show that the worst case result of the algorithm is within just a few percent of the performance of an optimal addition chain.

20090725, 14:53  #4  
Jul 2009
37_{8} Posts 
Quote:


20090725, 14:57  #5  
Jul 2009
31_{10} Posts 
Quote:
Is this the idea of precomputing a table of 1 x^2 x^3 x^4 x^5 x^6 x^7 (or up to some 2^m 1) and then taking big steps of m bits at once and just doing one table lookup and then m doubling steps? 

20090725, 16:02  #6 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
PRAC looks for what Montgomery dubbed "Lucas chains," which are addition chains with the extra condition that whenever a+b is formed from earlier chain elements a and b, then ab must also be in the chain, or must be 0. For example, 1,2,3,6,7 isn't a Lucas chain because you need 61=5 to make 6+1=7. However, 1,2,3,5,7 is a Lucas chain. Such chains are needed for arithmetic on elliptic curves in Montgomery form, and for P+1 factoring/primality testing. The relevant manuscript (it was never formally published) is "Evaluating recurrences of form X_{m+n} = f (X_m, X_n, X_{mn}) via Lucas chains", see ftp://ftp.cwi.nl/pub/pmontgom/Lucas.ps.gz.
Alex 
20090726, 00:06  #7  
Jul 2009
31 Posts 
Quote:
Knuth was so correct when he wrote that there was a rich and mysterious theory behind efficient addition chains. 30 years later it seems just as true. 

20090726, 17:23  #8  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Quote:
Just be sure to use "snail mail" (as Knuth writes: "So if you want to write to me about any topic, please use good ol' snail mail and send a letter to the following address: ") and send it to the address given on this page: http://wwwcsfaculty.stanford.edu/~knuth/email.html 

20090727, 12:44  #9  
Nov 2003
2^{2}·5·373 Posts 
Quote:
addition chain is in P or whether it is NPC. I suspect the latter. It may be reducible to the subsetsum problem in some way. 

20090728, 11:35  #10  
Nov 2003
2^{2}·5·373 Posts 
Quote:
http://scitation.aip.org/getabs/serv...cvips&gifs=yes 

20090728, 13:50  #11 
Oct 2007
2×53 Posts 
It might still be possible, albeit unlikely, that the special (and more often used) case where m=1 is solvable in P.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Generalised Cunningham Chains  robert44444uk  Open Projects  12  20130824 07:42 
Primecoin  Cunningham Chains  Redarm  Lounge  2  20130718 01:04 
Torture test best practices  Darin  Information & Answers  7  20120802 11:02 
Cockney rhyming slang chains.  davieddy  Puzzles  12  20110809 02:36 
On prime chains  Dougy  Math  10  20090911 21:05 