multiplication by 7

[Christian Bau]

Lew Pitcher wrote:

If I was looking for a shifty way, it would be:

((number << 3) - number)

I'd wondered about that: does it have funny overflow behaviour
(ie different to that of 7*number)?[/QUOTE]

For unsigned numbers, it is the same.

For signed numbers, there is a huge range of numbers where (number << 3)
- number will produce overflow and undefined behavior, whereas (number *
7) doesn't.

 

[Micah Cowan]

I'd wondered about that: does it have funny overflow behaviour
(ie different to that of 7*number)?

If the type is int, and number is greater than INT_MAX >> 3 (that
is, INT_MAX/8). Similarly for other signed integer types.

7*number only overflows if number is greater than INT_MAX/7.

-Micah

 

[Flash Gordon]

how does *8 -1 come out

e.g x=(x<<3)-x;

?

Useless for floats of course.

On one system I used to use it would definitely be slower.
x *= 7;
Implemented as
Load x in to product register,
1 clock cycle + read wait states
Multiply by 7, 1 clock cycle
Store result in x,
1 clock cycle + write wait states
Total = 3 clock cycle + read wait states + write wait states
x=(x<<3)-x
Implemented as
Load x in to accumulator shifting 3 bits left,
1 clock cycle + read wait states
Subtract x, 1 clock cycle + read wait states
Store result in x,
1 clock cycle + write wait states
Total = 3 clock cycle + (2 * read wait states) +
write wait states

So you have wasted however many wait states there are on the RAM.

On this processor, when you want to do a multiply by other than a power
of 2 absolutely *nothing* can beet doing a simple multiply when you want
to multiply two integers together because the multiple itself is always
1 clock cycle.

If you are multiplying by a power of two at the point where the number
is loaded from or stored to RAM you can get the shift for free, but the
compiler knows that too.

If the machine code was exactly right for it then there were tricks you
could sometimes pull to speed up sequences of arithmetic, but the entire
expression has to be considered and the code written in assembler since
it can involve doing screwy things like some of your arithmetic in
address registers and some in the ALU, and trying to write C code that
will get the compiler to do that would be rather tricky and
non-portable, so I would (and did) go for assembler for certain highly
time critical operations and had to put multiple comments for each line
of assembler!

I believe HW multipliers are quite common on DSP processors (or they
used to be anyway) because the MAC (Multiply and ACumulate) sequence is
so common.

To put it another way. Whatever micro-optimisation of this kind you do
it will be slower on some implementation.

If you want to check up on the processor in question, here is a link to
the processors manual http://focus.ti.com/lit/ds/symlink/tms320c25.pdf
I'm pretty sure it's a legal copy since it is on the manufacturer's web
site ;-)