Skip to content

Instantly share code, notes, and snippets.

@seh
Created Feb 13, 2017
Embed
What would you like to do?
Decimal length of a nonnegative integer
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
// 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
}
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)
}
@ericlagergren

This comment has been minimized.

Copy link

@ericlagergren ericlagergren commented Feb 13, 2017

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

@seh

This comment has been minimized.

Copy link
Owner Author

@seh seh commented Feb 13, 2017

@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?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment