Constant multiplication

I've just seen on Google that there was a thread on the multiplication by a constant (using shifts and adds) last September in rec.puzzles. I'm interested in all the results that could have been found about this

Dennis Yelle posted the solution 699829. What else would you like to know?

Luc

The result for 6 adders, for instance.

what problem?

The articles have disappeared from Google.

The problem is to know how many additions/subtractions are necessary to perform a multiplication by a constant n, where you can do left shifts, additions and subtractions.

For instance, we can search for the smallest value n such that k additions/subtractions are required. The articles posted a few months ago dealt with k = 6. But one of the posters said he was computing the result for k = 7. I'm writing programs for this problem too.

I also found interesting algorithms to generate (non-optimal, of course) shift-and-add code from a constant n in a polynomial time, and I'm still working to improve them...

No they haven't Go to www.deja.com, then search for 'constant multiplication 699829'. You'll get one of the messages, click on 'Show complete thread' to view the rest

Well, their search engine is broken. If I search for

constant multiplication group:rec.puzzles

I get only 2 articles (18 Apr 2001 and 27 Feb 2001). But if I search for

constant multiplication 699829 group:rec.puzzles

I get one article posted on 19 Sep 2000.

..and if you click on the first one, you'll end up in the thread you're looking for!

Strange indeed... But it will also take you to the thread you're looking for!

Hmm... yes, except it shouldn't be the same thread (the subject is the same, but there is no reference to the old thread).

Perhaps it only gives the last matching article of the thread.

Vincent,

I originally posed the problem. I've had an interest in this problem for some years.

I've searched up to 6 adders and n=1 billion. The first value of n that you can't get with 6 adders is 171398453.

As far as I know, there are two ways to exactly search the space. Dynamic programming is the first and most obvious. Initially it looks like polynomial time but you'll find that there is a subtle flaw in the dynamic programming solution that most people come up with, to do with sharing of subexpressions.

The more efficient approach is (believe it or not) to explore all the topologies of N adders and plug in all the shifts. You can prove that you only need 1 shift per adder, but there's still a huge number of combinations.

To explore 6 adders, I ran a threaded parallel executable on a 4-processor ultrasparc for 2 weeks.

If you have a better way of exploring the space, I'd be interested in hearing it.

Regards, Ross Donelly.

Thanks.

Yes, this is my current approach. I've currently written a program to generate DAGs representing a combination of N adders (with no useless adder), but there may still remain isomorphic DAGs. I don't know if this program could be much improved. FYI, for 5 adders, I get 194 DAGs, and for 6 adders, I get 1478 DAGs. Do you know an efficient algorithm for this?

Hmm... It would be quite difficult to find a result for 7 adders.

Well, I have a method that would explore only some particular topologies using the distributivity and the associativity of the multiplication. But of course the corresponding values are not the optimal ones: I got the following table for the smallest values that need N adders with this approach:

4 683 5 7339 6 175901 7 11199517

But it would be interesting to compare the average values of the cost (depending on the size of the constant)...