multiplication by 7

[sudharsan]

give a fast way to multiply a number by 7

[pemo]

Re: multiplication by 7

sudharsan wrote:[color=blue]
> give a fast way to multiply a number by 7[/color]

int n = 1;

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


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

[Vladimir S. Oka]

Re: multiplication by 7


sudharsan wrote:[color=blue]
> give a fast way to multiply a number by 7[/color]

Think along the lines of:

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

How is this related to C?

--
BR, Vladimir

[Tim Prince]

Re: multiplication by 7

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

[Vladimir S. Oka]

Re: multiplication by 7


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

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

[pemo]

Re: multiplication by 7

Vladimir S. Oka wrote:[color=blue]
> Tim Prince wrote:[color=green]
>> Vladimir S. Oka wrote:[color=darkred]
>>> 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?
>>>[/color]
>> Most C compilers know a reasonable compromise between generated code
>> size and speed for their target architecture.[/color]
>
> 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. ;-)[/color]

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

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

[Vladimir S. Oka]

Re: multiplication by 7


pemo wrote:[color=blue]
> Vladimir S. Oka wrote:[color=green]
> > Tim Prince wrote:[color=darkred]
> >> 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.[/color]
> >
> > 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. ;-)[/color]
>
> If you're thinking of 'shifting' - how's that going to work with floats?[/color]

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

[pablo reda]

Re: multiplication by 7

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

[Tim Prince]

Re: multiplication by 7

pablo reda wrote:[color=blue]
> x*7 = (x<<2)+(x<<1)+x
>[/color]
slow on P4

[Lew Pitcher]

Re: multiplication by 7

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

sudharsan wrote:[color=blue]
> give a fast way to multiply a number by 7[/color]

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/dJtagVFX4UWr64R AspvAKCtNLjd2mW qpBTcvHuV5P/Ut1PuiwCg3WdJ
+81jNXo/S08/426EtxBDK3Y=
=I4ET
-----END PGP SIGNATURE-----

[pemo]

Re: multiplication by 7

Vladimir S. Oka wrote:[color=blue]
> pemo wrote:[color=green]
>> Vladimir S. Oka wrote:[color=darkred]
>>> 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. ;-)[/color]
>>
>> If you're thinking of 'shifting' - how's that going to work with
>> floats?[/color]
>
> I was, yes. It won't, but I think the answer was at least as good as
> the question.[/color]

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


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

[Richard G. Riley]

Re: multiplication by 7

On 2006-02-23, Tim Prince <tprince@nospam computer.org> wrote:[color=blue]
> pablo reda wrote:[color=green]
>> x*7 = (x<<2)+(x<<1)+x
>>[/color]
> slow on P4[/color]


how does *8 -1 come out

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

?

Useless for floats of course.

--
Remove evomer to reply

[pete]

Re: multiplication by 7

Lew Pitcher wrote:[color=blue]
>
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> sudharsan wrote:[color=green]
> > give a fast way to multiply a number by 7[/color]
>
> 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;[/color]

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

((number << 3) - number)

--
pete

[Chris Dollin]

Re: multiplication by 7

sudharsan wrote:
[color=blue]
> give a fast way to multiply a number by 7[/color]

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

[Ian Malone]

Re: multiplication by 7

pete wrote:[color=blue]
> Lew Pitcher wrote:[/color]
[color=blue][color=green]
>> sudharsan wrote:[color=darkred]
>>> give a fast way to multiply a number by 7[/color]
>> P'haps you are looking for something other than
>> number = number * 7;
>>[/color][/color]
[color=blue][color=green]
>>
>> 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;[/color]
>
> If I was looking for a shifty way, it would be:
>
> ((number << 3) - number)
>[/color]

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

--
imalone