integer multiplication

Discussion in 'C Programming' started by robert bristow-johnson, May 20, 2013.

  1. (cross posted to comp.dsp and comp.lang.c.)

    are compilers now-a-days smart enough to multiply two N-bit numbers to
    a 2N-bit result without wasting instructions in the generated machine
    code?

    like, we know for C, a long times a long is a long. but if you cast
    one of the multiplicands to (long long), and then multiply, you get a
    long long without any loss of bits. but are the compilers smart
    enough to avoid that? let


    long *h, *x, *y; // coefs, input, output ptrs
    int L; // FIR length
    int n=0;

    ....

    while(TRUE)
    {

    long long accumulator=0LL;

    for(int i=0; i<L; i++)
    {
    accumulator += ( (long long)(h) )*(x[n-i]);
    }

    long y[n++] = (long)(accumulator>>(8*sizeof(long)-1);

    }

    (sorry for what google does to the = sign.)

    it's not complete code, but i hope you can get the drift. can anyone
    comment on whether or not some particular compiler (gcc?) codes that
    to an efficient mac instruction without actually sign extending the
    value or h and doing a long long multiply?

    this had been an old irritant with C, i think the language definition
    gets that wrong, but really smart compilers should know what to do,
    no?


    r b-j
     
    robert bristow-johnson, May 20, 2013
    #1
    1. Advertising

  2. In comp.dsp robert bristow-johnson <> wrote:

    > (cross posted to comp.dsp and comp.lang.c.)


    > are compilers now-a-days smart enough to multiply two N-bit numbers to
    > a 2N-bit result without wasting instructions in the generated machine
    > code?


    (snip)

    > long *h, *x, *y; // coefs, input, output ptrs
    > int L; // FIR length
    > int n=0;
    >
    > ...
    >
    > while(TRUE)
    > {
    >
    > long long accumulator=0LL;
    >
    > for(int i=0; i<L; i++)
    > {
    > accumulator += ( (long long)(h) )*(x[n-i]);
    > }


    The only one I ever looked at this on was the IA32 gcc.

    Since IA32 doesn't have an instruction for multiplying 64 bit
    integers (with either 64 or 128 bit product) that would normally
    be done by subroutine call. But it does recognize this case.

    I would be slightly less sure for a 64 bit archtecture, which
    does have the appropriate multiply instruction.

    The way the gcc code generator works, I would expect it
    (but still check) for any 32 bit system with an appropriate
    multiply instruction.

    I never looked at any other compilers.

    -- glen
     
    glen herrmannsfeldt, May 20, 2013
    #2
    1. Advertising

  3. robert bristow-johnson

    Rob Gaddi Guest

    On Sun, 19 May 2013 20:46:11 -0700 (PDT)
    robert bristow-johnson <> wrote:

    >
    > (cross posted to comp.dsp and comp.lang.c.)
    >
    > are compilers now-a-days smart enough to multiply two N-bit numbers to
    > a 2N-bit result without wasting instructions in the generated machine
    > code?
    >
    > like, we know for C, a long times a long is a long. but if you cast
    > one of the multiplicands to (long long), and then multiply, you get a
    > long long without any loss of bits. but are the compilers smart
    > enough to avoid that? let
    >
    >
    > long *h, *x, *y; // coefs, input, output ptrs
    > int L; // FIR length
    > int n=0;
    >
    > ...
    >
    > while(TRUE)
    > {
    >
    > long long accumulator=0LL;
    >
    > for(int i=0; i<L; i++)
    > {
    > accumulator += ( (long long)(h) )*(x[n-i]);
    > }
    >
    > long y[n++] = (long)(accumulator>>(8*sizeof(long)-1);
    >
    > }
    >
    > (sorry for what google does to the = sign.)
    >
    > it's not complete code, but i hope you can get the drift. can anyone
    > comment on whether or not some particular compiler (gcc?) codes that
    > to an efficient mac instruction without actually sign extending the
    > value or h and doing a long long multiply?
    >
    > this had been an old irritant with C, i think the language definition
    > gets that wrong, but really smart compilers should know what to do,
    > no?
    >
    >
    > r b-j


    I've played with it on GCC for ARM. If you cast the input operands
    first, then at least with optimization on it gives you sensible
    results. For instance:

    inline int32_t frac_mult(int32_t a, int32_t b) {
    int64_t result = (int64_t)a * b;
    return (result >> 32);
    }

    performs a 32x32=64 multiply into a dual-register result, and simply
    ignores the register with the low half of the result.

    If you really care though, I'd go read disassembly.

    --
    Rob Gaddi, Highland Technology -- www.highlandtechnology.com
    Email address domain is currently out of order. See above to fix.
     
    Rob Gaddi, May 20, 2013
    #3
  4. robert bristow-johnson <> writes:
    > (cross posted to comp.dsp and comp.lang.c.)
    >
    > are compilers now-a-days smart enough to multiply two N-bit numbers to
    > a 2N-bit result without wasting instructions in the generated machine
    > code?
    >
    > like, we know for C, a long times a long is a long. but if you cast
    > one of the multiplicands to (long long), and then multiply, you get a
    > long long without any loss of bits. but are the compilers smart
    > enough to avoid that? let


    Keep in mind that long long is not *necessarily* twice as wide as long.
    For example, on x86_64 Linux systems, both are typically 64 bits.

    Your example would work better with int32_t and int64_t.

    > long *h, *x, *y; // coefs, input, output ptrs
    > int L; // FIR length
    > int n=0;
    >
    > ...
    >
    > while(TRUE)
    > {
    >
    > long long accumulator=0LL;
    >
    > for(int i=0; i<L; i++)
    > {
    > accumulator += ( (long long)(h) )*(x[n-i]);
    > }
    >
    > long y[n++] = (long)(accumulator>>(8*sizeof(long)-1);
    >
    > }
    >
    > (sorry for what google does to the = sign.)


    The "=" characters look fine.

    > it's not complete code, but i hope you can get the drift. can anyone
    > comment on whether or not some particular compiler (gcc?) codes that
    > to an efficient mac instruction without actually sign extending the
    > value or h and doing a long long multiply?
    >
    > this had been an old irritant with C, i think the language definition
    > gets that wrong, but really smart compilers should know what to do,
    > no?


    Certainly a conforming compiler *can* perform this optimization. If it
    can confirm that both operands of "*" are small enough (which should be
    easy in this case), then it can determine that a 32-bit by 32-bit to
    64-bit multiplication will yield the same result as a 64x64->64
    multiplication.

    I don't know which actual compilers do this. It would be easy enough to
    find out by examining the generated assembl code (and being more
    familiar with the instruction set than I am).

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Working, but not speaking, for JetHead Development, Inc.
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, May 20, 2013
    #4
  5. robert bristow-johnson wrote:

    >(cross posted to comp.dsp and comp.lang.c.)
    >
    >are compilers now-a-days smart enough to multiply two N-bit numbers to
    >a 2N-bit result without wasting instructions in the generated machine
    >code?
    >
    >
    >

    I took a similar example:


    long x[200], y[200];

    foo(int L)
    {
    int i;
    long long accumulator;

    accumulator = 0;
    for(i=0;i<L;i++) {
    accumulator = (long long)x * y;
    }

    bar(accumulator);
    }

    and compiled it with the Dignus C compiler (in C89 mode) with
    optimizations, it generated this code:

    * *** accumulator = (long long)x * y;
    L 3,@lit_9_3
    L 5,0(2,3)
    M 4,800(2,3)
    STM 4,5,88(13) ; accumulator


    That used the z/Architecture M instruction (MULTIPLY) which multiplies
    two signed 32-bit values producing a signed 64-bit result.

    To walk thru this, the first instruction loads register #3 with a pointer
    to that data section, the array 'x' happens to be at offset 0 in that
    section,
    The second instruction loads register #5 with x (the value 4*i has been
    strength-reduced and is in register #2). The next instruction is the
    multiply isntruction - M. That is multipliying the 32-bit value in
    register #3
    with the 32-bit value in memory at 800(2,3) - which is y. The 64-bit
    result
    goes into register #4 and #5. Those two registers are then stored into
    'accumulator'.

    - Dave Rivers -

    --
    Work: (919) 676-0847
    Get your mainframe programming tools at http://www.dignus.com
     
    Thomas David Rivers, May 20, 2013
    #5
  6. On May 20, 1:31 pm, Keith Thompson <> wrote:
    > robert bristow-johnson <> writes:
    >
    > > (sorry for what google does to the = sign.)

    >
    > The "=" characters look fine.
    >


    boy, i just don't get it with Google Groups. when do they toss in the
    "3D" after the "=" sign and when don't they? if you go to the other
    thread (about interpolation), all of my "=" symbols have a "3D"
    inserted afterward. why not here?

    thanks everyone for responding. it indeed does look like smart
    compilers do exist that do not do the sign extension and unnecessary
    multiword multiplication

    r b-j
     
    robert bristow-johnson, May 21, 2013
    #6
  7. robert bristow-johnson

    Nobody Guest

    On Mon, 20 May 2013 22:00:38 -0700, robert bristow-johnson wrote:

    >> > (sorry for what google does to the = sign.)

    >>
    >> The "=" characters look fine.
    >>

    >
    > boy, i just don't get it with Google Groups. when do they toss in the
    > "3D" after the "=" sign and when don't they? if you go to the other
    > thread (about interpolation), all of my "=" symbols have a "3D"
    > inserted afterward. why not here?


    "= 3D" is quoted-printable (QP) encoding (the equals sign has code 3D in
    hex).

    Some clients will always send messages using QP, others will use it if the
    message contains any non-ASCII characters. Because QP uses the equals sign
    as an escape character, the equals sign itself must always be encoded when
    QP is used.

    The relevant message headers are:

    MIME-Version: 1.0
    Content-Type: text/plain; charset=ISO-8859-1
    Content-Transfer-Encoding: quoted-printable

    If QP was used but any of these headers are missing, QP probably won't be
    decoded and you'll see "= 3D" instead. If the reader doesn't support MIME
    (it was originally designed for email, not usenet), you'll see the
    behaviour with any message encoded using QP.

    Also, whether or not the message uses QP may depend upon the route taken
    by the message. Nowadays, most news software (servers and clients) is
    8-bit clean, so posting raw ISO-8859-* or UTF-8 will probably work. But
    some servers will automatically convert 8-bit data to QP (or even base-64)
    to be on the safe side.
     
    Nobody, May 21, 2013
    #7
  8. In comp.dsp Nobody <> wrote:

    (snip)

    > "= 3D" is quoted-printable (QP) encoding (the equals sign has
    > code 3D in hex).


    More fun is that $ is =24, and if used in e-mail, for example
    paypal telling you how much you spent, and if you don't think
    about it, it turns $3.00 into =243.00, and $15.00 into =2415.00!

    -- glen
     
    glen herrmannsfeldt, May 21, 2013
    #8
  9. In comp.dsp David Brown <> wrote:
    > On 20/05/13 05:46, robert bristow-johnson wrote:
    >> (cross posted to comp.dsp and comp.lang.c.)
    >> are compilers now-a-days smart enough to multiply two N-bit
    >> numbers to a 2N-bit result without wasting instructions in
    >> the generated machine code?


    (snip)
    >> long *h, *x, *y; // coefs, input, output ptrs
    >> int L; // FIR length
    >> int n=0;
    >> ...

    (snip)
    >> long long accumulator=0LL;

    (snip)
    >> accumulator += ( (long long)(h) )*(x[n-i]);


    (snip)
    > In general, yes - compilers are smart enough to do this. But it will
    > vary between compilers (including different targets for gcc), it may
    > vary according to the widths of the operands, and it will often vary
    > according to compiler flags (if you don't enable optimisation, expect to
    > get poor code).


    I know that 32 bit systems, with a 32x32=64 multiply, do it,
    but I haven't looked yet what any 64 bit systems do.
    If they have a 64x64=128 multiply, do they use that?

    -- glen
     
    glen herrmannsfeldt, May 21, 2013
    #9
    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. Christopher Dyken

    32x32 and 64x64 signed integer multiplication

    Christopher Dyken, Feb 17, 2004, in forum: C Programming
    Replies:
    18
    Views:
    1,458
    glen herrmannsfeldt
    Feb 24, 2004
  2. Pesso

    integer multiplication

    Pesso, Mar 10, 2007, in forum: C Programming
    Replies:
    31
    Views:
    1,064
    CBFalconer
    Mar 12, 2007
  3. helPlease

    long integer multiplication

    helPlease, Apr 29, 2007, in forum: C Programming
    Replies:
    8
    Views:
    452
    osmium
    Apr 29, 2007
  4. helPlease

    long integer multiplication

    helPlease, Apr 30, 2007, in forum: C Programming
    Replies:
    5
    Views:
    399
    Chris Dollin
    Apr 30, 2007
  5. William Hughes
    Replies:
    13
    Views:
    1,285
    Ben Bacarisse
    Mar 15, 2010
Loading...

Share This Page