proposal: math/big: add functions for floor and ceil of a rational number #76821
Description
Proposal Details
Some computations require floor and ceiling of a rational number.
I propose adding Floor and Ceil methods to big.Rat, which return
the floor and ceiling as a *big.Int respectively:
// Floor returns ⌊x⌋ (the floor of x) as a new [Int].
func (x *Rat) Floor() *Int
// Ceil returns ⌈x⌉ (the ceiling of x) as a new [Int].
func (x *Rat) Ceil() *IntPull request #76820
An example use case is computing the Engel expansion:
// ToEngel computes the Engel expansion of u > 0.
func ToEngel(u *big.Rat) (seq []*big.Int) {
one := big.NewRat(1, 1)
tmp := new(big.Rat)
for {
a := tmp.Inv(u).Ceil()
seq = append(seq, a)
u.Mul(u, tmp.SetInt(a))
u.Sub(u, one)
if u.Num().Sign() == 0 {
break
}
}
return seq
}Added later:
Since big.Int already has methods for Euclidean and truncated division,
I also propose adding methods for floor and ceiling division.
Dedicated division methods are more versatile:
They can return the modulus and accept negative divisors - not possible with Rat (Denom is always positive).
The Rat.Floor and Rat.Ceil can be convenience methods wrapping them.
// FloorDiv sets z to ⌊x/y⌋ for y != 0 and returns z.
// If y == 0, a division-by-zero run-time panic occurs.
// FloorDiv implements floor division (unlike Go); see [Int.FloorDivMod] for more details.
func (z *Int) FloorDiv(x, y *Int) *Int
// FloorDivMod sets z to ⌊x/y⌋ and m to x mod y
// for y != 0 and returns the pair (z, m).
// If y == 0, a division-by-zero run-time panic occurs.
//
// FloorDivMod implements floor division and modulus (unlike Go):
//
// q = ⌊x/y⌋ and
// m = x - y*q where 0 <= |m| < |y|, sgn(m) ∈ {0, sgn(y)}
//
// See [Int.QuoRem] for T-division and modulus (like Go).
func (z *Int) FloorDivMod(x, y, m *Int) (*Int, *Int)
// CeilDiv sets z to ⌈x/y⌉ for y != 0 and returns z.
// If y == 0, a division-by-zero run-time panic occurs.
// CeilDiv implements ceiling division (unlike Go); see [Int.CeilDivMod] for more details.
func (z *Int) CeilDiv(x, y *Int) *Int
// CeilDivMod sets z to ⌈x/y⌉ and m to x mod y
// for y != 0 and returns the pair (z, m).
// If y == 0, a division-by-zero run-time panic occurs.
//
// CeilDivMod implements ceiling division and modulus (unlike Go):
//
// q = ⌈x/y⌉ and
// m = x - y*q where 0 <= |m| < |y|, sgn(m) ∈ {0, -sgn(y)}
//
// See [Int.QuoRem] for T-division and modulus (like Go).
func (z *Int) CeilDivMod(x, y, m *Int) (*Int, *Int)