Re: integer divide by 7 trick?

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

  1. 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
    #1
    1. Advertising

  2. 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
    #2
    1. Advertising

  3. Robert W Hand

    Andre Guest

    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
    #3
  4. Robert W Hand

    Andre Guest

    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
    #4
  5. Robert W Hand

    Paul Hsieh Guest

    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
    #5
  6. 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
    #6
  7. 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
    #7
  8. Robert W Hand

    Paul Hsieh Guest

    (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
    the same answer, of course.

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


    Pot, Kettle, Black. Your dead wrong in your analysis. 2s complement
    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
    #8
  9. Robert W Hand

    Paul Hsieh Guest

    (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
    surprising about this?

    > 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
    #9
  10. 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
    >the same answer, of course.


    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
    >lead to identical results.


    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
    #10
  11. 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
    >surprising about this?


    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
    #11
  12. 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
    #12
  13. Robert W Hand

    Paul Hsieh Guest

    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
    #13
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. MG
    Replies:
    5
    Views:
    426
    Christian Bau
    Jul 22, 2003
  2. JS
    Replies:
    1
    Views:
    320
    Peter van Merkerk
    Jul 22, 2003
  3. yvan joffre

    Re: integer divide by 7 trick?

    yvan joffre, Jul 25, 2003, in forum: C++
    Replies:
    3
    Views:
    286
    Stewart Gordon
    Jul 25, 2003
  4. MG

    Re: integer divide by 7 trick?

    MG, Jul 20, 2003, in forum: C Programming
    Replies:
    5
    Views:
    3,907
    Christian Bau
    Jul 22, 2003
  5. Robert W Hand

    Re: integer divide by 7 trick?

    Robert W Hand, Jul 20, 2003, in forum: C Programming
    Replies:
    12
    Views:
    604
    Paul Hsieh
    Jul 25, 2003
Loading...

Share This Page