hash_step

std.seq.hash_step · Level L4

One step of a polynomial rolling hash: multiply by 131, add the next code, reduce modulo the prime 1 000 000 007. Every value stays below 2⁵³, so the arithmetic is exact. The body poly_hash scans.

h′ = (h·131 + c) mod 1 000 000 007

Signature

hash_step(h: i64[], c: i64[]) → i64[]

Structure

The function as NOVA stores it: one box per input, operation and output, and arrows that carry values. A double border marks another library function this one runs — called once, or by Scan once per element; select it to open that function.

hi64[]131ci64[]Multiplyscaled1000000007AddaddedModh2h2i64[]
  • input
  • operation
  • constant
  • call
  • output

Verification

  • Signature proven by NOVA’s shape solver, for every size.
  • Equal to the reference (h * 131 + c) % 1_000_000_007 in exact rational arithmetic, on all 40 test cases.
  • All 40 int64 results are exact: the error is zero.
  • Interpreter and NumPy backend return bit-identical results.
Accuracy in detail
correctly rounded (the int64 nearest the exact value)
100%
bit-equal to the NumPy formula in int64
100%
largest error, in units in the last place
0

Identity

Calls
—
Called by
poly_hash
sha256:e7d78b914df19a65d1dc6814c98f511e4f51a562e5f35c818f5ea240d7a8abbf

The semantic hash of the graph. It changes when the program changes, and never when only its documentation does.