compute the floor of an integer division efficiently

huangapple
go评论121阅读模式
英文:

compute the floor of an integer division efficiently

问题

如何在Go语言中高效地计算两个整数的商（向下取整，而不是向零取整）？以下代码似乎给出了正确的结果，但看起来笨拙且低效：

  1. func floorDiv(a, b int) int {
  2.     if b < 0 {
  3.         a, b = -a, -b
  4.     }
  5.     r := a % b
  6.     if r < 0 {
  7.         r += b
  8.     }
  9.     return (a - r) / b
  10. }

（也可以在playground上查看）。有更好的方法吗？

英文:

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:

  1. func floorDiv(a, b int) int {
  2. 	if b &lt; 0 {
  3. 		a, b = -a, -b
  4. 	}
  5. 	r := a % b
  6. 	if r &lt; 0 {
  7. 		r += b
  8. 	}
  9. 	return (a - r) / b
  10. }

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

答案1

得分: 3

将整数转换为float64，进行除法运算，并使用math.Floor函数。

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

基准测试显示它们的运行时间大致相同，并且与简单的加法函数相同。

  1. func BenchmarkFloorDiv(b *testing.B) {
  2.   for i := 0; i < b.N; i++ {
  3.     _ = floorDiv(i, 3)
  4.   }
  5. }
  7. func BenchmarkFloorDivGo(b *testing.B) {
  8.   for i := 0; i < b.N; i++ {
  9.     _ = floorDivGo(i, 3)
  10.   }
  11. }
  13. func BenchmarkFloorAdd(b *testing.B) {
  14.   for i := 0; i < b.N; i++ {
  15.     _ = add(i, 3)
  16.   }
  17. }
  19. goos: darwin
  20. goarch: amd64
  21. pkg: github.com/my/repo/test_go
  22. cpu: Intel(R) Core(TM) i7-8559U CPU @ 2.70GHz
  23. BenchmarkFloorDiv-8     	1000000000	         0.2612 ns/op
  24. BenchmarkFloorDivGo-8   	1000000000	         0.2610 ns/op
  25. BenchmarkFloorAdd-8     	1000000000	         0.2565 ns/op
  26. PASS
  27. ok  	github.com/my/repo/test_go	1.000s

这表明它运行得非常快，我们只是在对循环进行基准测试。它不太可能成为瓶颈，我建议选择最简单的选项。

英文:

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

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

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

  1. func BenchmarkFloorDiv(b *testing.B) {
  2.   for i := 0; i &lt; b.N; i++ {
  3.     _ = floorDiv(i, 3)
  4.   }
  5. }
  7. func BenchmarkFloorDivGo(b *testing.B) {
  8.   for i := 0; i &lt; b.N; i++ {
  9.     _ = floorDivGo(i, 3)
  10.   }
  11. }
  13. func BenchmarkFloorAdd(b *testing.B) {
  14.   for i := 0; i &lt; b.N; i++ {
  15.     _ = add(i, 3)
  16.   }
  17. }
  19. goos: darwin
  20. goarch: amd64
  21. pkg: github.com/my/repo/test_go
  22. cpu: Intel(R) Core(TM) i7-8559U CPU @ 2.70GHz
  23. BenchmarkFloorDiv-8     	1000000000	         0.2612 ns/op
  24. BenchmarkFloorDivGo-8   	1000000000	         0.2610 ns/op
  25. BenchmarkFloorAdd-8     	1000000000	         0.2565 ns/op
  26. PASS
  27. 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.

答案2

得分: 2

位操作在这里非常有用 - 我将其与将两个整数转换为浮点数并使用math.Floor()进行比较。

  1. func IntFloorDiv(x int, y int) int {
  2.   q := x / y
  3.   r := x % y
  4.   
  5.   if r != 0 && x&math.MinInt != y&math.MinInt {
  6.     q -= 1
  7.   }
  8.   
  9.   return q
  10. }

位操作使我们能够轻松确定二进制补码整数的符号：

  • 一个二进制补码整数可能包含的最小[负]值具有设置了符号位和其余位都清零的值（0x80000000）。

  • 整数值与该最小值进行按位与运算，可以得到0或该整数类型可能包含的最小值：

    • 5 & math.MinInt 得到0
    • 0 & math.MinInt 得到0
    • -5 & Math.MinInt 得到math.MinInt

这样我们就可以做到：

  1. 计算 x / y 的商和余数。

  2. 如果余数为零，则商为 ⌊ x / y ⌋。

  3. 否则（余数非零），

    1. 如果符号位不同，则商为负数，我们必须从商中减去1，得到 ⌊ x / y ⌋。
    2. 如果符号位相同，则商为正数，商为 ⌊ x / y ⌋。

点击这里查看Go Playground

对于 -10 ≤ x ≤ +10，y = 3 的结果：

X Y ⌊X÷Y⌋
-10 3 -4
-9 3 -3
-8 3 -3
-7 3 -3
-6 3 -2
-5 3 -2
-4 3 -2
-3 3 -1
-2 3 -1
-1 3 -1
0 3 0
1 3 0
2 3 0
3 3 1
4 3 1
5 3 1
6 3 2
7 3 2
8 3 2
9 3 3
10 3 3

基准测试

在5次不同运行中的基准测试时间显示，将其转换为浮点数并使用math.Floor()比整数除法和位操作慢了近21倍。

[是否真正重要完全取决于用例。]

基准测试代码每次循环迭代调用被基准测试的函数21次（对于-10到+10的范围），因此循环代码的成本不会掩盖被基准测试的函数。

  1. ❯ go test -bench=.
  2. goos: darwin
  3. goarch: amd64
  4. pkg: foobar.com/floordiv
  5. cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
  6. Benchmark_floorDiv_Int-8        1000000000               0.2730 ns/op
  7. Benchmark_floorDiv_Math-8       189576496                5.969 ns/op
  8. PASS
  9. ok      foobar.com/floordiv     2.266s
  11. ❯ go test -bench=.
  12. goos: darwin
  13. goarch: amd64
  14. pkg: foobar.com/floordiv
  15. cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
  16. Benchmark_floorDiv_Int-8        1000000000               0.2718 ns/op
  17. Benchmark_floorDiv_Math-8       196402200                5.954 ns/op
  18. PASS
  19. ok      foobar.com/floordiv     2.243s
  21. ❯ go test -bench=.
  22. goos: darwin
  23. goarch: amd64
  24. pkg: foobar.com/floordiv
  25. cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
  26. Benchmark_floorDiv_Int-8        1000000000               0.2756 ns/op
  27. Benchmark_floorDiv_Math-8       200432154                5.976 ns/op
  28. PASS
  29. ok      foobar.com/floordiv     2.271s
  31. ❯ go test -bench=.
  32. goos: darwin
  33. goarch: amd64
  34. pkg: foobar.com/floordiv
  35. cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
  36. Benchmark_floorDiv_Int-8        1000000000               0.2814 ns/op
  37. Benchmark_floorDiv_Math-8       195009298                6.083 ns/op
  38. PASS
  39. ok      foobar.com/floordiv     2.314s
  41. ❯ go test -bench=.
  42. goos: darwin
  43. goarch: amd64
  44. pkg: foobar.com/floordiv
  45. cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
  46. Benchmark_floorDiv_Int-8        1000000000               0.2751 ns/op
  47. Benchmark_floorDiv_Math-8       201196482                6.033 ns/op
  48. PASS
  49. ok      foobar.com/floordiv     2.290s

运行此基准测试的代码：

  1. package main
  3. import (
  4.   "math"
  5.   "testing"
  6. )
  8. func floorDiv_Int(x int, y int) int {
  9.   q := x / y
  10.   r := x % y
  11.   
  12.   if r != 0 && x&math.MinInt != y&math.MinInt {
  13.     q -= 1
  14.     }
  15.   
  16.   return q
  17. }
  19. func floorDiv_Math(x int, y int) int {
  20.   return int(math.Floor(
  21.     float64(x) / float64(y),
  22.   ))
  23. }
  25. func Benchmark_floorDiv_Int(b *testing.B) {
  26.   for i := 0; i < b.N; i++ {
  27.     floorDiv_Int(-10, 3)
  28.     floorDiv_Int(-9, 3)
  29.     floorDiv_Int(-8, 3)
  30.     floorDiv_Int(-7, 3)
  31.     floorDiv_Int(-6, 3)
  32.     floorDiv_Int(-5, 3)
  33.     floorDiv_Int(-4, 3)
  34.     floorDiv_Int(-3, 3)
  35.     floorDiv_Int(-2, 3)
  36.     floorDiv_Int(-1, 3)
  37.     floorDiv_Int(0, 3)
  38.     floorDiv_Int(1, 3)
  39.     floorDiv_Int(2, 3)
  40.     floorDiv_Int(3, 3)
  41.     floorDiv_Int(4, 3)
  42.     floorDiv_Int(5, 3)
  43.     floorDiv_Int(6, 3)
  44.     floorDiv_Int(7, 3)
  45.     floorDiv_Int(8, 3)
  46.     floorDiv_Int(9, 3)
  47.     floorDiv_Int(10, 3)
  48.   }
  49. }
  51. func Benchmark_floorDiv_Math(b *testing.B) {
  52.   for i := 0; i < b.N; i++ {
  53.     floorDiv_Math(-10, 3)
  54.     floorDiv_Math(-9, 3)
  55.     floorDiv_Math(-8, 3)
  56.     floorDiv_Math(-7, 3)
  57.     floorDiv_Math(-6, 3)
  58.     floorDiv_Math(-5, 3)
  59.     floorDiv_Math(-4, 3)
  60.     floorDiv_Math(-3, 3)
  61.     floorDiv_Math(-2, 3)
  62.     floorDiv_Math(-1, 3)
  63.     floorDiv_Math(0, 3)
  64.     floorDiv_Math(1, 3)
  65.     floorDiv_Math(2, 3)
  66.     floorDiv_Math(3, 3)
  67.     floorDiv_Math(4, 3)
  68.     floorDiv_Math(5, 3)
  69.     floorDiv_Math(6, 3)
  70.     floorDiv_Math(7, 3)
  71.     floorDiv_Math(8, 3)
  72.     floorDiv_Math(9, 3)
  73.     floorDiv_Math(10, 3)
  74.   }
  75. }
英文:

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

  1. func IntFloorDiv(x int, y int) int {
  2. q := x / y
  3. r := x % y
  4. if r != 0 &amp;&amp; x&amp;math.MinInt != y&amp;math.MinInt {
  5. q -= 1
  6. }
  7. return q
  8. }

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 &amp; math.MinInt yields 0
    • 0 &amp; math.MinInt yields 0
    • -5 &amp; 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:

X Y ⌊X÷Y⌋
-10 3 -4
-9 3 -3
-8 3 -3
-7 3 -3
-6 3 -2
-5 3 -2
-4 3 -2
-3 3 -1
-2 3 -1
-1 3 -1
0 3 0
1 3 0
2 3 0
3 3 1
4 3 1
5 3 1
6 3 2
7 3 2
8 3 2
9 3 3
10 3 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.

  1. ❯ go test -bench=.
  2. goos: darwin
  3. goarch: amd64
  4. pkg: foobar.com/floordiv
  5. cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
  6. Benchmark_floorDiv_Int-8        1000000000               0.2730 ns/op
  7. Benchmark_floorDiv_Math-8       189576496                5.969 ns/op
  8. PASS
  9. ok      foobar.com/floordiv     2.266s
  11. ❯ go test -bench=.
  12. goos: darwin
  13. goarch: amd64
  14. pkg: foobar.com/floordiv
  15. cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
  16. Benchmark_floorDiv_Int-8        1000000000               0.2718 ns/op
  17. Benchmark_floorDiv_Math-8       196402200                5.954 ns/op
  18. PASS
  19. ok      foobar.com/floordiv     2.243s
  21. ❯ go test -bench=.
  22. goos: darwin
  23. goarch: amd64
  24. pkg: foobar.com/floordiv
  25. cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
  26. Benchmark_floorDiv_Int-8        1000000000               0.2756 ns/op
  27. Benchmark_floorDiv_Math-8       200432154                5.976 ns/op
  28. PASS
  29. ok      foobar.com/floordiv     2.271s
  31. ❯ go test -bench=.
  32. goos: darwin
  33. goarch: amd64
  34. pkg: foobar.com/floordiv
  35. cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
  36. Benchmark_floorDiv_Int-8        1000000000               0.2814 ns/op
  37. Benchmark_floorDiv_Math-8       195009298                6.083 ns/op
  38. PASS
  39. ok      foobar.com/floordiv     2.314s
  41. ❯ go test -bench=.
  42. goos: darwin
  43. goarch: amd64
  44. pkg: foobar.com/floordiv
  45. cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
  46. Benchmark_floorDiv_Int-8        1000000000               0.2751 ns/op
  47. Benchmark_floorDiv_Math-8       201196482                6.033 ns/op
  48. PASS
  49. ok      foobar.com/floordiv     2.290s

running this benchmark:

  1. package main
  2. import (
  3. &quot;math&quot;
  4. &quot;testing&quot;
  5. )
  6. func floorDiv_Int(x int, y int) int {
  7. q := x / y
  8. r := x % y
  9. if r != 0 &amp;&amp; x&amp;math.MinInt != y&amp;math.MinInt {
  10. q -= 1
  11. }
  12. return q
  13. }
  14. func floorDiv_Math(x int, y int) int {
  15. return int(math.Floor(
  16. float64(x) / float64(y),
  17. ))
  18. }
  19. func Benchmark_floorDiv_Int(b *testing.B) {
  20. for i := 0; i &lt; b.N; i++ {
  21. floorDiv_Int(-10, 3)
  22. floorDiv_Int(-9, 3)
  23. floorDiv_Int(-8, 3)
  24. floorDiv_Int(-7, 3)
  25. floorDiv_Int(-6, 3)
  26. floorDiv_Int(-5, 3)
  27. floorDiv_Int(-4, 3)
  28. floorDiv_Int(-3, 3)
  29. floorDiv_Int(-2, 3)
  30. floorDiv_Int(-1, 3)
  31. floorDiv_Int(0, 3)
  32. floorDiv_Int(1, 3)
  33. floorDiv_Int(2, 3)
  34. floorDiv_Int(3, 3)
  35. floorDiv_Int(4, 3)
  36. floorDiv_Int(5, 3)
  37. floorDiv_Int(6, 3)
  38. floorDiv_Int(7, 3)
  39. floorDiv_Int(8, 3)
  40. floorDiv_Int(9, 3)
  41. floorDiv_Int(10, 3)
  42. }
  43. }
  44. func Benchmark_floorDiv_Math(b *testing.B) {
  45. for i := 0; i &lt; b.N; i++ {
  46. floorDiv_Math(-10, 3)
  47. floorDiv_Math(-9, 3)
  48. floorDiv_Math(-8, 3)
  49. floorDiv_Math(-7, 3)
  50. floorDiv_Math(-6, 3)
  51. floorDiv_Math(-5, 3)
  52. floorDiv_Math(-4, 3)
  53. floorDiv_Math(-3, 3)
  54. floorDiv_Math(-2, 3)
  55. floorDiv_Math(-1, 3)
  56. floorDiv_Math(0, 3)
  57. floorDiv_Math(1, 3)
  58. floorDiv_Math(2, 3)
  59. floorDiv_Math(3, 3)
  60. floorDiv_Math(4, 3)
  61. floorDiv_Math(5, 3)
  62. floorDiv_Math(6, 3)
  63. floorDiv_Math(7, 3)
  64. floorDiv_Math(8, 3)
  65. floorDiv_Math(9, 3)
  66. floorDiv_Math(10, 3)
  67. }
  68. }

答案3

得分: 2

在这里是你要翻译的内容：

如果在乘法运算（a*b）中，要选择更快的方法：

  1. func floorDivMustafa2(a, b int) int {
  3. 	if a%b != 0 && a*b < 0 {
  4. 		return a/b - 1
  5. 	}
  6. 	return a / b
  7. }

我尝试了异或方法，但速度较慢：

  1. //异或方法
  2. func floorDivMustafa(a, b int) int {
  4. 	if a%b != 0 && (a < 0 || b < 0) && !(a < 0 && b < 0) {
  5. 		return a/b - 1
  6. 	}
  7. 	return a / b
  8. }

这是我的单元测试方法：

  1. func Test_floorDivSchwern(t *testing.T) {
  3. 	var (
  4. 		got, want int
  5. 	)
  7. 	for a := -10; a < 10; a++ {
  8. 		for b := -10; b < 10; b++ {
  9. 			if b == 0 {
  10. 				continue
  11. 			}
  12. 			got = floorDivMustafa(a, b)
  13. 			want = floorDivSchwern(a, b)
  14. 			if got != want {
  15. 				t.Errorf("divRound(%v/%v) = %v, want %v", a, b, got, want)
  16. 			}
  17. 		}
  18. 	}
  19. }

基准测试方法：

  1. func BenchmarkFloorDivMustafa2(b *testing.B) {
  2. 	for i := 0; i < b.N; i++ {
  3. 		for a := -100; a < 100; a++ {
  4. 			for b := -100; b < 100; b++ {
  5. 				if b == 0 {
  6. 					continue
  7. 				}
  8. 				_ = floorDivMustafa2(a, b)
  10. 			}
  11. 		}
  12. 	}
  13. }

以及所有的输出：

  1. >>>go test -bench=^Benchmark  -benchtime=1000x
  2. BenchmarkSchwern-4                  1000            182345 ns/op
  3. BenchmarkFloorDivMustafa-4          1000            441682 ns/op
  4. BenchmarkFloorDivMustafa2-4         1000             31234 ns/op
  5. BenchmarkJochen-4                   1000             60315 ns/op
  6. BenchmarkIntfolurdiv-4              1000          26437611 ns/op
  7. BenchmarkFloorDivICza-4             1000          26406776 ns/op

编辑 在看到位操作在我的基准测试中较慢的结果后，我尝试了操作的基准方法，这是我的结果：

  1. BenchmarkTwentyNumberBitwise-4                    328639            113790 ns/op
  2. BenchmarkTwentyNumberMultiplication-4             295512            101345 ns/op
英文:

The benchmark in case multiply numbers (a*b) will be faster:-

  1. func floorDivMustafa2(a, b int) int {
  3. 	if a%b != 0 &amp;&amp; a*b &lt; 0 {
  4. 		return a/b - 1
  5. 	}
  6. 	return a / b
  7. }

I tried the Xor method but it is slower:

  1. //xor method
  2. func floorDivMustafa(a, b int) int {
  4. 	if a%b != 0 &amp;&amp; (a &lt; 0 || b &lt; 0) &amp;&amp; !(a &lt; 0 &amp;&amp; b &lt; 0) {
  5. 		return a/b - 1
  6. 	}
  7. 	return a / b
  8. }

this is my unit test method

  1. func Test_floorDivSchwern(t *testing.T) {
  3. 	var (
  4. 		got, want int
  5. 	)
  7. 	for a := -10; a &lt; 10; a++ {
  8. 		for b := -10; b &lt; 10; b++ {
  9. 			if b == 0 {
  10. 				continue
  11. 			}
  12. 			got = floorDivMustafa(a, b)
  13. 			want = floorDivSchwern(a, b)
  14. 			if got != want {
  15. 				t.Errorf(&quot;divRound(%v/%v) = %v, want %v&quot;, a, b, got, want)
  16. 			}
  17. 		}
  18. 	}
  19. }

the bench-mark method:

  1. func BenchmarkFloorDivMustafa2(b *testing.B) {
  2. 	for i := 0; i &lt; b.N; i++ {
  3. 		for a := -100; a &lt; 100; a++ {
  4. 			for b := -100; b &lt; 100; b++ {
  5. 				if b == 0 {
  6. 					continue
  7. 				}
  8. 				_ = floorDivMustafa2(a, b)
  10. 			}
  11. 		}
  12. 	}
  13. }

and the output for all:

  1. &gt;&gt;&gt;go test -bench=^Benchmark  -benchtime=1000x
  2. BenchmarkSchwern-4                  1000            182345 ns/op
  3. BenchmarkFloorDivMustafa-4          1000            441682 ns/op
  4. BenchmarkFloorDivMustafa2-4         1000             31234 ns/op
  5. BenchmarkJochen-4                   1000             60315 ns/op
  6. BenchmarkIntfolurdiv-4              1000          26437611 ns/op
  7. BenchmarkFloorDivICza-4             1000          26406776 ns/op

Edit after I saw the result of Bit twiddling slower in my benchmark I try the bench method of the op and this is my result:

  1. BenchmarkTwentyNumberBitwise-4                    328639            113790 ns/op
  2. BenchmarkTwentyNumberMultiplication-4             295512            101345 ns/op

huangapple
  • 本文由 发表于 2022年3月8日 02:40:12
  • 转载请务必保留本文链接：https://go.coder-hub.com/71385791.html
  • go
  • integer-division
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定