Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > How to replace /(division) operator

Reply
Thread Tools

How to replace /(division) operator

 
 
spl
Guest
Posts: n/a
 
      04-28-2008
Thanks Bartc & Eric. Your suggestions are very useful. By the way all
my variables are unsigned int only. So right shift gives me exact
value.
 
Reply With Quote
 
 
 
 
thomas.mertes@gmx.at
Guest
Posts: n/a
 
      04-28-2008
On 28 Apr., 14:15, Eric Sosman <(E-Mail Removed)> wrote:
> Bartc wrote:
> > "spl" <(E-Mail Removed)> wrote in message
> >news:(E-Mail Removed)...
> >> Sorry for the delay in getting back to your questions, Actually
> >> changing the division operator to bitwise operators is suggested by my
> >> tech lead. As she done so many such improvement by doing this and she
> >> is having enough evidence for the same. She suggested me to do the
> >> same in my current project too. Actually I want to divide some big
> >> number with constant number, say 1024 always. Please give me your
> >> suggestion please.

>
> > My suggestion is to just divide by 1024.

>
> > Your compiler will use the most appropriate coding, you probably don't even
> > have to tell it to optimise.

>
> > Only if your compiler is so basic that you might try using (A>>10) instead
> > of A/1024, if A is an appropriate type like int, followed by a comment as to
> > why you are doing this.

>
> Pay close attention to that "appropriate type" part, and
> view "like int" with caution. The problem is that the result
> of right-shifting a negative number is implementation-defined,
> and is usually not the same as the result of dividing by two.
> For example, on the two's complement machines that are all
> but universal nowadays the representation of -1 is a string
> of 1-bits. Shift the string one place to the right and you
> may get another string of 1-bits ("arithmetic shift") or a
> single 0-bit followed by 1-bits ("logical shift"). The first
> thus gives -1 again, while the second gives a large positive
> result -- but neither gives the correct result -1 / 2 == 0.
>
> So: "appropriate type" means either an *unsigned* integer
> or a signed integer that you happen to know is non-negative.


Agreed.
There can be even more problems with negative numbers.
IMHO the definition of the division in C89 allows also
-1 / 2 == -1. Although I did not find a C compiler which
does this, it is theoretically possible since in C89 the
division is defined as follows:

The binary / operator yields the quotient, and the % operator
the remainder, of the first operand by the second; if the
second operand is 0, the result is undefined. Otherwise, it
is always true that (a/b)*b + a%b is equal to a. If both
operands are non-negative, the remainder is non-negative and
smaller than the divisor; if not it is guaranteed only that
the absolute value of the remainder is smaller than the
absolute value of the divisor.

As said before this definition allows that the integer
division can be rounded towards minus infinite.
Note that when -1 / 2 == -1 at the same time -1 % 2 == 1

IMHO this definition was chosen to allow integer operations
with one machine instruction.

Greetings Thomas Mertes

Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.
 
Reply With Quote
 
 
 
 
christian.bau
Guest
Posts: n/a
 
      05-03-2008
On Apr 28, 10:13*am, spl <(E-Mail Removed)> wrote:
> Sorry for the delay in getting back to your questions, Actually
> changing the division operator to bitwise operators is suggested by my
> tech lead. As she done so many such improvement by doing this and she
> is having enough evidence for the same. She suggested me to do the
> same in my current project too. Actually I want to divide some big
> number with constant number, say 1024 always. Please give me your
> suggestion please.


Write two functions

unsigned int f1 (unsigned int x) { return x / 1024; }
unsigned int f2 (unsigned int x) { return x >> 10; }

Find a way to make the compiler show the assembler code that it
generates and compare. If you get different code, tell us which
compiler you are using so we can all avoid it. I can't actually
remember any C compiler that wouldn't produce optimal code for the
division, and that is going back more than 20 years.

 
Reply With Quote
 
christian.bau
Guest
Posts: n/a
 
      05-03-2008
On May 3, 12:59*pm, "christian.bau" <(E-Mail Removed)>
wrote:
> On Apr 28, 10:13*am, spl <(E-Mail Removed)> wrote:
>
> > Sorry for the delay in getting back to your questions, Actually
> > changing the division operator to bitwise operators is suggested by my
> > tech lead. As she done so many such improvement by doing this and she
> > is having enough evidence for the same. She suggested me to do the
> > same in my current project too. Actually I want to divide some big
> > number with constant number, say 1024 always. Please give me your
> > suggestion please.

>
> Write two functions
>
> * unsigned int f1 (unsigned int x) { return x / 1024; }
> * unsigned int f2 (unsigned int x) { return x >> 10; }
>
> Find a way to make the compiler show the assembler code that it
> generates and compare. If you get different code, tell us which
> compiler you are using so we can all avoid it. I can't actually
> remember any C compiler that wouldn't produce optimal code for the
> division, and that is going back more than 20 years.


Oh, I just noticed you mentioned using a reasonably modern Microsoft
compiler.

In that case, you should also check what code is produced for

unsigned int f3 (unsigned int x) { return x / 1000; }

and ask your lead to explain the code that is generated. Have fun.

 
Reply With Quote
 
Tomás Ó hÉilidhe
Guest
Posts: n/a
 
      05-03-2008
On Apr 25, 1:51*pm, spl <(E-Mail Removed)> wrote:
> I use normal Microsoft visual C++ compiler only. Due to lots of more
> frequency in accessing / operator, I feel to change it with bitwise
> operator, as it is always faster then / operator. So, If you know
> bitwise manipulation, please suggest me!!



If you can do it faster on your own, I'll take out a loan and buy you
a Porsche.

As others have said, a bitwise instruction might take less CPU cycles
on your platform than a division instruction, but I can guarantee that
the amount of bitwise instruction you use will result in the division
instruction being faster.

In fact, it it were possible to get better performance using your own
bitwise instructions, then I think a lot of people would be ringing up
the CPU manufacturer to ask why the division instruction isn't done
efficiently.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
Replace /n with a XHTML <br /> using string.replace Alun ASP .Net 3 02-18-2008 05:52 AM
Re: [Pyrex] pyrex functions to replace a method (Re: replace a method Greg Ewing Python 2 06-29-2006 05:25 PM
pyrex functions to replace a method (Re: replace a method in class:how?) Brian Blais Python 1 06-27-2006 12:13 PM
help with string replace - for doing selective replace Prasad S Javascript 2 08-27-2004 03:22 PM



Advertisments