mersenneforum.org Best practices in addition chains
 Register FAQ Search Today's Posts Mark Forums Read

 2009-07-25, 05:07 #1 SPWorley   Jul 2009 378 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 double-and-add-if-odd standard binary method. Ie, for 15, I'd like to get a 6-long chain like 1 2 3 6 12 15 which is better than the binary method which computes the 7-long 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(N-1), or 1+chain(N-2). 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!
 2009-07-25, 07:38 #2 Robert Holmes     Oct 2007 3×5×7 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
 2009-07-25, 11:43 #3 jasonp Tribal Bullet     Oct 2004 1101110001112 Posts GMP-ECM 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.
2009-07-25, 14:53   #4
SPWorley

Jul 2009

31 Posts

Quote:
 Originally Posted by Robert Holmes Bernstein has a survey with focus on exponentiation applications at: http://cr.yp.to/papers/pippenger.pdf
Excellent, lots of useful details in there!

2009-07-25, 14:57   #5
SPWorley

Jul 2009

31 Posts

Quote:
 Originally Posted by jasonp GMP-ECM 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.
Googling for Montgomery PRAC doesn't turn up anything.
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?

 2009-07-25, 16:02 #6 akruppa     "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 a-b 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 6-1=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_{m-n}) via Lucas chains", see ftp://ftp.cwi.nl/pub/pmontgom/Lucas.ps.gz. Alex
2009-07-26, 00:06   #7
SPWorley

Jul 2009

31 Posts

Quote:
 Originally Posted by akruppa 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 a-b 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 6-1=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_{m-n}) via Lucas chains", see ftp://ftp.cwi.nl/pub/pmontgom/Lucas.ps.gz.
Alex, wow, excellent.. I would never have found that. This is also a lot to digest! Thanks.

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.

2009-07-26, 17:23   #8

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts

Quote:
 Originally Posted by SPWorley 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.
Write him a note! I'm sure he'd appreciate it.

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://www-cs-faculty.stanford.edu/~knuth/email.html

2009-07-27, 12:44   #9
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by SPWorley Alex, wow, excellent.. I would never have found that. This is also a lot to digest! Thanks. 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.
Indeed. AFAIK even today it is not known if finding an optimal
addition chain is in P or whether it is NPC. I suspect the latter.
It may be reducible to the subset-sum problem in some way.

2009-07-28, 11:35   #10
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by R.D. Silverman Indeed. AFAIK even today it is not known if finding an optimal addition chain is in P or whether it is NPC. I suspect the latter. It may be reducible to the subset-sum problem in some way.
AHA!! It is known to be NPC.

http://scitation.aip.org/getabs/serv...cvips&gifs=yes

 2009-07-28, 13:50 #11 Robert Holmes     Oct 2007 10510 Posts It might still be possible, albeit unlikely, that the special (and more often used) case where m=1 is solvable in P.

 Similar Threads Thread Thread Starter Forum Replies Last Post robert44444uk Open Projects 12 2013-08-24 07:42 Redarm Lounge 2 2013-07-18 01:04 Darin Information & Answers 7 2012-08-02 11:02 davieddy Puzzles 12 2011-08-09 02:36 Dougy Math 10 2009-09-11 21:05

All times are UTC. The time now is 10:55.

Tue Aug 11 10:55:07 UTC 2020 up 25 days, 6:41, 1 user, load averages: 2.92, 2.56, 2.24