Decimal length of a nonnegative integer

benchmarks.txt

go test -run=NONE -bench=.
BenchmarkDecimalByDecay-8                	50000000	        32.7 ns/op
BenchmarkDecimalByDecay2-8               	50000000	        30.5 ns/op
BenchmarkDecimalByRecursiveDecay-8       	20000000	        84.5 ns/op
BenchmarkDecimalByLogarithmFloor-8       	30000000	        46.5 ns/op
BenchmarkDecimalByLogarithmCeiling-8     	30000000	        45.2 ns/op
BenchmarkDecimalByLinearTableScan-8      	100000000	        17.9 ns/op
BenchmarkDecimalByLinearTableScan2-8     	100000000	        18.6 ns/op
BenchmarkDecimalByBinaryTableSearch-8    	50000000	        27.9 ns/op
BenchmarkDecimalByManualBinarySearch-8   	200000000	         6.51 ns/op

length.go

// Package dlength provides functions for computing the length of numbers when formatted.
package dlength

import (
	"math"
	"sort"
)

func DecimalByDecay(n uint) uint8 {
	var length uint8 = 1
	for {
		n /= 10
		if n == 0 {
			break
		}
		length++
	}
	return length
}

func DecimalByDecay2(n uint) uint8 {
	var length uint8 = 1
	for {
		if n < 10 {
			break
		}
		n /= 10
		length++
	}
	return length
}

func decimalLengthRec(n uint, r uint8) uint8 {
	if n < 10 {
		return r
	}
	return decimalLengthRec(n/10, r+1)
}

func DecimalByRecursiveDecay(n uint) uint8 {
	return decimalLengthRec(n, 1)
}

func DecimalByLogarithmFloor(n uint) uint8 {
	if n == 0 {
		return 1
	}
	return uint8(math.Floor(math.Log10(float64(n))) + 1)
}

const maxUint = ^uint(0)

var (
	thresholds    []uint
	numThresholds int
	maxLength     uint8
)

func init() {
	for i := uint(10); ; i *= 10 {
		thresholds = append(thresholds, i-1)
		if maxUint/i < 10 {
			break
		}
	}
	thresholds = append(thresholds, maxUint)
	numThresholds = len(thresholds)
	maxLength = uint8(numThresholds)
}

func DecimalByLogarithmCeiling(n uint) uint8 {
	switch n {
	case 0, 1:
		return 1
	case maxUint:
		return maxLength
	default:
		return uint8(math.Ceil(math.Log10(float64(n + 1))))
	}
}

func DecimalByLinearTableScan(n uint) uint8 {
	for i, t := range thresholds {
		if n <= t {
			return uint8(i + 1)
		}
	}
	panic("unreachable")
}

func DecimalByLinearTableScan2(n uint) uint8 {
	for i := 0; ; i++ {
		if n <= thresholds[i] {
			return uint8(i + 1)
		}
	}
}

func DecimalByBinaryTableSearch(n uint) uint8 {
	return uint8(sort.Search(numThresholds, func(i int) bool { return thresholds[i] >= n }) + 1)
}

func DecimalByManualBinarySearch(n uint) uint8 {
	if n < 10000000000 {
		if n < 100000 {
			if n < 1000 {
				switch {
				case n < 10:
					return 1
				case n < 100:
					return 2
				default:
					return 3
				}
			}
			if n < 10000 {
				return 4
			}
			return 5
		}
		if n < 100000000 {
			switch {
			case n < 1000000:
				return 6
			case n < 10000000:
				return 7
			default:
				return 8
			}
		}
		if n < 1000000000 {
			return 9
		}
		return 10
	}
	if n < 1000000000000000 {
		if n < 10000000000000 {
			switch {
			case n < 100000000000:
				return 11
			case n < 1000000000000:
				return 12
			default:
				return 13
			}
		}
		if n < 100000000000000 {
			return 14
		}
		return 15
	}
	if n < 1000000000000000000 {
		switch {
		case n < 10000000000000000:
			return 16
		case n < 100000000000000000:
			return 17
		default:
			return 18
		}
	}
	if n < 10000000000000000000 {
		return 19
	}
	return maxLength
}

length_test.go

package dlength_test

import (
	"dlength"
	"math"
	"math/rand"
	"strconv"
	"testing"
)

const maxUint = ^uint(0)

func test(t *testing.T, f func(uint) uint8) {
	tests := []struct {
		n        uint
		expected uint8
	}{
		{0, 1},
		{9, 1},
		{10, 2},
		{11, 2},
		{99, 2},
		{100, 3},
		{101, 3},
		{99999, 5},
		{100000, 6},
		{maxUint, uint8(math.Floor(math.Log10(float64(maxUint))) + 1)},
	}
	for _, test := range tests {
		t.Run(strconv.FormatUint(uint64(test.n), 10), func(t *testing.T) {
			if got := f(test.n); got != test.expected {
				t.Fatalf("want %d, got %d", test.expected, got)
			}
		})
	}
}

const n = 1024

var (
	input  [n]uint
	result uint8
)

func init() {
	rand.Seed(0)
	for i := 0; i != n; i++ {
		// Until Go 1.8 provides rand.Uint64:
		input[i] = uint(uint64(rand.Int63())>>31 | uint64(rand.Int63())<<32)
	}
}

func bench(b *testing.B, f func(uint) uint8) {
	var r uint8
	for i := 0; i != b.N; i++ {
		r = f(input[i%n])
	}
	result = r
}

func TestDecimalByDecay(t *testing.T) {
	test(t, dlength.DecimalByDecay)
}

func BenchmarkDecimalByDecay(b *testing.B) {
	bench(b, dlength.DecimalByDecay)
}

func TestDecimalByDecay2(t *testing.T) {
	test(t, dlength.DecimalByDecay2)
}

func BenchmarkDecimalByDecay2(b *testing.B) {
	bench(b, dlength.DecimalByDecay2)
}

func TestDecimalByRecursiveDecay(t *testing.T) {
	test(t, dlength.DecimalByRecursiveDecay)
}

func BenchmarkDecimalByRecursiveDecay(b *testing.B) {
	bench(b, dlength.DecimalByRecursiveDecay)
}

func TestDecimalByLogarithmFloor(t *testing.T) {
	test(t, dlength.DecimalByLogarithmFloor)
}

func BenchmarkDecimalByLogarithmFloor(b *testing.B) {
	bench(b, dlength.DecimalByLogarithmFloor)
}

func TestDecimalByLogarithmCeiling(t *testing.T) {
	test(t, dlength.DecimalByLogarithmCeiling)
}

func BenchmarkDecimalByLogarithmCeiling(b *testing.B) {
	bench(b, dlength.DecimalByLogarithmCeiling)
}

func TestDecimalByLinearTableScan(t *testing.T) {
	test(t, dlength.DecimalByLinearTableScan)
}

func BenchmarkDecimalByLinearTableScan(b *testing.B) {
	bench(b, dlength.DecimalByLinearTableScan)
}

func TestDecimalByLinearTableScan2(t *testing.T) {
	test(t, dlength.DecimalByLinearTableScan2)
}

func BenchmarkDecimalByLinearTableScan2(b *testing.B) {
	bench(b, dlength.DecimalByLinearTableScan2)
}

func TestDecimalByBinaryTableSearch(t *testing.T) {
	test(t, dlength.DecimalByBinaryTableSearch)
}

func BenchmarkDecimalByBinaryTableSearch(b *testing.B) {
	bench(b, dlength.DecimalByBinaryTableSearch)
}

func TestDecimalByManualBinarySearch(t *testing.T) {
	test(t, dlength.DecimalByManualBinarySearch)
}

func BenchmarkDecimalByManualBinarySearch(b *testing.B) {
	bench(b, dlength.DecimalByManualBinarySearch)
}

@seh might also try: ((N - clz(x) + 1) * 1233) >> 12 where N is the size word size in bits.

@ericlagergren Were it not for 1,233 being such a strange number (with a high IDF), I would not have found this entry to help me understand your proposal. Thank you for the idea.

We won't have a CLZ function available in Go until golang/go#18616 comes to fruition, right?