Velocity Reviews > Re: How multiply two __int64 ...

Re: How multiply two __int64 ...

Jon
Guest
Posts: n/a

 11-06-2010
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/Arbitra...etic#Libraries

Bartc
Guest
Posts: n/a

 11-07-2010

"Kappa" <(E-Mail Removed)_NO_SPAM> wrote in message
news:4cd518d6\$0\$27968\$(E-Mail Removed) ...
> 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/Arbitra...etic#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

Marcin Grzegorczyk
Guest
Posts: n/a

 11-07-2010
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

Eric Sosman
Guest
Posts: n/a

 11-08-2010
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
http://www.velocityreviews.com/forums/(E-Mail Removed)lid

Eric Sosman
Guest
Posts: n/a

 11-08-2010
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
(E-Mail Removed)lid

Bartc
Guest
Posts: n/a

 11-08-2010
"Eric Sosman" <(E-Mail Removed)> wrote in message
news:ib7evn\$5ac\$(E-Mail Removed)-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

David Thompson
Guest
Posts: n/a

 11-16-2010
On Sun, 07 Nov 2010 19:04:06 -0500, Eric Sosman
<(E-Mail Removed)> 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);
>

(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>