/
Log2.lean
37 lines (32 loc) · 1.01 KB
/
Log2.lean
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/-
Copyright (c) 2021 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Gabriel Ebner
-/
prelude
import Init.NotationExtra
import Init.Data.Nat.Linear
namespace Nat
theorem log2_terminates : ∀ n, n ≥ 2 → n / 2 < n
| 2, _ => by decide
| 3, _ => by decide
| n+4, _ => by
rw [div_eq, if_pos]
refine succ_lt_succ (Nat.lt_trans ?_ (lt_succ_self _))
exact log2_terminates (n+2) (by simp_arith)
simp_arith
/--
Computes `⌊max 0 (log₂ n)⌋`.
`log2 0 = log2 1 = 0`, `log2 2 = 1`, ..., `log2 (2^i) = i`, etc.
-/
@[extern "lean_nat_log2"]
def log2 (n : @& Nat) : Nat :=
if n ≥ 2 then log2 (n / 2) + 1 else 0
decreasing_by exact log2_terminates _ ‹_›
theorem log2_le_self (n : Nat) : Nat.log2 n ≤ n := by
unfold Nat.log2; split
· next h =>
have := log2_le_self (n / 2)
exact Nat.lt_of_le_of_lt this (Nat.div_lt_self (Nat.le_of_lt h) (by decide))
· apply Nat.zero_le
decreasing_by exact Nat.log2_terminates _ ‹_›