Source/Packages

Std.Natural

packages/foundation/standard/src/Std/Natural.alpha

335 lines48 declarations13.5 KiBSHA-256 0a0af2339e6a

def · lines 256–264

naturalBelowTwoPower

Full file
"value < 2^bits" WITHOUT building 2^bits: halve bits times and ask whether anything is left. The general form of naturalBelowBytePower (a byte is eight halvings); it is what a limit such as "fits int64" (bits = 63) or "at most 16 MiB of input" (bits = 24) must use at runtime, since 2^24 alone costs 2.75 GB to materialise and 2^63 cannot be materialised at all.
256def naturalBelowTwoPower =
257  (lambda unrestricted bits : Nat . unrestricted value : Nat .
258    naturalIsZero
259      (nat-eliminate
260        (lambda unrestricted current : Nat . Nat)
261        value
262        (lambda unrestricted predecessor : Nat . unrestricted quotient : Nat .
263          naturalDivideUnchecked quotient 2)
264        bits))

The compiler supplied declaration spans and resolved links from this source snapshot. This page does not assert that this file belongs to a checked closure.