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

# Re: integer divide by 7 trick?

Alf P. Steinbach
Guest
Posts: n/a

 07-23-2003
On 23 Jul 2003 14:08:10 -0700, http://www.velocityreviews.com/forums/(E-Mail Removed) (Paul Hsieh) wrote:

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

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

Stewart Gordon
Guest
Posts: n/a

 07-24-2003
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.

Paul Hsieh
Guest
Posts: n/a

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