proposal: intmath: new package

[perillo]

In same cases, like pagination, it is necessary to do:

pages = int(math.Ceiling(float64(items) / float64(itemsPerPage);

According to http://www.cs.nott.ac.uk/~rcb/G51MPC/slides/NumberLogic.pdf, the code can be optimized to avoid using floating point support:

pages = (items + itemsPerPage - 1) / itemsPerPage

According to https://stackoverflow.com/questions/17944/how-to-round-up-the-result-of-integer-division, a simplified version exists that avoid a possible overflow:

pages = (items - 1)  / itemsPerPage + 1

I have not verified these algorithms. However it should be evident that it is not a trivial problem.

In addition to CeilDiv there are also the CeilMod, FloorDiv, FloorMod and Abs functions.

Finally I also propose to add functions so that integer overflow is reported with an error, like AbsExact, AddExact, DivideExact, MultiplyExact, NegateExact, SubtractExact, CeilDivExact, FloorDivExact.

These functions accept a signed integer (int) as arguments.

References

• https://download.java.net/java/early_access/jdk18/docs/api/java.base/java/lang/Math.html

[perillo]

For the Exact family of functions, it may be more useful to return the (possibly overflowed) result of a + b and a bool that is true if the result overflowed.

[Jorropo]

Other algorithms that would be nice to have in such package, overflow safe average:

return (a >> 2) + (b >> 2) + (a & b & 1)

And / or a version that supports variadic input.

[rsc]

It doesn't seem like this would need to be in the standard library.
Are there third-party packages that are widely used for this?
(That would be an indication that it's a common need.)

[rsc]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

[perillo]

@rsc A quick search for CeilDiv returned the following links:

• https://stackoverflow.com/questions/19890935/golang-ceil-function-like-php
• https://pkg.go.dev/github.com/containrrr/shoutrrr/pkg/util (imported by 0 packages)
• https://github.com/jvlmdr/go-cv/blob/8ab6d79/slide/size.go#L23

As for arithmetic operations that will return an error on overflow instead of doing two's complement wrapping, it is possible that there are existing programs that are currently incorrect and should use the proposed API.

[earthboundkid]

I would rather have integer arithmetic operators, like Zig's +| for saturating addition, than a special math package. Zig integers panic rather than wrapping by default, so they have +% to mean wrap on overflow. For Go, where integers wrap by default, it might be nice to have +! for panic on overflow. It could be a good intermediate step to take towards some sort of Go 2 with bigints as the default integer type.

[perillo]

@carlmjohnson I don't think it is necessary to add additional operators.

With the API

func AddIntN(a intn, b intn) (r intn, ok bool);
func AddUintN(a uintn, b uintn) (r uintm, ok bool);

the programmer can do

package main

import (
	"math"

	"golang.org/x/exp/imath" // or golang.org/x/exp/math/exact
)

func main() {
	var a int32 = math.MaxInt32
	var b int32 = 1

	// saturating arithmetic
	if r, ok := imath.AddInt32(a, b); !ok {
		r = math.MaxInt32
	}

	// panic
	if r, ok := imath.AddInt32(a, b); !ok {
		panic("a + b overflowed")
	}
}

[rsc]

This still seems like something that should be done as a third-party package before we consider adding it to the standard library.

[rsc]

Based on the discussion above, this proposal seems like a likely decline.
— rsc for the proposal review group

[ainar-g]

(This message is more about a generic intmath package as opposed to one for int only, so perhaps I should post consequent messages about that in #41157. Please let me know.)

@rsc

Are there third-party packages that are widely used for this?
(That would be an indication that it's a common need.)

I would say that packages aren't a good indication of a common need here, since a lot of these operations have a common “oneliner” equivalents. Which are, of course, easy to get wrong. A common need for at least Max, Min, CeilDiv, and RoundDiv (integer division rounding towards the nearest integer) can be found in code itself.

Just for the hell of it, I looked up examples of CeilDiv oneliners from the Go 1.18 source code, using a very rough regexp grep -e '+\(.*\)-.*1.*/.*\1' -n -r. Here are just a few:

• src/strings/strings_test.go:1688

  benchStr := Repeat(benchmarkString,
      (indexSizes[len(indexSizes)-1]+len(benchmarkString)-1)/len(benchmarkString))

  Which could be:

  benchStr := Repeat(benchmarkString, intmath.CeilDiv(indexSizes[len(indexSizes)-1], len(benchmarkString))

• src/text/tabwriter/tabwriter.go:283

  cellw = (cellw + b.tabwidth - 1) / b.tabwidth * b.tabwidth

  Which could be:

  cellw = intmath.CeilDiv(cellw, b.tabwitdh) * b.tabwitdh

• src/cmd/compile/internal/ssa/poset.go:21

  return make(bitset, (n+uintSize-1)/uintSize)

  Which could be:

  return make(bitset, intmath.CeilDiv(n, uintSize))

I could look up some other oneliners a bit later, if such arguments for this proposal or proposal #41157 are at all convincing.

[rsc]

No change in consensus, so declined.
— rsc for the proposal review group