Hi all,

How to program 128 bit integer in C language ?

Thank you.

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/>.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

"Eric Sosman" <esosman@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...

Lavanya Poondru a �crit :
> Hi all,
> 
> How to program 128 bit integer in C language ?
> 
> Thank you.
The lcc-win compiler features 128 bit integers

"BGB / cr88192" <cr88192@hotmail.com> writes:
> "Eric Sosman" <esosman@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) kst-u@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"

"Keith Thompson" <kst-u@mib.org> wrote in message 
news:lnocdrxxcy.fsf@nuthaus.mib.org...
> "BGB / cr88192" <cr88192@hotmail.com> writes:
>> "Eric Sosman" <esosman@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...

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.

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .  .
\X/     snipabacken.se>   O  o   .

On Thu, 29 Jul 2010, Jorgen Grahn wrote:

> 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

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.

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

On 2010-07-29, Andrey Tarasevich <andreytarasevich@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.

-s
-- 
Copyright 2010, all wrongs reversed.  Peter Seebach / usenet-nospam@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!

Seebs <usenet-nospam@seebs.net> writes:
> On 2010-07-29, Andrey Tarasevich <andreytarasevich@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".

-- 
Keith Thompson (The_Other_Keith) kst-u@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"

On Thu, 29 Jul 2010, Keith Thompson wrote:

> Seebs <usenet-nospam@seebs.net> writes:
>> On 2010-07-29, Andrey Tarasevich <andreytarasevich@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

On 2010-07-29, Keith Thompson <kst-u@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.

-s
-- 
Copyright 2010, all wrongs reversed.  Peter Seebach / usenet-nospam@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!

Keith Thompson <kst-u@mib.org> writes:

> Seebs <usenet-nospam@seebs.net> writes:
>> On 2010-07-29, Andrey Tarasevich <andreytarasevich@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" <usenet-nospam@seebs.net> wrote in message 
news:slrni53i0n.53.usenet-nospam@guild.seebs.net...
> On 2010-07-29, Andrey Tarasevich <andreytarasevich@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.

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.

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

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .  .
\X/     snipabacken.se>   O  o   .

On Thu, 2010-07-29, Seebs wrote:
> On 2010-07-29, Keith Thompson <kst-u@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).

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .  .
\X/     snipabacken.se>   O  o   .

On 2010-08-03, Jorgen Grahn <grahn+nntp@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.  :)

-s
-- 
Copyright 2010, all wrongs reversed.  Peter Seebach / usenet-nospam@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!

"Jorgen Grahn" <grahn+nntp@snipabacken.se> wrote in message 
news:slrni5gnrp.7ng.grahn+nntp@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

Jorgen Grahn wrote:
>> 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.

-- 
Best regards,
Andrey Tarasevich

In article <i3cu6n$gtq$1@news.eternal-september.org>, 
andreytarasevich@hotmail.com says...
> 
> Jorgen Grahn wrote:
> >> 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 

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.

On Tue, 2010-08-03, Seebs wrote:
> On 2010-08-03, Jorgen Grahn <grahn+nntp@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.)

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .  .
\X/     snipabacken.se>   O  o   .