multiplication by 7

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

  1. sudharsan

    sudharsan Guest

    give a fast way to multiply a number by 7
    sudharsan, Feb 23, 2006
    #1
    1. Advertising

  2. sudharsan

    pemo Guest

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

  3. 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
    #3
  4. sudharsan

    Tim Prince Guest

    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
    #4
  5. 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
    #5
  6. sudharsan

    pemo Guest

    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
    #6
  7. 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
    #7
  8. sudharsan

    pablo reda Guest

    x*7 = (x<<2)+(x<<1)+x
    pablo reda, Feb 23, 2006
    #8
  9. sudharsan

    Lew Pitcher Guest

    -----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
    #9
  10. sudharsan

    Tim Prince Guest

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

    slow on P4
    Tim Prince, Feb 23, 2006
    #10
  11. sudharsan

    pemo Guest

    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
    #11
  12. 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
    #12
  13. sudharsan

    pete Guest

    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
    #13
  14. sudharsan

    Chris Dollin Guest

    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
    #14
  15. sudharsan

    Ian Malone Guest

    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
    #15
  16. sudharsan

    pete Guest

    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
    #16
  17. sudharsan

    Mike Wahler Guest

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


    Use a calculator.

    -Mike
    Mike Wahler, Feb 23, 2006
    #17
  18. 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
    #18
  19. sudharsan

    Pedro Graca Guest

    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
    #19
  20. 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
    #20
    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. walala
    Replies:
    2
    Views:
    2,308
    joris
    Mar 24, 2010
  2. Patrick
    Replies:
    1
    Views:
    1,200
    Jerzy
    Nov 30, 2004
  3. Nisheeth

    multiplication prob

    Nisheeth, Mar 31, 2005, in forum: VHDL
    Replies:
    1
    Views:
    622
    Jonathan Bromley
    Mar 31, 2005
  4. Weng Tianxiang
    Replies:
    4
    Views:
    3,031
    Weng Tianxiang
    Apr 7, 2005
  5. William Hughes
    Replies:
    13
    Views:
    1,203
    Ben Bacarisse
    Mar 15, 2010
Loading...

Share This Page