>> to accelerate division

[fordge]

we usually use <<n as a cheaper option to multiplication when its
factor of
2^n right,

even for non 2^n say

ix24 ==> ix(16+8) ==> (i<<4)+(i<<3)

similarly divison 2^n is >>n

doubt is there a cheaper option to i/24 ==> i/(16+8) ==> ????????
or i/72.....

also are there other faster arithmetic alternatives like the >> and <<
for
div n multiplication
fORDGE

[Mysidia]

Well, you could reduce it somewhat, but the divide wants to stick
around...

i/(24) == i/(6*4) == i/6/4 == i/(3*2)/4 == i/3/2/2/2
== (i / 3) >> 1 >> 1 >> 1

i / 24 == (i >> 3) / 3

If you can figure out a way of expressing i / 3 as bit shifts,
then you have an improvement.
But I am doubting there is a way, without doing the full divide.

-Jh

[James McIninch]

<posted & mailed>

Keep in mind that your compiler will probably turn all of these statements
into the same code:

i>>1;
i/=2;
i=i/2;

.... so you wouldn't expect any performance difference. Likewise, the
following should all generate exactly the same code:

i<<1;
i*=2;
i=i*2;

Also, depending on the hardware, 'i * 24' may be faster than '(i<<4) +
(i<<3)' ... assuming that your machine didn't optimize the code into the
same thing...

fo****@gmail.com wrote:

we usually use <<n as a cheaper option to multiplication when its
factor of
2^n right,

even for non 2^n say

ix24 ==> ix(16+8) ==> (i<<4)+(i<<3)

similarly divison 2^n is >>n

doubt is there a cheaper option to i/24 ==> i/(16+8) ==> ????????
or i/72.....

also are there other faster arithmetic alternatives like the >> and <<
for
div n multiplication
fORDGE

--
Remove '.nospam' from e-mail address to reply by e-mail

[Ben Pfaff]

"Mysidia" <my*****@gmail.com> writes:

If you can figure out a way of expressing i / 3 as bit shifts,
then you have an improvement.
But I am doubting there is a way, without doing the full divide.

You can implement i/3 as a multiplication followed by a bit
shift. In some cases this may be an improvement. However, if it
is an improvement, your compiler may already be doing it for you.

See chapter 10 of Warren, Jr., _Hacker's Delight_, Addison-Wesley
2003, ISBN 0-201-91465-4, for details.
--
Ben Pfaff
email: bl*@cs.stanford.edu
web: http://benpfaff.org

[Andrey Tarasevich]

fo****@gmail.com wrote:

we usually use <<n as a cheaper option to multiplication when its
factor of
2^n right,

even for non 2^n say

ix24 ==> ix(16+8) ==> (i<<4)+(i<<3)

similarly divison 2^n is >>n
This is waste of characters and your time, let alone the reduced
readability of the code. In situations when the multiplier is a
compile-time constant, the compiler will do this optimization much
better than you will ever be able to. On many modern platforms in many
cases shifts are not the most efficient way to implement multiplication.
By obscuring your code with these shifts you are more likely to confuse
the compiler and impede real optimizations. The compiler has to be able
de-optimize your '(i << 4) + (i << 3)' into normal 'i * 24' and then
re-optimize it efficiently. Some compilers might not be able to do that,
leaving you with lousy shifts instead of really efficient multiplication.
also are there other faster arithmetic alternatives like the >> and <<
for
div n multiplication

What is 'div n multiplication'? Anyway, the fastest way to multiply 'i'
by 24 is to write 'i * 24'.

--
Best regards,
Andrey Tarasevich

[Andrey Tarasevich]

James McIninch wrote:

Keep in mind that your compiler will probably turn all of these statements
into the same code:

i>>1;
i/=2;
i=i/2;
Highly unlikely in case of signed 'i'. In general case shift and
division mean two completely different things for signed values.
Also, depending on the hardware, 'i * 24' may be faster than '(i<<4) +
(i<<3)' ... assuming that your machine didn't optimize the code into the
same thing...

Strictly speaking, it depends on the compiler, not on the hardware.
There's no direct correspondence between C operators and machine
language commands, i.e. the notion of "hardware-defined speed" is not
directly applicable to C operators.

--
Best regards,
Andrey Tarasevich

[E. Robert Tisdale]

James McIninch wrote:

<posted & mailed>

Keep in mind that your compiler will probably turn all of these statements
into the same code:

i>>1;
i/=2;
i=i/2;
Let's try that.
cat f0.c int f(int i) {
return i >> 1;
}
gcc -Wall -std=c99 -pedantic -O2 -S f0.c
cat f1.c int f(int i) {
return i >>= 1;
}
gcc -Wall -std=c99 -pedantic -O2 -S f1.c
cat f2.c int f(int i) {
return i/2;
}
gcc -Wall -std=c99 -pedantic -O2 -S f2.c
cat f3.c int f(int i) {
return i /= 2;
}
gcc -Wall -std=c99 -pedantic -O2 -S f3.c
cat f4.c int f(int i) {
return i = i/2;
}
gcc -Wall -std=c99 -pedantic -O2 -S f4.c
diff f0.s f1.s 1c1
< .file "f0.c"
--- .file "f1.c"
diff f1.s f2.s 1c1
< .file "f1.c"
--- .file "f2.c" 10a11,13 movl %eax, %edx
shrl $31, %edx
addl %edx, %eax
diff f2.s f3.s 1c1
< .file "f2.c"
--- .file "f3.c"
diff f3.s f4.s 1c1
< .file "f3.c"
--- .file "f4.c"

[Charlie Gordon]

"E. Robert Tisdale" <E.**************@jpl.nasa.gov> wrote in message
news:cp**********@nntp1.jpl.nasa.gov...

James McIninch wrote:

<posted & mailed>

Keep in mind that your compiler will probably turn all of these statements
into the same code:

i>>1;
i/=2;
i=i/2;
Let's try that. [...]

of all 4 tests, only 2 really make sense.

int fshift(int i) { return i >> 1; }
int fdiv(int i) { return i / 2; }

gcc optimizes i / 2 using shifts, but generates different code from i >> 1:

namely on intel chips, signed division by 2 is equivalent to :

(i + (i < 0)) >> 1

> cat f0.c int f(int i) {
return i >> 1;
}

> gcc -Wall -std=c99 -pedantic -O2 -S f0.c
> cat f1.c

int f(int i) {
return i >>= 1;
}

No difference in semanticsObviously

> gcc -Wall -std=c99 -pedantic -O2 -S f1.c
> cat f2.c

int f(int i) {
return i/2;
}

> gcc -Wall -std=c99 -pedantic -O2 -S f2.c
> cat f3.c

int f(int i) {
return i /= 2;
}

> gcc -Wall -std=c99 -pedantic -O2 -S f3.c
> cat f4.c

int f(int i) {
return i = i/2;
}

> gcc -Wall -std=c99 -pedantic -O2 -S f4.c
> diff f0.s f1.s

1c1
< .file "f0.c"
---

> .file "f1.c"
> diff f1.s f2.s

1c1
< .file "f1.c"
---

> .file "f2.c"

10a11,13

> movl %eax, %edx
> shrl $31, %edx
> addl %edx, %eax
> diff f2.s f3.s

1c1
< .file "f2.c"
---

> .file "f3.c"
> diff f3.s f4.s

1c1
< .file "f3.c"
---

> .file "f4.c"

[Charlie Gordon]

"Charlie Gordon" <ne**@chqrlie.org> wrote in message
news:cp**********@reader1.imaginet.fr...

"E. Robert Tisdale" <E.**************@jpl.nasa.gov> wrote in message
news:cp**********@nntp1.jpl.nasa.gov...

James McIninch wrote:

<posted & mailed>

Keep in mind that your compiler will probably turn all of these statements
into the same code:

i>>1;
i/=2;
i=i/2;

Let's try that. [...]

of all 4 tests, only 2 really make sense.

int fshift(int i) { return i >> 1; }
int fdiv(int i) { return i / 2; }

gcc optimizes i / 2 using shifts, but generates different code from i >> 1:

namely on intel chips, signed division by 2 is equivalent to :

(i + (i < 0)) >> 1

Sorry for not clipping the rest of the quote, this post was submitted
erroneously by a keyboard shortcut I wasn't aware of.

i / 2 <=> (i + (i < 0)) >> 1 assuming a ton of things that are mostly true
on the ia86 family :
- 2's complement
- signed division truncates toward 0
- signed shift duplicates the sign bit...

However, given this expression, gcc will generate a test and 2 JMPs.
You have to be very verbose to make it generate the same code :

return (i + (signed)((unsigned)i >> ((sizeof(i) * CHAR_BIT - 1)))) >> 1;

or the alternative:

return (i + ((i >> ((sizeof(i) * CHAR_BIT - 1))) & 1)) >> 1;

And still this assumes i is of type int. The expression must change for other
signed integral types.

Furthermore, for other simple divisions by a power of 2, gcc will generate a
test and 2 JMPs for the / operator.
But will generate linear (and potentially faster) code for these convoluted
expressions :

dividing by 4:

return (i + ((i >> ((sizeof(i) * CHAR_BIT - 1))) & 3)) >> 2;

dividing by 8:

return (i + ((i >> ((sizeof(i) * CHAR_BIT - 1))) & 7)) >> 3;

etc.

As a conclusion, it is more important to write readable code (using / and %) and
give the compiler every opportunity for optimisation by using or casting to
unsigned types. Yet this is a risky game:
- it is vain to rely on any particular compiler behaviour.
- even hand optimized code may prove slower.
- unsigned types have its own lot of problems.
- integer arithmetic is not necessarily 2's complement.
- >> has implementation defined semantics (can we list architectures where it
differs from ia86 ?).
- the java unsigned shift operator >>> was not added to the C standard (beats me
why).
- casting a signed arithmetic type to its unsigned version cannot be done
generically, reliably and portably.
- casting an unsigned arithmetic type to its signed version cannot be done
generically at all.

Such a can of worms!

--
Chqrlie.

[David Kastrup]

James McIninch <ja*******************@comcast.net> writes:

<posted & mailed>

Keep in mind that your compiler will probably turn all of these statements
into the same code:

i>>1;
i/=2;
i=i/2;
It better not. The first should do nothing (apart from which >>
should usually round towards negative infinity while / commonly rounds
towards zero).
... so you wouldn't expect any performance difference. Likewise, the
following should all generate exactly the same code:

i<<1;
i*=2;
i=i*2;

Again, the first should do nothing.
fo****@gmail.com wrote:

we usually use <<n as a cheaper option to multiplication when its
factor of
2^n right,

If your optimizer does not even do that, get another compiler.

--
David Kastrup, Kriemhildstr. 15, 44793 Bochum

[David Kastrup]

Ben Pfaff <bl*@cs.stanford.edu> writes:

"Mysidia" <my*****@gmail.com> writes:

If you can figure out a way of expressing i / 3 as bit shifts,
then you have an improvement.
But I am doubting there is a way, without doing the full divide.

You can implement i/3 as a multiplication followed by a bit
shift. In some cases this may be an improvement. However, if it
is an improvement, your compiler may already be doing it for you.

Why not just write

i *= 2863311531;

As long as i is multiple of 3, this will work fine on 32bit machines.

--
David Kastrup, Kriemhildstr. 15, 44793 Bochum

[Ben Pfaff]

David Kastrup <da*@gnu.org> writes:

Ben Pfaff <bl*@cs.stanford.edu> writes:

"Mysidia" <my*****@gmail.com> writes:

If you can figure out a way of expressing i / 3 as bit shifts,
then you have an improvement.
But I am doubting there is a way, without doing the full divide.

You can implement i/3 as a multiplication followed by a bit
shift. In some cases this may be an improvement. However, if it
is an improvement, your compiler may already be doing it for you.

Why not just write

i *= 2863311531;

As long as i is multiple of 3, this will work fine on 32bit machines.

Because it is hideously obfuscatory and nonportable? It is a
much better choice to get a compiler with a smart optimizer.
--
"You call this a *C* question? What the hell are you smoking?" --Kaz

[Nils O. Selåsdal]

fo****@gmail.com wrote:

we usually use <<n as a cheaper option to multiplication when its
factor of
2^n right,

No. You leave this to the compiler.
Don't obscure things like this unless you have determined
it to be a bottleneck. A sane compiler will optimize this
in the best way anyways.

[Lawrence Kirby]

On Wed, 08 Dec 2004 09:09:03 +0100, Charlie Gordon wrote:

....

- the java unsigned shift operator >>> was not added to the C
standard (beats me why).

In C you can use >> on an unsigned integer type to achieve this. Java
doesn't have unsigned integer types so requires a different approach.

Lawrence

[Richard Bos]

David Kastrup <da*@gnu.org> wrote:

Ben Pfaff <bl*@cs.stanford.edu> writes:

You can implement i/3 as a multiplication followed by a bit
shift. In some cases this may be an improvement. However, if it
is an improvement, your compiler may already be doing it for you.

Why not just write

i *= 2863311531;

As long as i is multiple of 3, this will work fine on 32bit machines.

Not if i is a signed int, it won't - at least, it's not guaranteed to.
Signed overflow has undefined behaviour.

Richard

[Chris Croughton]

On Tue, 07 Dec 2004 19:58:46 -0800, Andrey Tarasevich
<an**************@hotmail.com> wrote:

This is waste of characters and your time, let alone the reduced
readability of the code. In situations when the multiplier is a
compile-time constant, the compiler will do this optimization much
better than you will ever be able to. On many modern platforms in many
cases shifts are not the most efficient way to implement multiplication.
By obscuring your code with these shifts you are more likely to confuse
the compiler and impede real optimizations. The compiler has to be able
de-optimize your '(i << 4) + (i << 3)' into normal 'i * 24' and then
re-optimize it efficiently. Some compilers might not be able to do that,
leaving you with lousy shifts instead of really efficient multiplication.

Please get my cow-orkers to understand that, they criticise my code for
using "x * 2" and say that it should be "x << 1", I've had to fight to
get sensible things through. (Yes, there are times when using shifts is
clearer, like with bit field operations, but when it's an arithmetic
operation like finding the mean of two numbers it is nonobvious to use a
shift.)

Chris C

[jacob navia]

fo****@gmail.com wrote:

we usually use <<n as a cheaper option to multiplication when its
factor of
2^n right,

even for non 2^n say

ix24 ==> ix(16+8) ==> (i<<4)+(i<<3)

similarly divison 2^n is >>n

doubt is there a cheaper option to i/24 ==> i/(16+8) ==> ????????
or i/72.....

also are there other faster arithmetic alternatives like the >> and <<
for
div n multiplication
fORDGE

To divide by 24 the lcc-win32 compiler emits
movl 8(%ebp),%eax ; argument in eax
movl $715827883,%edx
movl %eax,%ecx ; copy eax since it will be destroyed
imull %edx ; multiply by the constant above
sarl $2,%edx ; shift result in eax:edx
sarl $31,%ecx
subl %ecx,%edx ; adjust
movl %edx,%eax ; result in edx moved to eax

You see?
No division at all.

In many cases it is not worth to try to outsmart the compiler in C
for this low level stuff...

And in general, optimizations for this level can't be done in C,
since it is a high level language that doesn't give you any access
to the registers of the machine anyway.

References:

This is the algorithm proposed by

Torbjorn Granlund and Peter L. Montgomery, "Division by Invariant
Integers using Multiplication", in Proceedings of the SIGPLAN PLDI'94
Conference, June 1994.

[Dave]

Chris Croughton wrote:

Please get my cow-orkers to understand that, they criticise my code for
using "x * 2" and say that it should be "x << 1", I've had to fight to
get sensible things through. (Yes, there are times when using shifts is
clearer, like with bit field operations, but when it's an arithmetic
operation like finding the mean of two numbers it is nonobvious to use a
shift.)

Chris C

Simply get them to show you experimental evidence that one is quicker
than the other. Or show them evidence that there is no difference. Or
compile via assembly and see what the compiler does with those two
statements.

Sounds to me like your organisation is placing an inappropriate value on
premature optimisation.

[Xenos]

"David Kastrup" <da*@gnu.org> wrote in message
news:x5************@lola.goethe.zz...

James McIninch <ja*******************@comcast.net> writes:

<posted & mailed>

Keep in mind that your compiler will probably turn all of these statements into the same code:

i>>1;
i/=2;
i=i/2;
It better not. The first should do nothing (apart from which >>
should usually round towards negative infinity while / commonly rounds
towards zero).

Any why should it do nothing?

... so you wouldn't expect any performance difference. Likewise, the
following should all generate exactly the same code:

i<<1;
i*=2;
i=i*2;

Again, the first should do nothing.

Again?

[Xenos]

"Andrey Tarasevich" <an**************@hotmail.com> wrote in message
news:10*************@news.supernews.com...

James McIninch wrote:

Keep in mind that your compiler will probably turn all of these statements into the same code:

i>>1;
i/=2;
i=i/2;

Highly unlikely in case of signed 'i'. In general case shift and
division mean two completely different things for signed values.

Not unlikely. There are a lot of processors that have signed preserved or
arithmetic shift operations.

[Michael Mair]

Xenos wrote:

"David Kastrup" <da*@gnu.org> wrote in message
news:x5************@lola.goethe.zz...

James McIninch <ja*******************@comcast.net> writes:

<posted & mailed>

Keep in mind that your compiler will probably turn all of these
statements
into the same code:

i>>1;
i/=2;
i=i/2;

It better not. The first should do nothing (apart from which >>
should usually round towards negative infinity while / commonly rounds
towards zero).

Any why should it do nothing?

Well, it does something -- but that has no effect for the rest
of the program (and probably will get optimised away), whereas
i >>= 1;
has an effect for i != 0.

... so you wouldn't expect any performance difference. Likewise, the
following should all generate exactly the same code:

i<<1;
i*=2;
i=i*2;

Again, the first should do nothing.

Again?

Indeed.
Cheers
Michael
--
E-Mail: Mine is a gmx dot de address.

[CBFalconer]

Dave wrote:

Chris Croughton wrote:

Please get my cow-orkers to understand that, they criticise my
code for using "x * 2" and say that it should be "x << 1", I've
had to fight to get sensible things through. (Yes, there are
times when using shifts is clearer, like with bit field operations,
but when it's an arithmetic operation like finding the mean of two
numbers it is nonobvious to use a shift.)

Simply get them to show you experimental evidence that one is
quicker than the other. Or show them evidence that there is no
difference. Or compile via assembly and see what the compiler
does with those two statements.

Sounds to me like your organisation is placing an inappropriate
value on premature optimisation.

Or run your and their code through a profiler, to demonstrate the
non-existent efficiency improvements, and the cost of bugs
introduced by obscure coding.

What is your firm? I may want to sell its stock short.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[Chris Croughton]

On Wed, 08 Dec 2004 12:59:29 +0000, Dave
<re*************@elcaro.moc> wrote:

Chris Croughton wrote:

Please get my cow-orkers to understand that, they criticise my code for
using "x * 2" and say that it should be "x << 1", I've had to fight to
get sensible things through. (Yes, there are times when using shifts is
clearer, like with bit field operations, but when it's an arithmetic
operation like finding the mean of two numbers it is nonobvious to use a
shift.)
Simply get them to show you experimental evidence that one is quicker
than the other. Or show them evidence that there is no difference. Or
compile via assembly and see what the compiler does with those two
statements.

On all possible compilers and output processors (that doesn't mean
'all', only all those which might be used for compiling our code)? They
say "Coding standards"...
Sounds to me like your organisation is placing an inappropriate value on
premature optimisation.

Yup. And there's so much other inefficiency that it makes no difference
at all...

Chris C

[Chris Croughton]

[ shift versus multiply/divide ]

On Wed, 08 Dec 2004 15:26:40 GMT, CBFalconer
<cb********@yahoo.com> wrote:

Or run your and their code through a profiler, to demonstrate the
non-existent efficiency improvements, and the cost of bugs
introduced by obscure coding.
Not possible on the targets (embedded processors). But showing that the
code generated is the same (for various compilers/targets) doesn't seem
to convince them.
What is your firm? I may want to sell its stock short.

I'm taking the Fifth <g>. But I doubt you have any stock of theirs
anyway. I haven't either...

Chris C

[Andrey Tarasevich]

Xenos wrote:

>
> Keep in mind that your compiler will probably turn all of these statements > into the same code:
>
> i>>1;
> i/=2;
> i=i/2;

Highly unlikely in case of signed 'i'. In general case shift and
division mean two completely different things for signed values.

Not unlikely. There are a lot of processors that have signed preserved or
arithmetic shift operations.

That's still not enough. It is already been mentioned that
sign-preserving shift implements "modulo-preserving" division (for
example, -5 >> 1 gives -3) while regular '/' implements a "round to
zero" division, as required by C99 and recommended by C89/C90 and C++
standards (for example, -5/2 gives -2). That's what I meant in my
previous message.

--
Best regards,
Andrey Tarasevich

[Thomas G. Marshall]

Chris Croughton coughed up:

On Tue, 07 Dec 2004 19:58:46 -0800, Andrey Tarasevich
<an**************@hotmail.com> wrote:

This is waste of characters and your time, let alone the reduced
readability of the code. In situations when the multiplier is a
compile-time constant, the compiler will do this optimization much
better than you will ever be able to. On many modern platforms in
many cases shifts are not the most efficient way to implement
multiplication. By obscuring your code with these shifts you are
more likely to confuse the compiler and impede real optimizations.
The compiler has to be able de-optimize your '(i << 4) + (i << 3)'
into normal 'i * 24' and then re-optimize it efficiently. Some
compilers might not be able to do that, leaving you with lousy
shifts instead of really efficient multiplication.

Please get my cow-orkers to understand that, they criticise my code
for using "x * 2" and say that it should be "x << 1", I've had to
fight to get sensible things through. (Yes, there are times when
using shifts is clearer, like with bit field operations, but when
it's an arithmetic operation like finding the mean of two numbers it
is nonobvious to use a shift.)

Absolutely correct.

HOWEVER....

Not absolutely correct for more bottom-dwelling platforms, like, oh, small 8
bit chips, etc.

This discussion on accomplishing division with shifts is a good one!

--
http://www.allexperts.com is a nifty way to get an answer to just about
/anything/.

[Chris Croughton]

On Wed, 08 Dec 2004 19:19:23 GMT, Thomas G. Marshall
<tg****************@replacetextwithnumber.hotmail. com> wrote:

Chris Croughton coughed up:

Please get my cow-orkers to understand that, they criticise my code
for using "x * 2" and say that it should be "x << 1", I've had to
fight to get sensible things through. (Yes, there are times when
using shifts is clearer, like with bit field operations, but when
it's an arithmetic operation like finding the mean of two numbers it
is nonobvious to use a shift.)
Absolutely correct.

HOWEVER....

Not absolutely correct for more bottom-dwelling platforms, like, oh, small 8
bit chips, etc.

Which, I suspect, is what they are thinking of. However any modern C
compiler which targets those chips should optimise correctly anyway (and
indeed optimisation is likely to be even more essential for those
platforms). Indeed, such platforms often don't even have a multiply
instruction and more of them don't have a divide (I spent many years
working on 8080, Z80, 6803, H8 and similar processors).
This discussion on accomplishing division with shifts is a good one!

Indeed, I hadn't heard of the "multiply by large number and adjust"
algorithms before (and even after reading some articles on them I'm not
convinced).

Chris C

[Andrey Tarasevich]

Thomas G. Marshall wrote:

...

This is waste of characters and your time, let alone the reduced
readability of the code. In situations when the multiplier is a
compile-time constant, the compiler will do this optimization much
better than you will ever be able to. On many modern platforms in
many cases shifts are not the most efficient way to implement
multiplication. By obscuring your code with these shifts you are
more likely to confuse the compiler and impede real optimizations.
The compiler has to be able de-optimize your '(i << 4) + (i << 3)'
into normal 'i * 24' and then re-optimize it efficiently. Some
compilers might not be able to do that, leaving you with lousy
shifts instead of really efficient multiplication.

Please get my cow-orkers to understand that, they criticise my code
for using "x * 2" and say that it should be "x << 1", I've had to
fight to get sensible things through. (Yes, there are times when
using shifts is clearer, like with bit field operations, but when
it's an arithmetic operation like finding the mean of two numbers it
is nonobvious to use a shift.)

Absolutely correct.

HOWEVER....

Not absolutely correct for more bottom-dwelling platforms, like, oh, small 8
bit chips, etc.

If by "platforms" you really mean "implementations", i.e. C compilers
available for that hardware (which is actually what the word "platform"
really means in C lingo), then I can agree with you. A separate question
in this case would be whether better implementations are available on
these platforms.

However, the fact that you mention 8-bitness of chips suggests that
under "platforms" you really understand the actual hardware [platforms].
In this case I disagree. Bad performance of explicit
multiplication/division in comparison with shifts is purely
implementation's fault. Hardware doesn't define anything here. There's
nothing that forbids the existence of a compiler that is able to
implement multiplication/division in the most efficient way for this
bottom-dwelling hardware platform.

--
Best regards,
Andrey Tarasevich

[Keith Thompson]

"Xenos" <do**********@spamhate.com> writes:

"David Kastrup" <da*@gnu.org> wrote in message
news:x5************@lola.goethe.zz...

James McIninch <ja*******************@comcast.net> writes:

> <posted & mailed>
>
> Keep in mind that your compiler will probably turn all of these statements > into the same code:
>
> i>>1;
> i/=2;
> i=i/2;

It better not. The first should do nothing (apart from which >>
should usually round towards negative infinity while / commonly rounds
towards zero).

Any why should it do nothing?

[...]

Because it has no side effects (it doesn't modify i), and the result
of the expression isn't used. Perhaps you're thinking of
i >>= 1;

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Christian Bau]

In article <sl******************@ccserver.keris.net>,
Chris Croughton <ch***@keristor.net> wrote:

On Tue, 07 Dec 2004 19:58:46 -0800, Andrey Tarasevich
<an**************@hotmail.com> wrote:

This is waste of characters and your time, let alone the reduced
readability of the code. In situations when the multiplier is a
compile-time constant, the compiler will do this optimization much
better than you will ever be able to. On many modern platforms in many
cases shifts are not the most efficient way to implement multiplication.
By obscuring your code with these shifts you are more likely to confuse
the compiler and impede real optimizations. The compiler has to be able
de-optimize your '(i << 4) + (i << 3)' into normal 'i * 24' and then
re-optimize it efficiently. Some compilers might not be able to do that,
leaving you with lousy shifts instead of really efficient multiplication.

Please get my cow-orkers to understand that, they criticise my code for
using "x * 2" and say that it should be "x << 1", I've had to fight to
get sensible things through. (Yes, there are times when using shifts is
clearer, like with bit field operations, but when it's an arithmetic
operation like finding the mean of two numbers it is nonobvious to use a
shift.)

Tell them they shouldn't try to save nanoseconds, they should try to
save microseconds :-)

If anyone asks you to replace x*2 with x<<1 because it is faster, just
ask them if they profiled it. If they haven't profiled it, write x*2.

[Mark McIntyre]

On 7 Dec 2004 17:44:33 -0800, in comp.lang.c , fo****@gmail.com wrote:

we usually use <<n as a cheaper option to multiplication when its
factor of 2^n right,

We do, but its quite probable that these days, we're wrong. If your
compiler isn't capable of doing this optimization for you, its a poor
compiler.
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>

----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

[E. Robert Tisdale]

James McIninch wrote:

Also, depending on the hardware,
'i * 24' may be faster than '(i<<4) + (i<<3)' ... assuming that
your machine didn't optimize the code into the same thing... cat f5.c int f(int i) {
return i*24;
}
gcc -Wall -std=c99 -pedantic -S f5.c
cat f6.c int f(int i) {
return (i << 4) + (i << 3);
}
gcc -Wall -std=c99 -pedantic -S f6.c
diff --side-by-side --width=68 f5.s f6.s .file "f5.c" | .file "f6.c"
.text .text
.globl f .globl f
.type f, @function .type f, @function
f: f:
pushl %ebp pushl %ebp
movl %esp, %ebp movl %esp, %ebp movl 8(%ebp), %eax
sall $4, %eax

movl 8(%ebp), %edx movl 8(%ebp), %edx
movl %edx, %eax | sall $3, %edx
addl %eax, %eax <
addl %edx, %eax addl %edx, %eax
sall $3, %eax <
popl %ebp popl %ebp
ret ret
.size f, .-f .size f, .-f
.section .note .section .note
.ident "GCC: (GNU) 3 .ident "GCC: (GNU) 3

[Flash Gordon]

On Wed, 8 Dec 2004 16:51:05 +0000
Chris Croughton <ch***@keristor.net> wrote:

[ shift versus multiply/divide ]

On Wed, 08 Dec 2004 15:26:40 GMT, CBFalconer
<cb********@yahoo.com> wrote:

Or run your and their code through a profiler, to demonstrate the
non-existent efficiency improvements, and the cost of bugs
introduced by obscure coding.

Not possible on the targets (embedded processors). But showing that
the code generated is the same (for various compilers/targets) doesn't
seem to convince them.

If seeing that the generated code is the same does not convince them
then it is probably a lost cause, so I suggest you start looking for a
job somewhere better.

However, you might want to point out that with a right shift for
division they could get rather unexpected results with negative numbers.

What is your firm? I may want to sell its stock short.

I'm taking the Fifth <g>. But I doubt you have any stock of theirs
anyway. I haven't either...

Possibly a good idea.
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.

[Stephen Sprunk]

<fo****@gmail.com> wrote in message
news:11**********************@z14g2000cwz.googlegr oups.com...

we usually use <<n as a cheaper option to multiplication when its
factor of
2^n right,

even for non 2^n say

ix24 ==> ix(16+8) ==> (i<<4)+(i<<3)

similarly divison 2^n is >>n

doubt is there a cheaper option to i/24 ==> i/(16+8) ==> ????????
or i/72.....

also are there other faster arithmetic alternatives like the >> and <<
for
div n multiplication

If you have a reasonably good optimizing compiler, it should do this
"strength reduction" for you. Keep your original intent (the division) in
the code unless you're sure you're using a broken compiler _and_ you'd done
some profiling to know it'll be worth the risks.

S

--
Stephen Sprunk "God does not play dice." --Albert Einstein
CCIE #3723 "God is an inveterate gambler, and He throws the
K5SSS dice at every possible opportunity." --Stephen Hawking

[Andrey Tarasevich]

Andrey Tarasevich wrote:

> Keep in mind that your compiler will probably turn all of these statements

> into the same code:
>
> i>>1;
> i/=2;
> i=i/2;

Highly unlikely in case of signed 'i'. In general case shift and
division mean two completely different things for signed values.

Not unlikely. There are a lot of processors that have signed preserved or
arithmetic shift operations.

That's still not enough. It is already been mentioned that
sign-preserving shift implements "modulo-preserving" division (for
example, -5 >> 1 gives -3)

It is worth noting that the above applies to 2's-complement platforms.
while regular '/' implements a "round to
zero" division, as required by C99 and recommended by C89/C90 and C++
standards (for example, -5/2 gives -2). That's what I meant in my
previous message.

--
Best regards,
Andrey Tarasevich

[Thomas G. Marshall]

Chris Croughton coughed up:

On Tue, 07 Dec 2004 19:58:46 -0800, Andrey Tarasevich
<an**************@hotmail.com> wrote:

This is waste of characters and your time, let alone the reduced
readability of the code. In situations when the multiplier is a
compile-time constant, the compiler will do this optimization much
better than you will ever be able to. On many modern platforms in
many cases shifts are not the most efficient way to implement
multiplication. By obscuring your code with these shifts you are
more likely to confuse the compiler and impede real optimizations.
The compiler has to be able de-optimize your '(i << 4) + (i << 3)'
into normal 'i * 24' and then re-optimize it efficiently. Some
compilers might not be able to do that, leaving you with lousy
shifts instead of really efficient multiplication.

Please get my cow-orkers to understand that, they criticise my code
for using "x * 2" and say that it should be "x << 1", I've had to
fight to get sensible things through. (Yes, there are times when
using shifts is clearer, like with bit field operations, but when
it's an arithmetic operation like finding the mean of two numbers it
is nonobvious to use a shift.)

Absolutely correct.

HOWEVER....

Not absolutely correct for more bottom-dwelling platforms, like, oh, small 8
bit chips, etc.

This discussion on accomplishing division with shifts is a good one!

PS. It is bad form to set followups to limit the scope of a crosspost
without announcing that you've done so.

--
http://www.allexperts.com is a nifty way to get an answer to just about
anything.

[Thomas G. Marshall]

Andrey Tarasevich coughed up:

Thomas G. Marshall wrote:

...
This is waste of characters and your time, let alone the reduced
readability of the code. In situations when the multiplier is a
compile-time constant, the compiler will do this optimization much
better than you will ever be able to. On many modern platforms in
many cases shifts are not the most efficient way to implement
multiplication. By obscuring your code with these shifts you are
more likely to confuse the compiler and impede real optimizations.
The compiler has to be able de-optimize your '(i << 4) + (i << 3)'
into normal 'i * 24' and then re-optimize it efficiently. Some
compilers might not be able to do that, leaving you with lousy
shifts instead of really efficient multiplication.

Please get my cow-orkers to understand that, they criticise my code
for using "x * 2" and say that it should be "x << 1", I've had to
fight to get sensible things through. (Yes, there are times when
using shifts is clearer, like with bit field operations, but when
it's an arithmetic operation like finding the mean of two numbers it
is nonobvious to use a shift.)

Absolutely correct.

HOWEVER....

Not absolutely correct for more bottom-dwelling platforms, like, oh,
small 8 bit chips, etc.

If by "platforms" you really mean "implementations", i.e. C compilers
available for that hardware (which is actually what the word
"platform" really means in C lingo), then I can agree with you. A
separate question in this case would be whether better
implementations are available on these platforms.

However, the fact that you mention 8-bitness of chips suggests that
under "platforms" you really understand the actual hardware
[platforms]. In this case I disagree. Bad performance of explicit
multiplication/division in comparison with shifts is purely
implementation's fault. Hardware doesn't define anything here. There's
nothing that forbids the existence of a compiler that is able to
implement multiplication/division in the most efficient way for this
bottom-dwelling hardware platform.

I suppose you're right. I should have been more clear--this is what I meant
to say, being all wordy smurdy :) :

Learning bit shifts combinations for non power of 2 arithmetic is very
useful, and a strong understanding of it is desirable outside of any
particular language, and required in assembler on low-frills chips that know
neither how to multiply nor divide.

My 6502 and z80 background brings to mind all kinds of unavoidable
mathematical hoohah....
--
It'salwaysbeenmygoalinlifetocreateasignaturethaten dedwiththeword"blarphoogy"
..

[Villy Kruse]

On Wed, 08 Dec 2004 22:38:07 +0000,
Mark McIntyre <ma**********@spamcop.net> wrote:

On 7 Dec 2004 17:44:33 -0800, in comp.lang.c , fo****@gmail.com wrote:

we usually use <<n as a cheaper option to multiplication when its
factor of 2^n right,

We do, but its quite probable that these days, we're wrong. If your
compiler isn't capable of doing this optimization for you, its a poor
compiler.

Such pinhole optimization has been common for at least 15 years.
Even multiply by 10 could be optimized as a couple of shifts and add
and this has been implemented by compilers. Perhaps computers these
days have very fast multiply instructions so such optimization would
actualy result in slower code.

Villy

[Charlie Gordon]

"Lawrence Kirby" <lk****@netactive.co.uk> wrote in message
news:pa****************************@netactive.co.u k...

On Wed, 08 Dec 2004 09:09:03 +0100, Charlie Gordon wrote:

...

- the java unsigned shift operator >>> was not added to the C
standard (beats me why).

In C you can use >> on an unsigned integer type to achieve this. Java
doesn't have unsigned integer types so requires a different approach.

You are missing my point.
In order to force unsigned right shift on a signed type, you have to cast the
left operand to the corresponding unsigned type, but this cannot be done without
explicit knowledge of said type. If the type of the left operand later changes
to a different size (char/short/int/long/long long) the cast may go unnoticed
and will produce incorrect results. There is a similar issue when comparing
signed expressions to unsigned ones : you cannot force signed comparison
semantics without explicit casts where the type must be known and maintained.
There are ways to fix this:
- disallowing unsigned and signed to be used without a size specifier (too
strong)
- changing the semantics of (signed) and (unsigned) casts to only convert
between compatible types, not assuming int size.
- adding extra operators such as java's unsigned right shift operator: >>>

--
Chqrlie.

[Charlie Gordon]

"Chris Croughton" <ch***@keristor.net> wrote in message
news:sl******************@ccserver.keris.net...

On Tue, 07 Dec 2004 19:58:46 -0800, Andrey Tarasevich
<an**************@hotmail.com> wrote:

This is waste of characters and your time, let alone the reduced
readability of the code. In situations when the multiplier is a
compile-time constant, the compiler will do this optimization much
better than you will ever be able to. On many modern platforms in many
cases shifts are not the most efficient way to implement multiplication.
By obscuring your code with these shifts you are more likely to confuse
the compiler and impede real optimizations. The compiler has to be able
de-optimize your '(i << 4) + (i << 3)' into normal 'i * 24' and then
re-optimize it efficiently. Some compilers might not be able to do that,
leaving you with lousy shifts instead of really efficient multiplication.

Please get my cow-orkers to understand that, they criticise my code for
using "x * 2" and say that it should be "x << 1", I've had to fight to
get sensible things through. (Yes, there are times when using shifts is
clearer, like with bit field operations, but when it's an arithmetic
operation like finding the mean of two numbers it is nonobvious to use a
shift.)

Here is THE solution :
- For the specific example above, where x is a variable, on can use "x + x".
- Using << instead of * is error prone because of precedence issues:
"y + x * 2 + z" is quite different from "y + x << 1 + z".
Using << when thinking multiplication is a good way to create bugs.
A well configured C compiler might emit a warning.
- Last but not least : x << 1 is undefined behaviour for x signed and negative !
Let me quote C99 6.5.7 verse 4:

"The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are
filled with
zeros. If E1 has an unsigned type, the value of the result is E1 x 2^E2, reduced
modulo
one more than the maximum value representable in the result type. If E1 has a
signed
type and nonnegative value, and E1 x 2^E2 is representable in the result type,
then that is
the resulting value; otherwise, the behavior is undefined."

For signed x with a negative value :
x << n is UNDEFINED BEHAVIOUR
the value of x >> n is implementation-defined.

Conclusion: Only use << and >> when dealing with bits on unsigned types.

--
Chqrlie.

[Lawrence Kirby]

On Thu, 09 Dec 2004 13:25:59 +0100, Charlie Gordon wrote:

"Lawrence Kirby" <lk****@netactive.co.uk> wrote in message
news:pa****************************@netactive.co.u k...

On Wed, 08 Dec 2004 09:09:03 +0100, Charlie Gordon wrote:

...

> - the java unsigned shift operator >>> was not added to the C
> standard (beats me why).
In C you can use >> on an unsigned integer type to achieve this. Java
doesn't have unsigned integer types so requires a different approach.

You are missing my point.
In order to force unsigned right shift on a signed type, you have to cast the
left operand to the corresponding unsigned type, but this cannot be done without
explicit knowledge of said type.

If you want unsigned shift semantics it is unclear to me why you would
have the value stored in a signed type in the first place, certainly with
negative values being a possibility. I would tend to consider this a
non-issue (or at least one not important enough to legislate for at
the language level) until I see a counterexample.
If the type of the left operand later changes
to a different size (char/short/int/long/long long) the cast may go unnoticed
and will produce incorrect results. There is a similar issue when comparing
signed expressions to unsigned ones : you cannot force signed comparison
semantics without explicit casts where the type must be known and maintained.
There are ways to fix this:
It is certainly possible for an unsigned short or unsigned char left
operand to promote to an int. However in that case the value must be
preserved i.e. the result of such a promotion will be non-negative and the
shift operation will produce the same result as if unsigned.
- disallowing unsigned and signed to be used without a size specifier (too
strong)
I don't follow.
- changing the semantics of (signed) and (unsigned) casts to only convert
between compatible types, not assuming int size.
Maybe an example would help.
- adding extra operators such as java's unsigned right shift operator: >>>

Again, an example of where this works where C's existing types and
operators don't would be helpful.

Lawrence