Friday, August 31, 2018

Adding isMultiple(of:) to Swift’s BinaryInteger

John McCall:

It is substantially more fluent than its standard implementation of value % divisor == 0. Divisibility testing is the operation people actually want; the % operator is just the way they have to achieve it. % is rarely used outside of this idiom, and many programmers have no other reason to know it. It is not a familiar operator for new programmers especially: they will usually be comfortable with remainders in the context of division, but they aren’t used to thinking about computing a remainder as a separate operation, and they certainly don’t recognize % as a symbol for it. Even experienced programmers often mentally “pattern-match” this sort of expression to recognize it as a divisibility test instead of thinking through the arithmetic of it.

Encouraging the use of isMultiple(of:) (and !isMultiple(of:)) serves to counter bugs around negative remainders.

It has some potential for better performance, especially when applied to large integers. In this case, this impact would probably not be a sufficient justification on its own.

Joe Groff (tweet):

A related common operation, the one I want to focus on here, is to test whether a number is an exact multiple of another, using the remainder operator[…]clang and gcc leverage the same division-into-multiplication trick to optimize this operation, first performing the division via multiplication, then multiplying by the divisor and comparing the result to see if the result matches[…]


Can we do better? It turns out we can, using some tricks with modular arithmetic. Integer arithmetic in a 32- or 64-bit CPU register wraps if it overflows, effectively implementing the integers modulo 2³² or 2⁶⁴. An interesting property of integers modulo 2ⁿ is that every odd number has a modular inverse, which is another number it can be multiplied with modulo 2ⁿ to produce 1.

Previously: Dividing by Multiplying.

Comments RSS · Twitter

Leave a Comment