multiplication by 7

Discussion in 'C Programming' started by sudharsan, Feb 23, 2006.

1. sudharsanGuest

give a fast way to multiply a number by 7

sudharsan, Feb 23, 2006

2. pemoGuest

sudharsan wrote:
> give a fast way to multiply a number by 7

int n = 1;

n *= 7; // Just a few clocks on my system!

--
==============
*Not a pedant*
==============

pemo, Feb 23, 2006

3. Vladimir S. OkaGuest

sudharsan wrote:
> give a fast way to multiply a number by 7

Think along the lines of:

x*7 = x*(4+2+1)

How is this related to C?

--
BR, Vladimir

Vladimir S. Oka, Feb 23, 2006
4. Tim PrinceGuest

Vladimir S. Oka wrote:
> sudharsan wrote:
>
>>give a fast way to multiply a number by 7

>
>
> Think along the lines of:
>
> x*7 = x*(4+2+1)
>
> How is this related to C?
>

Most C compilers know a reasonable compromise between generated code
size and speed for their target architecture.

Tim Prince, Feb 23, 2006
5. Vladimir S. OkaGuest

Tim Prince wrote:
> Vladimir S. Oka wrote:
> > sudharsan wrote:
> >
> >>give a fast way to multiply a number by 7

> >
> >
> > Think along the lines of:
> >
> > x*7 = x*(4+2+1)
> >
> > How is this related to C?
> >

> Most C compilers know a reasonable compromise between generated code
> size and speed for their target architecture.

I know that. The OP's question is obviously a homework or some-such. If
that's the case it'll still be useful for him to try and implement the
above. For good measure, I probably should have added The First Rule of
Optimisation:

1. DON'T

Other rules, for more advanced users can be found elsegroup. ;-)

--
BR, Vladimir

Vladimir S. Oka, Feb 23, 2006
6. pemoGuest

Vladimir S. Oka wrote:
> Tim Prince wrote:
>> Vladimir S. Oka wrote:
>>> sudharsan wrote:
>>>
>>>> give a fast way to multiply a number by 7
>>>
>>>
>>> Think along the lines of:
>>>
>>> x*7 = x*(4+2+1)
>>>
>>> How is this related to C?
>>>

>> Most C compilers know a reasonable compromise between generated code
>> size and speed for their target architecture.

>
> I know that. The OP's question is obviously a homework or some-such.
> If that's the case it'll still be useful for him to try and implement
> the above. For good measure, I probably should have added The First
> Rule of Optimisation:
>
> 1. DON'T
>
> Other rules, for more advanced users can be found elsegroup. ;-)

If you're thinking of 'shifting' - how's that going to work with floats?

--
==============
*Not a pedant*
==============

pemo, Feb 23, 2006
7. Vladimir S. OkaGuest

pemo wrote:
> Vladimir S. Oka wrote:
> > Tim Prince wrote:
> >> Vladimir S. Oka wrote:
> >>> sudharsan wrote:
> >>>
> >>>> give a fast way to multiply a number by 7
> >>>
> >>>
> >>> Think along the lines of:
> >>>
> >>> x*7 = x*(4+2+1)
> >>>
> >>> How is this related to C?
> >>>
> >> Most C compilers know a reasonable compromise between generated code
> >> size and speed for their target architecture.

> >
> > I know that. The OP's question is obviously a homework or some-such.
> > If that's the case it'll still be useful for him to try and implement
> > the above. For good measure, I probably should have added The First
> > Rule of Optimisation:
> >
> > 1. DON'T
> >
> > Other rules, for more advanced users can be found elsegroup. ;-)

>
> If you're thinking of 'shifting' - how's that going to work with floats?

I was, yes. It won't, but I think the answer was at least as good as
the question.

I could have offered 42 as well, choosing the `number` to be 6. ;-)

--
BR, Vladimir

Vladimir S. Oka, Feb 23, 2006
8. pablo redaGuest

x*7 = (x<<2)+(x<<1)+x

pablo reda, Feb 23, 2006
9. Lew PitcherGuest

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

sudharsan wrote:
> give a fast way to multiply a number by 7

P'haps you are looking for something other than
number = number * 7;

If so, then you could use shifts and additions

In algebra, you learn that
N * 7 = N * (4 + 2 + 1)
= (N * 4) + (N * 2) + (N * 1)

In binary maths, multiplication by a power of two can be accomplished with an
integer number of left shifts
N * 4 = N << 2
N * 2 = N << 1
N * 1 = N << 0

Substituting for common values gives
N * 7 = (N << 2) + (N << 1) + (N << 0)

Inverting order for algorithmic efficiency gives
N * 7 = (N << 0) + (N << 1) + (N << 2)

You can code this as
unsigned int number = 3;

number = (number) + (number << 1) + (number << 2);

But, this is likely to be /less/ efficient than
number = number * 7;

- --
Lew Pitcher
IT Specialist, Corporate Technology Solutions,
Enterprise Technology Solutions, TD Bank Financial Group

(Opinions expressed are my own, not my employers')
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (MingW32)

iD8DBQFD/dJtagVFX4UWr64RAspvAKCtNLjd2mWqpBTcvHuV5P/Ut1PuiwCg3WdJ
+81jNXo/S08/426EtxBDK3Y=
=I4ET
-----END PGP SIGNATURE-----

Lew Pitcher, Feb 23, 2006
10. Tim PrinceGuest

pablo reda wrote:
> x*7 = (x<<2)+(x<<1)+x
>

slow on P4

Tim Prince, Feb 23, 2006
11. pemoGuest

Vladimir S. Oka wrote:
> pemo wrote:
>> Vladimir S. Oka wrote:
>>> Tim Prince wrote:
>>>> Vladimir S. Oka wrote:
>>>>> sudharsan wrote:
>>>>>
>>>>>> give a fast way to multiply a number by 7
>>>>>
>>>>>
>>>>> Think along the lines of:
>>>>>
>>>>> x*7 = x*(4+2+1)
>>>>>
>>>>> How is this related to C?
>>>>>
>>>> Most C compilers know a reasonable compromise between generated
>>>> code size and speed for their target architecture.
>>>
>>> I know that. The OP's question is obviously a homework or some-such.
>>> If that's the case it'll still be useful for him to try and
>>> implement the above. For good measure, I probably should have added
>>> The First Rule of Optimisation:
>>>
>>> 1. DON'T
>>>
>>> Other rules, for more advanced users can be found elsegroup. ;-)

>>
>> If you're thinking of 'shifting' - how's that going to work with
>> floats?

>
> I was, yes. It won't, but I think the answer was at least as good as
> the question.

I agree - I was being more curious than I was critical.

--
==============
*Not a pedant*
==============

pemo, Feb 23, 2006
12. Richard G. RileyGuest

On 2006-02-23, Tim Prince <> wrote:
> pablo reda wrote:
>> x*7 = (x<<2)+(x<<1)+x
>>

> slow on P4

how does *8 -1 come out

e.g x=(x<<3)-x;

?

Useless for floats of course.

--
Remove evomer to reply

Richard G. Riley, Feb 23, 2006
13. peteGuest

Lew Pitcher wrote:
>
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> sudharsan wrote:
> > give a fast way to multiply a number by 7

>
> P'haps you are looking for something other than
> number = number * 7;
>
> If so, then you could use shifts and additions
>
> In algebra, you learn that
> N * 7 = N * (4 + 2 + 1)
> = (N * 4) + (N * 2) + (N * 1)
>
> In binary maths, multiplication by a power of two can be accomplished with an
> integer number of left shifts
> N * 4 = N << 2
> N * 2 = N << 1
> N * 1 = N << 0
>
> Substituting for common values gives
> N * 7 = (N << 2) + (N << 1) + (N << 0)
>
> Inverting order for algorithmic efficiency gives
> N * 7 = (N << 0) + (N << 1) + (N << 2)
>
> You can code this as
> unsigned int number = 3;
>
> number = (number) + (number << 1) + (number << 2);
>
> But, this is likely to be /less/ efficient than
> number = number * 7;

If I was looking for a shifty way, it would be:

((number << 3) - number)

--
pete

pete, Feb 23, 2006
14. Chris DollinGuest

sudharsan wrote:

> give a fast way to multiply a number by 7

Use the `*` operator: aNumber * 7.

If there's a fast way to implement this, /the compiler's code
generator will likely already know it/. Dinking around with
shifts is likely to make its job harder.

[As a shifty aside, if aNumber * 8 won't overflow, and if
you have VERY GOOD reason to believe the compiler is worse
at multiplication than at shifting, and that the underlying
machine can do more-than-one-bit shifts efficiently, observe:

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

--
Chris "was stirred, now shaken" Dollin
RIP Andreas "G'Kar" Katsulas, May 1946 - February 2006

Chris Dollin, Feb 23, 2006
15. Ian MaloneGuest

pete wrote:
> Lew Pitcher wrote:

>> sudharsan wrote:
>>> give a fast way to multiply a number by 7

>> P'haps you are looking for something other than
>> number = number * 7;
>>

>>
>> You can code this as
>> unsigned int number = 3;
>>
>> number = (number) + (number << 1) + (number << 2);
>>
>> But, this is likely to be /less/ efficient than
>> number = number * 7;

>
> If I was looking for a shifty way, it would be:
>
> ((number << 3) - number)
>

I'd wondered about that: does it have funny overflow behaviour
(ie different to that of 7*number)?

--
imalone

Ian Malone, Feb 23, 2006
16. peteGuest

Ian Malone wrote:
>
> pete wrote:
> > Lew Pitcher wrote:

>
> >> sudharsan wrote:
> >>> give a fast way to multiply a number by 7
> >> P'haps you are looking for something other than
> >> number = number * 7;
> >>

>
> >>
> >> You can code this as
> >> unsigned int number = 3;
> >>
> >> number = (number) + (number << 1) + (number << 2);
> >>
> >> But, this is likely to be /less/ efficient than
> >> number = number * 7;

> >
> > If I was looking for a shifty way, it would be:
> >
> > ((number << 3) - number)
> >

>
> I'd wondered about that: does it have funny overflow behaviour
> (ie different to that of 7*number)?

Yes.

--
pete

pete, Feb 23, 2006
17. Mike WahlerGuest

"sudharsan" <> wrote in message
news:...
> give a fast way to multiply a number by 7

Use a calculator.

-Mike

Mike Wahler, Feb 23, 2006
18. Richard TobinGuest

In article <>,
pablo reda <> wrote:

>x*7 = (x<<2)+(x<<1)+x

Your compiler is likely to know better than you whether this is a good
optimisation. (You may want to choose a type such as unsigned int to let
it know whether x can be negative.)

-- Richard

Richard Tobin, Feb 23, 2006
19. Pedro GracaGuest

sudharsan wrote:
> give a fast way to multiply a number by 7

Another approach (I have no idea if it's any better than any other)

n_times_seven = n + n + n + n + n + n + n;

--
If you're posting through Google read <http://cfaj.freeshell.org/google>

Pedro Graca, Feb 23, 2006
20. Christian BauGuest

In article <>,
"pablo reda" <> wrote:

> x*7 = (x<<2)+(x<<1)+x

On many compilers

x = x * 7;

will produce shorter and faster code than

x = (x << 2) + (x << 1) + x;

Christian Bau, Feb 23, 2006

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.