# division by 7 without using division operator

Discussion in 'C Programming' started by krypto.wizard@gmail.com, Feb 1, 2007.

1. ### Guest

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.

, Feb 1, 2007

2. ### David T. AshleyGuest

<> wrote in message
news:...
> 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 ()
http://gpl.e3ft.com (GPL Publications and Projects)

David T. Ashley, Feb 1, 2007

3. ### Christopher LayneGuest

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?

Christopher Layne, Feb 1, 2007
4. ### CBFalconerGuest

wrote:
>
> Last month I appeared for an interview with EA sports and they
>
> 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

CBFalconer, Feb 1, 2007
5. ### Jeffrey StedfastGuest

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

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

Jeffrey Stedfast, Feb 1, 2007
6. ### Ben PfaffGuest

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

Ben Pfaff, Feb 1, 2007
7. ### Guest

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?

, Feb 1, 2007
8. ### Jeffrey StedfastGuest

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

Jeffrey Stedfast, Feb 1, 2007
9. ### Keith ThompsonGuest

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) <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, Feb 1, 2007
10. ### Guest

On Jan 31, 8:03 pm, 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.
>

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

, Feb 1, 2007
11. ### Richard HeathfieldGuest

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.

Richard Heathfield, Feb 1, 2007
12. ### peteGuest

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

pete, Feb 1, 2007
13. ### Jeffrey StedfastGuest

pete wrote:
> 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

Jeffrey Stedfast, Feb 1, 2007

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

15. ### Richard TobinGuest

In article <>,
Richard Heathfield <> 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 ?

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

Richard Tobin, Feb 1, 2007
16. ### IcoGuest

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.

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

Ico, Feb 1, 2007
17. ### Ben PfaffGuest

Jeffrey Stedfast <> writes:

> 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

Ben Pfaff, Feb 1, 2007
18. ### Richard HeathfieldGuest

Richard Tobin said:

> In article <>,
> Richard Heathfield <> 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 ?

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

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 Heathfield, Feb 1, 2007
19. ### Richard TobinGuest

In article <>,
Ben Pfaff <> wrote:

>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, Feb 1, 2007
20. ### Richard TobinGuest

In article <>,
Richard Heathfield <> wrote:

>> 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
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);
>}
>

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

Richard Tobin, Feb 1, 2007