449,368 Members | 1,706 Online
Need help? Post your question and get tips & solutions from a community of 449,368 IT Pros & Developers. It's quick & easy.

>> to accelerate division

 P: n/a we usually use < 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 Nov 14 '05 #1
40 Replies

 P: n/a 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 Nov 14 '05 #2

 P: n/a 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 < 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 Nov 14 '05 #3

 P: n/a "Mysidia" 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 Nov 14 '05 #4

 P: n/a fo****@gmail.com wrote: we usually use < 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 Nov 14 '05 #5

 P: n/a 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 Nov 14 '05 #6

 P: n/a 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; 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" Nov 14 '05 #7

 P: n/a "E. Robert Tisdale" wrote in message news:cp**********@nntp1.jpl.nasa.gov... 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; 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" Nov 14 '05 #8

 P: n/a "Charlie Gordon" wrote in message news:cp**********@reader1.imaginet.fr... "E. Robert Tisdale" wrote in message news:cp**********@nntp1.jpl.nasa.gov... 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; 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. Nov 14 '05 #9

 P: n/a James McIninch writes: 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 <

 P: n/a Ben Pfaff writes: "Mysidia" 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 Nov 14 '05 #11

 P: n/a David Kastrup writes: Ben Pfaff writes: "Mysidia" 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 Nov 14 '05 #12

 P: n/a fo****@gmail.com wrote: we usually use <

 P: n/a 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 Nov 14 '05 #14

 P: n/a David Kastrup wrote: Ben Pfaff 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 Nov 14 '05 #15

 P: n/a On Tue, 07 Dec 2004 19:58:46 -0800, Andrey Tarasevich 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 Nov 14 '05 #16

 P: n/a fo****@gmail.com wrote: we usually use < 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. Nov 14 '05 #17

 P: n/a 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. Nov 14 '05 #18

 P: n/a "David Kastrup" wrote in message news:x5************@lola.goethe.zz... James McIninch writes: 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? Nov 14 '05 #19

 P: n/a "Andrey Tarasevich" 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. Nov 14 '05 #20

 P: n/a Xenos wrote: "David Kastrup" wrote in message news:x5************@lola.goethe.zz...James McIninch writes:Keep in mind that your compiler will probably turn all of these statementsinto 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 roundstowards 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, thefollowing 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. Nov 14 '05 #21

 P: n/a 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. USE worldnet address! Nov 14 '05 #22

 P: n/a On Wed, 08 Dec 2004 12:59:29 +0000, 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. 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 Nov 14 '05 #23

 P: n/a [ shift versus multiply/divide ] On Wed, 08 Dec 2004 15:26:40 GMT, CBFalconer 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 . But I doubt you have any stock of theirs anyway. I haven't either... Chris C Nov 14 '05 #24

 P: n/a 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 Nov 14 '05 #25

 P: n/a Chris Croughton coughed up: On Tue, 07 Dec 2004 19:58:46 -0800, Andrey Tarasevich 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/. Nov 14 '05 #26

 P: n/a On Wed, 08 Dec 2004 19:19:23 GMT, Thomas G. Marshall 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 Nov 14 '05 #27

 P: n/a 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 Nov 14 '05 #28

 P: n/a "Xenos" writes: "David Kastrup" wrote in message news:x5************@lola.goethe.zz... James McIninch writes: > > > 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 San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Nov 14 '05 #29

 P: n/a In article , Chris Croughton wrote: On Tue, 07 Dec 2004 19:58:46 -0800, Andrey Tarasevich 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. Nov 14 '05 #30

 P: n/a On 7 Dec 2004 17:44:33 -0800, in comp.lang.c , fo****@gmail.com wrote: we usually use < CLC readme: ----== 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 =---- Nov 14 '05 #31

 P: n/a 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 Nov 14 '05 #32

 P: n/a On Wed, 8 Dec 2004 16:51:05 +0000 Chris Croughton wrote: [ shift versus multiply/divide ] On Wed, 08 Dec 2004 15:26:40 GMT, CBFalconer 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 . 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. Nov 14 '05 #33

 P: n/a wrote in message news:11**********************@z14g2000cwz.googlegr oups.com... we usually use < 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 Nov 14 '05 #34

 P: n/a 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 Nov 14 '05 #35

 P: n/a Chris Croughton coughed up: On Tue, 07 Dec 2004 19:58:46 -0800, Andrey Tarasevich 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. Nov 14 '05 #36

 P: n/a 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" .. Nov 14 '05 #37

 P: n/a On Wed, 08 Dec 2004 22:38:07 +0000, Mark McIntyre wrote: On 7 Dec 2004 17:44:33 -0800, in comp.lang.c , fo****@gmail.com wrote:we usually use <

 P: n/a "Lawrence Kirby" 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. Nov 14 '05 #39

 P: n/a "Chris Croughton" wrote in message news:sl******************@ccserver.keris.net... On Tue, 07 Dec 2004 19:58:46 -0800, Andrey Tarasevich 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. Nov 14 '05 #40

 P: n/a On Thu, 09 Dec 2004 13:25:59 +0100, Charlie Gordon wrote: "Lawrence Kirby" 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 Nov 14 '05 #41