multiplication by 7

T

Tim Prince

Vladimir said:
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.
 
V

Vladimir S. Oka

Tim said:
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. ;-)
 
P

pemo

Vladimir said:
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?
 
V

Vladimir S. Oka

pemo said:
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. ;-)
 
L

Lew Pitcher

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
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-----
 
P

pete

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


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)
 
C

Chris Dollin

sudharsan said:
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
]
 
I

Ian Malone

pete said:
Lew Pitcher wrote:

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)?
 
R

Richard Tobin

pablo reda said:
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
 
P

Pedro Graca

sudharsan said:
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;
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,906
Latest member
SkinfixSkintag

Latest Threads

Top