lukechampine / uint128

uint128 for Go

uint128

go get lukechampine.com/uint128

uint128 provides a high-performance Uint128 type that supports standard arithmetic operations. Unlike math/big, operations on Uint128 values always produce new values instead of modifying a pointer receiver. A Uint128 value is therefore immutable, just like uint64 and friends.

The name uint128.Uint128 stutters, so I recommend either using a "dot import" or aliasing uint128.Uint128 to give it a project-specific name. Embedding the type is not recommended, because methods will still return uint128.Uint128; this means that, if you want to extend the type with new methods, your best bet is probably to copy the source code wholesale and rename the identifier. ¯\_(ツ)_/¯

Benchmarks

Addition, multiplication, and subtraction are on par with their native 64-bit equivalents. Division is slower: ~20x slower when dividing a Uint128 by a uint64, and ~100x slower when dividing by a Uint128. However, division is still faster than with big.Int (for the same operands), especially when dividing by a uint64.

BenchmarkArithmetic/Add-4              2000000000    0.45 ns/op    0 B/op      0 allocs/op
BenchmarkArithmetic/Sub-4              2000000000    0.67 ns/op    0 B/op      0 allocs/op
BenchmarkArithmetic/Mul-4              2000000000    0.42 ns/op    0 B/op      0 allocs/op
BenchmarkArithmetic/Lsh-4              2000000000    1.06 ns/op    0 B/op      0 allocs/op
BenchmarkArithmetic/Rsh-4              2000000000    1.06 ns/op    0 B/op      0 allocs/op

BenchmarkDivision/native_64/64-4       2000000000    0.39 ns/op    0 B/op      0 allocs/op
BenchmarkDivision/Div_128/64-4         2000000000    6.28 ns/op    0 B/op      0 allocs/op
BenchmarkDivision/Div_128/128-4        30000000      45.2 ns/op    0 B/op      0 allocs/op
BenchmarkDivision/big.Int_128/64-4     20000000      98.2 ns/op    8 B/op      1 allocs/op
BenchmarkDivision/big.Int_128/128-4    30000000      53.4 ns/op    48 B/op     1 allocs/op

BenchmarkString/Uint128-4              10000000      173 ns/op     48 B/op     1 allocs/op
BenchmarkString/big.Int-4              5000000       350 ns/op     144 B/op    3 allocs/op

uint128's Issues

Add tests for math/bits methods

The following methods are missing test coverage:

• TrailingZeros
• OnesCount
• RotateLeft
• RotateRight
• Reverse
• ReverseBytes
• Len

Ideally, you should copy the test cases from math/bits: https://golang.org/src/math/bits/bits_test.go (specifically, you'll probably want to use the tab array from the bottom of the file).

Feel free to submit tests for all of these, or just one. You can also convert the existing LeadingZeros test to match the testing format used in math/bits.

IsZero() method relies on exported variable

In the current implementation, the IsZero() method relies on the variable Zero. But Zero is an exported variable which could, in theory, be altered by code from another package. This would break IsZero() and other methods which rely on IsZero(), e.g. String().

I'd recommend to rewrite IsZero() in a way that does not depend on Zero, e.g.

func (u Uint128) IsZero() bool {
	return u == Uint128{}
}

Add overflow/underflow checking

The Sub and Sub64 methods should panic on underflow, and the Add, Add64, Mul, and Mul64 methods should panic on overflow. Lsh and Rsh can be left as-is.

[Question] Should Mul or Sub panic for overflow or underflow?

Hi. Internal uint64 type desn't panic in those cases. It just leaving available data

Implement more math/bits methods

Feel free to submit separate PRs for any of the following methods:

• Len
• OnesCount
• Reverse
• ReverseBytes
• RotateLeft
• RotateRight
• TrailingZeros

Tests are very much appreciated, but not strictly required.

Add Mod and Mod64 methods

These should be trivial; just use the second return value from QuoRem. (Note that "Rem" is perhaps the more accurate name here, but "Mod" is more familiar to programmers.)

Add fromString method

I would love to use this for uuid parsing. Being able to go to base10 strings is great, but without a way to go back I can't use this.

Right now I do the following:

uuid str -> hex bytes -> u128 -> base 10 str

But I'm unable to reverse it as there's no way to get to u128 from the string.

Pow

How I can do Pow math? (Trying to shorten UUIDs)