Verification Challenge: Fractional Cascading for Multi-Nuclide Grid Lookup

We present a verification challenge based on the fractional cascading (FC) technique for accelerating repeated searches across a collection of sorted arrays.The specific context is nuclear cross section lookup in a simulation code, where a material consists of many nuclides, each with its own sorted energy grid.A naive search performs a binary search in each array individually.The FC-based cascade grid structure reduces this cost by performing a single binary search followed by constanttime refinements.The challenge consists of verifying the correctness of the FC algorithm with respect to the naive approach and validating its structural properties. Problem DescriptionIn particle transport simulations-used to model how particles such as neutrons move through and interact with materials-accurate predictions depend on data known as nuclear cross sections.A nuclear cross section represents the probability of a specific interaction (e.g., scattering or absorption) between a particle and a nucleus, and this probability depends on the particle's energy.To compute these interactions, codes like OpenMC (https://openmc.org,[1]) store cross section data as numerical values tabulated on a sorted energy grid.Each nuclide (i.e., a specific type of atomic nucleus, such as uranium-235 or hydrogen-1) has its own energy grid, which provides microscopic cross sections-the interaction probabilities for individual nuclei-as a function of incident particle energy (the energy of a particle as it enters the material).During a simulation, when a particle with a given energy interacts with a material (which may be composed of many nuclides), the code must find where that energy lies in each nuclide's grid in order to interpolate the corresponding microscopic cross section.This results in repeated searches across multiple similar sorted arrays-one per nuclide.A straightforward method performs a binary search in each of the k sorted arrays, leading to a total query cost of O(k log(n)), where n is the average size of each grid.This challenge proposes an optimized data structure based on fractional cascading 1 (FC), which reduces the per-query cost to O(log(n) + k) by reusing information between searches. Cascade Grid AlgorithmThe FC technique, summarized in Algorithm 1, constructs a cascade grid structure consisting of k augmented energy grids M 1 , M 2 , . . ., M k , derived from the original nuclide energy grids L 1 , L 2 , . . ., L k .