hex

3.7. Worked example🔗

The block below runs the Nat extended GCD, the trial-division test, the Nat-level Barrett reducer, and one wide-word operation. The wide-word operations are @[extern]: elaboration runs their native C symbol rather than the Lean definition. HexArith is built with precompileModules, so that symbol is loaded for #eval and #guard here and in downstream packages.

open HexArith Hex.Nat namespace HexArithChapter -- gcd(12, 18) = 6, with Bezout (-1)·12 + 1·18 = 6. #guard extGcd 12 18 = (6, -1, 1) -- gcd(240, 46) = 2, with (-9)·240 + 47·46 = 2. #guard extGcd 240 46 = (2, -9, 47) -- Soundness: 97 is prime, 91 = 7·13 is not, and the -- test rejects 1 (it demands 2 ≤ n). #guard isPrimeTrial 97 = true #guard isPrimeTrial 91 = false #guard isPrimeTrial 1 = false -- Barrett reduction modulo 97 with pinv = ⌊2^64 / 97⌋ -- reproduces ordinary remainder: 1000 mod 97 = 30. #guard barrettReduceNat 97 (barrettRadix / 97) 1000 = 30 -- High word of (2^64 - 1)^2 is 2^64 - 2, from -- the native `lean_hex_uint64_mul_hi`. #guard UInt64.mulHi (0 - 1) (0 - 1) = 0 - 2 end HexArithChapter