Bresenham Distribution: O(1) even placement of remainder items

A technical note

Abstract

Bresenham Distribution (BD) assigns N items to B ordered buckets, giving each bucket either ⌊N/B⌋ or ⌈N/B⌉ items. An integer floor-difference predicate places the remainder items evenly: every circular interval of m buckets contains either ⌊mR/B⌋ or ⌈mR/B⌉ extra items, where R = N mod B. Individual bucket counts can be queried in O(1) time without mutable state. BD-0 denotes the unshifted baseline; an explicit phase parameter rotates its pattern. BD-C centers the minority: heavy buckets for sparse remainders, light buckets for dense remainders. This note separates the allocation guarantees from the application's phase policy, gives short proofs, and provides a reference C implementation.

For example, BD-0 and BD-C place the remainder items across nine buckets as follows. Each ● marks a bucket receiving base + 1 items; each . marks a bucket receiving base items.

     BD-0                 BD-C
     0 1 2 3 4 5 6 7 8    0 1 2 3 4 5 6 7 8   bucket
R=1  . . . . . . . . ●    . . . . ● . . . .
R=2  . . . . ● . . . ●    . . ● . . . ● . .
R=3  . . ● . . ● . . ●    . ● . . ● . . ● .
R=4  . . ● . ● . ● . ●    . ● . ● . ● . ● .
R=5  . ● . ● . ● . ● ●    ● . ● . ● . ● . ●
R=6  . ● ● . ● ● . ● ●    ● . ● ● . ● ● . ●
R=7  . ● ● ● . ● ● ● ●    ● ● . ● ● ● . ● ●
R=8  . ● ● ● ● ● ● ● ●    ● ● ● ● . ● ● ● ●

1. Problem and terminology

Let N ≥ 0 be an integer item count and B ≥ 1 the number of buckets, indexed 0..B−1. Define:

base = ⌊N / B⌋
R    = N mod B          (0 ≤ R < B)

Every bucket receives base items, and exactly R buckets receive one extra. Call these buckets heavy and the others light. When R = 0, all buckets receive the same count and none is heavy.

The aim is count balance and even placement in the bucket ordering. Spacing is measured on a circle, including the transition from bucket B−1 to bucket 0. Applications with a linear arrangement may additionally care about its two endpoints. Count balance is a work-balance guarantee only when items have equal cost and workers have equal capacity.

2. BD-0 and an explicit phase

2.1 The baseline

BD-0 uses the following heavy-bucket indicator:

h(k) = ⌊(k+1)R / B⌋ − ⌊kR / B⌋
count(k) = base + h(k)

Because 0 ≤ R/B < 1, h(k) is either zero or one. For R > 0, the heavy positions can equivalently be enumerated as:

k_j = ⌈(j+1)B / R⌉ − 1,    j = 0..R−1

This fixes the rounding and phase convention: the final baseline bucket is heavy whenever R > 0. The superficially similar positions ⌊jB/R⌋ use a different placement convention and must not be substituted into these examples.

2.2 Rotation

For an integer phase s with 0 ≤ s < B, define:

k = (b − s) mod B       (the residue in 0..B−1)
count_s(b) = base + h(k)

A positive phase moves heavy buckets towards increasing indices, wrapping at B. BD-0 is exactly s = 0. The allocation algorithm accepts the phase as input; deciding how it changes across batches is a separate application policy. All phases preserve the exact count and circular-balance guarantees.

3. Guarantees and proofs

3.1 Conservation and count balance

Summing the floor differences telescopes:

Σ h(k), k = 0..B−1 = ⌊BR/B⌋ − ⌊0⌋ = R

Thus exactly R buckets are heavy, the total is B·base + R = N, and any two bucket counts differ by at most one. Rotation permutes the buckets, preserving these statements.

3.2 Balance over intervals

Extend h periodically to integer indices. For any start a and length 0 ≤ m ≤ B, the number of heavy buckets in that interval is:

Σ h(a+i), i = 0..m−1 = ⌊(a+m)R/B⌋ − ⌊aR/B⌋

Writing aR/B = q + f, where q is integral and 0 ≤ f < 1, reduces this expression to ⌊mR/B + f⌋. It is therefore either ⌊mR/B⌋ or ⌈mR/B⌉. This also covers intervals crossing the boundary and rotated patterns, by changing the starting index.

Consequently, every interval's total allocation differs from the ideal mN/B by less than one item. Any two intervals of equal length differ in allocation by at most one item. This is the precise sense in which the pattern is evenly distributed.

3.3 Circular distances

For R > 0, consecutive heavy positions have circular distances ⌊B/R⌋ or ⌈B/R⌉. This follows by differencing the ceiling expression for k_j, extending it with k_R = k_0 + B to include the wraparound. These distances sum to B and differ by at most one. Their average is B/R, so no placement can have a smaller maximum circular distance than ⌈B/R⌉.

The number of light buckets between heavy buckets is the distance minus one. In particular, the longest circular run of light buckets has length ⌈B/R⌉ − 1. These statements include R = 1, where the single distance is B. They do not apply to R = 0, for which there are no heavy positions.

3.4 Cost and reproducibility

A query uses a bounded number of integer operations and O(1) space. Querying all buckets takes O(B) time. These bounds use fixed-width machine arithmetic; the checked-multiplication fallback in Section 6 is bounded by the type width. The result is deterministic in (N, B, b, s); the implementation has no allocation or mutable global state.

4. Choosing a placement policy

Requirement	Policy	Scope of the guarantee
A canonical, repeatable placement	Use BD-0: `s = 0`.	All per-run balance guarantees; no spreading across repeated identical batches.
Center the less numerous bucket type in a linear arrangement	Use BD-C (Section 4.3).	Balances margins around the minority positions; no general mirror-symmetry guarantee.
A different boundary placement	Choose an explicit offset.	Circular balance is unchanged; endpoint properties depend on the chosen offset.
Equal cumulative counts for fixed `N` and `B`	Visit all `B` phases equally often.	Each bucket receives exactly `R` extras per complete phase cycle.
Equal expected counts for a given remainder	Choose the phase uniformly conditional on that remainder.	Each bucket is heavy with probability `R/B`; finite runs need not tie.

4.1 Fixed batches: a complete rotation cycle

Fix N and B. As s visits 0..B−1, any particular bucket visits every baseline position once. It is therefore heavy exactly R times. Each bucket receives B·base + R = N items over those B batches. This is exact equality after a complete cycle, not a guarantee of equality after every partial cycle. The application maintains the cycle counter; individual allocation queries remain stateless.

4.2 Varying batches

If R changes between batches, cycling phases alone does not establish cumulative fairness: phase and remainder may be correlated. For example, with B = 8, N = 16..23, and s = (4 + N) mod 8, per-bucket heavy counts are:

bucket:       0 1 2 3 4 5 6 7
heavy count:  3 5 2 2 5 5 2 4

Every phase occurs once, yet the counts are unequal. The same heavy-count pattern repeats across subsequent complete cycles of N mod 8. A sufficient condition for equal expected extras, at fixed B, is that the phase be uniform conditional on each batch's remainder. This is a statement about a probability model, not a guarantee for an arbitrary deterministic input sequence.

A deployment offset, a batch counter, or a hash can supply a phase without becoming a separate allocation algorithm. A fixed offset repeats the same pattern for identical batches. Hashing may reduce correlations for some workloads, but neither hashing nor a deployment ID by itself establishes cumulative fairness or adversarial resistance.

4.3 BD-C: minority centering

BD-C centers the less numerous bucket type: heavy buckets when the remainder is sparse, and light buckets when it is dense. When their counts tie, it centers the heavy buckets. This gives a balanced linear placement without a special phase-inversion algorithm: construct a centered minority indicator, then complement it if necessary.

For R > 0, let M = min(R, B−R). Apply the BD predicate with M marked buckets, rotating its initial longest unmarked run across the boundary:

M = min(R, B−R)
L = ⌈B/M⌉ − 1
s = (B − ⌊L/2⌋) mod B
k = (b − s) mod B
marked(b) = ⌊(k+1)M/B⌋ − ⌊kM/B⌋

extra(b) = marked(b)       if R ≤ B/2
           1 − marked(b)   otherwise
BD-C count(b) = base + extra(b)

The marked positions have ⌈L/2⌉ unmarked buckets before them and ⌊L/2⌋ after them. The midpoint of their first and last positions is therefore within half a bucket of the range midpoint. For sparse remainders these margins are light buckets; for dense remainders they are heavy buckets around the light positions. For R = 0, return base directly; no centering is needed.

Centering splits a longest circular run of unmarked buckets as evenly as possible. It minimizes the longest linear unmarked run among rotations of that marked pattern, although other rotations may tie: a rotation can split only one circular run, and cutting a shorter run would leave a longest run intact. Thus sparse placements minimize the longest linear light run, while dense placements minimize the longest linear heavy run. This objective differs from simply minimizing the difference between end margins.

Complementation preserves exact counts and interval balance. An interval of length m has either ⌊mM/B⌋ or ⌈mM/B⌉ marked light buckets; subtracting this count from m gives either ⌊mR/B⌋ or ⌈mR/B⌉ heavy buckets. Circular heavy-to-heavy distances retain the Section 3 guarantee. For 0 < R < B with R ≠ B−R, the BD-C extra patterns for R and B−R are complements. At an exact tie, the heavy-first convention selects one pattern; a binary pattern cannot equal its own complement.

Balanced minority margins do not imply reflection symmetry of the full pattern. Section 7 gives both a symmetric example and a counterexample. In dense placements the endpoints become heavy, which may be undesirable for an application that prefers light boundaries. This is a linear-layout policy, not an improvement to the independent-worker makespan in Section 5 or a guarantee of cumulative fairness across batches.

4.4 Phase locality

A small phase change, measured around the circle, rotates an unchanged pattern when N and B are fixed. Changing N also changes the remainder pattern, potentially moving many heavy buckets even with a constant phase. Phase movement and allocation changes should therefore be evaluated separately.

5. Scheduling interpretation

Assume identical workers start together, each processes its assigned items sequentially, every item costs c, and there are no communication or dispatch costs. Then:

makespan = ⌈N/B⌉ · c

When R > 0, light workers finish c earlier than heavy workers; otherwise all finish together. The phase does not change these times. A spatial run of light buckets is not an interval of CPU idle time, and uniform item cost does not itself require a synchronous wave scheduler.

Position may matter for an ordered dispatcher, a physical layout, communication, or thermal behaviour, but any claimed improvement needs a model of that mechanism. With unequal item costs, count balance and circular spacing still hold; balanced processing time need not.

6. Reference implementation

The C23 interface uses uintmax_t for counts, indices, and phases, with checked arithmetic from <stdckdint.h>. It accepts 0 ≤ N < UINTMAX_MAX, 1 ≤ B ≤ UINTMAX_MAX, and 0 ≤ b, shift < B. The value UINTMAX_MAX is reserved as the error return and is rejected as an item count. A successful count is at most N, so it never conflicts with the sentinel.

The caller supplies an already-normalized phase to bd_count. bd_count_0 calls it with zero shift. bd_count_c computes the minority size and its centering shift, then calls bd_count to obtain the minority indicator. Dense placements complement this indicator before adding the base allocation. All public functions validate their inputs. The implementation needs no integer type wider than uintmax_t.

Download the API header and implementation.

#include <stdckdint.h>
#include "bresenham-distribution.h"

/* (a + b) mod m. Require a < m, b < m, and m > 0. */
static uintmax_t bd_addmod(uintmax_t a, uintmax_t b, uintmax_t m)
{
    uintmax_t sum;
    if (ckd_add(&sum, a, b) || sum >= m)
        sum -= m;  /* Unsigned wraparound is intentional when addition overflowed. */
    return sum;
}

/* (a * b) mod m, with the same preconditions as bd_addmod. */
static uintmax_t bd_mulmod(uintmax_t a, uintmax_t b, uintmax_t m)
{
    uintmax_t product;
    if (!ckd_mul(&product, a, b))
        return product % m;

    /* The wrapped product alone cannot recover the remainder: use doubling. */
    product = 0;
    while (b) {
        if (b & 1)
            product = bd_addmod(product, a, m);
        b >>= 1;
        if (b)
            a = bd_addmod(a, a, m);
    }
    return product;
}

uintmax_t bd_count(uintmax_t N, uintmax_t B, uintmax_t b, uintmax_t shift)
{
    if (N == UINTMAX_MAX || B == 0 || b >= B || shift >= B)
        return UINTMAX_MAX;

    uintmax_t base = N / B;
    uintmax_t R = N % B;
    if (R == 0)
        return base;

    /* (b - shift) mod B, without an overflowing intermediate sum. */
    uintmax_t k = b >= shift ? b - shift : B - (shift - b);

    /* The floor difference is one exactly when (k * R) mod B >= B - R. */
    return base + (bd_mulmod(k, R, B) >= B - R);
}

uintmax_t bd_count_0(uintmax_t N, uintmax_t B, uintmax_t b)
{
    return bd_count(N, B, b, 0);
}

uintmax_t bd_count_c(uintmax_t N, uintmax_t B, uintmax_t b)
{
    if (N == UINTMAX_MAX || B == 0 || b >= B)
        return UINTMAX_MAX;

    uintmax_t base = N / B;
    uintmax_t R = N % B;
    if (R == 0)
        return base;

    /* Center heavy buckets when sparse (or tied), light buckets when dense. */
    bool dense = R > B / 2;
    uintmax_t minority = dense ? B - R : R;

    /* Split a longest run between minority buckets across the endpoints. */
    uintmax_t left_rotation = ((B - 1) / minority) / 2;
    uintmax_t shift = left_rotation == 0 ? 0 : B - left_rotation;
    uintmax_t marked = bd_count(minority, B, b, shift);

    /* marked is 0 or 1; complement it when it marks a light bucket. */
    return base + (dense ? 1 - marked : marked);
}

The conditional subtraction computes the rotated index without an overflowing intermediate sum. To avoid forming two potentially overflowing products, write kR = qB + t, where 0 ≤ t < B. The floor difference is one exactly when t ≥ B − R, so only the modular product t = (kR) mod B is needed.

ckd_mul supplies a fast path when the product fits. If it overflows, repeated modular doubling and addition recover the remainder using only uintmax_t. The modular-addition helper requires both operands to be below the modulus, so their true sum is less than twice the modulus and at most one subtraction is necessary. ckd_add reports overflow and stores the wrapped sum; unsigned subtraction of the modulus then deliberately wraps to the correct remainder. The final count cannot overflow because it is at most the validated item count.

The multiplication fallback takes at most one iteration per value bit of uintmax_t (64 iterations when that type is 64 bits wide). It supports the full documented input range, but costs more than the fast path. In a variable-width arithmetic model its cost is O(w) word operations for a w-bit type; the fixed-width bound is O(1).

For many queries with the same inputs, the caller can cache base, R, and the phase (or BD-C's minority size and its internal shift). Sequential generation can instead use an error accumulator, avoiding division in the per-bucket loop. Constant-time random access is the reason for the closed form; it is not a claim that repeated queries are the fastest way to enumerate all buckets.

6.1 Runnable example

Save the header, implementation, and usage.c in the same directory, then compile and run:

cc -std=c23 -Wall -Wextra usage.c bresenham-distribution.c -o bd-example
./bd-example

#include <inttypes.h>
#include <stdio.h>
#include "bresenham-distribution.h"

static void show(uintmax_t N, uintmax_t B, int centered)
{
    printf("%s: N=%" PRIuMAX ", B=%" PRIuMAX ":",
           centered ? "BD-C" : "BD-0", N, B);
    for (uintmax_t b = 0; b < B; ++b)
        printf(" %" PRIuMAX, centered ? bd_count_c(N, B, b) : bd_count_0(N, B, b));
    putchar('\n');
}

int main(void)
{
    show(93, 10, 0);  /* BD-0: heavy buckets 3, 6, 9. */
    show(93, 10, 1);  /* BD-C: heavy buckets 2, 5, 8. */
    show(83, 9, 0);   /* BD-0: heavy buckets 4, 8. */
    show(83, 9, 1);   /* BD-C: heavy buckets 2, 6. */

    show(103, 11, 1); /* BD-C: balanced margins, but not mirror-symmetric. */

    show(89, 9, 1);   /* BD-C: the single light bucket is centered at 4. */

    /* Fixed N and B: visit every phase once. Each bucket gets R extras. */
    uintmax_t extras[9] = {0};
    for (uintmax_t shift = 0; shift < 9; ++shift)
        for (uintmax_t b = 0; b < 9; ++b)
            extras[b] += bd_count(83, 9, b, shift) - 83 / 9;

    printf("Extras over all 9 phases:");
    for (uintmax_t b = 0; b < 9; ++b)
        printf(" %" PRIuMAX, extras[b]);
    putchar('\n');
    return 0;
}

Output:

BD-0: N=93, B=10: 9 9 9 10 9 9 10 9 9 10
BD-C: N=93, B=10: 9 9 10 9 9 10 9 9 10 9
BD-0: N=83, B=9: 9 9 9 9 10 9 9 9 10
BD-C: N=83, B=9: 9 9 10 9 9 9 10 9 9
BD-C: N=103, B=11: 9 10 9 9 10 9 9 10 9 10 9
BD-C: N=89, B=9: 10 10 10 10 9 10 10 10 10
Extras over all 9 phases: 2 2 2 2 2 2 2 2 2

7. Worked placements

A dot marks a light bucket and a filled circle a heavy bucket. Indices start at zero.

7.1 Ten buckets, 93 items

Here base = 9, R = 3, and L = ⌈10/3⌉ − 1 = 3. The heavy buckets are the minority, so BD-C rotates their pattern left by one bucket, using internal shift s = 9.

BD-0 (s = 0): . . . ● . . ● . . ●    heavy buckets 3, 6, 9
BD-C (s = 9): . . ● . . ● . . ● .    heavy buckets 2, 5, 8

Both have circular heavy-to-heavy distances 3, 3, 4. The corresponding circular light runs have lengths 2, 2, 3. In the linear view, BD-C splits the three-light-bucket run across the two ends, leaving two leading and one trailing light bucket.

A half-range shift illustrates why equal margins alone are a weaker criterion:

BD-C (s = 9): . . ● . . ● . . ● .    margins 2,1; longest light run 2
B/2  (s = 5): . ● . . ● . . . ● .    margins 1,1; longest light run 3

The half-range shift has exactly equal end margins but leaves an internal run of three light buckets. For this sparse remainder, BD-C minimizes the longest linear light run, while keeping the boundary split balanced. This is a placement advantage whose practical value depends on the application; it changes neither circular balance nor the independent-worker makespan in Section 5.

7.2 Nine buckets, 83 items

Here base = 9, R = 2, and L = ⌈9/2⌉ − 1 = 4. The heavy buckets are the minority, so BD-C rotates their pattern left by two buckets, using internal shift s = 7.

BD-0 (s = 0): . . . . ● . . . ●    heavy buckets 4, 8
BD-C (s = 7): . . ● . . . ● . .    heavy buckets 2, 6

Both have circular distances 4, 5. BD-C happens to be mirror-symmetric about bucket 4, with two light buckets at each end. By contrast, shift = ⌊9/2⌋ = 4 gives heavy buckets 3 and 8 and is not mirror-symmetric.

7.3 Balanced margins without mirror symmetry

For N = 103 and B = 11, base = 9, R = 4, and L = ⌈11/4⌉ − 1 = 2. BD-C rotates left by one bucket:

BD-0 (s = 0):  . . ● . . ● . . ● . ●    heavy buckets 2, 5, 8, 10
BD-C (s = 10): . ● . . ● . . ● . ● .    heavy buckets 1, 4, 7, 9

BD-C leaves one light bucket at each endpoint. The first and last heavy buckets are centered about bucket 5, but the full pattern is not mirror-symmetric: bucket 4 is heavy while its reflection, bucket 6, is light. This distinguishes the guaranteed end-margin balance from symmetry of the interior.

7.4 Dense remainder: center the light bucket

For N = 89 and B = 9, base = 9 and R = 8. There is only one light bucket, so M = 1, L = 8, and the internal minority shift is s = 5. The marked position is bucket 4; complementing it produces:

BD-0: . ● ● ● ● ● ● ● ●    light bucket 0
BD-C: ● ● ● ● . ● ● ● ●    light bucket 4

BD-C splits the eight-heavy-bucket run into two linear runs of four. Their circular distance and balance properties are unchanged: the heavy run still joins across the circular boundary. The internal shift applies to the one-light-bucket indicator, not directly to BD-0's eight-heavy-bucket pattern.

8. Relationship to prior work

The floor-difference construction is an integer error-accumulation technique related to Bresenham's line algorithm. An accumulator initialized to zero, adding R per bucket and emitting an extra whenever it reaches B, generates this BD-0 convention. Other line-rasterization conventions use different initial errors or rounding rules; their exact pixel patterns need not match it.

Even cyclic binary patterns and rotations also appear in the literature on Euclidean rhythms. This note provides an allocation formulation, explicit guarantees, and a small query API; it does not claim that even spacing or phase selection is new.

J. E. Bresenham, Algorithm for computer control of a digital plotter, IBM Systems Journal 4(1), 25–30, 1965.
Godfried Toussaint, The Euclidean Algorithm Generates Traditional Musical Rhythms, 2005.

9. Scope

BD denotes the allocation algorithm with an explicit phase; BD-0 denotes its zero-phase baseline. BD-C centers the minority positions and complements the indicator for dense remainders. Conservation, count balance, and circular interval balance hold for all these placements. Endpoint preferences and cumulative allocation across batches depend on the application and workload; they require separate objectives and assumptions.