diff options
Diffstat (limited to 'theories/PArith/BinPosDef.v')
| -rw-r--r-- | theories/PArith/BinPosDef.v | 42 |
1 files changed, 20 insertions, 22 deletions
diff --git a/theories/PArith/BinPosDef.v b/theories/PArith/BinPosDef.v index 77239660..fefd1d76 100644 --- a/theories/PArith/BinPosDef.v +++ b/theories/PArith/BinPosDef.v @@ -1,7 +1,7 @@ (* -*- coding: utf-8 -*- *) (************************************************************************) (* v * The Coq Proof Assistant / The Coq Development Team *) -(* <O___,, * INRIA - CNRS - LIX - LRI - PPS - Copyright 1999-2014 *) +(* <O___,, * INRIA - CNRS - LIX - LRI - PPS - Copyright 1999-2015 *) (* \VV/ **************************************************************) (* // * This file is distributed under the terms of the *) (* * GNU Lesser General Public License Version 2.1 *) @@ -18,7 +18,7 @@ Require Export BinNums. -(** Postfix notation for positive numbers, allowing to mimic +(** Postfix notation for positive numbers, which allows mimicking the position of bits in a big-endian representation. For instance, we can write [1~1~0] instead of [(xO (xI xH))] for the number 6 (which is 110 in binary notation). @@ -30,8 +30,6 @@ Notation "p ~ 0" := (xO p) (at level 7, left associativity, format "p '~' '0'") : positive_scope. Local Open Scope positive_scope. -Local Unset Boolean Equality Schemes. -Local Unset Case Analysis Schemes. Module Pos. @@ -197,16 +195,16 @@ Infix "*" := mul : positive_scope. (** ** Iteration over a positive number *) -Fixpoint iter (n:positive) {A} (f:A -> A) (x:A) : A := - match n with +Definition iter {A} (f:A -> A) : A -> positive -> A := + fix iter_fix x n := match n with | xH => f x - | xO n' => iter n' f (iter n' f x) - | xI n' => f (iter n' f (iter n' f x)) + | xO n' => iter_fix (iter_fix x n') n' + | xI n' => f (iter_fix (iter_fix x n') n') end. (** ** Power *) -Definition pow (x y:positive) := iter y (mul x) 1. +Definition pow (x:positive) := iter (mul x) 1. Infix "^" := pow : positive_scope. @@ -257,20 +255,20 @@ Fixpoint size p := (** ** Comparison on binary positive numbers *) -Fixpoint compare_cont (x y:positive) (r:comparison) {struct y} : comparison := +Fixpoint compare_cont (r:comparison) (x y:positive) {struct y} : comparison := match x, y with - | p~1, q~1 => compare_cont p q r - | p~1, q~0 => compare_cont p q Gt + | p~1, q~1 => compare_cont r p q + | p~1, q~0 => compare_cont Gt p q | p~1, 1 => Gt - | p~0, q~1 => compare_cont p q Lt - | p~0, q~0 => compare_cont p q r + | p~0, q~1 => compare_cont Lt p q + | p~0, q~0 => compare_cont r p q | p~0, 1 => Gt | 1, q~1 => Lt | 1, q~0 => Lt | 1, 1 => r end. -Definition compare x y := compare_cont x y Eq. +Definition compare := compare_cont Eq. Infix "?=" := compare (at level 70, no associativity) : positive_scope. @@ -377,7 +375,7 @@ Fixpoint gcdn (n : nat) (a b : positive) : positive := Definition gcd (a b : positive) := gcdn (size_nat a + size_nat b)%nat a b. (** Generalized Gcd, also computing the division of a and b by the gcd *) - +Set Printing Universes. Fixpoint ggcdn (n : nat) (a b : positive) : (positive*(positive*positive)) := match n with | O => (1,(a,b)) @@ -484,19 +482,19 @@ Fixpoint lxor (p q:positive) : N := (** Shifts. NB: right shift of 1 stays at 1. *) -Definition shiftl_nat (p:positive)(n:nat) := nat_iter n xO p. -Definition shiftr_nat (p:positive)(n:nat) := nat_iter n div2 p. +Definition shiftl_nat (p:positive) := nat_rect _ p (fun _ => xO). +Definition shiftr_nat (p:positive) := nat_rect _ p (fun _ => div2). Definition shiftl (p:positive)(n:N) := match n with | N0 => p - | Npos n => iter n xO p + | Npos n => iter xO p n end. Definition shiftr (p:positive)(n:N) := match n with | N0 => p - | Npos n => iter n div2 p + | Npos n => iter div2 p n end. (** Checking whether a particular bit is set or not *) @@ -539,7 +537,7 @@ Definition iter_op {A}(op:A->A->A) := end. Definition to_nat (x:positive) : nat := iter_op plus x (S O). - +Arguments to_nat x: simpl never. (** ** From Peano natural numbers to binary positive numbers *) (** A version preserving positive numbers, and sending 0 to 1. *) @@ -559,4 +557,4 @@ Fixpoint of_succ_nat (n:nat) : positive := | S x => succ (of_succ_nat x) end. -End Pos.
\ No newline at end of file +End Pos. |