Rounding numbers (up/down) to nearest multiple and power


(Jens Persson) #1

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.


(Steve Canon) #2

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.


(Dennis Vennink) #3

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.)


#4

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.


(Jens Persson) #5

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.


(Jens Persson) #6

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.


#7

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.


(Jens Persson) #8

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
        }
    }
}

(Steve Canon) #9

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.


(Jens Persson) #10

I hadn't thought about that, and I can't think of a strong reason to prefer one way over the other.


(Jens Persson) #11

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.)


#12

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.