Hacker News Reader

Comment by aroman | Hacker News Reader

What sorts of applications/domains need or benefit from having 128 bit integers?

The main operation I can think of is multiplying by a ratio without losing precision. If all your values are specified in 64-bit fixed point, a 128-bit integer type gives you something with enough bits for the intermediate product. It's not something I've really dealt with myself, but I seem to remember reading that this is really handy to have in some physics simulations and control system algorithms that do numerical integration. At any rate, it's important enough that many Forth dialects have a word for this specific operation [1].

[1] https://www.forth.com/starting-forth/5-fixed-point-arithmeti...

Or more generally fixed point with big numbers and lots of decimals.

That's less of a concern for 64-bit (even for signed arithmetic, intermediary results can be close to 1.0E19) than for the typical 16-bit values and intermediary 32-bit result that Forth was designed for.

It also is a lot less of a concern on modern systems, where floating point operations aren't much slower than integer ones.

One example I know of is the Poly1305 MAC algorithm, which at its core multiplies two numbers and reduces the result modulo 2^130-5. The C implementation at https://github.com/floodyberry/poly1305-donna shows three ways to represent the 130-bit numbers during the calculation: as ten 13-bit limbs, as five 26-bit limbs, or as two 44-bit limbs plus one 42-bit limb. In the middle of the multiplication, before the carries are propagated, you need twice the number of bits: the first option needs 26 bits, which can be done with a 16x16->32 bit multiplication. The second option needs 52 bits, which can be done with a 32x32->64 bit multiplication. The last option, however, needs 88 bits, which won't fit in 64 bits; you need a 128-bit integer, so you can do a 64x64->128 bit multiplication.

At least on x86-64, the 64x64->128 bit multiplication is a single instruction, like the 32x32->64 bit and the 16x16->32 bit multiplications. Doing the calculation with only three limbs is clearly faster than doing it with five limbs; to start with, using 3 limbs you need 9 multiplies, while with 5 limbs you have to do 25 multiplies. The carry propagation and reduction steps also take time proportional to the number of limbs.

GUIDs are usually 128 bits. So are IPv6 addresses. Could be nice to store them in a single, native type? Probably no easier than a byte array though...

Neither one is used like an integer though. As in, you don't really add GUIDs together¹, so there's no real benefit over a byte array or struct.

1. I guess having bit mask operations for IPv6 addresses could be useful.

But you do want to compare GUIDs. And hash them, which can involve shifting, adding, xor'ing, multiplying, remaindering, etc.

If you can't already hash/compare an array of bytes, something terrible has happened with your language design.

well, you can already do operations on 128bit of data that represents and int as well, but that's a kind of silly thing to say because higher level abstractions are just about making things easier. so now you can do it in 1 operation rather than several; if that's all you gain, then it's still worth it

Not in a way that complies into one or two machine instructions. So, your array code is an order of magnitude or two too slow. Never mind having to write it at all.

Added: I'm talking about implementing specific, optimized hash functions on 128-bit values (e.g. GUIDs, IPv6 addresses), and not generic hash functions that can take any length input (although many of them speed up linearly in the size of int that gets used internally).

Rust isn't hashcode based. You don't define how to hash a type in that way. You define hashing algorithms which operate on arrays of bytes. All a type has to do to implement hashing is specify how to feed its bytes into a hasher.

Hashers provide conveniences for feeding in a u8, u16, u32, u64, etc., but most hashers just implement this as casting the value to an array of bytes and using the generic implementation. This is because most algorithms are defined in terms of bytes. Evidently there isn't any interesting optimization to do by statically knowing you have a u32 vs a u64 for these algorithms (appears to be the case for SipHash, XXHash, and Fnv).

And indeed, u128 continues this tradition in the PR: https://github.com/rust-lang/rust/pull/37900/files#diff-2327...

Whatever one can do on an i128, one can do "manually" on an array of bytes, e.g. coerce to a pair of u64s to avoid having to manipulate each byte individually.

Avoiding pointers to arrays is nice.

This is the big annoyance in Golang with it's net.IP type - it's `type IP []byte`, which means you can write ip1 == ip2 and you can't pass by value easily, nor use it as a map key.

I've ended up inventing my own type for that a lot of the time as a struct wit static fields, since those you can copy around and do 1:1 comparisons.

Though to be honest I'd be super happy if there was a drop-in varint type, or you could trivially have the compiler calculate instructions for a arbitrary fixed size ints.

Rust offers non-allocating fixed-sized arrays, so a GUID could be a (wrapper around) [u8; 16] and an IPv6 address could be [u16; 8].

That's exactly how the UUID crate implements them: https://github.com/rust-lang-nursery/uuid/blob/master/src/li...

So does Go, so a net.IP could be [16]byte or [4]byte, but I'm sure you can see the obvious problems that might occur there (with having two separate IP types).

Most UUID libraries I've seen and written use [16]byte as the concrete UUID type.

I don't see the obvious problem (fwiw, I really dislike such rhetorical devices): presumably net.IP could a struct that contains a [16]byte and an isV4 flag.

I think the point was that when it's a mere alias, you can end up passing an array of the right size and type that is not an IP address.

The problem is [16]byte would always be wasting 12 bytes for IPv4 addresses if you only used one type for both. So, two types must be made which requires extra code and doesn't allow for == comparison which is what OP (GP? whomever...) was complaining about not being able to do since net.IP is []byte.

Sorry for the rhetorical device.

Isn't the indirection overhead of a []byte more expensive than a spare 12 inline bytes?

Yes, and a []byte is even going to have at least as much inline overhead: it stores 24 bytes (length, capacity, pointer), and of course plus the 4 bytes of actual data. Even on a 32-bit platform, the []byte inline storage is 12 bytes.

If you are using default library IPv4 addresses stores as [16]byte: https://golang.org/src/net/ip.go

I don't think that's what the Godoc says. The IP type is defined as []byte

  type IP []byte

That is not the same as [16]byte.

  // Note that in this documentation, referring to an
  // IP address as an IPv4 address or an IPv6 address
  // is a semantic property of the address, not just the
  // length of the byte slice: a 16-byte slice can still
  // be an IPv4 address.

What I believe that comment is saying is that something that is [16]byte can still be an IPv4 address, but that doesn't mean that all IPv4 addresses are stored as [16]byte. At least that would be my interpretation based on the comment above it:

  // An IP is a single IP address, a slice of bytes.
  // Functions in this package accept either 4-byte (IPv4)
  // or 16-byte (IPv6) slices as input.

IP addresses are used like integers all the time. Ask your friendly neighborhood sysadmin how a network mask works.

(Maybe you want to foreach over an array every time you want to apply one. I'd rather not.)

I realize integer has rather specific meaning in this context. But really, your comment just highlights the issue.

In my world integer is a mathematical construct with no particular representation, making things like bitmasks and or shifts nonsensical.

If you really want to work with fixed length bitstrings why not just have a type for that? Operating on a string of 128-bits should be valid on all such bitstrings no matter wether those represent a number or a string of code points.

And equally operations on integers should not care about particular bitstrings representations of the number in question.

> In my world integer is a mathematical construct with no particular representation

Your world doesn't map to the reality of silicon and registers, whereas Rust does. As it happens, you can be fixed much more easily than the whole of modern computing.

> If you really want to work with fixed length bitstrings why not just have a type for that?

I don't. I want to work with integers. An IPv6 address is not the hex format that you read--it is a 128-bit integer. You can go read RFC 2460 if you don't believe me, but it's true. It is an integer that I can add and subtract from; I don't add 1 to an octet of an IP address and then do a bunch of carries if I want the next IP address in my network, I add 1 to the IP address. I don't perform some magic operation to determine what a subnet looks like, I bitand the integer. They are inescapably based on the representation used both by my computer and by my network hardware. (As is the performance of both my network hardware and yours. There's a reason that your router doesn't use BCD or whatever.)

There are programming languages that do not represent the underlying system. They are, for the most part, bad at dealing with the kinds of problems Rust is tailored to effectively represent. You can use those. It's pretty presumptuous to suggest that languages designed for lower-level problems accommodate your peculiarity.

Not really. They are never added, subtracted, multiplied, or divided. They are never compared for greater-than or less-than. Possibly they are compared for equality.

About the only mathematical operations I can think of which are ever done to them are bitwise-anding, bitwise-inclusive-oring, and testing for zero (and, as mentioned, equality).

Yes, really. I mean, I add to IP addresses regularly. How else do you enumerate a subnet (like, what do you think nmap does)? How else do you place, say, twelve machines at 172.17.0.120 through .131? If you're doing string concatenation, you are screwing up. Perhaps it's not enough of a screwup to impact what you do--but definitely wrong enough to impact what I do unless I were to do a lot of extra work in modeling an IP address just for the sake of somebody else's spherical cow of uniform density. (And I do mean work I'd have to do--the lack of a decent IP addressing library on the JVM is a recurring pain in my ass, but since they're just integers...)

If you have internalized an IP address as a dotted set of octets expressed in ASCII digits, that's a problem of comprehension. When you don't, it's pretty natural to just use this stuff like any other integer.

You're not adding addresses together, that doesn't make sense. You're adding ints to addresses, it's a completely different property, even if the representation happens to fit into the same amount of bits. Nothing more than a convenient coincidence.

You're right, I'm not adding addresses together. If you read my post, I say I'm adding to addresses, which you do to--now hold onto your hat--find the next one in sequence. And that, quite obviously, works because they are integers and map to an address space that matches the complete space, from 0x00000000 to 0xFFFFFFFF (and the equivalent 128-bit space for IPv6) of their bit length. It's not "a convenient coincidence". It's the definition of the thing in question.

It's like saying a pointer to RAM isn't an integer. Of course it is, and you add to them every time you de-reference an array in C. That it has additional semantic meaning doesn't mean it stops being a integer. The pedantry you're peddling doesn't fly.

I think what baq is saying is that IP addresses are torsors http://math.ucr.edu/home/baez/torsors.html . It makes sense to give them a type where you can't add two IP addresses to each other (but you can still subtract to get an integer, and add integers).

Sure, fine, but it'll still be an i128 somewhere, yeah? Like, you can put whatever abstraction you want on it, I still need to directly poke those bits and treat it in all ways as fundamentally the same thing as an integer, defined in those terms in order to use integral operations upon them, at the levels that somebody who's worrying about them has to care about. (Also, look at halomru's post for reasons one might intentionally add and subtract addresses from one another in the first place, which kind of holes this argument.)

That is a cool link though, I'm gonna give it a deeper read.

>They are never compared for greater-than or less-than.

    if ip >= IP(10.34.12.3) && ip <= IP(10.34.12.9)
        //is one of our database servers

> They are never added, subtracted,

    if abs(atk1.ip - atk2.ip) < 16
        //same source likely, modify threshold

Netmask are useful, but sometimes doing regular math is a better fit for your problem. Adding an integer to an IP, subtracting IPs or comparing IPs all yield meaningful results.

What is your point? u32/u128 are not mathematical integers. They are actually bit strings, just like IP addresses and unlike mathematical integers.

They are mathematical cyclic groups!

Then you could do this:

    ping6 42540577535212633203815888880477462122

Like you can do this:

    ping 2158835347
    PING 2158835347 (128.173.54.147) 56(84) bytes of data.
    64 bytes from 128.173.54.147: icmp_seq=1 ttl=52 time=20.4 ms
    64 bytes from 128.173.54.147: icmp_seq=2 ttl=52 time=20.5 ms

Implementing cryptographic hash functions like SHA-3 (see the original Kaccek paper for specific results under various 32-bit, 64-bit, and 128-bit native integer hardware support). And implementing other, faster but non-cryptographic hash functions like Spooky, etc.

Two applications off the top of my head: Reed-Solomon encoding and bigint math.

Finance and scientific computing.

Is this for implementing faster high precision floating point? It didn't mention 128 bit float.

For finance probably but it's mostly useful for statistics from what I understand.

I know fortran and Cobol code that banks use and is used for science (tm) often defines numbers this large for certain operations.

One such i can think of is a map reduce of large datasets. Let's say you want to find as a result a huge sum. 2^128 is a bit bigger then 2^64 and that difference may be big enough to provide the computation needed for getting to Mars rather then getting to the moon on 2^8 machines.

Fun fact: there are ~2^50 millimetres from here to mars

There are? It looks closer to 2^14. 2^50mm is around 7.5 au. Sorry to nitpick, but I thought this was a super interesting point!

I assume you meant to type 47 rather than 14?

I rounded a bit over-zealously, thanks for nit picking. It is indeed 2^47.6333. (also assuming you meant 47 not 14.)

Well, that's embarrassing. 2^47 it is! :)

128i[3] would be enough for 390x observable universe discrete grid in Euclidean space with nanometer precision. Or 0.39 observable universe with picometer resolution.

What number in finance is bigger than 2^64?

The sum of the whole planet's annual GDPs, expressed as US dollars with a precision of cents, requires about 53 bits. Choose a smaller unit or start considering long time spans, and you can easily get uncomfortably close to overflow.

Why would you express GDPs, which are estimated to an accuracy of millions of US dollars, with a precision of US cents?

Riches are getting richer.

POWER9 has hardware 128 bit float, so likely to start becoming relevant soon.

Measuring time in picoseconds. The current unix timestamp is roughly 2^70 picoseconds, so won't fit in 64 bits.

Can you present any imaginable situation where resolution of arbitrary time/dates to a billionth of a second is not adequate?

Something involving femtosecond lasers maybe?

LHC

You can store a bitboard for western chess perfectly with 64-bit integers. Some other chess variants(like Chinese Chess, or Shogi) need 128 bits for the same techniques, since the board is larger.

I haven't used it, but Julia lets you declare any(?) fixed size bitset. Which would probably come in handy for Go.

NS-3 network simulator uses 128bit integers to measure time and they have 3 implementations (search page for int64x64): http://code.nsnam.org/ns-3-dev/file/38d46996c708/src/core/mo...

It would be much easier for them to just build on top of i128.

Also, you can see that one of the implementations is copied from Cairo, so it seems graphics libraries have some use for 128-bit integers too.

I found myself asking the same question. 64 bit integers are useful because you'll never fill up an IntMap with a uint64 key, and 256 bit integers are useful because they offer sufficient (128 bit) collision resistance. In my mind, a uint128 is too big for use as an index, and too small as a GUID.

AES blocks!

(Some) NVMe statistics are specified as 128-bit integers. Not that you need to operate on them, necessarily, or that they'll practically ever exceed 64-bit values, but they are.

128-bit atomics for small structs—very convenient

can be handy for a really big space for ids, especially if you don't want to use strings. also bigger bitsets

...PS2 hacking?

But I don't think rust has support for the Emotion Engine in any case.

Reply on news.ycombinator.com