division by 7 without using division operator

[krypto.wizard]

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 ?

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.

Any comments ?

[David T. Ashley]

<kr***********@gmail.comwrote in message
news:11**********************@p10g2000cwp.googlegr oups.com...

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 ?

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.

The most obvious method is to shift, compare, and conditionally subtract and
mask a 1 into the quotient (very much like the necessary assembly-language
on a processor without a native division instruction). This is, however,
very inefficient. This involves some bit operations, but may not be what
the interviewer was looking for.

You might make another post and cross-post to sci.math as well. There may
be some good answers coming from those folks.

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.

I'm not sure that the direction you're going is anything except a dead end.
I'm not aware of a general method in the direction you've suggested that
will work with division. There are some good approximations (for example,
1/7 = 1/8 + 1/56 which is approximately equal to 1/8 + 1/64), but I'm not
aware of an exact method in the direction you're suggesting.

--
David T. Ashley (dt*@e3ft.com)
http://www.e3ft.com (Consulting Home Page)
http://www.dtashley.com (Personal Home Page)
http://gpl.e3ft.com (GPL Publications and Projects)

[Christopher Layne]

kr***********@gmail.com wrote:

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 ?

Divide by and truncate to integral result?

or

See if a number is divisible by 7 with no remainder?

[Jeffrey Stedfast]

kr***********@gmail.com wrote:

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 ?

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.

Any comments ?

(num >3) + 1 seems to work?

[krypto.wizard]

How ? For me it sometimes doesn't work.

For example 26/7 should give us 3.

26 is 11010 in binary and a right shift of 3 would give us 3 (binary
11) and adding 1 changes the result.

Correct me if I am wrong.

Thanks

(num >3) + 1 seems to work?

[CBFalconer]

kr***********@gmail.com wrote:

>
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?

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.

If you are multiplying (not dividing) then:
n = 8 * n - n;
or
n = (n << 3) - n; /* The latter only for unsigned n. */

otherwise he was asking you to build a division routine.

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

"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

[Ben Pfaff]

kr***********@gmail.com writes:

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

I'd look up the appropriate section in _Hacker's Delight_, which
not only gives the details of how to transform division by this
particular constant into multiplication followed by a correction,
but also explains how to figure out how to divide by any desired
constant using the same method. With proofs.

This same question came up, either here or in comp.programming,
within the last month or so. Try Google Groups to find the
earlier discussion.
--
"Some people *are* arrogant, and others read the FAQ."
--Chris Dollin

[Jeffrey Stedfast]

kr***********@gmail.com wrote:

How ? For me it sometimes doesn't work.

For example 26/7 should give us 3.

26 is 11010 in binary and a right shift of 3 would give us 3 (binary
11) and adding 1 changes the result.

Correct me if I am wrong.

Thanks

>(num >3) + 1 seems to work?

I was going on the assumption that you knew the value to be a multiple
of 7 to begin with...

but as someone else pointed out already, the +1 will not be sufficient
as the original number grows. I was only looking at "small" multiples of 7.

7, 14, 21, 28, 35, 42, 49...
It also wasn't clear to me if he wanted exact results or approximations.
Being that EA Sports is a 3d gaming house, I kinda figured approximation
is what they were looking for.

Jeff

[Keith Thompson]

kr***********@gmail.com writes:

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 ?

[...]

In a number system with wraparound semantics, such as C's unsigned
integer types (or signed integer types on most two's complement
implementations), you can often replace division by a constant with
multiplication by a constant.

I don't know the details of figuring out what constant to use, but
some compilers are smart enough to do this. If you can write a small
program that divides a number by 7 and examine the generated assembly
listing, you might see a multiplication instruction rather than a
division instruction.

<OT>gcc does this; I haven't studied the assembly listing enough to
understand what's going on, but you might want to.</OT>

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.

--
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.

[websnarf]

On Jan 31, 8:03 pm, [e-mail] wrote:

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 ?

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.

Any comments ?

For integers, here's a good way of doing it with 32 bit x86 assembly:

; uint32_t udiv_7 (uint32_t eax)
cmp eax, 0ccccccd1h
adc eax, 0ffffffffh
mov edx, 092492493h
mul edx
shr edx, 2
; value edx

The problem is that it requires a widening multiply which the C
standard does not have, so there is no easy way of translating this to
C.

For floating point, obviously you would want to multiply by the
reciprocal of 7. You might then check nearby floating point numbers
(some that is apparently possible in C99, or if you can assume
IEEE-754) to see if they are better approximations by multiplying the
7 back.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[Richard Heathfield]

kr***********@gmail.com said:

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 ?

Easy: q = exp(log(d) - log(7));

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.

I'd have replied that, unless we have some criteria by which to judge,
that's not better, merely different.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[pete]

kr***********@gmail.com wrote:

>
How ? For me it sometimes doesn't work.

For example 26/7 should give us 3.

26 is 11010 in binary and a right shift of 3 would give us 3 (binary
11) and adding 1 changes the result.

Correct me if I am wrong.

(num >3) + 1 seems to work?

"right shift of 3" is exactly equal to "division by 8"

(7 >3 == 0)
(8 >3 == 1)
(15 >3 == 1)
(16 >3 == 2)

--
pete

[Jeffrey Stedfast]

pete wrote:

kr***********@gmail.com wrote:

> How ? For me it sometimes doesn't work.

For example 26/7 should give us 3.

26 is 11010 in binary and a right shift of 3 would give us 3 (binary
11) and adding 1 changes the result.

Correct me if I am wrong.

>>(num >3) + 1 seems to work?

"right shift of 3" is exactly equal to "division by 8"

(7 >3 == 0)
(8 >3 == 1)
(15 >3 == 1)
(16 >3 == 2)

I know - it was a "rough estimation" (and also hence the +1)

anyways, this is a little better:

(x >2) - (x >3) + (x >6)

the first 2 terms are a /8, rounded up.

(7 >2) - (7 >3) + (7 >6) == 1 - 0 + 0 == 1
(8 >2) - (8 >3) + (8 >6) == 2 - 1 + 0 == 1
(15 >2) - (15 >3) + (15 >6) == 3 - 1 + 0 == 2
(16 >2) - (16 >3) + (16 >6) == 4 - 2 + 0 == 2
(21 >2) - (21 >3) + (21 >6) == 5 - 2 + 0 == 3
(28 >2) - (28 >3) + (28 >6) == 7 - 3 + 0 == 4
(35 >2) - (35 >3) + (35 >6) == 8 - 4 + 0 == 4 :(
....
(100 >2) - (100 >3) + (100 >6) == 25 - 12 + 1 = 14

[Richard Tobin]

In article <yp*********************@bt.com>,
Richard Heathfield <rj*@see.sig.invalidwrote:

>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 ?

>Easy: q = exp(log(d) - log(7));

The interviewer might well have replied that the purpose of the
interview was not merely to determine your logical skills, but your
ability to solve problems that you would be given in the course of
your job; and they might not always be expressed precisely, so an
ability to infer what the questioner really wants would be an
advantage. An insistence on treating questions literally is not
always regarded as a virtue outside comp.lang.c.

-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

[Ico]

kr***********@gmail.com wrote:

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 ?

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.

Pick your accuracy:

a: the required multiplication
b: the resulting factor from the operation

+ (a>>3)
a=0.142857 b=0.125 error=1.7857%

+ (a>>3) + (a>>6)
a=0.142857 b=0.140625 error=0.2232%

+ (a>>3) + (a>>6) + (a>>9)
a=0.142857 b=0.142578 error=0.0279%

+ (a>>3) + (a>>6) + (a>>9) + (a>>12)
a=0.142857 b=0.142822 error=0.0035%

+ (a>>3) + (a>>6) + (a>>9) + (a>>12) + (a>>15)
a=0.142857 b=0.142853 error=0.0004%

+ (a>>3) + (a>>6) + (a>>9) + (a>>12) + (a>>15) + (a>>18)
a=0.142857 b=0.142857 error=0.0001%

+ (a>>3) + (a>>6) + (a>>9) + (a>>12) + (a>>15) + (a>>18) + (a>>21)
a=0.142857 b=0.142857 error=0.0000%

--
:wq
^X^Cy^K^X^C^C^C^C

[Duncan Muirhead]

On Wed, 31 Jan 2007 20:03:38 -0800, krypto.wizard wrote:

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 ?

<snip>

>

If n >= 0 we can compute q>=0 and 0<=r<8 with n = 8*q + r using

>and &. So n = 7*q + q+r hence n/7 = q + (q+r)/7. For n>7

we have q+r < n, so we can iterate.
Duncan

[Ben Pfaff]

Jeffrey Stedfast <st******@comcast.netwrites:

I was going on the assumption that you knew the value to be a multiple
of 7 to begin with...

If x is a unsigned 32-bit integer that is a multiple of 7, then
you can divide by 7 with simply:
x *= 0xb6db6db7;
--
"I've been on the wagon now for more than a decade. Not a single goto
in all that time. I just don't need them any more. I don't even use
break or continue now, except on social occasions of course. And I
don't get carried away." --Richard Heathfield

[Richard Heathfield]

Richard Tobin said:

In article <yp*********************@bt.com>,
Richard Heathfield <rj*@see.sig.invalidwrote:

>>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 ?

>>Easy: q = exp(log(d) - log(7));

The interviewer might well have replied that the purpose of the
interview was not merely to determine your logical skills, but your
ability to solve problems that you would be given in the course of
your job;

Yup - and this solution works just fine.

and they might not always be expressed precisely, so an
ability to infer what the questioner really wants would be an
advantage. An insistence on treating questions literally is not
always regarded as a virtue outside comp.lang.c.

I think you're arguing from prejudice - that is, I believe you've made an
assumption about the interviewer's expectations. That isn't necessarily a
wise strategy. To give you a different example, if the interviewer asked
you what was wrong with this program:

#include <stdio.h>
#include <stdlib.h>
#include <strlen.h>
#include <assert.h>

main(int c, char **v)
{
char *p = malloc(strlen(v[0]));
char *q, *r;
assert(p);
strcpy(p, v[0]);
q = p;
r = q + strlen(p) - 1;
while(q < r)
{
char c = *q; *q++ = *r; *r-- = c;
}
puts(p);
}

how would you reply? What do you think the questioner really wants?

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Richard Tobin]

In article <87************@blp.benpfaff.org>,
Ben Pfaff <bl*@cs.stanford.eduwrote:

>If x is a unsigned 32-bit integer that is a multiple of 7, then
you can divide by 7 with simply:
x *= 0xb6db6db7;

.... because 0xb6db6db7 * 7 is 0x500000001, so 7y * 0xb6db6db7 is
y * 0x500000001, which is congruent to y mod 2^32.

Even more off-topic:

I used a similar trick years ago in Minix, which had no function for
sleeping less than a second. Internally, it slept in units of 1/60
second, and carelessly multiplied the argument to sleep() by 60. By
passing a suitable large number, one could arrange for the overflow to
produce a desired fraction of a second:

/* Sleep for t milliseconds (resolution 1/15 second). Assumes 32-bit ints. */

void msleep(t)
int t;
{
int s, f;

f = (t * 15 + 500) / 1000;

s = f / 15; f = f % 15;

sleep(s + 787410671 * f);

}

-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

[Richard Tobin]

In article <m-******************************@bt.com>,
Richard Heathfield <rj*@see.sig.invalidwrote:

>and they might not always be expressed precisely, so an
ability to infer what the questioner really wants would be an
advantage. An insistence on treating questions literally is not
always regarded as a virtue outside comp.lang.c.

>I think you're arguing from prejudice - that is, I believe you've made an
assumption about the interviewer's expectations. That isn't necessarily a
wise strategy.

Nonetheless, I think my assumption is likely to be right. Obviously
the best thing to do would be to verify that assumption before
answering the question. Just giving the answer you suggested does not
seem like a good strategy.

>To give you a different example, if the interviewer asked
you what was wrong with this program:

#include <stdio.h>
#include <stdlib.h>
#include <strlen.h>
#include <assert.h>

main(int c, char **v)
{
char *p = malloc(strlen(v[0]));
char *q, *r;
assert(p);
strcpy(p, v[0]);
q = p;
r = q + strlen(p) - 1;
while(q < r)
{
char c = *q; *q++ = *r; *r-- = c;
}
puts(p);
}

how would you reply?

"You aren't Richard Heathfield by any chance, are you?"

>What do you think the questioner really wants?

I would assume that the interviewer realised that there were several
errors of varying seriousness, and that he wanted me to list them. Of
course, I might be wrong, but such is life.

-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

[Ben Pfaff]

Richard Heathfield <rj*@see.sig.invalidwrites:

To give you a different example, if the interviewer asked you
what was wrong with this program:

[...]

how would you reply?

"From what point of view? I can do ISO 9899-1990, -1995, or -1999,
ISO 14882-1998, SUSv3, GNU, comp.lang.c, or clueless newbie."
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

[Richard Heathfield]

Richard Tobin said:

Richard Heathfield <rj*@see.sig.invalidwrote:

<snip>

>>I think you're arguing from prejudice - that is, I believe you've made an
assumption about the interviewer's expectations. That isn't necessarily a
wise strategy.

Nonetheless, I think my assumption is likely to be right. Obviously
the best thing to do would be to verify that assumption before
answering the question.

Actually, I'd give the answer I did give, along with weasel words such as
"well, this is the easiest, most obvious way", and then ask whether he had
expected a bit-twiddling answer. If so, I'd be prepared to give it,
obviously.

Just giving the answer you suggested does not seem like a good strategy.

I still think it's a perfectly valid answer. Had I asked the question with
bit-twiddling in mind, and then received that answer, I'd probably laugh
and say "er, oh yeah, good point - well, okay, how about a solution that
doesn't require any function calls?" (And I'd mentally award him a few
points for simplicity and creativity.) I once asked a candidate how he
would rotate an unsigned int. He wrote this:

unsigned int i = 42;

turned the piece of paper around (which I assumed was so that I could see
it), and sat back in an attitude of "okay, I'm ready for the next
question". It took me a moment to work it out, but I gave him 10/10 for
chutzpah and quick thinking. (And yes, then I asked the same question more
precisely, and yes, he came up with a good *technical* answer.)

>

>>To give you a different example, if the interviewer asked
you what was wrong with this program:

<buggy program snipped>

>>
how would you reply?

"You aren't Richard Heathfield by any chance, are you?"

<grin>

>

>>What do you think the questioner really wants?

I would assume that the interviewer realised that there were several
errors of varying seriousness, and that he wanted me to list them. Of
course, I might be wrong, but such is life.

Most were obvious, of course, but there was a subtlety in there that I would
expect only an expert to spot. If the candidate saw that one, I would
consider the question to be correctly answered, even if he dismissed the
rest with "oh, and there's a bunch of other stuff wrong as well".

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Ben Pfaff]

Richard Heathfield <rj*@see.sig.invalidwrites:

#include <stdio.h>
#include <stdlib.h>
#include <strlen.h>

No such standard header.

#include <assert.h>

main(int c, char **v)

Needs a return type, especially in C99.
It's kind to use the customary names argc and argv for the
arguments.

{
char *p = malloc(strlen(v[0]));

argc == 0 is permissible under the C standard, in which case
argv[0] is NULL, so this yields undefined behavior.

char *q, *r;
assert(p);

An assertion is not an appropriate way to check for failures that
can actually occur in practice.

strcpy(p, v[0]);

Didn't allocate enough memory for this.

q = p;
r = q + strlen(p) - 1;

If argv[0] == '\0', this attempts to back up past the beginning
of an allocated object, yielding undefined behavior.

while(q < r)
{
char c = *q; *q++ = *r; *r-- = c;
}

I'm not going to bother to analyze this. Likely problems include
stepping off the beginning or the end of the array.

puts(p);
}

Should return a value, probably 0 or EXIT_SUCCESS.
--
"...deficient support can be a virtue.
It keeps the amateurs off."
--Bjarne Stroustrup

[Richard Heathfield]

Ben Pfaff said:

Richard Heathfield <rj*@see.sig.invalidwrites:

>#include <stdio.h>
#include <stdlib.h>
#include <strlen.h>

No such standard header.

This was actually a genuine typo, which I spotted and was about to correct
when I thought, blow it, why not leave it in? I should actually have fixed
it, on reflection, as it would have left the program in a compilable state
despite the errors, and that would have clued the candidate in to the fact
that this is supposed to be C90 code (see below).

>

>#include <assert.h>

main(int c, char **v)

Needs a return type, especially in C99.

Actually, that was a clue that this was C90, and this is relevant.

<lots of good comments snipped>

> while(q < r)
{
char c = *q; *q++ = *r; *r-- = c;
}

I'm not going to bother to analyze this. Likely problems include
stepping off the beginning or the end of the array.

Actually, had you bothered to analyse it, you would have found that it's
about the only part of the program that is actually correct. :-)

Alas, you didn't spot the (admittedly C90-only, and there's a clue for you
if ever there was one) subtlety.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Ben Pfaff]

Richard Heathfield <rj*@see.sig.invalidwrites:

Alas, you didn't spot the (admittedly C90-only, and there's a clue for you
if ever there was one) subtlety.

Oh, you mean the assertion:

assert(p);

In C90, it needs to be assert(p != NULL);
--
"This is a wonderful answer.
It's off-topic, it's incorrect, and it doesn't answer the question."
--Richard Heathfield

[Richard Tobin]

In article <eK******************************@bt.com>,
Richard Heathfield <rj*@see.sig.invalidwrote:

>Most were obvious, of course, but there was a subtlety in there that I would
expect only an expert to spot.

Go on, tell us. I assume it's that assert(pointer) is not allowed
(but works on all known systems).

-- Richard

--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

[micans]

On Feb 1, 11:56 am, Ico <[e-mail]:

[e-mail] wrote:

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 ?

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.

Pick your accuracy:

a: the required multiplication
b: the resulting factor from the operation

+ (a>>3)
a=0.142857 b=0.125 error=1.7857%

+ (a>>3) + (a>>6)
a=0.142857 b=0.140625 error=0.2232%

+ (a>>3) + (a>>6) + (a>>9)
a=0.142857 b=0.142578 error=0.0279%

+ (a>>3) + (a>>6) + (a>>9) + (a>>12)
a=0.142857 b=0.142822 error=0.0035%

<snipprogression

nice.

This uses the following relationship:

1/(1-x) = 1 + x + x**2 + x**3 + x**4 ... (continued; x < 1)

and the fact that 1/7 equals -1 + 1/(1-1/8), so x/7
equals x ( 1/8 + (1/8)**2 + (1/8)**3 ... )

Stijn

[David T. Ashley]

"Richard Tobin" <ri*****@cogsci.ed.ac.ukwrote in message
news:ep***********@pc-news.cogsci.ed.ac.uk...

In article <87************@blp.benpfaff.org>,
Ben Pfaff <bl*@cs.stanford.eduwrote:

>>If x is a unsigned 32-bit integer that is a multiple of 7, then
you can divide by 7 with simply:
x *= 0xb6db6db7;

... because 0xb6db6db7 * 7 is 0x500000001, so 7y * 0xb6db6db7 is
y * 0x500000001, which is congruent to y mod 2^32.

I suppose one of these days I should actually read the standards you guys
cite so often ...

but ...

naive question ...

does the standard actually guarantee that if you overflow a multiplication
you get the modulo 2^32 result?

All processors that I'm aware of work this way (in fact, on all processors
I'm aware of MUL is sized so that overflow is impossible), but it seems
somebody somewhere might have a processor with a 32 = 32 x 32 multiply and
if you overflow you get an overflow flag and an undefined result ... and if
this is the case it would be inconvenient to provide the modulo 2^32 result.

Is this guaranteed on a multiplication overflow?

--
David T. Ashley (dt*@e3ft.com)
http://www.e3ft.com (Consulting Home Page)
http://www.dtashley.com (Personal Home Page)
http://gpl.e3ft.com (GPL Publications and Projects)

[Ben Pfaff]

"David T. Ashley" <dt*@e3ft.comwrites:

does the standard actually guarantee that if you overflow a multiplication
you get the modulo 2^32 result?

For an unsigned 32-bit type, yes.
For signed types, no.
--
A competent C programmer knows how to write C programs correctly,
a C expert knows enough to argue with Dan Pop, and a C expert
expert knows not to bother.

[Richard Tobin]

In article <xI******************************@giganews.com>,
David T. Ashley <dt*@e3ft.comwrote:

>does the standard actually guarantee that if you overflow a multiplication
you get the modulo 2^32 result?

We were assuming that unsigned ints are 32 bits, which is of course not
guaranteed, but arithmetic on unsigned ints *is* guaranteed to work
modulo 2^N, where N is the number of bits. For signed integers,
anything may happen.

-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

[Richard Heathfield]

Richard Tobin said:

In article <eK******************************@bt.com>,
Richard Heathfield <rj*@see.sig.invalidwrote:

>>Most were obvious, of course, but there was a subtlety in there that I
would expect only an expert to spot.

Go on, tell us.

Ben beat us to it.

I assume it's that assert(pointer) is not allowed

in C90.

(but works on all known systems).

It's the systems that I doesn't know as makes me worry mostest.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Krypto]

The correct answer as told to me by a person is

(N>>3) + ((N-7*(N>>3))>>3)

The above term always gives division by 7

[Richard Harter]

On 1 Feb 2007 09:13:37 -0800, mi****@gmail.com wrote:

>On Feb 1, 11:56 am, Ico <[e-mail]:

>[e-mail] wrote:

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 ?

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.

Pick your accuracy:

a: the required multiplication
b: the resulting factor from the operation

+ (a>>3)
a=0.142857 b=0.125 error=1.7857%

+ (a>>3) + (a>>6)
a=0.142857 b=0.140625 error=0.2232%

+ (a>>3) + (a>>6) + (a>>9)
a=0.142857 b=0.142578 error=0.0279%

+ (a>>3) + (a>>6) + (a>>9) + (a>>12)
a=0.142857 b=0.142822 error=0.0035%

<snipprogression

nice.

This uses the following relationship:

1/(1-x) = 1 + x + x**2 + x**3 + x**4 ... (continued; x < 1)

An alternative is

1/(1-x) = (1+x)*(1+x**2)*(1+x**4)...

>
and the fact that 1/7 equals -1 + 1/(1-1/8), so x/7
equals x ( 1/8 + (1/8)**2 + (1/8)**3 ... )

Stijn

[darshan.purandare]

On Feb 1, 3:29 pm, [e-mail] (Richard Harter) wrote:

On 1 Feb 2007 09:13:37 -0800, [e-mail] wrote:

On Feb 1, 11:56 am, Ico <[e-mail]:

[e-mail] wrote:
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 ?

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.

Pick your accuracy:

a: the required multiplication
b: the resulting factor from the operation

+ (a>>3)
a=0.142857 b=0.125 error=1.7857%

+ (a>>3) + (a>>6)
a=0.142857 b=0.140625 error=0.2232%

+ (a>>3) + (a>>6) + (a>>9)
a=0.142857 b=0.142578 error=0.0279%

+ (a>>3) + (a>>6) + (a>>9) + (a>>12)
a=0.142857 b=0.142822 error=0.0035%

<snipprogression

nice.

This uses the following relationship:

1/(1-x) = 1 + x + x**2 + x**3 + x**4 ... (continued; x < 1)

An alternative is

1/(1-x) = (1+x)*(1+x**2)*(1+x**4)...

and the fact that 1/7 equals -1 + 1/(1-1/8), so x/7
equals x ( 1/8 + (1/8)**2 + (1/8)**3 ... )

Stijn

How will it work ?

[Keith Thompson]

"Krypto" <kr***********@gmail.comwrites:

The correct answer as told to me by a person is

(N>>3) + ((N-7*(N>>3))>>3)

The above term always gives division by 7

A person was mistaken. The lowest non-negative value for which it
fails is 7. The highest non-negative value for which it succeeds is
384. (I didn't try it for negative values.) But the pattern of
failures (difference between the result of the expression and N/7) is
interesting, and may suggest that a correct answer would look similar
to what you wrote.

Here's my test program. WARNING: It will produce huge amounts of
output. Run it as "./prog | more", or "./prog | head -100", or
equivalent.

#include <stdio.h>
#include <limits.h>

#define DIV_BY_7(N) (((N)>>3) + (((N)-7*((N)>>3))>>3))

int main(void)
{
int i = 0;
while (1) {
int x = i / 7;
int y = DIV_BY_7(i);
printf("%6d ", i);
if (x != y) {
printf("%6d", x - y);
}
putchar('\n');
if (i == INT_MAX) {
break;
}
i++;
}
return 0;
}

--
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.

[Keith Thompson]

ri*****@cogsci.ed.ac.uk (Richard Tobin) writes:

In article <xI******************************@giganews.com>,
David T. Ashley <dt*@e3ft.comwrote:

does the standard actually guarantee that if you overflow a multiplication
you get the modulo 2^32 result?

We were assuming that unsigned ints are 32 bits, which is of course not
guaranteed, but arithmetic on unsigned ints *is* guaranteed to work
modulo 2^N, where N is the number of bits. For signed integers,
anything may happen.

To be painfully precise, N is the number of value bits. Unsigned
types are allowed to have padding bits as well, which do not
contribute to the value.

Results are reduced modulo (MAX+1), where MAX is the maximum value of
the unsigned type, also expressible as (type)-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.

[Richard Harter]

On 1 Feb 2007 12:42:23 -0800, da***************@gmail.com wrote:

>On Feb 1, 3:29 pm, [e-mail] (Richard Harter) wrote:

>On 1 Feb 2007 09:13:37 -0800, [e-mail] wrote:

>On Feb 1, 11:56 am, Ico <[e-mail]:
[e-mail] wrote:
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 ?

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.

>Pick your accuracy:

>a: the required multiplication
b: the resulting factor from the operation

> + (a>>3)
a=0.142857 b=0.125 error=1.7857%

> + (a>>3) + (a>>6)
a=0.142857 b=0.140625 error=0.2232%

> + (a>>3) + (a>>6) + (a>>9)
a=0.142857 b=0.142578 error=0.0279%

> + (a>>3) + (a>>6) + (a>>9) + (a>>12)
a=0.142857 b=0.142822 error=0.0035%

><snipprogression

>nice.

>This uses the following relationship:

>1/(1-x) = 1 + x + x**2 + x**3 + x**4 ... (continued; x < 1)

An alternative is

1/(1-x) = (1+x)*(1+x**2)*(1+x**4)...

>and the fact that 1/7 equals -1 + 1/(1-1/8), so x/7
equals x ( 1/8 + (1/8)**2 + (1/8)**3 ... )

>Stijn

How will it work ?

/* ans = x/7, accuracy up to 51 bits module corner cases, code untested
and will probably fail within 3 bits of maximum int. The idea is to
exploit the formula 1/(1-x) = (1+x)*(1+x^2)*(1+x^4)...
*/

ans = x + x>>3;
ans += ans * (x>>6);
ans += ans * (x>>12);
ans += ans * (x>>24);
ans = ans >>3;

[Flash Gordon]

Krypto wrote, On 01/02/07 20:27:

Subject: division by 7 without using division operator

The correct answer as told to me by a person is

(N>>3) + ((N-7*(N>>3))>>3)

The above term always gives division by 7

If we put in N=7 we get:
(7>>3) + ((7 - 7*(7>>3)) >3)
=0 + ((7 - 7*0) >3)
=(7-0) >3
=7 >3
=0

I think you should not trust what that person tells you. Either that or
take a lot more care in listening and noting down what they tell you.

Or to put it in C:

#include <stdio.h>
#include <stdlib.h>

int main(int argc,char **argv)
{
unsigned long n;
char *end;

if (argc < 2) {
fputs("Give me a number!\n", stderr);
return EXIT_FAILURE;
}

n = strtoul(argv[1], &end, 10);

if (end==argv[1] || *end) {
fputs("Give me a number!\n", stderr);
return EXIT_FAILURE;
}

printf("%lu / 7 = %lu\n", n, (n>>3) + ((n-7*(n>>3))>>3));

return EXIT_SUCCESS;
}

markg@brenda:~$ gcc t.c -ansi -pedantic -Wall -W -O3
markg@brenda:~$ ./a.out 7
7 / 7 = 0
markg@brenda:~$
--
Flash Gordon

[Dik T. Winter]

In article <11**********************@h3g2000cwc.googlegroups. com"Krypto" <kr***********@gmail.comwrites:

The correct answer as told to me by a person is

(N>>3) + ((N-7*(N>>3))>>3)

The above term always gives division by 7

Except when N is a multiple of 7 and a large number of other cases.
Try it with N == 7.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, [phone]
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[Dik T. Winter]

In article <ep***********@pc-news.cogsci.ed.ac.ukri*****@cogsci.ed.ac.uk (Richard Tobin) writes:

In article <87************@blp.benpfaff.org>,
Ben Pfaff <bl*@cs.stanford.eduwrote:

If x is a unsigned 32-bit integer that is a multiple of 7, then
you can divide by 7 with simply:
x *= 0xb6db6db7;

... because 0xb6db6db7 * 7 is 0x500000001, so 7y * 0xb6db6db7 is
y * 0x500000001, which is congruent to y mod 2^32.

This works indeed works for multiples of 7. The same technique can
be used for all odd numbers.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, [phone]
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[CBFalconer]

Richard Heathfield wrote:

Ben Pfaff said:

.... snip ...

>

>> while(q < r)
{
char c = *q; *q++ = *r; *r-- = c;
}

I'm not going to bother to analyze this. Likely problems include
stepping off the beginning or the end of the array.

Actually, had you bothered to analyse it, you would have found that
it's about the only part of the program that is actually correct. :-)

It also has a bug. If strlen(p) == 0, then q is pointing outside
any object, and the comparison q < r is illegal. Assuming the
initialization of q could be done, which is also not guaranteed.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

[Christopher Layne]

Richard Heathfield wrote:

how would you reply? What do you think the questioner really wants?

char *p = malloc(strlen(v[0]));

[...] ^^^^^^^^^

strcpy(p, v[0]);

^^^^^^^

[Christopher Layne]

Richard Heathfield wrote:

>I assume it's that assert(pointer) is not allowed

in C90.

>(but works on all known systems).

It's the systems that I doesn't know as makes me worry mostest.

And this is what answer you would expect to receive as your basis for what
determines the appropriate level of technicality for the candidate? Cmon.

If you state generally "what is wrong with this code?" you're not going to get
the prime answer as one focusing on the most subtle element in the first
place.

[Christopher Layne]

Richard Tobin wrote:

Even more off-topic:

I used a similar trick years ago in Minix, which had no function for
sleeping less than a second. Internally, it slept in units of 1/60
second, and carelessly multiplied the argument to sleep() by 60. By
passing a suitable large number, one could arrange for the overflow to
produce a desired fraction of a second:

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

Richard 1, Minix 0.

[Richard Heathfield]

Christopher Layne said:

Richard Heathfield wrote:

>>I assume it's that assert(pointer) is not allowed

in C90.

>>(but works on all known systems).

It's the systems that I doesn't know as makes me worry mostest.

And this is what answer you would expect to receive as your basis for what
determines the appropriate level of technicality for the candidate?

I'd expect the successful candidate to be drawn from those who spotted it,
yes.

Cmon.

Hmm? If I'm hiring, I want someone who knows the language. Something wrong
with that?

If you state generally "what is wrong with this code?" you're not going to
get the prime answer as one focusing on the most subtle element in the
first place.

No, but the people I'd want to hire would at least mention it, possibly with
a little non-spoonfeedy prompting, like Ben did (although if I were hiring,
I wouldn't bother interviewing Ben - I'd just show him his reserved parking
spot and ask when he planned to start using it).

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Richard Heathfield]

CBFalconer said:

Richard Heathfield wrote:

>Ben Pfaff said:

... snip ...

>>

>>> while(q < r)
{
char c = *q; *q++ = *r; *r-- = c;
}

I'm not going to bother to analyze this. Likely problems include
stepping off the beginning or the end of the array.

Actually, had you bothered to analyse it, you would have found that
it's about the only part of the program that is actually correct. :-)

It also has a bug.

No, it doesn't.

If strlen(p) == 0, then q is pointing outside
any object,

....and that is a bug, yes. But the first assignment of q does not happen in
the while-loop under discussion. So the bug lies elsewhere.

and the comparison q < r is illegal.

The bug's already happened by then, because q already has an indeterminate
value. The loop itself is fine. Yes, you're right to point out that it can
break if code around it is broken, but that's true of just about all
working code, and so does not constitute a useful observation.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Richard Heathfield]

Christopher Layne said:

Richard Heathfield wrote:

>how would you reply? What do you think the questioner really wants?

> char *p = malloc(strlen(v[0]));

[...] ^^^^^^^^^

> strcpy(p, v[0]);

^^^^^^^

Yes, well done - but, whilst your observation is an important one, it lacks
completeness. (Others have already provided more complete answers.)

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Richard Bos]

ri*****@cogsci.ed.ac.uk (Richard Tobin) wrote:

In article <eK******************************@bt.com>,
Richard Heathfield <rj*@see.sig.invalidwrote:

Most were obvious, of course, but there was a subtlety in there that I would
expect only an expert to spot.

Go on, tell us. I assume it's that assert(pointer) is not allowed
(but works on all known systems).

If it is, it's a wrong gotcha. I would have disallowed the assertion on
the result of a runtime problem wholesale, and not have bothered to
check whether it would have been theoretically correct had it not been
an abomination.

Richard

[Richard Heathfield]

Richard Bos said:

ri*****@cogsci.ed.ac.uk (Richard Tobin) wrote:

>In article <eK******************************@bt.com>,
Richard Heathfield <rj*@see.sig.invalidwrote:

>Most were obvious, of course, but there was a subtlety in there that I
would expect only an expert to spot.

Go on, tell us. I assume it's that assert(pointer) is not allowed
(but works on all known systems).

If it is, it's a wrong gotcha.

No, it isn't.

I would have disallowed the assertion on
the result of a runtime problem wholesale, and not have bothered to
check whether it would have been theoretically correct had it not been
an abomination.

But you would have re-examined the assertion if prompted to do so. And then
you would have spotted what you call the "gotcha".

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[micans]

On Feb 2, 7:03 am, Richard Heathfield <[e-mail]:

Christopher Layne said:

Richard Heathfield wrote:

>I assume it's that assert(pointer) is not allowed

in C90.

>(but works on all known systems).

It's the systems that I doesn't know as makes me worry mostest.

And this is what answer you would expect to receive as your basis for what
determines the appropriate level of technicality for the candidate?

I'd expect the successful candidate to be drawn from those who spotted it,
yes.

Cmon.

Hmm? If I'm hiring, I want someone who knows the language. Something wrong
with that?

Presumably you test something that is related to understanding
algorithms and
data structures as well.

Now what if the intersection of candidates that get the assert thingy
right with
those that have suitable knowledge of algorithms and data structures
is empty,
and both set differences are non-empty. Whom do you pick?

Of course there are still many more dimensions.

Stijn