mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2009-07-25, 05:07   #1
SPWorley
 
Jul 2009

3110 Posts
Default 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!
SPWorley is offline   Reply With Quote
Old 2009-07-25, 07:38   #2
Robert Holmes
 
Robert Holmes's Avatar
 
Oct 2007

23·13 Posts
Default

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
Robert Holmes is offline   Reply With Quote
Old 2009-07-25, 11:43   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101101000012 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2009-07-25, 14:53   #4
SPWorley
 
Jul 2009

31 Posts
Default

Quote:
Originally Posted by Robert Holmes View Post
Bernstein has a survey with focus on exponentiation applications at:

http://cr.yp.to/papers/pippenger.pdf
Excellent, lots of useful details in there!
SPWorley is offline   Reply With Quote
Old 2009-07-25, 14:57   #5
SPWorley
 
Jul 2009

31 Posts
Default

Quote:
Originally Posted by jasonp View Post
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?
SPWorley is offline   Reply With Quote
Old 2009-07-25, 16:02   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000002 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2009-07-26, 00:06   #7
SPWorley
 
Jul 2009

31 Posts
Default

Quote:
Originally Posted by akruppa View Post
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.
SPWorley is offline   Reply With Quote
Old 2009-07-26, 17:23   #8
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×599 Posts
Default

Quote:
Originally Posted by SPWorley View Post
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
cheesehead is offline   Reply With Quote
Old 2009-07-27, 12:44   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by SPWorley View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2009-07-28, 11:35   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

723210 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2009-07-28, 13:50   #11
Robert Holmes
 
Robert Holmes's Avatar
 
Oct 2007

23×13 Posts
Default

It might still be possible, albeit unlikely, that the special (and more often used) case where m=1 is solvable in P.
Robert Holmes is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Generalised Cunningham Chains robert44444uk Open Projects 12 2013-08-24 07:42
Primecoin - Cunningham Chains Redarm Lounge 2 2013-07-18 01:04
Torture test best practices Darin Information & Answers 7 2012-08-02 11:02
Cockney rhyming slang chains. davieddy Puzzles 12 2011-08-09 02:36
On prime chains Dougy Math 10 2009-09-11 21:05

All times are UTC. The time now is 04:23.

Thu Nov 26 04:23:28 UTC 2020 up 77 days, 1:34, 3 users, load averages: 1.46, 1.85, 1.83

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.