# Re: integer divide by 7 trick?

Discussion in 'C++' started by Robert W Hand, Jul 20, 2003.

1. ### Robert W HandGuest

On 20 Jul 2003 01:05:40 -0700, (krazyman) wrote:

>Does anyone know a good trick to perform an integer divide by 7
>(the equivalent of x/7 in C) without using a divide? I'm familiar
>with the multiply by 7 trick (x<<3-x), and I was asked this question
>with the implication that something similar exists for divide-by-7. I

How does (x<<3-x) work? If x, type int, has the value 10, the right
hand side is a negative number. That should be undefined behavior.
Some trick? :-( Obviously, I'm missing something.

Best wishes,

Bob

Robert W Hand, Jul 20, 2003

2. ### Alf P. SteinbachGuest

On Sun, 20 Jul 2003 08:13:07 -0400, Robert W Hand <> wrote:

>On 20 Jul 2003 01:05:40 -0700, (krazyman) wrote:
>
>>Does anyone know a good trick to perform an integer divide by 7
>>(the equivalent of x/7 in C) without using a divide? I'm familiar
>>with the multiply by 7 trick (x<<3-x), and I was asked this question
>>with the implication that something similar exists for divide-by-7. I

>
>How does (x<<3-x) work? If x, type int, has the value 10, the right
>hand side is a negative number. That should be undefined behavior.
>Some trick? :-( Obviously, I'm missing something.

Just a parenthesis missing:

(x << 3) - x = 8x - x = 7x

Of course, this expression can overflow where 7*x won't...

Alf P. Steinbach, Jul 20, 2003

3. ### AndreGuest

Exactly. Even if it's (x<<3)-x, it still doesn't work.

-Andre

Robert W Hand wrote:
> On 20 Jul 2003 01:05:40 -0700, (krazyman) wrote:
>
>
>>Does anyone know a good trick to perform an integer divide by 7
>>(the equivalent of x/7 in C) without using a divide? I'm familiar
>>with the multiply by 7 trick (x<<3-x), and I was asked this question
>>with the implication that something similar exists for divide-by-7. I

>
>
> How does (x<<3-x) work? If x, type int, has the value 10, the right
> hand side is a negative number. That should be undefined behavior.
> Some trick? :-( Obviously, I'm missing something.
>
> Best wishes,
>
> Bob

Andre, Jul 20, 2003
4. ### AndreGuest

Ah.

Alf P. Steinbach wrote:
> On Sun, 20 Jul 2003 08:13:07 -0400, Robert W Hand <> wrote:
>
>
>>On 20 Jul 2003 01:05:40 -0700, (krazyman) wrote:
>>
>>
>>>Does anyone know a good trick to perform an integer divide by 7
>>>(the equivalent of x/7 in C) without using a divide? I'm familiar
>>>with the multiply by 7 trick (x<<3-x), and I was asked this question
>>>with the implication that something similar exists for divide-by-7. I

>>
>>How does (x<<3-x) work? If x, type int, has the value 10, the right
>>hand side is a negative number. That should be undefined behavior.
>>Some trick? :-( Obviously, I'm missing something.

>
>
>
> Just a parenthesis missing:
>
>
> (x << 3) - x = 8x - x = 7x
>
>
> Of course, this expression can overflow where 7*x won't...
>

Andre, Jul 20, 2003
5. ### Paul HsiehGuest

In article <>, says...
> On Sun, 20 Jul 2003 08:13:07 -0400, Robert W Hand <> wrote:
> >On 20 Jul 2003 01:05:40 -0700, (krazyman) wrote:
> >>Does anyone know a good trick to perform an integer divide by 7
> >>(the equivalent of x/7 in C) without using a divide? I'm familiar
> >>with the multiply by 7 trick (x<<3-x), and I was asked this question
> >>with the implication that something similar exists for divide-by-7. I

> >
> >How does (x<<3-x) work? If x, type int, has the value 10, the right
> >hand side is a negative number. That should be undefined behavior.
> >Some trick? :-( Obviously, I'm missing something.

>
> Just a parenthesis missing:
>
> (x << 3) - x = 8x - x = 7x
>
> Of course, this expression can overflow where 7*x won't...

7*x can also overflow. It just has a different overflow condition than
(x << 3)-x. But if your C compiler implments ordinary 2s complement
mathematics (i.e., the ring Z(2**n) is embedded in the C integer operations),
then both expresions will yield identical results regarless of intermediate
overflowings or which of the base fixed point scalar types x is.

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

Paul Hsieh, Jul 20, 2003
6. ### Alf P. SteinbachGuest

On Sun, 20 Jul 2003 17:09:29 GMT, (Paul Hsieh) wrote:

>In article <>, says...
>> On Sun, 20 Jul 2003 08:13:07 -0400, Robert W Hand <> wrote:
>> >On 20 Jul 2003 01:05:40 -0700, (krazyman) wrote:
>> >>Does anyone know a good trick to perform an integer divide by 7
>> >>(the equivalent of x/7 in C) without using a divide? I'm familiar
>> >>with the multiply by 7 trick (x<<3-x), and I was asked this question
>> >>with the implication that something similar exists for divide-by-7. I
>> >
>> >How does (x<<3-x) work? If x, type int, has the value 10, the right
>> >hand side is a negative number. That should be undefined behavior.
>> >Some trick? :-( Obviously, I'm missing something.

>>
>> Just a parenthesis missing:
>>
>> (x << 3) - x = 8x - x = 7x
>>
>> Of course, this expression can overflow where 7*x won't...

>
>7*x can also overflow.

NSS...

>It just has a different overflow condition than (x << 3)-x.

So what do you think I wrote above?

>But if your C compiler implments ordinary 2s complement
>mathematics (i.e., the ring Z(2**n) is embedded in the C integer operations),
>then both expresions will yield identical results regarless of intermediate
>overflowings or which of the base fixed point scalar types x is.

That is incorrect. First, a left shift is not a rotation. When the most
significant bit is lost, it's lost, and won't come back by magic.

E.g., try the value 2^(n-3) where n is the number of bits in an int.

Secondly, although I don't share your impressive math terminology and
notation I can tell you straight out that the "ring" only exists
formally for unsigned integer aritmetic. Perhaps you don't understand
the math, and/or perhaps you don't know C or C++. But don't put such
disinformation forth in the newsgroups, please.

Btw., this thread is crossposted to comp.lang.c and comp.lang.c++.

I'm posting in comp.lang.c++.

Alf P. Steinbach, Jul 20, 2003
7. ### Alf P. SteinbachGuest

On Sun, 20 Jul 2003 18:59:31 GMT, (Alf P. Steinbach) wrote:

>On Sun, 20 Jul 2003 17:09:29 GMT, (Paul Hsieh) wrote:
>
>>In article <>, says...
>>> On Sun, 20 Jul 2003 08:13:07 -0400, Robert W Hand <> wrote:
>>> >On 20 Jul 2003 01:05:40 -0700, (krazyman) wrote:
>>> >>Does anyone know a good trick to perform an integer divide by 7
>>> >>(the equivalent of x/7 in C) without using a divide? I'm familiar
>>> >>with the multiply by 7 trick (x<<3-x), and I was asked this question
>>> >>with the implication that something similar exists for divide-by-7. I
>>> >
>>> >How does (x<<3-x) work? If x, type int, has the value 10, the right
>>> >hand side is a negative number. That should be undefined behavior.
>>> >Some trick? :-( Obviously, I'm missing something.
>>>
>>> Just a parenthesis missing:
>>>
>>> (x << 3) - x = 8x - x = 7x
>>>
>>> Of course, this expression can overflow where 7*x won't...

>>
>>7*x can also overflow.

>
>NSS...
>
>
>>It just has a different overflow condition than (x << 3)-x.

>
>So what do you think I wrote above?
>
>
>
>>But if your C compiler implments ordinary 2s complement
>>mathematics (i.e., the ring Z(2**n) is embedded in the C integer operations),
>>then both expresions will yield identical results regarless of intermediate
>>overflowings or which of the base fixed point scalar types x is.

Further wrongdoings, didn't see that: "fixed point scalar types" are not
part of C/C++.

>That is incorrect. First, a left shift is not a rotation. When the most
>significant bit is lost, it's lost, and won't come back by magic.
>
>E.g., try the value 2^(n-3) where n is the number of bits in an int.

Even more, this time _mine_: the above correction is incorrect...

I'm very very sorry, crawling backwards on stomach, ass up.

It's just very surprising and unbelievable that for x = 2^k >= 2^(n-3)
one gets 7*x = -x (mod 2^n), and no information loss from the shifting.

I haven't seen that before.

No wonder the ancients thought the number 7 was special.

Alf P. Steinbach, Jul 20, 2003
8. ### Paul HsiehGuest

(Alf P. Steinbach) wrote:
> On Sun, 20 Jul 2003 17:09:29 GMT, (Paul Hsieh) wrote:
> >In article <>, says...
> >> On Sun, 20 Jul 2003 08:13:07 -0400, Robert W Hand <> wrote:
> >> >On 20 Jul 2003 01:05:40 -0700, (krazyman) wrote:
> >> >>Does anyone know a good trick to perform an integer divide by 7
> >> >>(the equivalent of x/7 in C) without using a divide? I'm familiar
> >> >>with the multiply by 7 trick (x<<3-x), and I was asked this question
> >> >>with the implication that something similar exists for divide-by-7. I
> >> >
> >> >How does (x<<3-x) work? If x, type int, has the value 10, the right
> >> >hand side is a negative number. That should be undefined behavior.
> >> >Some trick? :-( Obviously, I'm missing something.
> >>
> >> Just a parenthesis missing:
> >>
> >> (x << 3) - x = 8x - x = 7x
> >>
> >> Of course, this expression can overflow where 7*x won't...

> >
> >7*x can also overflow.

>
> NSS...
>
> >It just has a different overflow condition than (x << 3)-x.

>
> So what do you think I wrote above?

I thought you said would expression could overflow, and the other
couldn't. If you wish to make precise statement not subject to
misinterpretation, you should probably say something like one
overflows on a different domain, or value of x. This is not relevant
to my later claim of course ...

> >But if your C compiler implments ordinary 2s complement
> >mathematics (i.e., the ring Z(2**n) is embedded in the C integer
> >operations), then both expresions will yield identical results regarless of
> >intermediate overflowings or which of the base fixed point scalar types x is.

>
> That is incorrect.

You need only show one numerical example by suggesting x and what
bitness your 2s complement machine supports. I challenge you to do
this. (Even a 4 bit machine will do this correctly, for all inputs
x.)

> [...] First, a left shift is not a rotation. When the most
> significant bit is lost, it's lost, and won't come back by magic.

That is not relevant to my statement. I have not confusing rotate
with shift.

> E.g., try the value 2^(n-3) where n is the number of bits in an int.

This does not lead to to any problems. The two expressions result in

> Secondly, although I don't share your impressive math terminology

Its not impressive to someone who has taken an introduction to algebra
in college. And assuming you took and passed such a course, my
statement would immediately justify to you why I am able to so
brazenly make such a claim as to say that those two expression always
lead to identical results. There's a reason why people waste time
learning such abtract things in their education ...

> [...] and notation I can tell you straight out that the "ring" only exists
> formally for unsigned integer aritmetic.

No ... I suggest you review the properties of 2s complement
arithmetic. The signedness or unsignedness do not affect the Z(2**n)
ring properties of the *, << or - operators.

> [...] Perhaps you don't understand the math, and/or perhaps you don't know C
> or C++.

I have a master's degree in Mathematics, twice scored in the top 300
on the William Lowel Putnam examination, and qualified to write the
USAMO (top 200 or so out of 400,000 participants the US high schools.)
I am roughly speaking, in the top 0.025% of the population,
mathematically speaking. It is unlikely that I mistaken about the
simplest properties of something as trivial as Z(2**n).

As to knowing C/C++, that's not really relevant, as I explicitely said
my assumption was that I was referring to a 2s complement
implemenation.

> [...] But don't put such disinformation forth in the newsgroups, please.

is a useful and powerful thing. So are introductory college algebra
courses.

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

Paul Hsieh, Jul 23, 2003
9. ### Paul HsiehGuest

(Alf P. Steinbach) wrote in message
> It's just very surprising and unbelievable that for x = 2^k >= 2^(n-3)
> one gets 7*x = -x (mod 2^n), and no information loss from the shifting.

Just look at the numbers in bits when you do this. What's so

> I haven't seen that before.

You don't need to see any of this. Look up, or recall the definition
of a ring. Then review 2s complement. Then satisfy yourself that 2s
complement on 32 bits is a ring on Z(2**32) (with the *, +, -
operators that come with the language, and the 0 and 1 values
present.) Then satisfy yourself that x << n == x * (2**n) in this
ring. Then there is nothing else to it (well you have to subtract 1
from 8 and get 7 ... hopefully you can handle that.)

When it overflows and weird observations like the one you've just made
above miss the point.

> No wonder the ancients thought the number 7 was special.

It has nothing to do with the number 7. Just try it for other
expressions like:

5*x = (x << 3) - (x << 2) + x;

Its the same damn thing, and again, it has nothing to do with
signedness, whether or not any expression overflows, or not. So long
as you are on a 2s complement machine, it will work.

And if you need further proof, here's a list of 1000s of examples of
this kind of thing:

http://www.pobox.com/~qed/amult.html

And of course they all work.

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

Paul Hsieh, Jul 23, 2003
10. ### Alf P. SteinbachGuest

On 23 Jul 2003 13:55:56 -0700, (Paul Hsieh) wrote:

A follow-up to a posting where I erred and later corrected and
apologized for that.

> (Alf P. Steinbach) wrote:
>> On Sun, 20 Jul 2003 17:09:29 GMT, (Paul Hsieh) wrote:
>> >In article <>, says...
>> >> On Sun, 20 Jul 2003 08:13:07 -0400, Robert W Hand <> wrote:
>> >> >On 20 Jul 2003 01:05:40 -0700, (krazyman) wrote:
>> >> >>Does anyone know a good trick to perform an integer divide by 7
>> >> >>(the equivalent of x/7 in C) without using a divide? I'm familiar
>> >> >>with the multiply by 7 trick (x<<3-x), and I was asked this question
>> >> >>with the implication that something similar exists for divide-by-7. I
>> >> >
>> >> >How does (x<<3-x) work? If x, type int, has the value 10, the right
>> >> >hand side is a negative number. That should be undefined behavior.
>> >> >Some trick? :-( Obviously, I'm missing something.
>> >>
>> >> Just a parenthesis missing:
>> >>
>> >> (x << 3) - x = 8x - x = 7x
>> >>
>> >> Of course, this expression can overflow where 7*x won't...
>> >
>> >7*x can also overflow.

>>
>> NSS...
>>
>> >It just has a different overflow condition than (x << 3)-x.

>>
>> So what do you think I wrote above?

>
>I thought you said would expression could overflow, and the other
>couldn't.

Nope, I wrote that one could overflow _where_ the other couldn't.

But as it turns out that was incorrect for unsigned integers.

Do note that neither C nor C++ specify two's complement format for
signed integers, so for signed integers there is a difference.

>This does not lead to to any problems. The two expressions result in

They do for unsigned integer arithmetic.

Other languages may define signed arithmetic differently.

>> Secondly, although I don't share your impressive math terminology

>
>Its not impressive to someone who has taken an introduction to algebra
>in college. And assuming you took and passed such a course, my
>statement would immediately justify to you why I am able to so
>brazenly make such a claim as to say that those two expression always

Nope. This is not a math group, it's a pair of programming groups, and
they're not US or English national groups, but international groups. When
you use notation and/or terminology from another field, without explanation,
and probably specific to english-speaking countries, you're either
(intentionally or unintentionally) showing off, or not, uh, thinking.

Given all the spelling errors I incorrectly assumed the latter, sorry
for that.

I judged content by form, which sometimes leads to incorrect conclusions.

>No ... I suggest you review the properties of 2s complement
>arithmetic. The signedness or unsignedness do not affect the Z(2**n)
>ring properties of the *, << or - operators.

The signedness does matter in C and C++, because you're not guaranteed
a two's complement representation.

>> [...] Perhaps you don't understand the math, and/or perhaps you don't know C
>> or C++.

>
>I have a master's degree in Mathematics, twice scored in the top 300
>on the William Lowel Putnam examination, and qualified to write the
>USAMO (top 200 or so out of 400,000 participants the US high schools.)
> I am roughly speaking, in the top 0.025% of the population,
>mathematically speaking. It is unlikely that I mistaken about the
>simplest properties of something as trivial as Z(2**n).

Quite. Your problems are with communication and C/C++. My problem is
that I sometimes react to appearances, and then have to retract and
apologize, as I did; but then, we who choose to help out here don't
have all the time in the world to use for that.

>As to knowing C/C++, that's not really relevant, as I explicitely said
>my assumption was that I was referring to a 2s complement
>implemenation.

It's true that what you wrote could be interpreted as such an assumption.

But these are a C/C++ groups, where anything else is off-topic.

So if you wish to make precise statement not subject to misinterpretation,
you should probably not write things like "base fixed point scalar types".

Now I hope that the harsh first-time comment hasn't discouraged you from
helping out in this and other groups.

Just put the apologies (such as the one I posted earlier) in a special
trophy directory. ;-)

Alf P. Steinbach, Jul 23, 2003
11. ### Alf P. SteinbachGuest

On 23 Jul 2003 14:08:10 -0700, (Paul Hsieh) wrote:

> (Alf P. Steinbach) wrote in message
>> It's just very surprising and unbelievable that for x = 2^k >= 2^(n-3)
>> one gets 7*x = -x (mod 2^n), and no information loss from the shifting.

>
>Just look at the numbers in bits when you do this. What's so

It's surprising as an immediate impression, where 7 is not perceived as
2^3-1 but as something more like 5, say. But I guess in order for
something like that to be surprising it's necessary to see it real
quick and then not reflect further on it. It's not at all surprising
when it's written as 8x = 0 (mod 2^n), and of course it's true for more
than the three values I used as example above (8 values in all).

Btw., thanks for the further explanations; I don't need them, but some
people reading this may or will.

The thing about 7 and the ancients _was_ an attempt at a joke... ;-)

Cheers,

- Alf

Alf P. Steinbach, Jul 23, 2003
12. ### Stewart GordonGuest

On 23/7/03 10:08 pm (UK time), Paul Hsieh let loose these words:
<snip>
>> No wonder the ancients thought the number 7 was special.

>
>
> It has nothing to do with the number 7. Just try it for other
> expressions like:
>
> 5*x = (x << 3) - (x << 2) + x;

Is there any way in which this is any more special than the more
efficient (x<<2) + x?

Stewart.

--
My e-mail is valid but not my primary mailbox. Please keep replies on
on the 'group where everyone may benefit.

Stewart Gordon, Jul 24, 2003
13. ### Paul HsiehGuest

Stewart Gordon <> wrote:
> On 23/7/03 10:08 pm (UK time), Paul Hsieh let loose these words:
> <snip>
> >> No wonder the ancients thought the number 7 was special.

> >
> > It has nothing to do with the number 7. Just try it for other
> > expressions like:
> >
> > 5*x = (x << 3) - (x << 2) + x;

>
> Is there any way in which this is any more special than the more
> efficient (x<<2) + x?

No, my point only was that it was the same, not more efficient.

Knowing the most efficient encoding in general can be a harder problem
than you might think. First off some processors (like x86s) have
built-in support for odd things like, *3, *5, *9, *17 in single
instructions. Secondly you have consider both subtraction and
factorings as possible ways of decomposing the constant being
multiplied. In the end there is no general formula for figuring out
the fastest path.

Nevertheless, you can determine the fastest solution anyhow through
brute force:

http://www.pobox.com/~qed/amult.html

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

Paul Hsieh, Jul 25, 2003