Velocity Reviews > C++ > Re: integer divide by 7 trick?

# Re: integer divide by 7 trick?

Robert W Hand
Guest
Posts: n/a

 07-20-2003
On 20 Jul 2003 01:05:40 -0700, http://www.velocityreviews.com/forums/(E-Mail Removed) (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

Alf P. Steinbach
Guest
Posts: n/a

 07-20-2003
On Sun, 20 Jul 2003 08:13:07 -0400, Robert W Hand <(E-Mail Removed)> wrote:

>On 20 Jul 2003 01:05:40 -0700, (E-Mail Removed) (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
Guest
Posts: n/a

 07-20-2003
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, (E-Mail Removed) (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
Guest
Posts: n/a

 07-20-2003
Ah.

Alf P. Steinbach wrote:
> On Sun, 20 Jul 2003 08:13:07 -0400, Robert W Hand <(E-Mail Removed)> wrote:
>
>
>>On 20 Jul 2003 01:05:40 -0700, (E-Mail Removed) (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...
>

Paul Hsieh
Guest
Posts: n/a

 07-20-2003
In article <(E-Mail Removed)>, (E-Mail Removed) says...
> On Sun, 20 Jul 2003 08:13:07 -0400, Robert W Hand <(E-Mail Removed)> wrote:
> >On 20 Jul 2003 01:05:40 -0700, (E-Mail Removed) (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/

Alf P. Steinbach
Guest
Posts: n/a

 07-20-2003
On Sun, 20 Jul 2003 17:09:29 GMT, (E-Mail Removed) (Paul Hsieh) wrote:

>In article <(E-Mail Removed)>, (E-Mail Removed) says...
>> On Sun, 20 Jul 2003 08:13:07 -0400, Robert W Hand <(E-Mail Removed)> wrote:
>> >On 20 Jul 2003 01:05:40 -0700, (E-Mail Removed) (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
Guest
Posts: n/a

 07-20-2003
On Sun, 20 Jul 2003 18:59:31 GMT, (E-Mail Removed) (Alf P. Steinbach) wrote:

>On Sun, 20 Jul 2003 17:09:29 GMT, (E-Mail Removed) (Paul Hsieh) wrote:
>
>>In article <(E-Mail Removed)>, (E-Mail Removed) says...
>>> On Sun, 20 Jul 2003 08:13:07 -0400, Robert W Hand <(E-Mail Removed)> wrote:
>>> >On 20 Jul 2003 01:05:40 -0700, (E-Mail Removed) (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.

Paul Hsieh
Guest
Posts: n/a

 07-23-2003
(E-Mail Removed) (Alf P. Steinbach) wrote:
> On Sun, 20 Jul 2003 17:09:29 GMT, (E-Mail Removed) (Paul Hsieh) wrote:
> >In article <(E-Mail Removed)>, (E-Mail Removed) says...
> >> On Sun, 20 Jul 2003 08:13:07 -0400, Robert W Hand <(E-Mail Removed)> wrote:
> >> >On 20 Jul 2003 01:05:40 -0700, (E-Mail Removed) (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
Guest
Posts: n/a

 07-23-2003
(E-Mail Removed) (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/

Alf P. Steinbach
Guest
Posts: n/a

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

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

>(E-Mail Removed) (Alf P. Steinbach) wrote:
>> On Sun, 20 Jul 2003 17:09:29 GMT, (E-Mail Removed) (Paul Hsieh) wrote:
>> >In article <(E-Mail Removed)>, (E-Mail Removed) says...
>> >> On Sun, 20 Jul 2003 08:13:07 -0400, Robert W Hand <(E-Mail Removed)> wrote:
>> >> >On 20 Jul 2003 01:05:40 -0700, (E-Mail Removed) (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.

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post ledinhkha@gmail.com VHDL 2 12-15-2005 08:06 AM yvan joffre C++ 3 07-25-2003 03:03 PM JS C++ 1 07-22-2003 09:05 AM MG C++ 5 07-22-2003 07:33 AM MG C Programming 5 07-22-2003 07:33 AM