intmath

README

intmath

intmath implements some useful integer math functions. Think of it as the package that complements math/bits to have a wholly usable math but for integers.

You can read the package documentation. You can also read a rambly blogpost about it. Your choice!

---

In the tests, you'll find

• "basic" tests that sanity check form a handful of values, comparing the result to known values.
• "quick" tests (using testing/quick) that compare the result with slower, assumed-correct implementations. Some of these are not quick, despite the name; if you run the tests without -short you'll probably need to add a bigger -timeout.
• benchmarks that compare the functions to the slower versions.

Documentation

Index

• func Abs[V constraints.Signed](n V) V
• func Binomial[V constraints.Unsigned](n, k V) (uint64, bool)
• func CeilLog10[V constraints.Unsigned](u V) V
• func CeilLog2[V constraints.Unsigned](u V) V
• func FloorLog10[V constraints.Unsigned](u V) V
• func FloorLog2[V constraints.Unsigned](u V) V
• func Len[V constraints.Integer](n V) V
• func Pow[V constraints.Unsigned](m, n V) V
• func PowX[V constraints.Unsigned](m, n V) (pow uint64, overflowed bool)
• func Sqrt[V constraints.Unsigned](n V) V

Functions

func Abs

func Abs[V constraints.Signed](n V) V

Abs(n) computes the absolute value of n, without branching.

I haven't been able to track down the original source of this algorithm. Read more on Sean Eron Anderson's “Bit Twiddling Hacks”, https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs

func Binomial

func Binomial[V constraints.Unsigned](n, k V) (uint64, bool)

Binomial(n, k) == ‹(n k), false›. Unless the result overflows uint64, in which case it returns ‹0, true›.

This is a generic iterative algorithm using `math/bits` multiplication to detect overflow (and to allow the internal operations to slightly exceed uint64 in some cases).

func CeilLog10

func CeilLog10[V constraints.Unsigned](u V) V

CeilLog10(u) returns ⌈log₁₀u⌉.

If u is 0, you'll get a nonsense result.

This is almost exactly the same as `FloorLog10`. The difference is a single `>=` instead of a `>` when deciding whether an offset is needed.

func CeilLog2

func CeilLog2[V constraints.Unsigned](u V) V

CeilLog2(u) returns ⌈log₂u⌉.

If u is 0, you'll get a nonsense result.

This one cheats, as ⌈log₂u⌉ is just `math/bits.Len64(u-1)`.

func FloorLog10

func FloorLog10[V constraints.Unsigned](u V) V

FloorLog10(u) returns ⌊log₁₀u⌋

If u is 0, you'll get a nonsense result.

This starts from Sean Eron Anderson's “Bit Twiddling Hacks” entry on “Find integer log base 10 of an integer”, but combines that with the fact that ⌈log₂u⌉ is just `math/bits.Len64(u-1)` and that in most places that's a hardware instruction. There are some pesky offsets that need to be tracked in a table.

func FloorLog2

func FloorLog2[V constraints.Unsigned](u V) V

FloorLog10(u) returns ⌊log₂u⌋

If u is 0, you'll get a nonsense result.

This algorithm is from “Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup” from Sean Eron Anderson's “Bit Twiddling Hacks”

func Len

func Len[V constraints.Integer](n V) V

Len(n) returns the length of the base-10 string of n.

Len(u) is essentially ⌊log₁₀u⌋+1.

func Pow

func Pow[V constraints.Unsigned](m, n V) V

Pow(m, n) == mⁿ

from TAOCPv2, §4.6.3 (p462 in the 3rd edition)

func PowX

func PowX[V constraints.Unsigned](m, n V) (pow uint64, overflowed bool)

PowX(m, n) == ‹mⁿ, false› as long as it fits in a uint64. As soon as it overflows it returns ‹0, true›.

from TAOCPv2, §4.6.3 (p462 in the 3rd edition)

func Sqrt

func Sqrt[V constraints.Unsigned](n V) V

Sqrt(u) returns √u

The current implementation uses floating point as that is implemented in hardware in most places (see SqrtI and associated benchmarks in the tests). This might change if somebody points me to a faster version.