division by 7 without using division operator

[Richard Bos]

I have found on more than one occasion developers leaving in assertions in
production code on hardware (network equipment) for serious "should not
happen" cases. When it does happen - you submit a bug and they follow up.
What are people's opinions on this?

That's different. If it really is not supposed to happen, even if
there's a minor bug in earlier code, a cryptic error message may be
excusable. I'd still advocate putting it up where a normal user of the
program can see it, but if you're writing a hardware driver, it's hard
to see where that is.

Richard

 

[Christopher Layne]

That's different. If it really is not supposed to happen, even if
there's a minor bug in earlier code, a cryptic error message may be
excusable. I'd still advocate putting it up where a normal user of the
program can see it, but if you're writing a hardware driver, it's hard
to see where that is.

Richard

The cases which have exemplified this were like the following:

1. Failing memory.
2. Failing hardware (signal egregiously out of spec, etc.).
3. Indirect "should not happen"'s which were really "this shouldn't happen if
we had no bug."

 

[CBFalconer]

CBFalconer said:

An exercise for those with way too much time on their hands: what
is the smallest-magnitude integer (i.e. regardless of sign) for
which it fails? If this number is negative, what is the smallest
*positive* integer for which it fails?

Without spending too much time on it, the error will be roughly
0.000000000000000143 * N. Equating this expression (abs) to 1.0
should give you the answer.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

 

[Serve Laurijssen]

Of course it does. I can't imagine why you would think it doesn't.
For example, coding includes maintaining existing code, some of which
might depend on those rules you're trying to ignore.

Well then, might as well let job applicants cite whole pages from the
standard then.
Considering somebody an expert because he knows why assert(p) is wrong is
taking it too far, all he had to do is read comp.lang.c a week There's
far worse maintenance problems than assert and enum comma's

 

[Serve Laurijssen]

Well assert is not the way to gio then. You can add an assert like debug
facility that can be turned on/off by the user

If there's a bug in my code, I probably don't want the user to be able
to disable its detection.[/QUOTE]

assert in production code "disables" detection of bugs at users already so
Im not sure if you been keeping up here. Better provide assert like
functionality where at least you and the user have the choice of turning it
on.

 

[quarkLore]

Last month I appeared for an interview with EA sports and they asked
me this question.

How would you divide a number by 7 without using division operator ?

quotient = ( value >> 3 ) & 0x1FFFF;

The assumption is that of 4 byte integer and signed types. & is to be
used when using signed integers because if the most significant bit of
value was filled right shift will append 1's at the beginning of your
number.

I did by doing a subtraction and keeping a counter that kept a tab on
how many times I subtracted.

Later, the EA sport guy told me that of course there are can be better
technique by using bit operator.

Since 7 has a binary representation 111, my guess is that a left shift
operation of 3 bits should give the answer, but I couldn't get it to
work.

The right shift will work. This technique works only when the divisor
is of the bit pattern 11...1 in other words it has to be 1 less than a
power of 2. 7,15,31 will work.

This technique is used a lot in linux kernel/related system software
to create circular buffers which have number of elements as a power of
2 and then use this technique to wrap around the buffer when index
reaches end (though here remainder calculation is done which is simple
x = x & 0x0003 )

Any comments ?

Bit masking techniques take lesser MIPS in general than iteration
based techniques. Loop based techniques also need loop index
variables. But bit masking techniques churn out cryptic code and often
non portable so one must use them with utmost caution.

 

[quarkLore]

The fact that compilers can perform this optimization -- and, perhaps

more important, can decide when it is and isn't necessary -- is a good
reason *not* to bother doing this yourself. Just divide by 7; that's
what the "/" operator is for.

/ operator often leads to 32 instructions of shift and add or an
instruction which takes that much time unless you have a multiplier
application to do it. This is the reason many a times it is avoided in
DSP, embedded systems applications and such hacks are needed.

 

[Guest]

CBFalconer said:

An exercise for those with way too much time on their hands: what is the
smallest-magnitude integer (i.e. regardless of sign) for which it
fails? If this number is negative, what is the smallest *positive*
integer for which it fails?

It depends on the implementation's precision and the rounding mode.
One possible answer: C90 (but not C99) allows integer division to
round towards negative infinity, so -1 / 7 could be -1, but -1 *
0.142857142857143 is always 0.

Mathematically, 0.142857142857143 is equal to 1.000000000000001 / 7,
so another possible answer is easy to guess and confirm:
100000000000000.

100000000000000 * 0.142857142857143 is 142857142857143
100000000000000 / 7 is 142857142857142.8..., which becomes
142857142857142 because floating point to integer conversions round
towards zero. For any smaller positive number, the exact difference
between the two numbers cannot be greater than 1/7, so when rounding
towards zero, it cannot make a difference. Also, when rounding towards
zero, the sign doesn't matter.

There are other possible answers depending on the representation of
double.

 

[Flash Gordon]

Christopher Layne wrote, On 06/02/07 07:12:

The cases which have exemplified this were like the following:

1. Failing memory.
2. Failing hardware (signal egregiously out of spec, etc.).

An assert is not always correct (what if the purpose of the program is
to test the HW?) but I would have no problem with some appropriate form
of "display message and terminate" be it abort or some other appropriate
mechanism, and depending on the program assert may be fine.

3. Indirect "should not happen"'s which were really "this shouldn't happen if
we had no bug."

Again, sometimes "display message and terminate" would be appropriate so
sometimes assert may be OK, but other times you might need to use
something else for the "display message" part or you might want to save
the current state somewhere so an attempt at recovery can be made.

In short, it depends.

 

[Serve Laurijssen]

This is such an awesomely unportable hack - I love it.

Richard 1, Minix 0.

sometimes programming is fun

 

[Ben Bacarisse]

quotient = ( value >> 3 ) & 0x1FFFF;

The assumption is that of 4 byte integer and signed types. & is to be
used when using signed integers because if the most significant bit of
value was filled right shift will append 1's at the beginning of your
number.

C leaves the result of right shifting a signed int up to the
implementation, so you don't know what will happen. If the sign is
extended down, it is probably because it is arithmetically correct on
that implementation, so masking is then the wrong thing to do. If the
shift is not sign-extended, masking won't help so I don't see the
value of it.

I don't think shifting by 3 when the interviewer wanted a divide by 7
would get you the job!

 

[Keith Thompson]

Well then, might as well let job applicants cite whole pages from the
standard then.
Considering somebody an expert because he knows why assert(p) is wrong is
taking it too far, all he had to do is read comp.lang.c a week There's
far worse maintenance problems than assert and enum comma's

Yes, there are, and I never claimed otherwise, nor did I claim that
knowing why assert(p) is wrong makes someone an expert. It is,
however, *part* of being an expert.

Here's what you said upthread:
| I'm talking about the assert and enum comma example. Knowing those rules
| doesnt help one at all to become a better C coder.

That statement was clearly wrong. No one piece of knowledge can make
you an expert, but surely more knowledge is better than less
knowledge. The assert and enum comma examples are relatively minor
points, but they not *completely* insignificant.

 

[Keith Thompson]

quotient = ( value >> 3 ) & 0x1FFFF;

The assumption is that of 4 byte integer and signed types. & is to be
used when using signed integers because if the most significant bit of
value was filled right shift will append 1's at the beginning of your
number.

So 7 / 7 == 0? Fascinating.

 

[Keith Thompson]

I wrote the above. Please don't snip attribution lines.

/ operator often leads to 32 instructions of shift and add or an
instruction which takes that much time unless you have a multiplier
application to do it. This is the reason many a times it is avoided in
DSP, embedded systems applications and such hacks are needed.

If you're dividing by a constant, the compiler is likley to be able to
figure out how to do it more efficiently. If it fails to do so *and*
if the (measured!) performance cost is significant, then go ahead and
use some hack (but not the one you posted elsewhere in this thread if
you want correct answers).

 

[¬a\\/b]

_So_ nice for you.

Most production peons wouldn't know which end of a CLI was which.


Your species of luser much be about twelve thousand years futher along
the evolutionary ladder than mine. Congratulations.

I wasn't talking about assert() messages that _I_ see, but about those
that the average, Windows-only, can't-remember-any-numbers, Word-is-
complicated data entry employee sees.

Richard

easy

redirect too the output of all asserts
in a file that can grow < xMb limit
file that is "a queue"
and eliminate double assert that look the same

email that file 1 time for month to who make that program
for the first 3 months (if it is not 0lenght)