integer division


D

Darius Fatakia

hi,
i'm new to MS Visual Studio and C++ but not to C programming in general. i'm
trying to divide two integers and get their actual quotient (eg 5/3 =
1.666667 etc). i thought i had type cast correctly, but please let me know,
because it appears to be rounding off. my code follows. Thanks!

void DrawLine(GLint x1, GLint y1, GLint x2, GLint y2)

{
int i, pk, dy, dx, yc, xc, inc, temp;
float m;
/*
x1 = 100;
y1 = 200;
x2 = 110;
y2 = 206;
*/

if((x1 >= x2) && (y1 >= y2)) {
temp = x1;
x1 = x2;
x2 = temp;
temp = y1;
y1 = y2;
y2 = temp;
}

dy = y2 - y1;
dx = x2 - x1;
if (dx != 0) m = (float)(dy/dx);
else m = -999;

// Debugging info
printf("\nDrawLine called!\n");
printf("x1 = %d\n", x1);
printf("y1 = %d\n", y1);
printf("x2 = %d\n", x2);
printf("y2 = %d\n", y2);
printf("dx = %d\n", dx);
printf("dy = %d\n", dy);
if (dx != 0) printf("dy/dx = %d\n", dy/dx);
printf("m = %.2f\n", m);
}

DrawLine called!
x1 = 286
y1 = 204
x2 = 309
y2 = 187
dx = 23
dy = -17
dy/dx = 0
m = 0.00
 
Ad

Advertisements

J

Jim Lambert

Darius said:
hi,
i'm new to MS Visual Studio and C++ but not to C programming in
general. i'm trying to divide two integers and get their actual
quotient (eg 5/3 =
1.666667 etc). i thought i had type cast correctly, but please let me
know, because it appears to be rounding off. my code follows. Thanks!

void DrawLine(GLint x1, GLint y1, GLint x2, GLint y2)

{
int i, pk, dy, dx, yc, xc, inc, temp;
float m;
/*
x1 = 100;
y1 = 200;
x2 = 110;
y2 = 206;
*/

if((x1 >= x2) && (y1 >= y2)) {
temp = x1;
x1 = x2;
x2 = temp;
temp = y1;
y1 = y2;
y2 = temp;
}

dy = y2 - y1;
dx = x2 - x1;
if (dx != 0) m = (float)(dy/dx);

One solution would be:

if (dx != 0) m = (float)dy/(float)dx;
 
N

Nick Landsberg

You are typecasting the result of the INTEGER
arithmetic (dy/dx) to a FLOAT. You should rather
typecast both dy and dx to a FLOAT (or double)
in the expression.

e.g.

m = ( float(dy)/float(dx) );

or declare float( or double) variables to which you
assign the integer values of dy and dx.
 
J

Jack Klein

hi,
i'm new to MS Visual Studio and C++ but not to C programming in general. i'm
trying to divide two integers and get their actual quotient (eg 5/3 =
1.666667 etc). i thought i had type cast correctly, but please let me know,
because it appears to be rounding off. my code follows. Thanks!
void DrawLine(GLint x1, GLint y1, GLint x2, GLint y2)

{
int i, pk, dy, dx, yc, xc, inc, temp;
float m;
[snip]

if (dx != 0) m = (float)(dy/dx);

The type of an expression in C depends solely on the type of its
arguments, and is not influenced in any way by what you might do with
the result of the expression.

dy and dx are ints, so dx/dy is an int division expression which
produces an int result, that is truncates the quotient to an int.

The fact that you cast the result afterwards does not change this.
The int result, with no fractional part, will be converted to float
even without the cast, simply by assigning it to the float object m.

To force the expression to be performed as a float operation, one or
both of the operands must be a float. So you need to do one of:

if (dx != 0) m = ((float)dy/dx);

if (dx != 0) m = (dy/(float)dx);

if (dx != 0) m = ((float)dy/(float)dx);

If you convert either of the operands to float by a cast, the compiler
must automatically promote the other float, perform a float divide,
and produce a float result.
 
J

James Dow Allen

Jack Klein said:
dy and dx are ints, so dx/dy is an int division expression which
produces an int result, that is truncates the quotient to an int.

This answer is, of course, correct, but I want to seize on it as
a simple example of the advantages of *Low-level* (WYSIWYG) languages.

One needn't be a C expert to deduce Mr. Klein's correct answer.
Just examining the parentheses one sees (dy/dx) or (5/3)
"should" be evaluated before the (float) part. Since (5/3) is 1,
(float)(5/3) is (float)(1) is 1.0000, not 1.6667. In this simple
case, if you understand parentheses you understand C.

Now perhaps a "friendly" high-level language would remember where
the (1) came from and evaluate (float)(1) as 1.6667. Would you like
that? Not I, but I gather some people find such "friendly" features
.... er, friendly!

C++ will also evaluate (float)(5/3) as 1.0000 but that's only because
the friendly C++ designers haven't gotten around to letting parentheses
be overloadable :)

In slightly less egregious cases, C++ prides itself on doing the friendly
thing rather than the WYSIWYG thing.

That's what the debate is about between C++ fans and C fans.
The C fans aren't too lazy to construct operator inheritance mazes;
we just put more of a premium on transparent clarity.

James
 
A

ark

Jack Klein said:
On Tue, 27 Jan 2004 17:24:51 -0800, "Darius Fatakia"
To force the expression to be performed as a float operation, one or
both of the operands must be a float. So you need to do one of:

if (dx != 0) m = ((float)dy/dx);

if (dx != 0) m = (dy/(float)dx);

if (dx != 0) m = ((float)dy/(float)dx);

If you convert either of the operands to float by a cast, the compiler
must automatically promote the other float, perform a float divide,
and produce a float result.
<snip>
IMHO, compilers are not created equal, and while these three options are
mathematically equivalent, a compiler may have a better chance of optimizing
the 1st variant (essentially, by dividing integer mantissa of the
not-necessarily-fully-formed float). It may be more important for targets
without a hardware FPU or even a division instruction. For the same reason,
one may want to keep the divisor in an unsigned type when possible.
As a separate note, I believe there are 100% integral line drawing
algorithms out there (cannot give references now, try search).
Ark
 
Ad

Advertisements

J

Jack Klein

<snip>
IMHO, compilers are not created equal, and while these three options are
mathematically equivalent, a compiler may have a better chance of optimizing
the 1st variant (essentially, by dividing integer mantissa of the
not-necessarily-fully-formed float). It may be more important for targets
without a hardware FPU or even a division instruction. For the same reason,
one may want to keep the divisor in an unsigned type when possible.
As a separate note, I believe there are 100% integral line drawing
algorithms out there (cannot give references now, try search).
Ark

Optimization is not a language issue, and whether certain compilers
might generate more efficient code for one of the expressions above is
irrelevant in this group. What might be the "most efficient" on one
compiler might be least on another, or even on the same compiler with
a different set of options.

As for the algorithm you are referring to, a Google search on "Integer
Bresenham Algorithm" should turn up the references. Twenty years ago
I used it to generate pixel coordinates for displaying machine tool
contours on a Tecmar Grahpics Master (this was before such things as
EGA and VGA video) with an 8088.

There was no Internet or search engines in those days, so I invented
my own integer only algorithm similar to Breshenham's for circles and
circular arcs.
 
Z

Zoran Cutura

Nick Landsberg said:
You are typecasting the result of the INTEGER
arithmetic (dy/dx) to a FLOAT. You should rather
typecast both dy and dx to a FLOAT (or double)
in the expression.

e.g.

m = ( float(dy)/float(dx) );

That would be C++, but in C typecasts must be written (float)dx ...
Also Note that it should be enough to cast either of the operands
to float (or even better double) to force the calculation to be done
in float. The other operand will be magically converted according to
usual arithmetic conversions.
 
A

ark

Jack Klein said:
comp.lang.c:
Optimization is not a language issue, and whether certain compilers
might generate more efficient code for one of the expressions above is
irrelevant in this group. What might be the "most efficient" on one
compiler might be least on another, or even on the same compiler with
a different set of options.
<snip>

Languages are made to accomplish certain tasks, not just for syntactic fun.
For instance,
unsigned x; ..., x/=2;
is equivalent to x>>=1;
whereas
int x; ..., x/=2;
is roughly equivalent to
if(x<0) x+=1; x>>=1;
or about 200% overhead plus possible pipeline break, if any.
So I am not convinced that efficiency is totally off topic here...
- Ark
 
Ad

Advertisements

R

Richard Bos

ark said:
Languages are made to accomplish certain tasks, not just for syntactic fun.

True, but the language specification cannot rule over everything. And
the topic of this newsgroup is ISO C, not C-as-it-happens-to-run-on-
your-system, because tomorrow you may have a new computer which may make
these micro-optimisations completely unreliable.
For instance,
unsigned x; ..., x/=2;
is equivalent to x>>=1;

True, because it is guaranteed by the Standard; but you do not know
which of them will turn out to be more efficient on any particular
system until you measure it, and those measurements will not be valid
for most other systems. And in fact, many good compilers will compile
these two expressions to the very same machine code.
whereas
int x; ..., x/=2;
is roughly equivalent to
if(x<0) x+=1; x>>=1;

Wrong, wrong, utterly wrong.
For positive values and zero, the same equivalence as for unsigned int
holds. For negative values, however, the result of the shift is
implementation-defined. It is certainly possible that _your_
implementation happens to define it as the above code; but this is by no
means guaranteed, and anyone relying on it is setting himself up for a
surprise.
The division, OTOH, is perfectly defined for all values. So the division
and the shift-complex aren't equivalent at all, not even roughly.
or about 200% overhead plus possible pipeline break, if any.

You do not know any of that. You do not know that the +=1 gives you a
200% overhead. You do not know that the target computer even _has_ a
pipeline, let alone that this code could break it. You do not know that
the end result is the same. And finally, you do not know how efficiently
the target system implements signed integral divisions and shifts, so
you have no idea which of the two alternatives actually _is_ the most
efficient until you measure it.
So I am not convinced that efficiency is totally off topic here...

It is. It is totally system-dependent, and therefore totally off-topic.

Richard
 

Top