On several occasions, I've found myself in need of the following methods (on both floating point and integer types):
let a = b.rounded(.up, toMultipleOf: 8)
let c = d.rounded(.down, toPowerOf: 2)
As I've never been satisfied with any of my implementations of these, I figured I might ask here how you would name and implement them.
In computing, you basically only ever need to do this with powers of two, for which there's an easy method for multiples, taking advantage of their two's-complement representation.
extension FixedWidthInteger {
func roundUp(toMultipleOf powerOfTwo: Self) -> Self {
// Check that powerOfTwo really is.
precondition(powerOfTwo > 0 && powerOfTwo & (powerOfTwo &- 1) == 0)
// Round up and return. This may overflow and trap, but only if the rounded
// result would have overflowed anyway.
return (self + (powerOfTwo &- 1)) & (0 &- powerOfTwo)
}
}
Rounding down left as an exercise to the reader.
There's very little clever you can do with rounding to a power of two. It's just find the index of the leading bit, then construct the desired power of two with a shift, check of equality, shift one more bit if needed.
I've been doing some experiments with combined operators lately. It turns out it works for rounded(_:toMultipleOf:).
Here be dragons:
infix operator ⌈/⌉*
extension Float {
static func ⌈/⌉* (_ value: Float, _ multiples: Int) -> Int {
precondition(multiples > 0, "multiples has to be positive")
return Int((value / Float(multiples)).rounded(.up)) * multiples
}
}
print(17 ⌈/⌉* 8)
// Prints "24"
(x ⌈/⌉* y translates into ⌈x / y⌉ * y.)
Steve already covered the power-of-2 case, so here are some general-purpose rounded-to-multiple functions:
extension BinaryInteger {
func roundedTowardZero(toMultipleOf m: Self) -> Self {
return self - (self % m)
}
func roundedAwayFromZero(toMultipleOf m: Self) -> Self {
let x = self.roundedTowardZero(toMultipleOf: m)
if x == self { return x }
return (m.signum() == self.signum()) ? (x + m) : (x - m)
}
func roundedDown(toMultipleOf m: Self) -> Self {
return (self < 0) ? self.roundedAwayFromZero(toMultipleOf: m)
: self.roundedTowardZero(toMultipleOf: m)
}
func roundedUp(toMultipleOf m: Self) -> Self {
return (self > 0) ? self.roundedAwayFromZero(toMultipleOf: m)
: self.roundedTowardZero(toMultipleOf: m)
}
}
If you want roundedToNearest as well (perhaps with options for tiebreakers such as “toward zero”, “away from zero”, “up”, “down”, and “to even multiple”) that gets a little trickier but is still doable.
Note that the existing implementation of “%” makes it easy to write roundedTowardZero. If we had euclideanRemainder (whose result is non-negative) then roundedDown would be just as simple. However, if we had a mod function that takes its sign from the divisor, that would not help with any of these.
• • •
The behavior of FloatingPoint.remainder is somewhat different, and I haven’t tried writing the corresponding functions but they should be possible as well.
• • •
If you actually need to round to powers of numbers other than 2, you may want to use exponentiation-by-squaring.
Thank you all. I'll try and see if I'll actually need anything more than this:
extension FixedWidthInteger {
func roundedUp(toMultipleOf powerOfTwo: Self) -> Self {
precondition(powerOfTwo > 0 && powerOfTwo & (powerOfTwo &- 1) == 0)
return (self + (powerOfTwo &- 1)) & (0 &- powerOfTwo)
}
func roundedDown(toMultipleOf powerOfTwo: Self) -> Self {
precondition(powerOfTwo > 0 && powerOfTwo & (powerOfTwo &- 1) == 0)
return self & (0 &- powerOfTwo)
}
func roundedUpToPowerOfTwo() -> Self {
precondition(self > 0)
let shifts = bitWidth &- leadingZeroBitCount
return nonzeroBitCount == 1 ? self : 1 &<< shifts
}
}
(That is, rounding up and down only to multiples which are powers of two, and only rounding up to powers of two.)
I do think it would be nice to have them on floating point types as well (eg snap to grid in a graphics application). But I guess the naming and semantics would be less obvious for floating point types.
The example of snapping to a 2D grid is a good one because it nicely demonstrates a lot of various related needs. For example rounding both up and down (enlarge a rect so that it snaps to the closest grid points, grid cell size being eg 0.25 units) as well as rounding to nearest (snap a point to the nearest grid point).
Here's a quick attempt at using remainder(dividingBy:) and truncatingRemainder(dividingBy:) to implement the various "rounding to multiple of", not sure if it works as expected:
extension BinaryFloatingPoint {
func roundedToNearest(multipleOf m: Self) -> Self {
return self - self.remainder(dividingBy: m)
}
func roundedTowardZero(toMultipleOf m: Self) -> Self {
return self - self.truncatingRemainder(dividingBy: m)
}
func roundedAwayFromZero(toMultipleOf m: Self) -> Self {
let s = self >= 0 ? (self + m).nextDown : (self - m).nextUp
return s - s.truncatingRemainder(dividingBy: m)
}
func roundedDown(toMultipleOf m: Self) -> Self {
return (self < 0) ? self.roundedAwayFromZero(toMultipleOf: m)
: self.roundedTowardZero(toMultipleOf: m)
}
func roundedUp(toMultipleOf m: Self) -> Self {
return (self > 0) ? self.roundedAwayFromZero(toMultipleOf: m)
: self.roundedTowardZero(toMultipleOf: m)
}
}
EDIT: No, these doesn't work correctly, for example:
print(Float(2).nextUp.roundedUp(toMultipleOf: 2.0)) // Prints 2.0, should be 4.0
And, although probably much less needed, I guess one interpretation of binary floating point number "rounded toward zero to power of two" is available for free via .binade.
Another attempt, still not entirely sure if everything works correctly:
extension FixedWidthInteger {
func roundedTowardZero(toMultipleOf m: Self) -> Self {
return self - (self % m)
}
func roundedAwayFromZero(toMultipleOf m: Self) -> Self {
let x = self.roundedTowardZero(toMultipleOf: m)
if x == self { return x }
return (m.signum() == self.signum()) ? (x + m) : (x - m)
}
func roundedDown(toMultipleOf m: Self) -> Self {
return self < 0
? self.roundedAwayFromZero(toMultipleOf: m)
: self.roundedTowardZero(toMultipleOf: m)
}
func roundedUp(toMultipleOf m: Self) -> Self {
return self >= 0
? self.roundedAwayFromZero(toMultipleOf: m)
: self.roundedTowardZero(toMultipleOf: m)
}
func roundedUpToPowerOfTwo() -> Self {
precondition(self > 0)
let shifts = bitWidth &- leadingZeroBitCount
return nonzeroBitCount == 1 ? self : 1 &<< shifts
}
}
extension BinaryFloatingPoint {
func roundedToNearest(multipleOf m: Self) -> Self {
return self - self.remainder(dividingBy: m)
}
func roundedTowardZero(toMultipleOf m: Self) -> Self {
return self - self.truncatingRemainder(dividingBy: m)
}
func roundedAwayFromZero(toMultipleOf m: Self) -> Self {
let x = self.roundedTowardZero(toMultipleOf: m)
if self == x {
return self
} else {
return self >= 0 ? x + m : x - m
}
}
func roundedDown(toMultipleOf m: Self) -> Self {
return self < 0
? self.roundedAwayFromZero(toMultipleOf: m)
: self.roundedTowardZero(toMultipleOf: m)
}
func roundedUp(toMultipleOf m: Self) -> Self {
return self >= 0
? self.roundedAwayFromZero(toMultipleOf: m)
: self.roundedTowardZero(toMultipleOf: m)
}
}
Note for example that:
print(Float(1.5).roundedToNearest(multipleOf: 1.0)) // 2.0
print(Float(2.5).roundedToNearest(multipleOf: 1.0)) // 2.0 (we might have expected 3.0)
This is because roundedToNearest(multipleOf:) uses remainder(dividingBy:) which has the following property:
For two finite values x and y, the remainder r of dividing x by y satisfies x == y * q + r, where q is the integer nearest to x / y. If x / y is exactly halfway between two integers, q is chosen to be even.
So:
print(Float(1.5).remainder(dividingBy: 1.0)) // -0.5
print(Float(2.5).remainder(dividingBy: 1.0)) // 0.5
An alternative implementation of roundedToNearest(multipleOf:) could perhaps be:
func roundedToNearest(multipleOf m: Self) -> Self {
let x = self >= 0 ? self + m/2 : self - m/2
return x - x.truncatingRemainder(dividingBy: m)
}
And since these two implementations corresponds to the two rounding rules .toNearestOrEven and .toNearestOrAwayFromZero we can implement all variants as this single method:
extension BinaryFloatingPoint {
func rounded(_ roundingRule: FloatingPointRoundingRule,
toMultipleOf m: Self) -> Self
{
switch roundingRule {
case .toNearestOrEven:
return self - self.remainder(dividingBy: m)
case .toNearestOrAwayFromZero:
let x = self >= 0 ? self + m/2 : self - m/2
return x - x.truncatingRemainder(dividingBy: m)
case .awayFromZero:
let x = self.rounded(.towardZero, toMultipleOf: m)
if self == x {
return self
} else {
return self >= 0 ? x + m : x - m
}
case .towardZero:
return self - self.truncatingRemainder(dividingBy: m)
case .down:
return self < 0
? self.rounded(.awayFromZero, toMultipleOf: m)
: self.rounded(.towardZero, toMultipleOf: m)
case .up:
return self >= 0
? self.rounded(.awayFromZero, toMultipleOf: m)
: self.rounded(.towardZero, toMultipleOf: m)
}
}
}
Though perhaps the "even" in .toNearestOrEven doesn't quite make sense in the context of this method.
These both go awry when m is negative (and thus so do the .up and .down cases that call them). The easy fix is to use abs(m) in the add-or-subtract lines.
• • •
Also just for fun, here’s my first crack at rounded-to-nearest, ties-to-even, for integers:
extension BinaryInteger {
func roundedToNearest(multipleOf m: Self) -> Self {
let (q, r) = self.quotientAndRemainder(dividingBy: m)
if r == 0 { return self }
let x = self - r // `self` rounded toward zero
let y = (m.signum() == self.signum()) ? (x + m) : (x - m) // and away
let (low, high) = (self < 0) ? (y, x) : (x, y)
let a = self - low
let b = high - self
return (a < b) ? low
: (b < a) ? high
: q.isEven ? x : y
}
var isEven : Bool {
return self._lowWord & 1 == 0
}
}
Making it “ties away from zero” is as simple as deleting “q.isEven ? x :” so it returns y in case of a tie.
Note that this is not a perfect implementation, because for very large values where the “away from zero” multiple overflows, it will overflow even if the proper rounding does not.
Ah, thanks! I didn't think about negative m (never had a use case for that).
And thanks for sharing the integer roundedToNearest(multipleOf:) code, it would be nice if this thread lead to good implementations of all these functions.
Here is an attempt at rounded to power of two for floating point:
extension BinaryFloatingPoint {
func roundedDownToPowerOfTwo() -> Self {
precondition(self > 0)
return self.binade
}
func roundedUpToPowerOfTwo() -> Self {
precondition(self > 0)
if self == self.binade {
return self
} else {
return self.binade * 2
}
}
}
How do you want to handle values in the top binade? Your implementation will return .infinity, which is reasonable, but you might also error out.
I hadn't thought about that, and I can't think of a strong reason to prefer one way over the other.
Perhaps the following might be simpler versions for those two round to nearest multiple functions:
func roundedToNearestTieingAwayFromZero(multipleOf m: Self) -> Self {
let x = self + (m/2) * m.signum() * self.signum()
return x - (x % m)
}
func roundedToNearestTieingToEven(multipleOf m: Self) -> Self {
let a = (self / m) & 1
let b = (m - a * m.signum()) / 2
let c = self + b * m.signum() * self.signum()
return c - (c % m)
}
?
(Also overflows in some cases where the correct result doesn't.)
Yes that is simpler, assuming the compiler is smart enough to optimize multiplication by signums.
This one has two divisions (“self / m” and “c % m”) so it is probably less efficient.