"""Exact floor-function envelope for the interval paper's prime-density check. The original independent audit evaluated the same formula in C++. This NumPy implementation uses only integer arithmetic. """ import numpy as np INDICES = np.arange(31, dtype=np.int64) def envelope(numerator, denominator): """Return sixteen times the envelope at x = numerator / denominator.""" if not 0 < denominator <= numerator <= 400 * denominator: raise ValueError("The density partition covers 1 <= x <= 400.") # Each affine numerator has absolute value below 1000 * numerator. # Division bounds each summand independently of the integer inputs. if numerator > np.iinfo(np.int64).max // 1000: raise OverflowError("Input exceeds the integer range of this implementation.") scale = 96 * denominator period = 2 * scale corners = np.concatenate(( [0, scale], (INDICES * numerator) % scale, ((96 - INDICES) * numerator) % scale, [(-72 * numerator - scale // 2) % scale, (168 * numerator - scale // 2) % scale], )) # In the doubled coordinate, the next integer evaluates the right # limit at each breakpoint. For 1 <= x < 2 the y interval ends at x-1. points = np.column_stack((2 * corners, 2 * corners + 1)).ravel() upper = min(period, 192 * (numerator - denominator)) points = points[points <= upper] values = 2 - 3 * ( (points + 144 * numerator + scale) // period - (points - 336 * numerator + scale) // period ) y = points[:, None] contributions = ( ((192 - 2 * INDICES) * numerator - y) // period + (y - 2 * INDICES * numerator) // period + 1 ) best = max(0, int((values + contributions.sum(axis=1)).max())) return 16 * best - 221 * (numerator // denominator)