Re: How multiply two __int64 ...

Discussion in 'C Programming' started by Jon, Nov 6, 2010.

  1. Jon

    Jon Guest

    Kappa wrote:
    > Hi,
    >
    > I was wondering if someone has already written a routine to multiply
    > two __int64 for obtain a __int128.
    >
    > Can someone help me ?
    >


    It is "straightforward" (akin to learning math in gradeschool) to
    implement multi-precision arithmetic in (x86) assembly language (if not
    (re)educational). Links to alternatives here for the "faint of heart":
    http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic#Libraries
    Jon, Nov 6, 2010
    #1
    1. Advertising

  2. Jon

    Bartc Guest

    "Kappa" <_NO_SPAM> wrote in message
    news:4cd518d6$0$27968$...
    > Hi Jon,
    >
    >> It is "straightforward" (akin to learning math in gradeschool) to
    >> implement multi-precision arithmetic in (x86) assembly language (if not
    >> (re)educational). Links to alternatives here for the "faint of heart":
    >> http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic#Libraries

    >
    > You're not the only one who knows the theory of "multiplication". I
    > already have multiplied two __int64 to obtain a result to 128 bits. I
    > wondered if the compilers are "ready" for this type of multiplication.
    > Nothing more.


    (I wonder why I read your original post as wanting to multiply two 128-bit
    quantities? Odd that I misread it on my big screen, but read correctly on
    this tiny netbook..)

    Anyway, my comments on 256/128/64-bits probably apply just as well to
    128/64/32-bits... but it seems you've solved the problem now.

    In general, it's awkward to get a programming language to give you a 2N-bit
    result when you multiply two N-bit numbers (the simplest way is to just
    multiply, inefficiently, with 2N-bits anyway, and assume the result also
    fits in 2N-bits).

    One way might be to just use a special operator for that, but it's more of a
    language rather than compiler problem. A compiler could probably do this
    special widening multiply when it sees, for example, a128=b64*c64, but then
    some might expect the result to be clipped to the smaller width as seems to
    happen now with a64=b32*b32.

    It's a similar problem to getting dividend and remainder of a/b in one
    operation, or sin and cos together.

    --
    bartc
    Bartc, Nov 7, 2010
    #2
    1. Advertising

  3. Bartc wrote:
    > In general, it's awkward to get a programming language to give you a 2N-bit
    > result when you multiply two N-bit numbers (the simplest way is to just
    > multiply, inefficiently, with 2N-bits anyway, and assume the result also
    > fits in 2N-bits).


    True, but any decent optimizing compiler should recognize this idiom and
    use the efficient widening multiply instruction (if the target
    architecture supports such an instruction, of course).

    > It's a similar problem to getting dividend and remainder of a/b in one
    > operation,


    There are library functions for that in C99 (div() et al.). Of course,
    a compiler is free to implement those functions as built-ins.

    > or sin and cos together.


    Again, at least some optimizing compilers should be able to use the
    appropriate instruction if both sin() and cos() have the same variable
    as argument.
    --
    Marcin Grzegorczyk
    Marcin Grzegorczyk, Nov 7, 2010
    #3
  4. Jon

    Eric Sosman Guest

    [OT] Re: How multiply two __int64 ...

    On 11/7/2010 6:18 PM, Bartc wrote:
    > [...]
    > In general, it's awkward to get a programming language to give you a 2N-bit
    > result when you multiply two N-bit numbers (the simplest way is to just
    > multiply, inefficiently, with 2N-bits anyway, and assume the result also
    > fits in 2N-bits).


    It always will. The operands of greatest magnitude will be no
    worse than -(2**(N-1)), which squares to 2**(2N-2), and a 2N-bit
    type is good to at least ±((2**(2N-1))-1).

    > One way might be to just use a special operator for that, but it's more of a
    > language rather than compiler problem.


    Long ago I used a language that had two integer multiplication
    operators:

    * multiplied two signed two's complement 16-bit numbers and
    gave a product in the same form, possibly overflowing

    '*' interpreted its two 16-bit operands as unsigned and gave
    a 32-bit unsigned product, with no overflow possible

    One use of the latter was to generate random numbers in an integer
    range, with (paraphrasing):

    int16 limit = 42;
    int16 value = (int16)( (rand() '*' limit) >> 16);

    Still not as good as a rejection method, but quite a lot better
    than the `rand() % limit' one so frequently sees in C.

    > A compiler could probably do this
    > special widening multiply when it sees, for example, a128=b64*c64, but then
    > some might expect the result to be clipped to the smaller width as seems to
    > happen now with a64=b32*b32.


    C uses "local context" rather than "statement context" to decide
    how to carry out arithmetic: The rules for applying an operator take
    into account only the operator and its operands, not what will happen
    to the result later. That leads to the infelicity you mention, but it
    avoids what might be a worse problem:

    // assume an "eventual use governs evaluation" rule
    int i;
    double d;
    i = 5 / 8; // int destination, integer rules, zero
    d = 5 / 8; // double destination, double rules, 0.525
    i = d = 5 / 8; // Mister Gumby, my brain hurts!

    > It's a similar problem to getting dividend and remainder of a/b in one
    > operation, or sin and cos together.


    ???

    --
    Eric Sosman
    lid
    Eric Sosman, Nov 8, 2010
    #4
  5. Jon

    Eric Sosman Guest

    Re: [OT] Re: How multiply two __int64 ...

    On 11/7/2010 7:04 PM, Eric Sosman wrote:
    > [...]
    > // assume an "eventual use governs evaluation" rule
    > int i;
    > double d;
    > i = 5 / 8; // int destination, integer rules, zero
    > d = 5 / 8; // double destination, double rules, 0.525


    On early-model Pentium processors, obviously. (Sigh.)

    --
    Eric Sosman
    lid
    Eric Sosman, Nov 8, 2010
    #5
  6. Jon

    Bartc Guest

    Re: [OT] Re: How multiply two __int64 ...

    "Eric Sosman" <> wrote in message
    news:ib7evn$5ac$-september.org...
    > On 11/7/2010 6:18 PM, Bartc wrote:


    >> It's a similar problem to getting dividend and remainder of a/b in one
    >> operation, or sin and cos together.

    >
    > ???


    (Where the hardware returns an extended or multiple result that is awkward
    to utilise in a language.

    So on x86 at least, a/b also gives you the remainder, And the 'fsincos'
    instruction gives you both sin and cos more efficiently than separate
    calculations.)

    --
    Bartc
    Bartc, Nov 8, 2010
    #6
  7. Re: [OT] Re: How multiply two __int64 ...

    On Sun, 07 Nov 2010 19:04:06 -0500, Eric Sosman
    <> wrote:
    <snip: multiply two Nbit numbers fits in 2Nbits>

    > Long ago I used a language that had two integer multiplication
    > operators:
    >
    > * multiplied two signed two's complement 16-bit numbers and
    > gave a product in the same form, possibly overflowing
    >
    > '*' interpreted its two 16-bit operands as unsigned and gave
    > a 32-bit unsigned product, with no overflow possible
    >

    If I recognize that right, conversely for divisions: s16 / s16 -> s16
    always fits except any / 0 and -32768 / -1, while u32 '/' u16 -> u16
    with possible overflow. The underlying machine operation for u32/u16
    internally produced both quotient and remainder also u16 always fits,
    like C div(), but TAL could get both only by using (inline) assembler.
    The signed forms, only, also handled 32bit and (probably) 64bit, an
    annoying asymmetry not relevant to the point(s) here.

    > One use of the latter was to generate random numbers in an integer
    > range, with (paraphrasing):
    >
    > int16 limit = 42;
    > int16 value = (int16)( (rand() '*' limit) >> 16);
    >

    Additionally TAL didn't implicitly promote; you had to write
    (uint32)(u16value) as well as demotion (uint16)(u32value).
    No semantic difference, just syntactic salt.

    > Still not as good as a rejection method, but quite a lot better
    > than the `rand() % limit' one so frequently sees in C.
    >

    Depends on your rand(), and I don't recall Guardian having one -- or
    at least exposing one, and I can't think offhand of anything it had in
    the (early?) kernel that would need randoms. It certainly didn't have
    things like TCP (SYNseqs) and DNS (ids) in the kernel, and I *think*
    I recall InterProcesssorBus backoff was deterministic

    <snip rest>
    David Thompson, Nov 16, 2010
    #7
    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. Jam
    Replies:
    3
    Views:
    2,790
    Martin Thompson
    Sep 15, 2004
  2. Replies:
    12
    Views:
    2,667
    Slartibartfast
    Sep 23, 2003
  3. Ben Bacarisse

    Re: How multiply two __int64 ...

    Ben Bacarisse, Oct 31, 2010, in forum: C Programming
    Replies:
    3
    Views:
    444
  4. jacob navia

    Re: How multiply two __int64 ...

    jacob navia, Nov 1, 2010, in forum: C Programming
    Replies:
    2
    Views:
    720
    jacob navia
    Nov 1, 2010
  5. BartC

    Re: How multiply two __int64 ...

    BartC, Nov 1, 2010, in forum: C Programming
    Replies:
    0
    Views:
    598
    BartC
    Nov 1, 2010
Loading...

Share This Page