Re: 128 bit integer
Eric Sosman
> Hi all,
>
> How to program 128 bit integer in C language ?
See Question 18.15d on the comp.lang.c Frequently Asked
Questions (FAQ) page at <http://www.c-faq.com/>.
--
Eric Sosman
eso...@ieee-dot-org.invalid
BGB / cr88192
"Eric Sosman" <eso...@ieee-dot-org.invalid> wrote in message
news:i2p5hj$2tu$1...@news.eternal-september.org...
> On 7/28/2010 7:34 AM, Lavanya Poondru wrote:
>> Hi all,
>>
>> How to program 128 bit integer in C language ?
>
> See Question 18.15d on the comp.lang.c Frequently Asked
> Questions (FAQ) page at <http://www.c-faq.com/>.
>
also (will add this much):
some compilers add 128 bit (or more) integer types as an extension feature,
but there is no real standardization here AFAIK.
it is also common to roll ones' own large integer support, such as using by
a struct of smaller integers, and then applying similar strategies to
elementary-school arithmetic to make it behave like a larger value.
or such...
jacob navia
> Hi all,
>
> How to program 128 bit integer in C language ?
>
The lcc-win compiler features 128 bit integers
Keith Thompson
> "Eric Sosman" <eso...@ieee-dot-org.invalid> wrote in message
> news:i2p5hj$2tu$1...@news.eternal-september.org...
>> On 7/28/2010 7:34 AM, Lavanya Poondru wrote:
>>> Hi all,
>>>
>>> How to program 128 bit integer in C language ?
>>
>> See Question 18.15d on the comp.lang.c Frequently Asked
>> Questions (FAQ) page at <http://www.c-faq.com/>.
>>
>
> also (will add this much):
> some compilers add 128 bit (or more) integer types as an extension feature,
> but there is no real standardization here AFAIK.
Well, there's some.
An implementation that provides 128-bit integer types will probably
define int128_t, intleast128_t, and intfast128_t in <stdint.h>. All
these are optional, so even if long long is 128 bits an implementation
isn't *required* to define these typedefs (only the 8, 16, 32, and
64-bit "least" and "fast" typedefs are mandatory), but it would be silly
not to define them for 128 bits if the corresponding types exist.
And if any integer type is 128 bits or wider, intmax_t will be such a
type.
Repeat the above replacing "int" with "uint" for unsigned types.
But most current implementations, as far as I know, only support
integers up to 64 bits.
--
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"
BGB / cr88192
"Keith Thompson" <ks...@mib.org> wrote in message
news:lnocdrx...@nuthaus.mib.org...
> "BGB / cr88192" <cr8...@hotmail.com> writes:
>> "Eric Sosman" <eso...@ieee-dot-org.invalid> wrote in message
>> news:i2p5hj$2tu$1...@news.eternal-september.org...
>>> On 7/28/2010 7:34 AM, Lavanya Poondru wrote:
>>>> Hi all,
>>>>
>>>> How to program 128 bit integer in C language ?
>>>
>>> See Question 18.15d on the comp.lang.c Frequently Asked
>>> Questions (FAQ) page at <http://www.c-faq.com/>.
>>>
>>
>> also (will add this much):
>> some compilers add 128 bit (or more) integer types as an extension
>> feature,
>> but there is no real standardization here AFAIK.
> [...]
>
> Well, there's some.
>
> An implementation that provides 128-bit integer types will probably
> define int128_t, intleast128_t, and intfast128_t in <stdint.h>. All
> these are optional, so even if long long is 128 bits an implementation
> isn't *required* to define these typedefs (only the 8, 16, 32, and
> 64-bit "least" and "fast" typedefs are mandatory), but it would be silly
> not to define them for 128 bits if the corresponding types exist.
>
forgot about stdint.h, I suspect partly because MSVC lacks this header...
> And if any integer type is 128 bits or wider, intmax_t will be such a
> type.
>
> Repeat the above replacing "int" with "uint" for unsigned types.
>
> But most current implementations, as far as I know, only support
> integers up to 64 bits.
>
yeah, this is true of both MSVC and GCC AFAIK (actually, IIRC GCC supports
128 bit ints for certain targets, but I am not sure).
both my compiler and Mr. Navia's compiler support 128 bit ints (mine uses
the type name "__int128" internally).
I think also Open64 and a few others as well support them.
not really sure though, I haven't really looked into it much...
Jorgen Grahn
> Hi all,
>
> How to program 128 bit integer in C language ?
I'm a bit curious: for what purpose do you need it? 64-bit integers
can hold values almost up to 19,000,000,000,000,000,000 which is ...
a lot.
I am not saying it would be useless, just that I cannot think of a use
for it.
/Jorgen
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
Ersek, Laszlo
> On Wed, 2010-07-28, Lavanya Poondru wrote:
>> Hi all,
>>
>> How to program 128 bit integer in C language ?
>
> I'm a bit curious: for what purpose do you need it? 64-bit integers
> can hold values almost up to 19,000,000,000,000,000,000 which is ...
> a lot.
>
> I am not saying it would be useless, just that I cannot think of a use
> for it.
http://en.wikipedia.org/wiki/Block_size_(cryptography)
lacos
Andrey Tarasevich
> I'm a bit curious: for what purpose do you need it? 64-bit integers
> can hold values almost up to 19,000,000,000,000,000,000 which is ...
> a lot.
>
> I am not saying it would be useless, just that I cannot think of a use
> for it.
The use for it is rather obvious. For example, if your program uses
64-bit integers, then every time you multiply these integers, you have
to perform that multiplication within a 128-bit type. You have a
rectangle, whose coordinates are 64-bit integers? Well, then the the
area of that rectangle is a 128-bit integer, whether you like it or not.
It also happens extremely often that 64-bit input has to produce a
64-bit result, but the intermediate evaluation has to go through a
64x64-bit (i.e. 128 bit) multiplications.
The often-used practice in such situations is to use floating-point
types for intermediate evaluations, which is obviously nothing else than
"losers way out" forced by the unavailability of integer types of
required bit-width.
--
Best regards,
Andrey Tarasevich
Seebs
> The use for it is rather obvious.
You caught one of the obvious ones. The one that leapt out at me, of
course, was IPV6.
-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / usenet...@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
Keith Thompson
> On 2010-07-29, Andrey Tarasevich <andreyta...@hotmail.com> wrote:
>> The use for it is rather obvious.
>
> You caught one of the obvious ones. The one that leapt out at me, of
> course, was IPV6.
I'm not as familiar with IPV6 as I probably should be. What benefit
does using, say, uint128_t to store IPV6 address give you over using,
say, unsigned char[16]? (Or wrap the array in a struct so you can do
assignment and equality comparison.)
In other words, how much sense does it make to do arithmetic in IPV6
addresses?
I'm not suggesting that the answer is "none".
Ersek, Laszlo
> Seebs <usenet...@seebs.net> writes:
>> On 2010-07-29, Andrey Tarasevich <andreyta...@hotmail.com> wrote:
>>> The use for it is rather obvious.
>>
>> You caught one of the obvious ones. The one that leapt out at me, of
>> course, was IPV6.
>
> I'm not as familiar with IPV6 as I probably should be. What benefit
> does using, say, uint128_t to store IPV6 address give you over using,
> say, unsigned char[16]? (Or wrap the array in a struct so you can do
> assignment and equality comparison.)
>
> In other words, how much sense does it make to do arithmetic in IPV6
> addresses?
I'm not as familiar with IPv6 as I definitely should be, but I'll
extrapolate from IPv4.
http://en.wikipedia.org/wiki/Classless_Inter-Domain_Routing
http://en.wikipedia.org/wiki/Routing_table
Very superficially, you need fast bitand to see if an IP address matches a
route (an IP prefix): ip_addr & route_netmask == route_prefix. The route
with the longest matching prefix is taken. There are many tricks to speed
this up; for example, I just stumbled on
http://en.wikipedia.org/wiki/Lule%C3%A5_algorithm
but that seems to require fast bitand and bitwise shifts too.
lacos
Tim Rentsch
> Seebs <usenet...@seebs.net> writes:
>> On 2010-07-29, Andrey Tarasevich <andreyta...@hotmail.com> wrote:
>>> The use for it is rather obvious.
>>
>> You caught one of the obvious ones. The one that leapt out at me, of
>> course, was IPV6.
>
> I'm not as familiar with IPV6 as I probably should be. What benefit
> does using, say, uint128_t to store IPV6 address give you over using,
> say, unsigned char[16]? (Or wrap the array in a struct so you can do
> assignment and equality comparison.)
>
> In other words, how much sense does it make to do arithmetic in IPV6
> addresses?
Some, but most of the benefit is probably just plain data movement.
IPv6 addresses divide nicely into two 64-bit essentially independent
pieces, so uint64_t[2] should provide nearly all of the benefit, as
far as arithmetic/logical operations go, of using uint128_t.
Seebs
> I'm not as familiar with IPV6 as I probably should be. What benefit
> does using, say, uint128_t to store IPV6 address give you over using,
> say, unsigned char[16]? (Or wrap the array in a struct so you can do
> assignment and equality comparison.)
>
> In other words, how much sense does it make to do arithmetic in IPV6
> addresses?
>
> I'm not suggesting that the answer is "none".
I seem to recall that there are cases where it might be convenient to do
a bitwise mask on something, and "x & y" is simpler than iterating over an
array.
BGB / cr88192
"Seebs" <usenet...@seebs.net> wrote in message
news:slrni53i0n.53...@guild.seebs.net...
> On 2010-07-29, Andrey Tarasevich <andreyta...@hotmail.com> wrote:
>> The use for it is rather obvious.
>
> You caught one of the obvious ones. The one that leapt out at me, of
> course, was IPV6.
>
there are also GUID and PRNG related uses.
Jorgen Grahn
> Jorgen Grahn wrote:
>> I'm a bit curious: for what purpose do you need it? 64-bit integers
>> can hold values almost up to 19,000,000,000,000,000,000 which is ...
>> a lot.
>>
>> I am not saying it would be useless, just that I cannot think of a use
>> for it.
>
> The use for it is rather obvious. For example, if your program uses
> 64-bit integers, then every time you multiply these integers, you have
> to perform that multiplication within a 128-bit type. You have a
> rectangle, whose coordinates are 64-bit integers? Well, then the the
> area of that rectangle is a 128-bit integer, whether you like it or not.
But what would the purpose of that rectangle be? If it's a real shape,
and you measure with 1um resolution, with 32 bits you can express
areas as large as 4300 x 4300 m. Possibly useful if you build nuclear
plants or aircraft carriers, but that's not something I do regularly.
(With 64-bit integers, the largest rectangle you can express is on the
order of a thousand light-years on the side, still with micrometer
precision.)
> It also happens extremely often that 64-bit input has to produce a
> 64-bit result, but the intermediate evaluation has to go through a
> 64x64-bit (i.e. 128 bit) multiplications.
I think "extremely often" is an extreme exaggeration, or that you work
in very different domains from me (the very ones I asked about, in
fact). I have never seen the need myself, and I've been programming
since the early 1990s.
Jorgen Grahn
> On 2010-07-29, Keith Thompson <ks...@mib.org> wrote:
>> I'm not as familiar with IPV6 as I probably should be. What benefit
>> does using, say, uint128_t to store IPV6 address give you over using,
>> say, unsigned char[16]? (Or wrap the array in a struct so you can do
>> assignment and equality comparison.)
>>
>> In other words, how much sense does it make to do arithmetic in IPV6
>> addresses?
>>
>> I'm not suggesting that the answer is "none".
>
> I seem to recall that there are cases where it might be convenient to do
> a bitwise mask on something, and "x & y" is simpler than iterating over an
> array.
But then you'd want uint256_t, uint512_t ... etc, when you hit the
128-bit limit, wouldn't you?
We have to stop *somewhere* (with the builtin C integer types, that is).
Seebs
> But then you'd want uint256_t, uint512_t ... etc, when you hit the
> 128-bit limit, wouldn't you?
The specific question was "IPv6", which is 128-bit. There's not yet an
IPv7. :)
Bartc
news:slrni5gnrp.7...@frailea.sa.invalid...
> On Thu, 2010-07-29, Andrey Tarasevich wrote:
>> Jorgen Grahn wrote:
>>> I'm a bit curious: for what purpose do you need it? 64-bit integers
>>> can hold values almost up to 19,000,000,000,000,000,000 which is ...
>>> a lot.
>>>
>>> I am not saying it would be useless, just that I cannot think of a use
>>> for it.
>>
>> The use for it is rather obvious. For example, if your program uses
>> 64-bit integers, then every time you multiply these integers, you have
>> to perform that multiplication within a 128-bit type. You have a
>> rectangle, whose coordinates are 64-bit integers? Well, then the the
>> area of that rectangle is a 128-bit integer, whether you like it or not.
(And the volume would be a 192-bit integer...)
> (With 64-bit integers, the largest rectangle you can express is on the
> order of a thousand light-years on the side, still with micrometer
> precision.)
>> It also happens extremely often that 64-bit input has to produce a
>> 64-bit result, but the intermediate evaluation has to go through a
>> 64x64-bit (i.e. 128 bit) multiplications.
>
> I think "extremely often" is an extreme exaggeration, or that you work
> in very different domains from me (the very ones I asked about, in
> fact). I have never seen the need myself, and I've been programming
> since the early 1990s.
The requirements for integers tend to be 32-bits, 64-bits or unlimited (ie.
bigints).
I don't think there's an urgent need for a dedicated 128-bit integer that
supports all arithmetic ops, except that 64-bit processors make this trivial
to implement, so it might as well be used.
--
Bartc
Andrey Tarasevich
>> The use for it is rather obvious. For example, if your program uses
>> 64-bit integers, then every time you multiply these integers, you have
>> to perform that multiplication within a 128-bit type. You have a
>> rectangle, whose coordinates are 64-bit integers? Well, then the the
>> area of that rectangle is a 128-bit integer, whether you like it or not.
>
> But what would the purpose of that rectangle be? If it's a real shape,
> and you measure with 1um resolution, with 32 bits you can express
> areas as large as 4300 x 4300 m. Possibly useful if you build nuclear
> plants or aircraft carriers, but that's not something I do regularly.
Ha! _I_ actually use it regularly. And I work with semiconductor
microchips. Note: not aircraft carriers or nuclear plants, but
_microchips_. Where do such large values come from, you might ask? Well,
firstly, the modern semiconductor technologies work with resolutions
much higher than 1 um. Secondly, to reduce the chance of serious
rounding problems in intermediate integral calculations with
non-rectilinear geometry we use "super-precision": the coordinates are
usually multiplied by some constant (like 2, 16, 32 etc., depending on
the angle variety in the input data). And yes, we have already grew out
of the range offered by 32-bit signed integer types. 32-bit signed
integer is no longer enough to represent coordinates in microchip
geometry with sufficient "super-precision" (multiplier).
> (With 64-bit integers, the largest rectangle you can express is on the
> order of a thousand light-years on the side, still with micrometer
> precision.)
Which is why there's hope that 64-bit integer range should be enough for
everybody :) At least when it comes to linear dimensions.
>> It also happens extremely often that 64-bit input has to produce a
>> 64-bit result, but the intermediate evaluation has to go through a
>> 64x64-bit (i.e. 128 bit) multiplications.
>
> I think "extremely often" is an extreme exaggeration, or that you work
> in very different domains from me (the very ones I asked about, in
> fact). I have never seen the need myself, and I've been programming
> since the early 1990s.
Well, just for another example, when you one's dealing with systems of
linear equations of small pre-determined fixed size (again, often
happens in geometrical applications), which have to be solved precisely,
often the best way to get to the solution is to use the well-known
Cramer's rule, especially if the system is sparse[-ish]. To solve a 4x4
system with 32-bit coefficients you generally need 128-bit integer
arithmetics. After switching to 64-bit coefficients, 256-bit integer
arithmetics becomes necessary. In this case, for obvious reasons, the
required "bitness" of the intermediate arithmetic grows even faster than
in the example with rectangle area.
Dann Corbit
andreyta...@hotmail.com says...
Other areas requiring high precision integer mathematics:
1. Crypto (look at the openssl code)
2. Factoring (look at yafu)
3. Fractals (look at Fractint)
4. Number theory (see PARI/Gp)
Probably plenty besides these.
Jorgen Grahn
> On 2010-08-03, Jorgen Grahn <grahn...@snipabacken.se> wrote:
>> But then you'd want uint256_t, uint512_t ... etc, when you hit the
>> 128-bit limit, wouldn't you?
>
> The specific question was "IPv6", which is 128-bit. There's not yet an
> IPv7. :)
Oops, you're right. I dropped the context.
(Although I have a feeling that masking on the full 128-bit IPv6
address is less useful than masking on a 32-bit IPv4 address. The 64
LSB is unsually a MAC address, not subnetting-related.)