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 constant-time refinements. The challenge consists of verifying the correctness of the FC algorithm with respect to the naive approach and validating its structural properties.
翻译:暂无翻译