Fraction based quantization of a value

Question

I'm developing a basic Python 2.7 musical sequencer.

A small background for people not used to musical terms.
A sequencer is a program that can "ask" some other program or device to "play" events at specific times, somehow similar to the "piano rolls" of an old Player piano. One thing that a software sequencer always makes available to the user is the "quantization", which is the ability to "move" events (usually notes that have been input via GUI or through an external instrument) to specific timings, and then obtain a more precise sound reproduction based on the current tempo.
Musical timings are based on simple 2 or 3 multiples fractions, so you can have a note that starts or has a length of a quater, 3 eights, a third and so on.

What I need is a fast function that is able to quantize "inaccurate" values.
For example, if the quantization is set to quarters and a note has a timing of 2.6, its value will become 2.5. If the quantization is based on eights, the value will be 2.625.

So far, the fastest function I was able to find was this one:

def quantize(value, numerator, denominator):
    #use the least common multiple, so I can get a
    #reference integer to round to.
    temp = round(value * numerator * denominator, 0)
    #return the re-normalized value
    return temp * numerator / float(denominator)

I've been looking into the Python decimal module and its quantize() method, but I wasn't able to understand if it can actually do what I need.

Is there a faster and, maybe, builtin function/method in the standard library that I could use instead?

Please note that I'm not interested in the round method differences whenever the last reference float is 5, as it doesn't need to be "programmatically" precise by concept.

Also, to all the musicians reading this: the actual reference will be "beats" (as in quarter notes for common time based music), so I will obviously multiply the temp value by 4 before rounding and then divide the value again before returning, but that's not the point here :-)

Answer 1

Fast solutions

All of these solutions are significantly faster than the OP's quantize function (see this old thread for a discussion of the reasons why). Take your pick depending on your desired rounding behavior.

Round to nearest

This exactly reproduces the behavior of the OP's quantize function:

from __future__ import division

def quantizeRound(value, numerator, denominator):
    ratio = (numerator/denominator)
    return (value + ratio/2) // ratio * ratio

Round up

from __future__ import division

def quantizeCeil(value, numerator, denominator):
    ratio = (numerator/denominator)
    return (value // ratio + 1) * ratio

Round down

from __future__ import division

def quantizeFloor(value, numerator, denominator):
    ratio = (numerator/denominator)
    return value // ratio * ratio

Testing

I compared the output of the OP's quantize and my quantizeRound (in both Python 2.7 and 3.6) over a wide range of possible inputs, and ensured that they matched:

for denom in (2,4,8):
    for v in np.linspace(0,5,51):
        assert quantize(v, 1, denom) == quantizeRound(v, 1, denom)

Timings

%%timeit
quantize(2.6, 1, 8)
833 ns ± 11.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%%timeit
quantizeRound(2.6, 1, 8)
296 ns ± 2.93 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%%timeit
quantizeCeil(2.6, 1, 8)
277 ns ± 3.49 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%%timeit
quantizeFloor(2.6, 1, 8)
241 ns ± 3.61 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Python 2/3 compatibility

The line from __future__ import division ensures that, whether you run the code in Python 2 or 3, in either case / will perform float division. You may not want to use from __future__ import division in your code (since it will change the behavior of all code in the module in which it's imported). In that case, you can either place the quantization function in its own separate module, or you can use this alternative Python 2/3 compatible version of quantizeRound:

# alternative Python 2/3 compatible version 
def quantizeRound(value, numerator, denominator):
    ratio = (float(numerator)/denominator)
    return (value + ratio/2.0) // ratio * ratio

However, it is a bit slower than the version that uses from __future__ ...:

%%timeit
# alternative Python 2/3 compatible version
quantizeRound(2.6, 1, 8)
441 ns ± 9.91 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Speeding up batch quantization of many notes at a time

If you have large batches of notes to quantize, you can speed up the process by using Numpy arrays. The form of quantizeRound (and my other quantization functions) is compatible with using arrays as inputs. Given an array of notes, quantizeRound will quantize them all using a single vectorized calculation. For example:

notes = np.arange(10) + .6
print(quantizeRound(notes, 1, 8))

Output:

[0.625 1.625 2.625 3.625 4.625 5.625 6.625 7.625 8.625 9.625]

Timings

The vectorized array-based approach is almost twice as fast as the equivalent for loop:

%%timeit
for n in notes:
    quantizeRound(n, 1, 8)
5.63 µs ± 40.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%%timeit
quantizeRound(notes, 1, 8)
2.93 µs ± 20.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Answer 2

Maybe I'm missing something, but isn't good old integer arithmetic all you need?

def quantize(value, numerator, denominator):
    #use the least common multiple, so I can get a
    #reference integer to round to.
    temp = round(value * numerator * denominator, 0)
    #return the re-normalized value
    return temp * numerator / float(denominator)

from decimal import Decimal, ROUND_FLOOR
def quantize2(number, numerator, denominator):
    number, ratio = Decimal(number), Decimal(numerator/denominator)
    return (number / ratio).quantize(Decimal(1), rounding=ROUND_FLOOR) * ratio


def quantize3(number, numerator, denominator):
    ratio = numerator/denominator
    return (number // ratio) * ratio


def testfunc():
    return quantize(2.6,1,4)

def testfunc2():
    return quantize2(2.6,1,4)

def testfunc3():
    return quantize3(2.6,1,4)

$ python -mtimeit -s'import quantize' 'quantize.testfunc()'
1000000 loops, best of 3: 1.11 usec per loop

$ python -mtimeit -s'import quantize' 'quantize.testfunc2()'
100000 loops, best of 3: 3.3 usec per loop

$ python -mtimeit -s'import quantize' 'quantize.testfunc3()'
1000000 loops, best of 3: 0.421 usec per loop

>>> print quantize3(2.6,1,4)

2.5