With -O2 -mcpu=i686 or newer, gcc uses "imul" for both 100003 and 65599,
rather than shifts and adds.
There may be a few people who care about some other processor, but I
wouldn't listen to them. (the only non-x86 CPU I program for on a weekly
basis doesn't have hardware multiply, but it's also much too small for