How multiply two __int64 ...
Kappa
I was wondering if someone has already written a routine to multiply two
__int64 for obtain a __int128.
Can someone help me ?
Thanks very much.
K.
Ben Bacarisse
> I was wondering if someone has already written a routine to multiply two
> __int64 for obtain a __int128.
If these are extended integer types provided by your implementation,
what's wrong with:
__int128 multiply(__int64 a, __int64 b)
{
return (__int128)a * b;
}
?
--
Ben.
Tim Prince
> I was wondering if someone has already written a routine to multiply two
> __int64 for obtain a __int128.
Are you hoping to rekindle a flame war by implying that Microsoft and
lcc-win32 are the only true standard? If you found lcc version of this
unsuitable, tell us in which way.
--
Tim Prince
Kappa
> If these are extended integer types provided by your implementation,
> what's wrong with:
>
> __int128 multiply(__int64 a, __int64 b)
> {
> return (__int128)a * b;
> }
>
This would be perfect, but __int128 is not a valid definition ... :-( ...
There is some library that does what I ask ?
Thanks.
Kappa.
Kappa
> Are you hoping to rekindle a flame war by implying that Microsoft and
> lcc-win32 are the only true standard? If you found lcc version of this
> unsuitable, tell us in which way.
If it is sufficient to start to look for "__int128" for me that's okay ...
:-) ...
Thanks.
Kappa.
Ben Bacarisse
You'll get better answers in a group that deals with your C
implementation since this is no longer about standard C. There are, of
course, arbitrary precision arithmetic libraries, but that does not seem
to be what you are asking about.
--
Ben.
Keith Thompson
What is __int128? Where did you see it?
There is no type named __int64 or __int128 in standard C.
Are you asking about types with those particular names, or are you
asking about 64-bit and 128-bit integer arithmetic?
C does not require support for integer types wider than 64 bits
(in C90, it was 32 bits), but implementations can support integer
types as wide as they like.
If an implementation supports 128-bit integer types, then it
will support arithmetic on them. If not, there may be ways to
simulate them. GMP and other libraries support arbitrary-precision
arithmetic, but that might be overkill for your purposes.
I suspect your use of the specific name "__int128" has obscured
your actual question.
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
BartC
"Kappa" <NO_SPAM_...@virgilio.it_NO_SPAM> wrote in message
news:4ccd3833$0$40004$4faf...@reader3.news.tin.it...
> Hi,
>
> I was wondering if someone has already written a routine to multiply two
> __int64 for obtain a __int128.
>
> Can someone help me ?
Google? There must be some code out there.
If you want to do this yourself, as C code where 64-bit multiply is
available, but not 128-bit, then it's quite tricky:
* Even using 64-bits, you will need access to the top half of the 128-bit
product, which leaves you almost where you started. C will not give you
this.
* You need some 128-bit adds and shifts, or access to a carry flag, again
awkward with C.
* You also need to consider that a general 128-bit multiply will have a
256-bit result (you might choose to ignore this).
An attempt at trying to use 64-bit multiplies might look as follows:
If you define one *unsigned* 128-bit int as (a*m + b), where a and b are
high and low 64-bit halves, and m is a scale factor (2**64), and another as
(c*m+d), then the product will be (I think, as I haven't tried it):
(a*b*m*m + a*d*m + b*c*m + b*d)
But each product as I said could overflow into 128-bits, and the additions
and shifts (*m) must be 128-bits too. (Actually the shifts aren't too
difficult.)
You could do it with a *lot* of 32-bit arithmetic inside 64-bit types (and
it would be very slow), but I think the way to go, if you have to do this
yourself, is to drop into assembler (either inline, or as an external
function).
--
Bartc
BartC
news:iamm82$p7d$1...@speranza.aioe.org...
> Le 31/10/10 10:34, Kappa a �crit :
>> I was wondering if someone has already written a routine to multiply two
>> __int64 for obtain a __int128.
> Write a small program like this using lcc-win:
>
> #include <int128.h>
>
> int main(void)
> {
> int128 a=12LL,b=10LL;
> int128 c=a*b;
> }
>
> Compile it with debug info and start the debugger. Put a breakpoint in the
> line with the multiplication. When the debugger stops there, open the
> disassembly window and press F8 (step in). You will eventually arrive at
> the multiplication procedure. List its assembly contents
> and you have a 64*64 multiplication routine.
How do you get the 128*128-bit routine?
--
Bartc
jacob navia
>
>>> I was wondering if someone has already written a routine to multiply two
>>> __int64 for obtain a __int128.
>
>> Write a small program like this using lcc-win:
>>
>> #include <int128.h>
>>
>> int main(void)
>> {
>> int128 a=12LL,b=10LL;
>> int128 c=a*b;
>> }
>>
>> Compile it with debug info and start the debugger. Put a breakpoint in
>> the line with the multiplication. When the debugger stops there, open
>> the disassembly window and press F8 (step in). You will eventually
>> arrive at the multiplication procedure. List its assembly contents
>> and you have a 64*64 multiplication routine.
>
> How do you get the 128*128-bit routine?
>
Actually reading the code above, you are calling the 128 multiply since
a and b are 128 bit ints,
What a stupid!
To get the 64*64-->128 you just have to do a normal 64 bit
multiply since ALL 64*64 yield a 128 Bit result in the intel
machines, stored in RAX:RDX
Sorry.
Jon
> "Kappa" <NO_SPAM_...@virgilio.it_NO_SPAM> writes:
>>> If these are extended integer types provided by your implementation,
>>> what's wrong with:
>>>
>>> __int128 multiply(__int64 a, __int64 b)
>>> {
>>> return (__int128)a * b;
>>> }
>>>
>>
>> This would be perfect, but __int128 is not a valid definition ...
>> :-( ...
>>
>> There is some library that does what I ask ?
>
> What is __int128? Where did you see it?
>
> There is no type named __int64 or __int128 in standard C.
>
Well "la di da". The newsgroup is comp.lang.c, *not* comp.lang.std_c. To
your probable dismay, "occassionally" people ask *programming* questions
in here, rather than about the intricate details of some archaic
"standard" that has about as much to do with software development as any
other ancient chiseled tablets.
> I suspect your use of the specific name "__int128" has obscured
> your actual question.
Contraire! You, OTOH, are hardly subtle in your spewing of dogma. Not
everyone is or wants to be a "language lawyer".
Jon
> 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
Kappa
> 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.
Thanks very much.
K.
Bartc
"Kappa" <NO_SPAM_...@virgilio.it_NO_SPAM> wrote in message
(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
> 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
> [...]
> 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
eso...@ieee-dot-org.invalid
Eric Sosman
> [...]
> // 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
eso...@ieee-dot-org.invalid
Bartc
news:ib7evn$5ac$1...@news.eternal-september.org...
(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
Noob
> I was wondering if someone has already written a routine to multiply two
> __int64 for obtain a __int128.
If you'd asked on a GNU forum, I would have suggested you try
typedef unsigned int uint128_t __attribute__((mode(TI)));
result = ((uint128_t) x * y) >> 64;
Regards.
David Thompson
<eso...@ieee-dot-org.invalid> 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>
io_x
"Kappa" <NO_SPAM_...@virgilio.it_NO_SPAM> ha scritto nel messaggio
news:4ccd3833$0$40004$4faf...@reader3.news.tin.it...
> Hi,
>
> I was wondering if someone has already written a routine to multiply two
> __int64 for obtain a __int128.
i think __int64 __int128 are not words from the C Language, are out of the
standard; ( you should be OT )
they are reserved to the compiler