Multiply by a constant --> shift-and-adds algorithm?

>> Do you have examples? My version (and it is optimal) runs in
>> couple of seconds for _ALL_ 32K numbers (executed in a loop from
>> 1 to 32000, total time). One hour per constant seems uncomprehensible...


Remember that there are more than 32K "numbers". Lots of compilers
are targeting 32 and 64 bit machines and, if the compiler writers
aren't careful (i.e., if they don't review the literature), they can
make a mistake and chew up lots of compile time.


>And even if it *did* take a bit of time, you'd only do this once: you
>can then set up a static lookup table for each constant, and the
>optimizer can do a simple lookup


Better use a hash table -- don't want to keep complete records for all
the 64-bit integers.


>For instance, as far back as 1985, HP's optimizer (and assembler, for
>that matter) used to have a lookup table for all constants upto 1037


The usual approach (read the literature!) is to have a general
heuristic augmented by an exception table that handles cases where the
heuristic falls down. So the first thing to do is check the exception
table. If the answer is there, great. Otherwise, use the heuristic.


Preston Briggs
--

Return to the comp.compilers page.
Search the comp.compilers archives again.