Fast division, modulus and divisibility checks in Go for divisors known only at runtime.

Overview

fastdiv

GoDoc

Fast division, modulus and divisibility checks for divisors known only at runtime via the method of:

"Faster Remainder by Direct Computation: Applications to Compilers and Software Libraries" Daniel Lemire, Owen Kaser, Nathan Kurz arXiv:1902.01961

Usage:

var divisor uint32 = 3

// intialize a divisor at runtime
d := fastdiv.NewUint32(divisor)

// use it repeatedly
var total uint32
for i := uint32(1); i < 10; i++ {
	total += d.Div(i)
	if d.Divisible(i) {
		fmt.Printf("%d is divisible by %d\n", i, divisor)
	}
}
fmt.Printf("Sum of quotients = %d", total)

// Output:
// 3 is divisible by 3
// 6 is divisible by 3
// 9 is divisible by 3
// Sum of quotients = 12

The method works by pre-computing an approximate inverse of the divisor such that the quotient is given by the high part of the multiplication and the remainder can be calculated by multiplying the fraction contained in the low part by the original divisor. In general, the required accuracy for the approximate inverse is twice the width of the original divisor. For divisors that are half the width of a register or less, this means that the quotient can be calculated with one high-multiplication (top word of a full-width multiplication), the remainder can be calculated with one low-multiplication followed by a high-multiplication and both can be calculated with one full-width multiplication and one high-multiplication.

On amd64 architecture for divisors that are 32-bits or less, this method can be faster than the traditional Granlund-Montgomery-Warren approach used to optimize constant divisions in the compiler. The requirement that the approximate inverse be twice the divisor width means that extended arithmetic is required for 64-bit divisors. The extended arithmetic makes this method is somewhat slower than the Granlund-Montgomery-Warren approach for these larger divisors, but still faster than 64-bit division instructions.

The per operation speed up over a division instruction is ~2-3x and the overhead of pre-computing the inverse can be amortized after 1-6 repeated divisions with the same divisor.

op size var const fastdiv var / fastdiv # to breakeven
div uint16 15.5 ns 5.46 ns 5.32 ns 2.9x 1
mod uint16 16.2 ns 7.68 ns 7.68 ns 2.1x 1
div int16 16.7 ns 5.91 ns 6.55 ns 2.5x 1
mod int16 17.5 ns 8.86 ns 8.86 ns 2.0x 1
div uint32 15.5 ns 7.28 ns 5.53 ns 2.8x 2
mod uint32 15.7 ns 9.63 ns 7.09 ns 2.2x 2
div int32 16.0 ns 5.91 ns 5.91 ns 2.7x 2
mod int32 16.1 ns 8.86 ns 8.27 ns 1.9x 2
div uint64 21.4 ns 5.91 ns 6.89 ns 3.1x 5
mod uint64 20.3 ns 8.30 ns 8.87 ns 2.3x 6
div int64 26.2 ns 7.26 ns 8.51 ns 3.0x 5
mod int64 25.8 ns 9.57 ns 16.8 ns 1.5x 6
You might also like...
A little fast cloc(Count Lines Of Code)

gocloc A little fast cloc(Count Lines Of Code), written in Go. Inspired by tokei. Installation $ go get -u github.com/hhatto/gocloc/cmd/gocloc Usage

Jenkins tracer is used to record all the Jenkins job environment variables and metrics, and send them to Elasticsearch

Jenkins Tracer Jenkins tracer is used to record all the jenkins job variables like record the build duration, build variables, repository metadata, et

Clean architecture validator for go, like a The Dependency Rule and interaction between packages in your Go projects.
Clean architecture validator for go, like a The Dependency Rule and interaction between packages in your Go projects.

Clean Architecture checker for Golang go-cleanarch was created to keep Clean Architecture rules, like a The Dependency Rule and interaction between mo

Manage your repository's TODOs, tickets and checklists as config in your codebase.

tickgit 🎟️ tickgit is a tool to help you manage latent work in a codebase. Use the tickgit command to view pending tasks, progress reports, completio

depth is tool to retrieve and visualize Go source code dependency trees.

depth is tool to retrieve and visualize Go source code dependency trees. Install Download the appropriate binary for your platform from the Rele

A reference for the Go community that covers the fundamentals of writing clean code and discusses concrete refactoring examples specific to Go.

A reference for the Go community that covers the fundamentals of writing clean code and discusses concrete refactoring examples specific to Go.

Tool to populate your code with traceable and secure error codes

Essential part of any project, especially customer facing is proper and secure error handling. When error happens and customer reports it, it would be nice to know the context of the error and where it exactly occured.

🔥 ~6x faster, stricter, configurable, extensible, and beautiful drop-in replacement for golint
🔥 ~6x faster, stricter, configurable, extensible, and beautiful drop-in replacement for golint

revive Fast, configurable, extensible, flexible, and beautiful linter for Go. Drop-in replacement of golint. Revive provides a framework for developme

Comments
  • [question] big.Int divisor

    [question] big.Int divisor

    Really nice project! I didn't go far to fastdiv, can the operations(DIV/MOD) be used in big.Int(math/big)? If so, some elliptic curves(such as secp256k1) in go code would be more faster. Thanks.

    opened by BohuTANG 0
Owner
null
The Golang linter that checks that there is no simultaneous return of `nil` error and an invalid value.

nilnil Checks that there is no simultaneous return of nil error and an invalid value. Installation & usage $ go install github.com/Antonboom/[email protected]

Anton Telyshev 12 Aug 30, 2022
apicompat checks recent changes to a Go project for backwards incompatible changes

Introduction apicompat is a tool to check for the introduction of backwards incompatible changes. apicompat: Guarantees that all consumers of a librar

Bradley Falzon 175 Aug 3, 2022
errcheck checks that you checked errors.

errcheck errcheck is a program for checking for unchecked errors in go programs. Install go get -u github.com/kisielk/errcheck errcheck requires Go 1

Kamil Kisiel 1.9k Sep 27, 2022
This is a style verifier intended to be used with the Gerrit checks plugin.

GERRITFMT This is a style verifier intended to be used with the Gerrit checks plugin. HOW TO USE Install formatters: go install github.com/bazelbuild/

Google 23 Sep 2, 2022
Go linter which checks for dangerous unicode character sequences

bidichk - checks for dangerous unicode character sequences bidichk finds dangerous unicode character sequences in Go source files. Considered dangerou

Lucas Bremgartner 25 Oct 1, 2022
nostdglobals is a simple Go linter that checks for usages of global variables defined in the go standard library

nostdglobals is a simple Go linter that checks for usages of global variables defined in the go standard library

Nassos Kat 1 Feb 17, 2022
Converts a trace of Datadog to a sequence diagram of PlantUML (Currently, supports only gRPC)

jigsaw Automatically generate a sequence diagram from JSON of Trace in Datadog. ⚠️ Only gRPC calls appear in the sequence diagram. Example w/ response

Yu SERIZAWA 6 Jul 12, 2022
Sloc, Cloc and Code: scc is a very fast accurate code counter with complexity calculations and COCOMO estimates written in pure Go

Sloc Cloc and Code (scc) A tool similar to cloc, sloccount and tokei. For counting physical the lines of code, blank lines, comment lines, and physica

Ben Boyter 3.8k Sep 30, 2022
Bundle k6 with extensions as fast and easily as possible

xk6bundler xk6bundler is a CLI tool and GitHub Action makes bundle k6 with extensions as fast and easily as possible. Features Build for multiple targ

Iván Szkiba 10 Sep 26, 2022
Fast linters Runner for Go

golangci-lint Fast linters runner for Go golangci-lint is a fast Go linters runner. It runs linters in parallel, uses caching, supports yaml config, h

null 11.2k Sep 26, 2022