How can I efficiently compute the quotient of two integers, rounded down (not towards zero) in Go? The following code seems to give the correct result, but looks awkward and inefficient:

func floorDiv(a, b int) int {
    if b < 0 {
        a, b = -a, -b
    }
    r := a % b
    if r < 0 {
        r  = b
    }
    return (a - r) / b
}

(also on the playground). Is there a better way?

CodePudding user response：

Convert the integers to float64, divide, and use math.Floor.

func floorDiv(a, b int) int {
  return int(math.Floor(float64(a)/float64(b)))
}

Benchmarking shows they run in about the same time, and the same as a simple add function.

func BenchmarkFloorDiv(b *testing.B) {
  for i := 0; i < b.N; i   {
    _ = floorDiv(i, 3)
  }
}

func BenchmarkFloorDivGo(b *testing.B) {
  for i := 0; i < b.N; i   {
    _ = floorDivGo(i, 3)
  }
}

func BenchmarkFloorAdd(b *testing.B) {
  for i := 0; i < b.N; i   {
    _ = add(i, 3)
  }
}

goos: darwin
goarch: amd64
pkg: github.com/my/repo/test_go
cpu: Intel(R) Core(TM) i7-8559U CPU @ 2.70GHz
BenchmarkFloorDiv-8         1000000000           0.2612 ns/op
BenchmarkFloorDivGo-8       1000000000           0.2610 ns/op
BenchmarkFloorAdd-8         1000000000           0.2565 ns/op
PASS
ok      github.com/my/repo/test_go  1.000s

This suggests it's so fast we're just benchmarking the loop. It is unlikely to be a bottleneck, I would suggest the simplest option.

CodePudding user response：

Bit twiddling is your friend here — I'll put this up against converting two integers to doubles and using math.Floor().

func IntFloorDiv(x int, y int) int {
  q := x / y
  r := x % y
  
  if r != 0 && x&math.MinInt != y&math.MinInt {
    q -= 1
  }
  
  return q
}

Bit-twiddling allows us to easily identify the sign of a two's-complement integer:

• The smallest [negative] value that a two's-complement integer may contain has the sign bit set and the remaining bits all clear (0x80000000).

• A bitwise AND of an integer value against that smallest value gives us either 0 or the smallest value that that integer type may contain:

  • 5 & math.MinInt yields 0
  • 0 & math.MinInt yields 0
  • -5 & Math.MinInt yields math.MinInt

That lets us do this:

1. Compute the quotient and remainder for x / y.

2. If the remainder is zero, the quotient is ⌊ x / y ⌋.

3. Otherwise (the remainder is non-zero),

   1. If the sign bits differ, the quotient is negative and we must subtract 1 from the quotient to yield ⌊ x / y ⌋.
   2. if the sign bits are identical, the quotient is positive and the quotient is ⌊ x / y ⌋.

Click here for the Go Playground

Results for x such that -10 ≤ x ≤ 10, and y = 3:

Benchmarks

Benchmark timings across 5 different runs show that converting to float and using math.Floor() to be nearly 21x slower than integer division and bit twiddling.

[Whether or not that actually matters is entirely dependent on the use case.]

The benchmark code calls the function being benchmarked 21x per loop iteration (for -10 to 10 inclusive) so the cost of the loop code doesn't mask the function being benchmarked.

❯ go test -bench=.
goos: darwin
goarch: amd64
pkg: foobar.com/floordiv
cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
Benchmark_floorDiv_Int-8        1000000000               0.2730 ns/op
Benchmark_floorDiv_Math-8       189576496                5.969 ns/op
PASS
ok      foobar.com/floordiv     2.266s

❯ go test -bench=.
goos: darwin
goarch: amd64
pkg: foobar.com/floordiv
cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
Benchmark_floorDiv_Int-8        1000000000               0.2718 ns/op
Benchmark_floorDiv_Math-8       196402200                5.954 ns/op
PASS
ok      foobar.com/floordiv     2.243s

❯ go test -bench=.
goos: darwin
goarch: amd64
pkg: foobar.com/floordiv
cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
Benchmark_floorDiv_Int-8        1000000000               0.2756 ns/op
Benchmark_floorDiv_Math-8       200432154                5.976 ns/op
PASS
ok      foobar.com/floordiv     2.271s

❯ go test -bench=.
goos: darwin
goarch: amd64
pkg: foobar.com/floordiv
cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
Benchmark_floorDiv_Int-8        1000000000               0.2814 ns/op
Benchmark_floorDiv_Math-8       195009298                6.083 ns/op
PASS
ok      foobar.com/floordiv     2.314s

❯ go test -bench=.
goos: darwin
goarch: amd64
pkg: foobar.com/floordiv
cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
Benchmark_floorDiv_Int-8        1000000000               0.2751 ns/op
Benchmark_floorDiv_Math-8       201196482                6.033 ns/op
PASS
ok      foobar.com/floordiv     2.290s

running this benchmark:

package main

import (
  "math"
  "testing"
)

func floorDiv_Int(x int, y int) int {
  q := x / y
  r := x % y
  
  if r != 0 && x&math.MinInt != y&math.MinInt {
    q -= 1
    }
  
  return q
}

func floorDiv_Math(x int, y int) int {
  return int(math.Floor(
    float64(x) / float64(y),
  ))
}

func Benchmark_floorDiv_Int(b *testing.B) {
  for i := 0; i < b.N; i   {
    floorDiv_Int(-10, 3)
    floorDiv_Int(-9, 3)
    floorDiv_Int(-8, 3)
    floorDiv_Int(-7, 3)
    floorDiv_Int(-6, 3)
    floorDiv_Int(-5, 3)
    floorDiv_Int(-4, 3)
    floorDiv_Int(-3, 3)
    floorDiv_Int(-2, 3)
    floorDiv_Int(-1, 3)
    floorDiv_Int(0, 3)
    floorDiv_Int(1, 3)
    floorDiv_Int(2, 3)
    floorDiv_Int(3, 3)
    floorDiv_Int(4, 3)
    floorDiv_Int(5, 3)
    floorDiv_Int(6, 3)
    floorDiv_Int(7, 3)
    floorDiv_Int(8, 3)
    floorDiv_Int(9, 3)
    floorDiv_Int(10, 3)
  }
}

func Benchmark_floorDiv_Math(b *testing.B) {
  for i := 0; i < b.N; i   {
    floorDiv_Math(-10, 3)
    floorDiv_Math(-9, 3)
    floorDiv_Math(-8, 3)
    floorDiv_Math(-7, 3)
    floorDiv_Math(-6, 3)
    floorDiv_Math(-5, 3)
    floorDiv_Math(-4, 3)
    floorDiv_Math(-3, 3)
    floorDiv_Math(-2, 3)
    floorDiv_Math(-1, 3)
    floorDiv_Math(0, 3)
    floorDiv_Math(1, 3)
    floorDiv_Math(2, 3)
    floorDiv_Math(3, 3)
    floorDiv_Math(4, 3)
    floorDiv_Math(5, 3)
    floorDiv_Math(6, 3)
    floorDiv_Math(7, 3)
    floorDiv_Math(8, 3)
    floorDiv_Math(9, 3)
    floorDiv_Math(10, 3)
  }
}