pith. machine review for the scientific record. sign in
def definition def or abbrev

grayToNat

show as:
view Lean formalization →

No prose has been written for this declaration yet. The Lean source and graph data below render without it.

generate prose now

formal statement (Lean)

  38def grayToNat (g : ℕ) : ℕ :=

proof body

Definition body.

  39  -- Inverse Gray code: repeatedly XOR with shifted versions
  40  -- g XOR (g >> 1) XOR (g >> 2) XOR ...
  41  -- For bounded values, this terminates
  42  let rec aux (shift : ℕ) (acc : ℕ) (fuel : ℕ) : ℕ :=
  43    match fuel with
  44    | 0 => acc
  45    | fuel' + 1 =>
  46      let shifted := g >>> shift
  47      if shifted = 0 then acc
  48      else aux (shift + 1) (acc ^^^ shifted) fuel'
  49  aux 0 0 64  -- 64 shifts is enough for any practical number
  50
  51-- Properties and classical results are provided via
  52-- `IndisputableMonolith.Patterns.GrayCodeAxioms.GrayCodeFacts`.
  53-- This module remains axiom-free and parametric over those facts.
  54
  55end Patterns
  56end IndisputableMonolith

used by (2)

From the project-wide theorem graph. These declarations reference this one in their body.

depends on (8)

Lean names referenced from this declaration's body.