Common — library colibrilib.fbin — module Impl

The model of fp.Intf

The definitions of the symbols of Intf, and its axioms as lemmas for the clone at the end.

485
module Impl
486
use int.Int
487
use int.Power
488
use int.EuclideanDivision
489
use real.RealInfix
490
use real.FromInt
491
use real.Truncate
492
use option.Option
493
use colibrilib.fp.Widen
494
use colibrilib.fp.Ereal
495
use colibrilib.zarith.Zbit
496
use colibrilib.zbit.ZbitInt
497
use colibrilib.zarith.Z as Zarith
498
use real.Square as S
499
use Pow2r
500
use Format
501
use Float
502
use Round
503
Valid (23ms) (colibri2)
504
let
format_of
(x: t) : format
505
ensures { result = x.fmt }
506
= x.fmt
507
Valid (25ms) (colibri2)
508
let
widen
(fm: format) : option format
509
ensures { match result with
510
| None -> false
511
| Some fm' -> fm'.eb = fm.eb /\ fm'.sb = fm.sb + 1 end }
512
= Some { eb = fm.eb; sb = fm.sb + 1 }

The classes

516
let predicate
is_nan
(x: t) = match x.value with NaN -> true | _ -> false end
517
predicate
is_plus_infinity
(x: t) = x.value = PlusInf
518
predicate
is_minus_infinity
(x: t) = x.value = MinusInf
519
let predicate
is_zero
(x: t) = match x.value with Finite _ k -> k = 0 | _ -> false end
520
let predicate
is_positive
(x: t) =
521
match x.value with Finite neg _ -> not neg | PlusInf -> true | _ -> false end
522
predicate
is_subnormal
(x: t) =
523
match x.value with Finite _ k -> 0 < k < binade x.fmt | _ -> false end
524
predicate
is_normal
(x: t) =
525
match x.value with Finite _ k -> binade x.fmt <= k | _ -> false end
526
527
function
not_a_number
(fm: format) : t = mk fm NaN
528
function
plus_infinity
(fm: format) : t = mk fm PlusInf
529
function
minus_infinity
(fm: format) : t = mk fm MinusInf

The index

533
function
index
(x: t) : int =
534
match x.value with
535
| Finite neg k -> if neg then -1 - k else k
536
| PlusInf -> nb_sign x.fmt - 1
537
| MinusInf -> - nb_sign x.fmt
538
| NaN -> 0
539
end
540
541
function
of_index
(fm: format) (i: int) : t =
542
if 0 <= i < nb_sign fm - 1 then mk fm (Finite false i)
543
else if - nb_sign fm < i < 0 then mk fm (Finite true (-1 - i))
544
else if i = nb_sign fm - 1 then mk fm PlusInf
545
else if i = - nb_sign fm then mk fm MinusInf
546
else mk fm NaN
547
548
predicate
le_dz
(x y: t) =
549
not is_nan x /\ not is_nan y /\ x.fmt = y.fmt /\ index x <= index y
550
predicate
lt_dz
(x y: t) =
551
not is_nan x /\ not is_nan y /\ x.fmt = y.fmt /\ index x < index y
552
Valid (30ms) (colibri2 5) (split_vc) (depth 1)
553
let ghost
nb_sign_ge
(fm: format) : unit
554
ensures { 2 * binade fm + 1 <= nb_sign fm }
555
= {proof…}
556
binade_ge_2 fm;
557
assert { power 2 (fm.eb - 1) = 2 * power 2 (fm.eb - 2) /\ 1 <= power 2 (fm.eb - 2) };
558
assert { power 2 fm.eb = 2 * power 2 (fm.eb - 1) };
559
assert { 3 <= power 2 fm.eb - 1 };
560
assert { 3 * binade fm <= (power 2 fm.eb - 1) * binade fm }
561
{qed}
562
Valid (27ms) (colibri2)
563
let
index_p
(x: t) : int
564
requires { not is_nan x }
565
ensures { result = index x }
566
= match x.value with
567
| Finite neg k -> if neg then -1 - k else k
568
| PlusInf -> nb_sign_p x.fmt - 1
569
| MinusInf -> - nb_sign_p x.fmt
570
| NaN -> absurd
571
end
572
Valid (28ms) (colibri2)
573
let
eq_format
(a b: format) : bool
574
ensures { result <-> a = b }
575
= {proof…} if a.eb = b.eb && a.sb = b.sb then assert { format'eq a b }; {qed}
576
a.eb = b.eb && a.sb = b.sb
577
Valid (30ms) (colibri2)
578
let
le_diff_zero
(x y: t) : bool
579
ensures { result <-> le_dz x y }
580
= not (is_nan x) && not (is_nan y) && eq_format x.fmt y.fmt && index_p x <= index_p y
581
Valid (27ms) (colibri2)
582
let
lt_diff_zero
(x y: t) : bool
583
ensures { result <-> lt_dz x y }
584
= not (is_nan x) && not (is_nan y) && eq_format x.fmt y.fmt && index_p x < index_p y
585
Valid (38ms) (colibri2)
586
let ghost
index_range
(x: t) : unit
587
requires { not is_nan x }
588
ensures { - nb_sign x.fmt <= index x < nb_sign x.fmt }
589
= ()
590
Valid (1.6s) (colibri2) (cvc4 2) (split_vc 2) (depth 2)
591
let ghost
of_index_range
(fm: format) (i: int) : unit
592
requires { - nb_sign fm <= i < nb_sign fm }
593
ensures { not is_nan (of_index fm i) /\ index (of_index fm i) = i }
594
ensures { (of_index fm i).fmt = fm }
595
= ()

Two floats are equal when their formats and values are

  Valid (20ms) (colibri2)
598
let ghost
t_ext
(x y: t) : unit
599
requires { x.fmt = y.fmt /\ x.value = y.value }
600
ensures { x = y }
601
= {proof…} assert { t'eq x y } {qed}
602
Valid (82ms) (colibri2)
603
let ghost
index_inj
(x: t) : unit
604
requires { not is_nan x }
605
ensures { of_index x.fmt (index x) = x }
606
= {proof…}
607
let i = index x in
608
of_index_range x.fmt i;
609
match x.value with
610
| Finite neg k -> if neg then assert { (of_index x.fmt i).value = Finite true k }
611
| _ -> ()
612
end;
613
t_ext (of_index x.fmt i) x
614
{qed}
615
Valid (27ms) (colibri2)
616
let ghost
nan_unique
(x: t) : unit
617
requires { is_nan x }
618
ensures { x = not_a_number x.fmt }
619
= {proof…} t_ext x (not_a_number x.fmt) {qed}
620
Valid (28ms) (colibri2)
621
let ghost
plus_infinity_unique
(x: t) : unit
622
requires { is_plus_infinity x }
623
ensures { x = plus_infinity x.fmt }
624
= {proof…} t_ext x (plus_infinity x.fmt) {qed}
625
Valid (27ms) (colibri2)
626
let ghost
minus_infinity_unique
(x: t) : unit
627
requires { is_minus_infinity x }
628
ensures { x = minus_infinity x.fmt }
629
= {proof…} t_ext x (minus_infinity x.fmt) {qed}

The IEEE 754 encoding

The bits of a float of fm: the sign bit, then the eb bits of the biased exponent and the sb - 1 bits of the significand, that is the magnitude k. The magnitude nb_sign fm - 1 is the infinity, the larger ones are NaNs. Only the eb + sb lowest bits of b count.

638
function
half_bits
(fm: format) : int = power 2 (fm.eb + fm.sb - 1)
639
640
function
of_bits
(fm: format) (b: int) : t =
641
let c = mod b (2 * half_bits fm) in
642
let neg = half_bits fm <= c in
643
let k = if neg then c - half_bits fm else c in
644
if k < nb_sign fm - 1 then mk fm (Finite neg k)
645
else if k = nb_sign fm - 1 then mk fm (if neg then MinusInf else PlusInf)
646
else mk fm NaN

NaN is the quiet NaN with the sign bit

649
function
to_bits
(x: t) : int =
650
match x.value with
651
| Finite neg k -> if neg then half_bits x.fmt + k else k
652
| PlusInf -> nb_sign x.fmt - 1
653
| MinusInf -> half_bits x.fmt + nb_sign x.fmt - 1
654
| NaN -> half_bits x.fmt + nb_sign x.fmt - 1 + power 2 (x.fmt.sb - 2)
655
end
656
Valid (109ms) (colibri2)
657
let ghost
half_bits_nb_sign
(fm: format) : unit
658
ensures { half_bits fm = nb_sign fm - 1 + binade fm }
659
ensures { 2 * power 2 (fm.sb - 2) = binade fm }
660
= {proof…}
661
assert { half_bits fm = power 2 fm.eb * binade fm };
662
assert { binade fm = 2 * power 2 (fm.sb - 2) }
663
{qed}
664
Valid (62ms) (colibri2)
665
let ghost
to_bits_range
(x: t) : unit
666
ensures { 0 <= to_bits x < 2 * half_bits x.fmt }
667
= half_bits_nb_sign x.fmt
668
Valid (676ms) (colibri2)
669
let ghost
of_to_bits
(x: t) : unit
670
ensures { of_bits x.fmt (to_bits x) = x }
671
= {proof…}
672
let fm = x.fmt in
673
half_bits_nb_sign fm;
674
to_bits_range x;
675
assert { mod (to_bits x) (2 * half_bits fm) = to_bits x };
676
t_ext (of_bits fm (to_bits x)) x
677
{qed}
678
Valid (1.4s) (colibri2 3) (cvc4) (cvc5) (split_vc 2) (depth 2)
679
let ghost
to_of_bits
(fm: format) (b: int) : unit
680
requires { not is_nan (of_bits fm b) }
681
ensures { to_bits (of_bits fm b) = mod b (2 * half_bits fm) }
682
= half_bits_nb_sign fm;
683
{proof…}
684
let ghost c = mod b (2 * half_bits fm) in
685
let ghost k = if half_bits fm <= c then c - half_bits fm else c in
686
if k < nb_sign fm - 1 then
687
assert { (of_bits fm b).value = Finite (half_bits fm <= c) k }
688
else assert { k = nb_sign fm - 1 }
689
{qed}
690
Valid (81ms) (colibri2)
691
let
of_bits_p
(fm: format) (b: int) : t
692
ensures { result = of_bits fm b }
693
= let h = pow2_int (fm.eb + fm.sb - 1) in
694
let q = Zarith.fdiv b (2 * h) in
695
let c = b - q * (2 * h) in
696
{proof…}
697
assert { 0 <= c < 2 * h };
698
assert { b = q * (2 * h) + c };
699
assert { div b (2 * h) = q /\ mod b (2 * h) = c };
700
{qed}
701
let neg = h <= c in
702
let k = if neg then c - h else c in
703
let n1 = nb_sign_p fm - 1 in
704
if k < n1 then mk fm (Finite neg k)
705
else if k = n1 then mk fm (if neg then MinusInf else PlusInf)
706
else mk fm NaN
707
Valid (39ms) (colibri2)
708
let
to_bits_p
(x: t) : int
709
ensures { result = to_bits x }
710
= let fm = x.fmt in
711
let h = pow2_int (fm.eb + fm.sb - 1) in
712
match x.value with
713
| Finite neg k -> if neg then h + k else k
714
| PlusInf -> nb_sign_p fm - 1
715
| MinusInf -> h + nb_sign_p fm - 1
716
| NaN -> h + nb_sign_p fm - 1 + pow2_int (fm.sb - 2)
717
end

The comparisons of IEEE 754: the zeros are equal, NaN is unordered

721
predicate
ieee_eq
(x y: t) =
722
not is_nan x /\ not is_nan y /\ (is_zero x /\ is_zero y \/ index x = index y)
723
predicate
ieee_lt
(x y: t) =
724
not is_nan x /\ not is_nan y /\ not (is_zero x /\ is_zero y) /\ index x < index y
725
predicate
ieee_le
(x y: t) = ieee_lt x y \/ ieee_eq x y
726
Valid (43ms) (colibri2)
727
let
ieee_eq_p
(x y: t) : bool
728
ensures { result <-> ieee_eq x y }
729
= not (is_nan x) && not (is_nan y)
730
&& (is_zero x && is_zero y || index_p x = index_p y)
731
Valid (43ms) (colibri2)
732
let
ieee_lt_p
(x y: t) : bool
733
ensures { result <-> ieee_lt x y }
734
= not (is_nan x) && not (is_nan y) && not (is_zero x && is_zero y)
735
&& index_p x < index_p y
736
Valid (34ms) (colibri2)
737
let
ieee_le_p
(x y: t) : bool
738
ensures { result <-> ieee_le x y }
739
= ieee_lt_p x y || ieee_eq_p x y

Negation, absolute value, minimum and maximum

  Valid (37ms) (colibri2)
743
let function
neg
(x: t) : t =
744
match x.value with
745
| NaN -> x
746
| PlusInf -> mk x.fmt MinusInf
747
| MinusInf -> mk x.fmt PlusInf
748
| Finite b k -> mk x.fmt (Finite (not b) k)
749
end
750
Valid (1.1s) (colibri2)
751
let ghost
index_neg
(x: t) : unit
752
requires { not is_nan x }
753
ensures { not is_nan (neg x) /\ (neg x).fmt = x.fmt }
754
ensures { index (neg x) = -1 - index x }
755
ensures { is_finite x -> is_finite (neg x) }
756
= ()
757
Valid (34ms) (colibri2)
758
let function
abs
(x: t) : t =
759
match x.value with
760
| MinusInf -> mk x.fmt PlusInf
761
| Finite _ k -> mk x.fmt (Finite false k)
762
| _ -> x
763
end
764
765
function
min
(x y: t) : t =
766
if is_nan x then y else if is_nan y then x
767
else if le_dz x y then x else y
768
function
max
(x y: t) : t =
769
if is_nan x then y else if is_nan y then x
770
else if le_dz x y then y else x

The values

774
function
ext
(x: t) : ereal =
775
match x.value with
776
| PlusInf -> PInf
777
| MinusInf -> MInf
778
| _ -> Fin (to_real x)
779
end
780
Valid (31ms) (colibri2)
781
let ghost
vom_le
(fm: format) (k l: int) : unit
782
requires { 0 <= k <= l }
783
ensures { vom fm k <=. vom fm l }
784
= {proof…} if k < l then vom_lt fm k l {qed}
785
Valid (23ms) (colibri2)
786
let ghost
vom_pos
(fm: format) (k: int) : unit
787
requires { 0 < k }
788
ensures { 0.0 <. vom fm k }
789
= {proof…} vom_zero fm; vom_lt fm 0 k {qed}
790
Valid (372ms) (colibri2 5) (split_vc) (depth 1)
791
let ghost
ext_le
(x y: t) : unit
792
requires { le_dz x y }
793
ensures { ele (ext x) (ext y) }
794
= {proof…}
795
let fm = x.fmt in
796
match x.value, y.value with
797
| Finite nx k, Finite ny l ->
798
vom_zero fm;
799
if not nx && not ny then vom_le fm k l
800
else if nx && ny then vom_le fm l k
801
else begin vom_le fm 0 k; vom_le fm 0 l end
802
| _ -> ()
803
end
804
{qed}
805
Valid (1.0s) (colibri2 7) (split_vc) (depth 1)
806
let ghost
ext_lt
(x y: t) : unit
807
requires { lt_dz x y /\ not (is_zero x /\ is_zero y) }
808
ensures { not ele (ext y) (ext x) }
809
= {proof…}
810
let fm = x.fmt in
811
vom_zero fm;
812
match x.value, y.value with
813
| Finite nx k, Finite ny l ->
814
if not nx && not ny then vom_lt fm k l
815
else if nx && ny then vom_lt fm l k
816
else begin
817
vom_le fm 0 k; vom_le fm 0 l;
818
if k > 0 then vom_pos fm k else if l > 0 then vom_pos fm l
819
end
820
| _ -> ()
821
end
822
{qed}
823
Valid (83ms) (colibri2)
824
let ghost
ext_zero
(x: t) : unit
825
requires { not is_nan x }
826
ensures { is_zero x <-> ext x = Fin 0.0 }
827
= {proof…}
828
vom_zero x.fmt;
829
match x.value with
830
| Finite _ k -> if k > 0 then vom_pos x.fmt k
831
| _ -> ()
832
end
833
{qed}
834
Valid (1.4s) (colibri2)
835
let ghost
ext_neg
(x: t) : unit
836
requires { not is_nan x }
837
ensures { ext (neg x) = eneg (ext x) }
838
= ()

The axioms of Intf on the classes, the index and the values

  Valid (23ms) (colibri2)
842
let lemma
nan_unique_l
(x: t)
843
requires { is_nan x } ensures { x = not_a_number x.fmt }
844
= nan_unique x
845
Valid (19ms) (colibri2)
846
let lemma
plus_infinity_unique_l
(x: t)
847
requires { is_plus_infinity x } ensures { x = plus_infinity x.fmt }
848
= plus_infinity_unique x
849
Valid (22ms) (colibri2)
850
let lemma
minus_infinity_unique_l
(x: t)
851
requires { is_minus_infinity x } ensures { x = minus_infinity x.fmt }
852
= minus_infinity_unique x
853
Valid (20ms) (colibri2)
854
let lemma
index_inj_l
(x: t)
855
requires { not is_nan x } ensures { of_index x.fmt (index x) = x }
856
= index_inj x
857
Valid (24ms) (colibri2)
858
let lemma
nb_sign_ge_l
(fm: format)
859
ensures { 2 * binade fm + 1 <= nb_sign fm }
860
= nb_sign_ge fm
861
Valid (25ms) (colibri2)
862
let lemma
ext_le_l
(x y: t)
863
requires { le_dz x y } ensures { ele (ext x) (ext y) }
864
= ext_le x y
865
Valid (26ms) (colibri2)
866
let lemma
ext_lt_l
(x y: t)
867
requires { lt_dz x y /\ not (is_zero x /\ is_zero y) }
868
ensures { not ele (ext y) (ext x) }
869
= ext_lt x y
870
Valid (25ms) (colibri2)
871
let lemma
ext_zero_l
(x: t)
872
requires { not is_nan x } ensures { is_zero x <-> ext x = Fin 0.0 }
873
= ext_zero x

Rounding

  Valid (41ms) (colibri2)
877
let ghost
kdn_mono
(fm: format) (r1 r2: real) : unit
878
requires { 0.0 <=. r1 <=. r2 }
879
ensures { kdn fm r1 <= kdn fm r2 }
880
= {proof…}
881
let k1 = kdn fm r1 in
882
let k2 = kdn fm r2 in
883
if k2 < k1 then vom_le fm (k2 + 1) k1
884
{qed}
885
Valid (63ms) (colibri2)
886
let ghost
round_mag_range
(fm: format) (m: mode) (r: real) : unit
887
requires { 0.0 <=. r }
888
ensures { 0 <= kdn fm r <= round_mag fm m r <= kdn fm r + 1 }
889
ensures { vom fm (kdn fm r) = r -> round_mag fm m r = kdn fm r }
890
ensures { m = RTN \/ m = RTZ -> round_mag fm m r = kdn fm r }
891
ensures { m = RTP -> vom fm (kdn fm r) <> r -> round_mag fm m r = kdn fm r + 1 }
892
= {proof…} let _ = kdn fm r in () {qed}
893
Valid (351ms) (colibri2)
894
let ghost
round_mag_mono
(fm: format) (m: mode) (r1 r2: real) : unit
895
requires { 0.0 <=. r1 <=. r2 }
896
ensures { round_mag fm m r1 <= round_mag fm m r2 }
897
= {proof…}
898
kdn_mono fm r1 r2; round_mag_range fm m r1; round_mag_range fm m r2;
899
let k1 = kdn fm r1 in
900
let k2 = kdn fm r2 in
901
if k1 = k2 then
902
if pure { vom fm k1 <> r1 } then assert { vom fm k2 <> r2 }
903
{qed}
904
Valid (33ms) (colibri2)
905
let ghost
round_mag_exact
(fm: format) (m: mode) (k: int) : unit
906
requires { 0 <= k }
907
ensures { round_mag fm m (vom fm k) = k }
908
= {proof…}
909
vom_lt fm k (k + 1); vom_zero fm; vom_le fm 0 k; kdn_unique fm k (vom fm k)
910
{qed}

The magnitude of the result of of_mag, for k >= 1

913
function
cmag
(fm: format) (m: mode) (k: int) : int =
914
if k < nb_sign fm - 1 then k
915
else match m with RTN | RTZ -> nb_sign fm - 2 | _ -> nb_sign fm - 1 end
916
Valid (830ms) (colibri2 5) (cvc4 2) (split_vc) (depth 1)
917
let ghost
of_mag_index
(fm: format) (m: mode) (neg: bool) (k: int) : unit
918
requires { 1 <= k }
919
ensures { not is_nan (of_mag fm m neg k) /\ (of_mag fm m neg k).fmt = fm }
920
ensures { 1 <= cmag fm m k <= nb_sign fm - 1 }
921
ensures { index (of_mag fm m neg k) = if neg then -1 - cmag fm m k else cmag fm m k }
922
ensures { not is_zero (of_mag fm m neg k) }
923
ensures { is_positive (of_mag fm m neg k) <-> not neg }
924
ensures { cmag fm m k < nb_sign fm - 1 ->
925
to_real (of_mag fm m neg k) =
926
if neg then -. vom fm (cmag fm m k) else vom fm (cmag fm m k) }
927
ensures { cmag fm m k = nb_sign fm - 1 ->
928
ext (of_mag fm m neg k) = if neg then MInf else PInf }
929
= {proof…} nb_sign_ge fm {qed}
930
Valid (987ms) (cvc5)
931
let ghost
round_fin_facts
(fm: format) (m: mode) (z: bool) (r: real) : unit
932
ensures { not is_nan (round_fin fm m z r) /\ (round_fin fm m z r).fmt = fm }
933
ensures { is_zero (round_fin fm m z r) ->
934
(is_positive (round_fin fm m z r) <-> not z) }
935
= {proof…}
936
nb_sign_ge fm;
937
if pure { 0.0 <=. r } then begin
938
round_mag_range fm m r;
939
let k = round_mag fm m r in
940
if k <> 0 then of_mag_index fm m false k
941
end else begin
942
round_mag_range fm (mirror m) (-. r);
943
let k = round_mag fm (mirror m) (-. r) in
944
if k <> 0 then of_mag_index fm (mirror m) true k
945
end
946
{qed}
947
Valid (2.0s) (colibri2 18) (cvc4 2) (cvc5 5) (split_vc 8) (depth 4)
948
let ghost
round_fin_le
(fm: format) (m: mode) (z1 z2: bool) (r1 r2: real) : unit
949
requires { r1 <=. r2 }
950
requires { is_zero (round_fin fm m z1 r1) /\ is_zero (round_fin fm m z2 r2) -> z2 -> z1 }
951
ensures { le_dz (round_fin fm m z1 r1) (round_fin fm m z2 r2) }
952
= {proof…}
953
round_fin_facts fm m z1 r1; round_fin_facts fm m z2 r2;
954
nb_sign_ge fm;
955
if pure { 0.0 <=. r1 } then begin
956
round_mag_range fm m r1; round_mag_range fm m r2;
957
round_mag_mono fm m r1 r2;
958
let k1 = round_mag fm m r1 in
959
let k2 = round_mag fm m r2 in
960
if k1 >= 1 then begin
961
of_mag_index fm m false k1; of_mag_index fm m false k2
962
end else if k2 >= 1 then of_mag_index fm m false k2
963
end else if pure { 0.0 <=. r2 } then begin
964
round_mag_range fm (mirror m) (-. r1); round_mag_range fm m r2;
965
let k1 = round_mag fm (mirror m) (-. r1) in
966
let k2 = round_mag fm m r2 in
967
if k1 >= 1 then of_mag_index fm (mirror m) true k1;
968
if k2 >= 1 then of_mag_index fm m false k2
969
end else begin
970
round_mag_range fm (mirror m) (-. r1); round_mag_range fm (mirror m) (-. r2);
971
round_mag_mono fm (mirror m) (-. r2) (-. r1);
972
let k1 = round_mag fm (mirror m) (-. r1) in
973
let k2 = round_mag fm (mirror m) (-. r2) in
974
if k2 >= 1 then begin
975
of_mag_index fm (mirror m) true k1; of_mag_index fm (mirror m) true k2
976
end else if k1 >= 1 then of_mag_index fm (mirror m) true k1
977
end
978
{qed}
979
Valid (1.2s) (colibri2 5) (cvc5) (split_vc 2) (depth 2)
980
let ghost
round_f_le
(fm: format) (m: mode) (z1 z2: bool) (e1 e2: ereal) : unit
981
requires { ele e1 e2 }
982
requires { is_zero (round_f fm m z1 e1) /\ is_zero (round_f fm m z2 e2) -> z2 -> z1 }
983
ensures { le_dz (round_f fm m z1 e1) (round_f fm m z2 e2) }
984
= {proof…}
985
nb_sign_ge fm;
986
match e1, e2 with
987
| Fin r1, Fin r2 -> round_fin_le fm m z1 z2 r1 r2
988
| Fin r1, _ -> round_fin_facts fm m z1 r1
989
| _, Fin r2 -> round_fin_facts fm m z2 r2
990
| _ -> ()
991
end
992
{qed}
993
Valid (1.0s) (colibri2 10) (split_vc) (depth 1)
994
let ghost
round_f_exact
(m: mode) (x: t) : unit
995
requires { not is_nan x }
996
ensures { round_f x.fmt m (if is_positive x then false else true) (ext x) = x }
997
= {proof…}
998
let fm = x.fmt in
999
vom_zero fm;
1000
match x.value with
1001
| Finite neg k ->
1002
if neg then begin
1003
if k = 0 then round_mag_exact fm m 0
1004
else begin
1005
vom_pos fm k;
1006
assert { -. (-. vom fm k) = vom fm k };
1007
round_mag_exact fm (mirror m) k
1008
end
1009
end else begin
1010
round_mag_exact fm m k;
1011
if k > 0 then vom_pos fm k;
1012
assert { ext x = Fin (vom fm k) /\ 0.0 <=. vom fm k }
1013
end;
1014
t_ext (round_f fm m (if is_positive x then false else true) (ext x)) x
1015
| _ -> t_ext (round_f fm m (if is_positive x then false else true) (ext x)) x
1016
end
1017
{qed}
1018
Valid (1.0s) (colibri2 7) (cvc4) (cvc5 3) (split_vc 4) (depth 3)
1019
let ghost
round_fin_down
(fm: format) (z: bool) (r: real) : unit
1020
ensures { ele (ext (round_fin fm RTN z r)) (Fin r) }
1021
= {proof…}
1022
vom_zero fm; nb_sign_ge fm;
1023
if pure { 0.0 <=. r } then begin
1024
round_mag_range fm RTN r;
1025
let k = round_mag fm RTN r in
1026
if k <> 0 then begin
1027
of_mag_index fm RTN false k; vom_le fm (cmag fm RTN k) k
1028
end
1029
end else begin
1030
round_mag_range fm RTP (-. r);
1031
let k = round_mag fm RTP (-. r) in
1032
assert { k <> 0 };
1033
of_mag_index fm RTP true k;
1034
if k < nb_sign fm - 1 then
1035
assert { -. r <=. vom fm k by vom fm (kdn fm (-. r)) <> -. r -> k = kdn fm (-. r) + 1 }
1036
end
1037
{qed}
1038
Valid (2.9s) (colibri2 6) (cvc5 3) (split_vc 3) (depth 2)
1039
let ghost
round_fin_up
(fm: format) (z: bool) (r: real) : unit
1040
ensures { ele (Fin r) (ext (round_fin fm RTP z r)) }
1041
= {proof…}
1042
vom_zero fm; nb_sign_ge fm;
1043
if pure { 0.0 <=. r } then begin
1044
round_mag_range fm RTP r;
1045
let k = round_mag fm RTP r in
1046
if k <> 0 then begin
1047
of_mag_index fm RTP false k;
1048
if k < nb_sign fm - 1 then
1049
assert { r <=. vom fm k by vom fm (kdn fm r) <> r -> k = kdn fm r + 1 }
1050
end
1051
end else begin
1052
round_mag_range fm RTN (-. r);
1053
let k = round_mag fm RTN (-. r) in
1054
if k <> 0 then begin
1055
of_mag_index fm RTN true k; vom_le fm (cmag fm RTN k) k
1056
end
1057
end
1058
{qed}

One more bit of significand

1062
predicate
widens
(fm fm': format) = fm'.eb = fm.eb /\ fm'.sb = fm.sb + 1
1063
Valid (357ms) (colibri2 13) (split_vc) (depth 1)
1064
let ghost
vom_widen
(fm fm': format) (k: int) : unit
1065
requires { widens fm fm' /\ 0 <= k }
1066
ensures { vom fm' (2 * k) = vom fm k }
1067
ensures { vom fm' (2 * k + 1) = (vom fm k +. vom fm (k + 1)) /. 2.0 }
1068
= {proof…}
1069
vom_dec fm k;
1070
let u = uexp fm k in
1071
let s = sig fm k in
1072
assert { binade fm' = 2 * binade fm };
1073
assert { qmin fm' = qmin fm - 1 };
1074
assert { u - 1 - qmin fm' = u - qmin fm };
1075
assert { (u - qmin fm) * binade fm' = 2 * ((u - qmin fm) * binade fm) };
1076
assert { 2 * k = (u - 1 - qmin fm') * binade fm' + 2 * s };
1077
assert { 2 * k + 1 = (u - 1 - qmin fm') * binade fm' + (2 * s + 1) };
1078
vom_s fm' (u - 1) (2 * s); vom_s fm' (u - 1) (2 * s + 1);
1079
pow2r_succ (u - 1)
1080
{qed}
1081
Valid (1.6s) (colibri2 15) (cvc4 2) (cvc5 4) (split_vc 2) (depth 2)
1082
let ghost
ext_widen
(fm fm': format) (i: int) : unit
1083
requires { widens fm fm' /\ - nb_sign fm <= i < nb_sign fm }
1084
ensures { ext (of_index fm' (if 0 <= i then 2 * i else 2 * i + 1)) = ext (of_index fm i) }
1085
= {proof…}
1086
assert { binade fm' = 2 * binade fm };
1087
assert { (power 2 fm'.eb - 1) * binade fm' = 2 * ((power 2 fm.eb - 1) * binade fm) };
1088
assert { nb_sign fm' = 2 * nb_sign fm - 1 };
1089
if 0 <= i then begin
1090
if i = nb_sign fm - 1 then begin
1091
assert { 2 * i = nb_sign fm' - 1 };
1092
assert { of_index fm' (2 * i) = mk fm' PlusInf };
1093
assert { of_index fm i = mk fm PlusInf };
1094
assert { ext (of_index fm' (if 0 <= i then 2 * i else 2 * i + 1)) = ext (of_index fm i) }
1095
end else begin
1096
vom_widen fm fm' i;
1097
assert { of_index fm' (2 * i) = mk fm' (Finite false (2 * i)) };
1098
assert { of_index fm i = mk fm (Finite false i) };
1099
assert { ext (of_index fm' (if 0 <= i then 2 * i else 2 * i + 1)) = ext (of_index fm i) }
1100
end
1101
end else begin
1102
if i = - nb_sign fm then begin
1103
assert { 2 * i + 1 = - nb_sign fm' };
1104
assert { of_index fm' (2 * i + 1) = mk fm' MinusInf };
1105
assert { of_index fm i = mk fm MinusInf };
1106
assert { ext (of_index fm' (if 0 <= i then 2 * i else 2 * i + 1)) = ext (of_index fm i) }
1107
end else begin
1108
vom_widen fm fm' (-1 - i);
1109
assert { of_index fm' (2 * i + 1) = mk fm' (Finite true (2 * (-1 - i))) };
1110
assert { of_index fm i = mk fm (Finite true (-1 - i)) };
1111
assert { ext (of_index fm' (if 0 <= i then 2 * i else 2 * i + 1)) = ext (of_index fm i) }
1112
end
1113
end
1114
{qed}
1115
Valid (38ms) (colibri2)
1116
let ghost
nb_sign_widen
(fm fm': format) : unit
1117
requires { widens fm fm' }
1118
ensures { nb_sign fm' = 2 * nb_sign fm - 1 }
1119
= {proof…}
1120
assert { binade fm' = 2 * binade fm };
1121
assert { (power 2 fm'.eb - 1) * binade fm' = 2 * ((power 2 fm.eb - 1) * binade fm) }
1122
{qed}

The rounding of a negative real is at most 0

  Valid (1.2s) (cvc5)
1125
let ghost
round_fin_neg_le
(fm: format) (m: mode) (z: bool) (r: real) : unit
1126
requires { r <. 0.0 }
1127
ensures { ele (ext (round_fin fm m z r)) (Fin 0.0) }
1128
= {proof…}
1129
vom_zero fm; nb_sign_ge fm;
1130
round_mag_range fm (mirror m) (-. r);
1131
let k = round_mag fm (mirror m) (-. r) in
1132
if k <> 0 then begin
1133
of_mag_index fm (mirror m) true k;
1134
vom_le fm 0 (cmag fm (mirror m) k)
1135
end
1136
{qed}

Rounding toward zero a real r >= 0 gives at most r

  Valid (1.4s) (cvc4)
1139
let ghost
round_fin_pos_down
(fm: format) (m: mode) (z: bool) (r: real) : unit
1140
requires { 0.0 <=. r /\ (m = RTN \/ m = RTZ) }
1141
ensures { ele (ext (round_fin fm m z r)) (Fin r) }
1142
= {proof…}
1143
vom_zero fm; nb_sign_ge fm;
1144
round_mag_range fm m r;
1145
let k = round_mag fm m r in
1146
if k <> 0 then begin
1147
of_mag_index fm m false k; vom_le fm (cmag fm m k) k
1148
end
1149
{qed}

Below a float b (not –0), the rounding is at most b

  Valid (55ms) (colibri2)
1152
let ghost
round_le_of
(fm: format) (m: mode) (z: bool) (r: real) (b: t) : unit
1153
requires { not is_nan b /\ b.fmt = fm /\ index b <> -1 /\ ele (Fin r) (ext b) }
1154
ensures { le_dz (round_fin fm m z r) b }
1155
= {proof…}
1156
round_f_exact m b;
1157
round_fin_facts fm m z r;
1158
let zb = if is_positive b then false else true in
1159
match ext b with
1160
| Fin rb -> round_fin_le fm m z zb r rb
1161
| _ -> index_range (round_fin fm m z r)
1162
end
1163
{qed}
1164
Valid (3.7s) (colibri2 68) (cvc4 4) (cvc5 24) (split_vc 10) (depth 4)
1165
let ghost
round_f_ge_thr
(fm fm': format) (m: mode) (z: bool) (e: ereal) (a: t) : unit
1166
requires { widens fm fm' /\ a.fmt = fm /\ not is_nan a /\ not is_minus_infinity a }
1167
requires { index a <> 0 /\ le_dz a (round_f fm m z e) }
1168
ensures { ele (ext (of_index fm' (windex (index a) + lo_off m (index a)))) e }
1169
= {proof…}
1170
let i = index a in
1171
nb_sign_ge fm; nb_sign_widen fm fm'; index_range a; vom_zero fm;
1172
match e with
1173
| PInf -> ()
1174
| MInf -> ()
1175
| Fin r ->
1176
let res = round_fin fm m z r in
1177
round_fin_facts fm m z r;
1178
ext_le a res;
1179
let b = of_index fm (i - 1) in
1180
of_index_range fm (i - 1);
1181
ext_widen fm fm' i; ext_widen fm fm' (i - 1);
1182
assert { windex i - 2 = windex (i - 1) };
1183
match m with
1184
| RTN -> round_fin_down fm z r
1185
| RTP ->
1186
if pure { not ele (ext b) (Fin r) } then round_le_of fm m z r b
1187
| RTZ ->
1188
if 0 <= i then begin
1189
if pure { 0.0 <=. r } then round_fin_pos_down fm m z r
1190
else begin
1191
round_fin_neg_le fm m z r;
1192
match a.value with Finite _ k -> vom_pos fm k | _ -> () end
1193
end
1194
end else
1195
if pure { not ele (ext b) (Fin r) } then round_le_of fm m z r b
1196
| RNE | RNA ->
1197
if 0 <= i then begin
1198
vom_widen fm fm' (i - 1);
1199
assert { of_index fm' (windex i - 1) = mk fm' (Finite false (2 * (i - 1) + 1)) };
1200
let mid = (vom fm (i - 1) +. vom fm i) /. 2.0 in
1201
assert { windex i + lo_off m i = 2 * (i - 1) + 1 };
1202
assert { ext (of_index fm' (2 * (i - 1) + 1)) = Fin mid };
1203
if pure { r <. mid } then begin
1204
if pure { not ele (ext b) (Fin r) } then begin
1205
round_le_of fm m z r b; assert { index res <= i - 1 }
1206
end else begin
1207
assert { ext b = Fin (vom fm (i - 1)) };
1208
vom_lt fm (i - 1) i;
1209
vom_le fm 0 (i - 1);
1210
assert { 0.0 <=. vom fm (i - 1) <=. r <. vom fm i };
1211
kdn_unique fm (i - 1) r;
1212
assert { round_mag fm m r = i - 1 };
1213
if i - 1 <> 0 then of_mag_index fm m false (i - 1);
1214
assert { index res <= i - 1 }
1215
end
1216
end;
1217
assert { mid <=. r }
1218
end else begin
1219
let ka = -1 - i in
1220
vom_widen fm fm' ka;
1221
assert { of_index fm' (windex i - 1) = mk fm' (Finite true (2 * ka + 1)) };
1222
let mid = (vom fm ka +. vom fm (ka + 1)) /. 2.0 in
1223
assert { windex i + lo_off m i = 2 * i };
1224
assert { ext (of_index fm' (2 * i)) = Fin (-. mid) };
1225
if pure { r <. -. mid } then begin
1226
vom_lt fm ka (ka + 1); vom_le fm 0 ka;
1227
assert { vom fm ka <. mid <. -. r };
1228
kdn_unique fm ka (vom fm ka);
1229
kdn_mono fm (vom fm ka) (-. r);
1230
round_mag_range fm (mirror m) (-. r);
1231
assert { mirror m = m };
1232
let k = round_mag fm (mirror m) (-. r) in
1233
assert { ka + 1 <= k };
1234
of_mag_index fm (mirror m) true k;
1235
assert { ka + 1 <= nb_sign fm - 1 };
1236
assert { cmag fm (mirror m) k = (if k < nb_sign fm - 1 then k else nb_sign fm - 1) };
1237
assert { cmag fm (mirror m) k >= ka + 1 };
1238
assert { index res <= i - 1 }
1239
end;
1240
assert { -. mid <=. r }
1241
end
1242
end
1243
end
1244
{qed}
1245
Valid (1.0s) (cvc4)
1246
let ghost
neg_of_mag
(fm: format) (m: mode) (ng: bool) (k: int) : unit
1247
requires { 1 <= k }
1248
ensures { neg (of_mag fm m ng k) = of_mag fm m (not ng) k }
1249
= {proof…}
1250
nb_sign_ge fm;
1251
t_ext (neg (of_mag fm m ng k)) (of_mag fm m (not ng) k)
1252
{qed}
1253
Valid (1.6s) (colibri2 15) (cvc5 2) (split_vc 4) (depth 3)
1254
let ghost
round_f_neg
(fm: format) (m: mode) (z: bool) (e: ereal) : unit
1255
ensures { round_f fm m z (eneg e) = neg (round_f fm (mirror m) (not z) e) }
1256
= {proof…}
1257
nb_sign_ge fm; vom_zero fm;
1258
assert { mirror (mirror m) = m };
1259
match e with
1260
| Fin r ->
1261
let lhs = round_fin fm m z (-. r) in
1262
let rhs = neg (round_fin fm (mirror m) (not z) r) in
1263
if pure { 0.0 <. r } then begin
1264
let k = round_mag fm (mirror m) r in
1265
round_mag_range fm (mirror m) r;
1266
if k <> 0 then neg_of_mag fm (mirror m) false k
1267
end else if pure { r <. 0.0 } then begin
1268
let k = round_mag fm m (-. r) in
1269
round_mag_range fm m (-. r);
1270
if k <> 0 then neg_of_mag fm m true k
1271
end else begin
1272
round_mag_exact fm m 0; round_mag_exact fm (mirror m) 0;
1273
assert { -. r = 0.0 /\ r = 0.0 }
1274
end;
1275
t_ext lhs rhs
1276
| PInf -> t_ext (round_f fm m z (eneg e)) (neg (round_f fm (mirror m) (not z) e))
1277
| MInf -> t_ext (round_f fm m z (eneg e)) (neg (round_f fm (mirror m) (not z) e))
1278
end
1279
{qed}
1280
Valid (1.5s) (cvc4)
1281
let ghost
of_index_neg
(fm: format) (i: int) : unit
1282
requires { - nb_sign fm <= i < nb_sign fm }
1283
ensures { of_index fm (-1 - i) = neg (of_index fm i) }
1284
= {proof…} t_ext (of_index fm (-1 - i)) (neg (of_index fm i)) {qed}
1285
Valid (2.9s) (colibri2 12) (cvc4 3) (cvc5 4) (split_vc 5) (depth 2)
1286
let ghost
round_f_le_thr
(fm fm': format) (m: mode) (z: bool) (e: ereal) (b: t) : unit
1287
requires { widens fm fm' /\ b.fmt = fm /\ not is_nan b /\ not is_plus_infinity b }
1288
requires { index b <> -1 /\ le_dz (round_f fm m z e) b }
1289
ensures { ele e (ext (of_index fm' (windex (index b) + hi_off m (index b)))) }
1290
= {proof…}
1291
let j = index b in
1292
let m' = mirror m in
1293
assert { mirror m' = m };
1294
round_f_neg fm m' (not z) e;
1295
let x = round_f fm m z e in
1296
match e with Fin r -> round_fin_facts fm m z r | _ -> () end;
1297
assert { round_f fm m' (not z) (eneg e) = neg x };
1298
index_neg b; index_neg x;
1299
assert { le_dz (neg b) (neg x) };
1300
round_f_ge_thr fm fm' m' (not z) (eneg e) (neg b);
1301
let w = windex j + hi_off m j in
1302
assert { windex (-1 - j) + lo_off m' (-1 - j) = -1 - w };
1303
nb_sign_widen fm fm'; index_range b; nb_sign_ge fm;
1304
of_index_neg fm' w;
1305
ext_neg (of_index fm' w);
1306
assert { index (neg b) = -1 - j };
1307
assert { ele (eneg (ext (of_index fm' w))) (eneg e) }
1308
{qed}
1309
Valid (24ms) (colibri2)
1310
let lemma
round_f_ge_thr_l
(fm fm': format) (m: mode) (z: bool) (e: ereal) (a: t)
1311
requires { widens fm fm' /\ a.fmt = fm /\ not is_nan a /\ not is_minus_infinity a }
1312
requires { index a <> 0 /\ le_dz a (round_f fm m z e) }
1313
ensures { ele (ext (of_index fm' (windex (index a) + lo_off m (index a)))) e }
1314
= round_f_ge_thr fm fm' m z e a
1315
Valid (25ms) (colibri2)
1316
let lemma
round_f_le_thr_l
(fm fm': format) (m: mode) (z: bool) (e: ereal) (b: t)
1317
requires { widens fm fm' /\ b.fmt = fm /\ not is_nan b /\ not is_plus_infinity b }
1318
requires { index b <> -1 /\ le_dz (round_f fm m z e) b }
1319
ensures { ele e (ext (of_index fm' (windex (index b) + hi_off m (index b)))) }
1320
= round_f_le_thr fm fm' m z e b
1321
Valid (26ms) (colibri2)
1322
let lemma
round_f_le_l
(fm: format) (m: mode) (z1 z2: bool) (e1 e2: ereal)
1323
requires { ele e1 e2 }
1324
requires { is_zero (round_f fm m z1 e1) /\ is_zero (round_f fm m z2 e2) -> z2 -> z1 }
1325
ensures { le_dz (round_f fm m z1 e1) (round_f fm m z2 e2) }
1326
= round_f_le fm m z1 z2 e1 e2
1327
Valid (29ms) (colibri2)
1328
let lemma
round_f_exact_l
(m: mode) (x: t)
1329
requires { not is_nan x }
1330
ensures { round_f x.fmt m (if is_positive x then false else true) (ext x) = x }
1331
= round_f_exact m x

The magnitude of the integer n, 1 <= n, scaled by 2^j below 2 binade: the significand n 2^j with the ulp 2^-j

  Valid (383ms) (colibri2 19) (cvc5) (split_vc 5) (depth 3)
1335
let rec ghost
mag_of_int
(fm: format) (n j: int) : int
1336
requires { 1 <= n /\ 0 <= j /\ n * power 2 j < 2 * binade fm }
1337
ensures { 0 <= result /\ vom fm result = from_int n }
1338
variant { fm.sb - j }
1339
= {proof…}
1340
binade_ge_2 fm;
1341
let s = n * power 2 j in
1342
assert { power 2 j <= s };
1343
if binade fm <= s then begin
1344
assert { j < fm.sb by power 2 j < power 2 fm.sb = 2 * binade fm };
1345
assert { power 2 (fm.eb - 1) >= 1 };
1346
assert { qmin fm <= - j };
1347
vom_s fm (- j) s;
1348
pow2r_add j (- j); pow2r_int j;
1349
assert { pow2r j *. pow2r (- j) = 1.0 by pow2r 0 = 1.0 };
1350
assert { from_int s = from_int n *. pow2r j };
1351
assert { from_int s *. pow2r (- j) = from_int n *. (pow2r j *. pow2r (- j)) };
1352
(- j - qmin fm) * binade fm + s
1353
end else begin
1354
assert { power 2 (j + 1) = 2 * power 2 j };
1355
assert { n * power 2 (j + 1) = 2 * s };
1356
mag_of_int fm n (j + 1)
1357
end
1358
{qed}

The integers of magnitude at most 2^sb and at most the largest finite float are floats

  Valid (788ms) (colibri2 15) (cvc5) (split_vc 3) (depth 3)
1362
let ghost
int_exact
(fm: format) (i: int) : t
1363
requires { - power 2 fm.sb <= i <= power 2 fm.sb }
1364
requires { -. to_real (of_index fm (nb_sign fm - 2)) <=. from_int i <=.
1365
to_real (of_index fm (nb_sign fm - 2)) }
1366
ensures { result.fmt = fm /\ not is_nan result /\ ext result = Fin (from_int i) }
1367
= {proof…}
1368
nb_sign_ge fm; binade_ge_2 fm;
1369
let mx = nb_sign fm - 2 in
1370
assert { to_real (of_index fm mx) = vom fm mx };
1371
let n = if i < 0 then - i else i in
1372
assert { from_int n <=. vom fm mx };
1373
let k =
1374
if n = 0 then begin vom_zero fm; 0 end
1375
else if n < power 2 fm.sb then begin
1376
assert { power 2 0 = 1 }; mag_of_int fm n 0 end
1377
else begin
1378
assert { power 2 fm.sb = 2 * binade fm };
1379
assert { power 2 (fm.eb - 1) >= 1 };
1380
vom_s fm 1 (binade fm);
1381
assert { pow2r 1 = 2.0 };
1382
(1 - qmin fm) * binade fm + binade fm
1383
end in
1384
if mx < k then begin vom_lt fm mx k; absurd end;
1385
let x = mk fm (Finite (i < 0) k) in
1386
assert { to_real x = from_int i };
1387
x
1388
{qed}

The magnitude of the dyadic s 2^u, 1 <= s < 2 binade, normalized by shifting s left

  Valid (210ms) (colibri2)
1392
let rec ghost
mag_of_dy
(fm: format) (s u: int) : int
1393
requires { 1 <= s < 2 * binade fm /\ qmin fm <= u }
1394
ensures { 0 <= result /\ vom fm result = from_int s *. pow2r u }
1395
variant { u - qmin fm }
1396
= {proof…}
1397
binade_ge_2 fm;
1398
if binade fm <= s || u = qmin fm then begin
1399
vom_s fm u s;
1400
(u - qmin fm) * binade fm + s
1401
end else begin
1402
pow2r_succ (u - 1);
1403
assert { from_int (2 * s) *. pow2r (u - 1) = from_int s *. pow2r u };
1404
mag_of_dy fm (2 * s) (u - 1)
1405
end
1406
{qed}

The magnitude of the infinity is at 2^(bias + 1)

  Valid (99ms) (colibri2)
1409
let ghost
vom_inf
(fm: format) : unit
1410
ensures { vom fm (nb_sign fm - 1) = pow2r (bias fm + 1) }
1411
= {proof…}
1412
binade_ge_2 fm;
1413
let b = binade fm in
1414
let u = power 2 fm.eb - 2 + qmin fm in
1415
assert { power 2 fm.eb = 2 * power 2 (fm.eb - 1) };
1416
assert { power 2 (fm.eb - 1) >= 2 by power 2 (fm.eb - 1) = 2 * power 2 (fm.eb - 2) /\ power 2 (fm.eb - 2) >= 1 };
1417
assert { nb_sign fm - 1 = (u - qmin fm) * b + b };
1418
vom_s fm u b;
1419
pow2r_int (fm.sb - 1); pow2r_add (fm.sb - 1) u;
1420
assert { fm.sb - 1 + u = bias fm + 1 }
1421
{qed}

A finite float is a float of the wider formats

  Valid (790ms) (colibri2 14) (cvc5 2) (split_vc) (depth 1)
1424
let ghost
widen_exact
(fm': format) (x: t) : t
1425
requires { x.fmt.eb <= fm'.eb /\ x.fmt.sb <= fm'.sb }
1426
requires { not is_nan x /\ not is_plus_infinity x /\ not is_minus_infinity x }
1427
ensures { result.fmt = fm' /\ not is_nan result /\ ext result = ext x }
1428
= {proof…}
1429
let fm = x.fmt in
1430
match x.value with
1431
| Finite ng k ->
1432
vom_zero fm; vom_zero fm'; nb_sign_ge fm'; binade_ge_2 fm;
1433
if k = 0 then mk fm' (Finite ng 0)
1434
else begin
1435
vom_dec fm k; vom_pos fm k;
1436
let s = sig fm k in
1437
let u = uexp fm k in
1438
pow2r_pos u;
1439
assert { 1 <= s by from_int s *. pow2r u >. 0.0 };
1440
assert { power 2 (fm.sb - 1) <= power 2 (fm'.sb - 1) };
1441
assert { power 2 (fm.eb - 1) <= power 2 (fm'.eb - 1) };
1442
assert { qmin fm' <= qmin fm };
1443
let k' = mag_of_dy fm' s u in
1444
vom_lt fm k (nb_sign fm - 1); vom_inf fm; vom_inf fm';
1445
pow2r_le (bias fm + 1) (bias fm' + 1);
1446
if k' >= nb_sign fm' - 1 then begin vom_le fm' (nb_sign fm' - 1) k'; absurd end;
1447
let y = mk fm' (Finite ng k') in
1448
assert { to_real y = to_real x };
1449
y
1450
end
1451
| _ -> absurd
1452
end
1453
{qed}
1454
Valid (629ms) (colibri2)
1455
let lemma
round_f_facts_l
(fm: format) (m: mode) (z: bool) (e: ereal)
1456
ensures { not is_nan (round_f fm m z e) /\ (round_f fm m z e).fmt = fm }
1457
ensures { is_zero (round_f fm m z e) -> (is_positive (round_f fm m z e) <-> not z) }
1458
= match e with Fin r -> round_fin_facts fm m z r | _ -> () end
1459
Valid (34ms) (colibri2)
1460
let lemma
round_f_down_l
(fm: format) (z: bool) (e: ereal)
1461
ensures { ele (ext (round_f fm RTN z e)) e }
1462
= match e with Fin r -> round_fin_down fm z r | _ -> () end
1463
Valid (44ms) (colibri2)
1464
let lemma
round_f_up_l
(fm: format) (z: bool) (e: ereal)
1465
ensures { ele e (ext (round_f fm RTP z e)) }
1466
= match e with Fin r -> round_fin_up fm z r | _ -> () end
1467
Valid (1.1s) (cvc5)
1468
let lemma
round_f_fin_zero_l
(fm: format) (m: mode) (z: bool)
1469
ensures { is_zero (round_f fm m z (Fin 0.0)) }
1470
= vom_zero fm; round_mag_exact fm m 0
1471
Valid (25ms) (colibri2)
1472
let lemma
ext_widen_l
(fm fm': format) (i: int)
1473
requires { widens fm fm' /\ - nb_sign fm <= i < nb_sign fm }
1474
ensures { ext (of_index fm' (if 0 <= i then 2 * i else 2 * i + 1)) = ext (of_index fm i) }
1475
= ext_widen fm fm' i

Addition, multiplication and conversion

  Valid (56ms) (colibri2)
1479
let ghost
finite_sign
(x: t) : unit
1480
ensures { match x.value with
1481
| Finite ng k ->
1482
(k = 0 -> to_real x = 0.0) /\
1483
(0 < k -> (ng -> to_real x <. 0.0) /\ (not ng -> 0.0 <. to_real x))
1484
| _ -> true end }
1485
= {proof…}
1486
vom_zero x.fmt;
1487
match x.value with Finite _ k -> if 0 < k then vom_pos x.fmt k | _ -> () end
1488
{qed}

The sign of a zero sum (IEEE 754 §6.3)

1491
function
add_zneg
(m: mode) (x y: t) : bool =
1492
if is_positive x <-> is_positive y then (if is_positive x then false else true)
1493
else (if m = RTN then true else false)
1494
1495
function
fp_add
(m: mode) (x y: t) : t =
1496
if is_nan x \/ is_nan y \/ opposite (ext x) (ext y) then not_a_number x.fmt
1497
else round_f x.fmt m (add_zneg m x y) (eadd (ext x) (ext y))
1498
Valid (825ms) (colibri2)
1499
let
add
(m: mode) (x y: t) : t
1500
ensures { x.fmt = y.fmt -> result = fp_add m x y }
1501
= let fm = x.fmt in
1502
if not (eq_format fm y.fmt) then mk fm NaN else
1503
match x.value, y.value with
1504
| NaN, _ | _, NaN -> mk fm NaN
1505
| PlusInf, MinusInf | MinusInf, PlusInf -> mk fm NaN
1506
| PlusInf, _ | _, PlusInf -> mk fm PlusInf
1507
| MinusInf, _ | _, MinusInf -> mk fm MinusInf
1508
| Finite _ _, Finite _ _ ->
1509
let rtn = match m with RTN -> true | _ -> false end in
1510
let z = if is_positive x then (if is_positive y then false else rtn)
1511
else (if is_positive y then rtn else true) in
1512
round_d fm m z (dadd (to_dyadic x) (to_dyadic y))
1513
end
1514
1515
predicate
is_infinity
(x: t) = is_plus_infinity x \/ is_minus_infinity x

The sign of a product (IEEE 754 §6.3)

1518
function
mul_zneg
(x y: t) : bool =
1519
if is_positive x <-> is_positive y then false else true
1520
1521
function
fp_mul
(m: mode) (x y: t) : t =
1522
if is_nan x \/ is_nan y \/ (is_zero x /\ is_infinity y)
1523
\/ (is_infinity x /\ is_zero y) then not_a_number x.fmt
1524
else round_f x.fmt m (mul_zneg x y) (emul (ext x) (ext y))
1525
Valid (1.4s) (colibri2 33) (cvc5 2) (split_vc 3) (depth 3)
1526
let
mul
(m: mode) (x y: t) : t
1527
ensures { x.fmt = y.fmt -> result = fp_mul m x y }
1528
= let fm = x.fmt in
1529
if not (eq_format fm y.fmt) then mk fm NaN else
1530
let z = if is_positive x then not (is_positive y) else is_positive y in
1531
let inf = if z then MinusInf else PlusInf in
1532
{proof…} finite_sign x; finite_sign y; {qed}
1533
match x.value, y.value with
1534
| NaN, _ | _, NaN -> mk fm NaN
1535
| Finite _ k, (PlusInf | MinusInf) | (PlusInf | MinusInf), Finite _ k ->
1536
if k = 0 then mk fm NaN else mk fm inf
1537
| (PlusInf | MinusInf), (PlusInf | MinusInf) -> mk fm inf
1538
| Finite _ _, Finite _ _ -> round_d fm m z (dmul (to_dyadic x) (to_dyadic y))
1539
end
1540
1541
function
fp_convert
(fm: format) (m: mode) (x: t) : t =
1542
if is_nan x then not_a_number fm
1543
else round_f fm m (if is_positive x then false else true) (ext x)
1544
Valid (40ms) (colibri2)
1545
let
convert
(fm: format) (m: mode) (x: t) : t
1546
ensures { result = fp_convert fm m x }
1547
= match x.value with
1548
| NaN -> mk fm NaN
1549
| PlusInf -> mk fm PlusInf
1550
| MinusInf -> mk fm MinusInf
1551
| Finite _ _ -> round_d fm m (not (is_positive x)) (to_dyadic x)
1552
end

Rounding to an integral float

The rounding of a real to an integer in the mode

1557
function
round_int
(m: mode) (r: real) : int =
1558
let f = Truncate.floor r in
1559
let d = r -. from_int f in
1560
match m with
1561
| RTN -> f
1562
| RTP -> if d = 0.0 then f else f + 1
1563
| RTZ -> if 0.0 <=. r \/ d = 0.0 then f else f + 1
1564
| RNE -> if d <. 0.5 then f else if 0.5 <. d then f + 1
1565
else if mod f 2 = 0 then f else f + 1
1566
| RNA -> if d <. 0.5 then f else if 0.5 <. d then f + 1
1567
else if 0.0 <=. r then f + 1 else f
1568
end
1569
Valid (43ms) (colibri2)
1570
let ghost
floor_unique
(r: real) (n: int) : unit
1571
requires { from_int n <=. r <. from_int n +. 1.0 }
1572
ensures { Truncate.floor r = n }
1573
= {proof…}
1574
assert { n <= Truncate.floor r by Truncate.floor (from_int n) = n };
1575
assert { Truncate.floor r < n + 1 by from_int (Truncate.floor r) <=. r }
1576
{qed}
1577
Valid (106ms) (cvc5)
1578
let ghost
round_int_monotonic
(m: mode) (x y: real) : unit
1579
requires { x <=. y }
1580
ensures { round_int m x <= round_int m y }
1581
= {proof…}
1582
let fx = Truncate.floor x in
1583
let fy = Truncate.floor y in
1584
assert { fx <= fy };
1585
if fx = fy then begin
1586
if fx >= 0 then assert { 0.0 <=. x }
1587
else assert { y <. 0.0 by from_int fy +. 1.0 <=. 0.0 }
1588
end
1589
{qed}
1590
Valid (33ms) (colibri2)
1591
let lemma
round_int_monotonic_l
(m: mode) (x y: real)
1592
requires { x <=. y }
1593
ensures { round_int m x <= round_int m y }
1594
= round_int_monotonic m x y

The rounding to an integer of a dyadic number

  Valid (1.1s) (colibri2 29) (split_vc) (depth 1)
1597
let
round_int_d
(m: mode) (d: dyadic) : int
1598
ensures { result = round_int m (dval d) }
1599
= if d.de >= 0 then begin
1600
{proof…}
1601
lsl_mul d.dm d.de; pow2r_int d.de;
1602
assert { dval d = from_int (d.dm * power 2 d.de) };
1603
floor_unique (dval d) (d.dm * power 2 d.de);
1604
{qed}
1605
lsl_int d.dm d.de
1606
end else begin
1607
let sh = - d.de in
1608
let pw = Round.pow2_int sh in
1609
let f = asr_int d.dm sh in
1610
let rem = d.dm - f * pw in
1611
{proof…}
1612
asr_div d.dm sh;
1613
assert { 0 <= rem < pw /\ d.dm = f * pw + rem };
1614
let ghost c = pure { pow2r d.de } in
1615
pow2r_add sh d.de; pow2r_int sh; pow2r_pos d.de;
1616
assert { from_int pw *. c = 1.0 };
1617
assert { from_int d.dm = from_int f *. from_int pw +. from_int rem };
1618
assert { dval d = from_int f *. (from_int pw *. c) +. from_int rem *. c };
1619
assert { dval d = from_int f +. from_int rem *. c };
1620
scale_cmp 0 rem c; scale_cmp rem pw c;
1621
floor_unique (dval d) f;
1622
assert { dval d -. from_int f = from_int rem *. c };
1623
assert { rem = 0 <-> from_int rem *. c = 0.0 };
1624
assert { 0.0 <=. dval d <-> 0 <= d.dm by
1625
(0 <= d.dm -> 0 <= f) /\ (d.dm < 0 -> f < 0) };
1626
{qed}
1627
match m with
1628
| RTN -> f
1629
| RTP -> if rem = 0 then f else f + 1
1630
| RTZ -> if d.dm >= 0 || rem = 0 then f else f + 1
1631
| RNE | RNA ->
1632
let h = Round.pow2_int (sh - 1) in
1633
{proof…}
1634
assert { pw = 2 * h };
1635
assert { 0.5 = from_int h *. c };
1636
scale_cmp rem h c;
1637
{qed}
1638
if rem < h then f
1639
else if rem > h then f + 1
1640
else match m with
1641
| RNA -> if d.dm >= 0 then f + 1 else f
1642
| _ -> if even f then f else f + 1
1643
end
1644
end
1645
end
1646
1647
function
eround_int
(m: mode) (e: ereal) : ereal =
1648
match e with Fin r -> Fin (from_int (round_int m r)) | _ -> e end
1649
1650
function
fp_rti
(m: mode) (x: t) : t =
1651
if is_nan x then not_a_number x.fmt
1652
else round_f x.fmt m (if is_positive x then false else true) (eround_int m (ext x))
1653
Valid (88ms) (colibri2)
1654
let
round_to_integral
(m: mode) (x: t) : t
1655
ensures { result = fp_rti m x }
1656
= match x.value with
1657
| Finite _ _ ->
1658
let n = round_int_d m (to_dyadic x) in
1659
{proof…} pow2r_int 0; {qed}
1660
round_d x.fmt m (not (is_positive x)) { dm = n; de = 0 }
1661
| _ -> {proof…} t_ext x (fp_rti m x); {qed} x
1662
end

Rounding to odd

The reals strictly between n * 2^w and (n+1) * 2^w round alike, when 2^w is at most half the ulp of the result: w <= e - sb with 2^e <= r. The quotient and the square root are computed with such a w, and their remainder gives the odd dyadic number (2n+1) * 2^(w-1) of the same rounding.

  Valid (158ms) (colibri2 8) (split_vc) (depth 1)
1672
let ghost
uexp_ge
(fm: format) (r: real) (e: int) : unit
1673
requires { pow2r e <=. r }
1674
ensures { e - fm.sb + 1 <= uexp fm (kdn fm r) }
1675
= {proof…}
1676
pow2r_pos e;
1677
let k = kdn fm r in
1678
vom_dec fm k;
1679
let u = uexp fm k in
1680
pow2r_add fm.sb u; pow2r_int fm.sb; pow2r_pos u;
1681
assert { power 2 fm.sb = 2 * binade fm };
1682
scale_cmp (sig fm k + 1) (power 2 fm.sb) (pow2r u);
1683
assert { r <. pow2r (fm.sb + u) };
1684
if e > u + fm.sb - 1 then pow2r_le (fm.sb + u) e
1685
{qed}

Two reals strictly inside the same cell, on the same side of its midpoint, have the same rounded magnitudes

  Valid (881ms) (cvc5)
1689
let ghost
round_mag_same_side
(fm: format) (r r': real) (k: int) : unit
1690
requires { kdn fm r = k /\ kdn fm r' = k }
1691
requires { vom fm k <> r /\ vom fm k <> r' }
1692
requires { let mid = (vom fm k +. vom fm (k + 1)) /. 2.0 in
1693
(mid <. r /\ mid <. r') \/ (r <. mid /\ r' <. mid) }
1694
ensures { forall m. round_mag fm m r = round_mag fm m r' }
1695
= ()
1696
Valid (617ms) (colibri2 21) (cvc4) (cvc5 8) (split_vc 4) (depth 2)
1697
let ghost
round_mag_cell
(fm: format) (r r': real) (n w e: int) : unit
1698
requires { 0 <= n }
1699
requires { from_int n *. pow2r w <. r <. from_int (n + 1) *. pow2r w }
1700
requires { from_int n *. pow2r w <. r' <. from_int (n + 1) *. pow2r w }
1701
requires { pow2r e <=. r /\ w <= e - fm.sb }
1702
ensures { forall m. round_mag fm m r = round_mag fm m r' }
1703
= {proof…}
1704
let c = pow2r w in
1705
pow2r_pos w;
1706
assert { 0.0 <=. from_int n *. c };
1707
let k = kdn fm r in
1708
uexp_ge fm r e;
1709
vom_dec fm k;
1710
let u = uexp fm k in
1711
let s = sig fm k in
1712
let t = Round.pow2_int (u - w - 1) in
1713
pow2r_add w (u - w); pow2r_int (u - w);
1714
assert { power 2 (u - w) = 2 * t };
1715
assert { pow2r u = from_int (2 * t) *. c };
1716
let a = s * (2 * t) in
1717
let b = (s + 1) * (2 * t) in
1718
let mm = (2 * s + 1) * t in
1719
assert { vom fm k = from_int a *. c };
1720
assert { vom fm (k + 1) = from_int b *. c };
1721
assert { (vom fm k +. vom fm (k + 1)) /. 2.0 = from_int mm *. c };
1722
scale_cmp a (n + 1) c; scale_cmp n b c; scale_cmp (n + 1) b c;
1723
scale_cmp a n c; scale_cmp mm n c; scale_cmp mm (n + 1) c;
1724
assert { a <= n /\ n + 1 <= b };
1725
assert { vom fm k <. r' <. vom fm (k + 1) };
1726
kdn_unique fm k r';
1727
assert { vom fm k <> r /\ vom fm k <> r' };
1728
if mm <= n then
1729
assert { from_int mm *. c <. r /\ from_int mm *. c <. r' }
1730
else
1731
assert { r <. from_int mm *. c /\ r' <. from_int mm *. c };
1732
round_mag_same_side fm r r' k
1733
{qed}

Two reals of the same sign and the same rounded magnitudes round alike

  Valid (445ms) (colibri2 3) (cvc4) (split_vc) (depth 1)
1737
let ghost
round_fin_same
(fm: format) (m: mode) (z: bool) (r r': real) : unit
1738
requires { (0.0 <. r /\ 0.0 <. r') \/ (r <. 0.0 /\ r' <. 0.0) }
1739
requires { forall m. round_mag fm m (if 0.0 <. r then r else -. r) =
1740
round_mag fm m (if 0.0 <. r' then r' else -. r') }
1741
ensures { round_fin fm m z r = round_fin fm m z r' }
1742
= {proof…}
1743
if pure { 0.0 <. r } then
1744
assert { round_mag fm m r = round_mag fm m r' }
1745
else begin
1746
let mm = mirror m in
1747
assert { round_mag fm mm (if 0.0 <. r then r else -. r) =
1748
round_mag fm mm (if 0.0 <. r' then r' else -. r') };
1749
assert { round_mag fm mm (-. r) = round_mag fm mm (-. r') }
1750
end
1751
{qed}

The rounding is constant between two multiples of 2^(qmin-1)

The floats and the midpoints of two consecutive floats are multiples of g = 2^(qmin-1): two reals strictly between n g and (n+1) g round to the same float.

vom fm k is the even multiple 2 N of g

  Valid (106ms) (colibri2)
1760
let ghost
vom_cell
(fm: format) (k: int) : int
1761
requires { 0 <= k }
1762
ensures { vom fm k = from_int (2 * result) *. pow2r (qmin fm - 1) }
1763
= let b = binade fm in
1764
binade_ge_2 fm;
1765
pow2r_succ (qmin fm - 1);
1766
let e = div k b in
1767
if e = 0 then begin
1768
assert { vom fm k = from_int (mod k b) *. pow2r (qmin fm) };
1769
mod k b
1770
end else begin
1771
pow2r_add (qmin fm) (e - 1); pow2r_int (e - 1);
1772
assert { 0 < e };
1773
assert { vom fm k = from_int (b + mod k b) *. pow2r (e - 1 + qmin fm) };
1774
assert { vom fm k = from_int ((b + mod k b) * power 2 (e - 1)) *. pow2r (qmin fm) };
1775
(b + mod k b) * power 2 (e - 1)
1776
end

A multiple N g compares with a real of the cell (n g, (n+1) g) as N with n

  Valid (85ms) (colibri2)
1780
let ghost
cell_cmp
(fm: format) (n nn: int) (r: real) : unit
1781
requires { from_int n *. pow2r (qmin fm - 1) <. r <. from_int (n + 1) *. pow2r (qmin fm - 1) }
1782
ensures { from_int nn *. pow2r (qmin fm - 1) <=. r <-> nn <= n }
1783
ensures { from_int nn *. pow2r (qmin fm - 1) <. r <-> nn <= n }
1784
ensures { r <. from_int nn *. pow2r (qmin fm - 1) <-> n < nn }
1785
= {proof…}
1786
let g = pow2r (qmin fm - 1) in
1787
pow2r_pos (qmin fm - 1);
1788
scale_cmp nn n g; scale_cmp n nn g; scale_cmp nn (n + 1) g; scale_cmp (n + 1) nn g
1789
{qed}

The magnitudes of two positive reals of the same cell

  Valid (1.5s) (colibri2)
1792
let ghost
round_mag_gcell
(fm: format) (m: mode) (c: int) (x x': real) : unit
1793
requires { 0 <= c }
1794
requires { from_int c *. pow2r (qmin fm - 1) <. x <. from_int (c + 1) *. pow2r (qmin fm - 1) }
1795
requires { from_int c *. pow2r (qmin fm - 1) <. x' <. from_int (c + 1) *. pow2r (qmin fm - 1) }
1796
ensures { round_mag fm m x = round_mag fm m x' }
1797
= {proof…}
1798
let g = pow2r (qmin fm - 1) in
1799
pow2r_pos (qmin fm - 1);
1800
assert { 0.0 <=. from_int c *. g };
1801
let k = kdn fm x in
1802
let a = vom_cell fm k in
1803
let b = vom_cell fm (k + 1) in
1804
cell_cmp fm c (2 * a) x; cell_cmp fm c (2 * a) x';
1805
cell_cmp fm c (2 * b) x; cell_cmp fm c (2 * b) x';
1806
cell_cmp fm c (a + b) x; cell_cmp fm c (a + b) x';
1807
assert { between fm k x' };
1808
kdn_unique fm k x';
1809
assert { vom fm k <> x /\ vom fm k <> x' };
1810
assert { (vom fm k +. vom fm (k + 1)) /. 2.0 = from_int (a + b) *. g }
1811
{qed}

Two reals of the same cell round to the same float

  Valid (89ms) (colibri2 17) (cvc5 2) (split_vc) (depth 1)
1814
let ghost
round_cell
(fm: format) (m: mode) (z: bool) (n: int) (r r': real) : unit
1815
requires { from_int n *. pow2r (qmin fm - 1) <. r <. from_int (n + 1) *. pow2r (qmin fm - 1) }
1816
requires { from_int n *. pow2r (qmin fm - 1) <. r' <. from_int (n + 1) *. pow2r (qmin fm - 1) }
1817
ensures { round_fin fm m z r = round_fin fm m z r' }
1818
= {proof…}
1819
let g = pow2r (qmin fm - 1) in
1820
pow2r_pos (qmin fm - 1);
1821
if 0 <= n then begin
1822
assert { 0.0 <=. from_int n *. g };
1823
assert { 0.0 <. r /\ 0.0 <. r' };
1824
let lemma all (mm: mode) : unit
1825
ensures { round_mag fm mm r = round_mag fm mm r' }
1826
= round_mag_gcell fm mm n r r' in
1827
round_fin_same fm m z r r'
1828
end else begin
1829
let c = - n - 1 in
1830
assert { from_int (n + 1) *. g <=. 0.0 };
1831
assert { r <. 0.0 /\ r' <. 0.0 };
1832
assert { from_int c *. g = -. (from_int (n + 1) *. g) };
1833
assert { from_int (c + 1) *. g = -. (from_int n *. g) };
1834
let lemma all (mm: mode) : unit
1835
ensures { round_mag fm mm (-. r) = round_mag fm mm (-. r') }
1836
= round_mag_gcell fm mm c (-. r) (-. r') in
1837
round_fin_same fm m z r r'
1838
end
1839
{qed}
1840
Valid (130ms) (colibri2)
1841
let ghost
mul_le_r
(x y c: int) : unit
1842
requires { 0 <= c /\ x <= y }
1843
ensures { x * c <= y * c }
1844
= {proof…} assert { (y - x) * c >= 0 } {qed}
1845
Valid (83ms) (colibri2 8) (cvc5) (split_vc) (depth 1)
1846
let ghost
div_neg
(x y: real) : unit
1847
requires { y <> 0.0 }
1848
ensures { (-. x) /. y = -. (x /. y) }
1849
ensures { x /. (-. y) = -. (x /. y) }
1850
ensures { (-. x) /. (-. y) = x /. y }
1851
= {proof…}
1852
let q = x /. y in
1853
assert { q *. y = x };
1854
assert { q *. (-. y) = -. x };
1855
assert { ((-. x) /. (-. y)) *. (-. y) = -. x };
1856
assert { ((-. x) /. (-. y) -. q) *. (-. y) = 0.0 };
1857
assert { (-. x) /. (-. y) = q }
1858
{qed}

A dyadic number that rounds as (a / b) * 2^e, a, b > 0

  Valid (456ms) (colibri2 41) (cvc4) (cvc5 5) (split_vc 4) (depth 2)
1861
let
div_d
(fm: format) (a b e: int) : dyadic
1862
requires { 0 < a /\ 0 < b }
1863
ensures { 0.0 <. dval result }
1864
ensures { forall m. round_mag fm m (dval result) =
1865
round_mag fm m (from_int a /. from_int b *. pow2r e) }
1866
= let na = numbits a in
1867
let nb = numbits b in
1868
let l = if fm.sb + 1 + nb - na > 0 then fm.sb + 1 + nb - na else 0 in
1869
let num = lsl_int a l in
1870
let q = Zarith.fdiv num b in
1871
let rem = num - q * b in
1872
let w = e - l in
1873
{proof…}
1874
let ghost g = na - 1 + l - nb in
1875
numbits_lsl_lt b; numbits_lsl_le a;
1876
lsl_mul 1 nb; lsl_mul 1 (na - 1); lsl_mul a l;
1877
assert { power 2 (na - 1) <= a /\ b < power 2 nb };
1878
assert { power 2 (na - 1 + l) = power 2 g * power 2 nb };
1879
assert { power 2 (na - 1 + l) = power 2 (na - 1) * power 2 l };
1880
assert { 1 <= na };
1881
assert { 0 <= g };
1882
assert { num = a * power 2 l };
1883
mul_le_r (power 2 (na - 1)) a (power 2 l);
1884
assert { power 2 g * b < power 2 g * power 2 nb };
1885
assert { power 2 g * b < num };
1886
mul_lt_cancel (power 2 g) q b;
1887
assert { power 2 g <= q };
1888
assert { 1 <= power 2 g };
1889
let ghost c = pure { pow2r w } in
1890
let ghost r = pure { from_int a /. from_int b *. pow2r e } in
1891
pow2r_pos w; pow2r_add w l; pow2r_int l;
1892
assert { r = (from_int num /. from_int b) *. c };
1893
assert { from_int num /. from_int b = from_int q +. from_int rem /. from_int b };
1894
assert { 0 <= rem < b };
1895
assert { 0.0 <=. from_int rem /. from_int b <. 1.0 };
1896
assert { r = from_int q *. c +. (from_int rem /. from_int b) *. c };
1897
pow2r_add w g; pow2r_int g;
1898
assert { pow2r (g + w) <=. from_int q *. c by
1899
pow2r (g + w) = from_int (power 2 g) *. c };
1900
{qed}
1901
if rem = 0 then begin
1902
{proof…} assert { r = from_int q *. c }; {qed}
1903
{ dm = q; de = w }
1904
end else begin
1905
{proof…}
1906
assert { 0.0 <. from_int rem /. from_int b };
1907
assert { (from_int rem /. from_int b) *. c <. c };
1908
assert { from_int (q + 1) *. c = from_int q *. c +. c };
1909
assert { from_int q *. c <. r <. from_int (q + 1) *. c };
1910
pow2r_succ (w - 1);
1911
assert { pow2r (w - 1) = 0.5 *. c };
1912
assert { from_int (2 * q + 1) = 2.0 *. from_int q +. 1.0 };
1913
assert { from_int (2 * q + 1) *. pow2r (w - 1) =
1914
(2.0 *. from_int q +. 1.0) *. (0.5 *. c) };
1915
assert { from_int (2 * q + 1) *. pow2r (w - 1) = (from_int q +. 0.5) *. c };
1916
round_mag_cell fm r (from_int (2 * q + 1) *. pow2r (w - 1)) q w (g + w);
1917
{qed}
1918
{ dm = 2 * q + 1; de = w - 1 }
1919
end

Division

1923
function
fp_div
(m: mode) (x y: t) : t =
1924
if is_nan x \/ is_nan y \/ (is_zero x /\ is_zero y)
1925
\/ (is_infinity x /\ is_infinity y) then not_a_number x.fmt
1926
else if is_zero y then
1927
(if mul_zneg x y then minus_infinity x.fmt else plus_infinity x.fmt)
1928
else round_f x.fmt m (mul_zneg x y) (ediv (ext x) (ext y))
1929
Valid (53ms) (colibri2)
1930
let ghost
round_zero
(fm: format) (m: mode) (z: bool) : unit
1931
ensures { round_fin fm m z 0.0 = mk fm (Finite z 0) }
1932
= {proof…} vom_zero fm; round_mag_exact fm m 0 {qed}
1933
Valid (1.3s) (colibri2 49) (cvc4) (cvc5 3) (split_vc 9) (depth 3)
1934
let
div
(m: mode) (x y: t) : t
1935
ensures { x.fmt = y.fmt -> result = fp_div m x y }
1936
= let fm = x.fmt in
1937
if not (eq_format fm y.fmt) then mk fm NaN else
1938
let z = if is_positive x then not (is_positive y) else is_positive y in
1939
let inf = if z then MinusInf else PlusInf in
1940
{proof…} finite_sign x; finite_sign y; round_zero fm m z; {qed}
1941
match x.value, y.value with
1942
| NaN, _ | _, NaN -> mk fm NaN
1943
| (PlusInf | MinusInf), (PlusInf | MinusInf) -> mk fm NaN
1944
| (PlusInf | MinusInf), Finite _ _ ->
1945
{proof…} assert { mk fm inf = fp_div m x y }; {qed}
1946
mk fm inf
1947
| Finite _ _, (PlusInf | MinusInf) ->
1948
{proof…} assert { mk fm (Finite z 0) = fp_div m x y }; {qed}
1949
mk fm (Finite z 0)
1950
| Finite _ kx, Finite _ ky ->
1951
if ky = 0 then (if kx = 0 then mk fm NaN else mk fm inf)
1952
else if kx = 0 then begin
1953
{proof…} assert { mk fm (Finite z 0) = fp_div m x y }; {qed}
1954
mk fm (Finite z 0)
1955
end else begin
1956
let dx = to_dyadic x in
1957
let dy = to_dyadic y in
1958
let a = if dx.dm < 0 then - dx.dm else dx.dm in
1959
let b = if dy.dm < 0 then - dy.dm else dy.dm in
1960
{proof…}
1961
pow2r_pos dx.de; pow2r_pos dy.de;
1962
assert { dx.dm <> 0 /\ dy.dm <> 0 };
1963
let ghost r = pure { to_real x *. (1.0 /. to_real y) } in
1964
let ghost e = dx.de - dy.de in
1965
pow2r_add e dy.de; pow2r_pos e;
1966
let ghost qq = pure { from_int dx.dm /. from_int dy.dm } in
1967
assert { r = qq *. pow2r e by
1968
to_real x = from_int dx.dm *. (pow2r e *. pow2r dy.de)
1969
/\ to_real y = from_int dy.dm *. pow2r dy.de };
1970
div_neg (from_int dx.dm) (from_int dy.dm);
1971
assert { from_int (- dx.dm) = -. from_int dx.dm };
1972
assert { from_int (- dy.dm) = -. from_int dy.dm };
1973
if dx.dm > 0 then begin
1974
if dy.dm > 0 then assert { from_int a /. from_int b = qq /\ 0.0 <. qq }
1975
else assert { from_int a /. from_int b = -. qq /\ qq <. 0.0
1976
by from_int b = -. from_int dy.dm }
1977
end else begin
1978
if dy.dm > 0 then assert { from_int a /. from_int b = -. qq /\ qq <. 0.0
1979
by from_int a = -. from_int dx.dm }
1980
else assert { from_int a /. from_int b = qq /\ 0.0 <. qq
1981
by from_int a = -. from_int dx.dm /\ from_int b = -. from_int dy.dm }
1982
end;
1983
assert { dx.dm > 0 <-> is_positive x };
1984
assert { dy.dm > 0 <-> is_positive y };
1985
assert { not z -> 0.0 <. r /\ r = from_int a /. from_int b *. pow2r e };
1986
assert { z -> r <. 0.0 /\ -. r = from_int a /. from_int b *. pow2r e };
1987
{qed}
1988
let d = div_d fm a b (dx.de - dy.de) in
1989
let sd = if z then { dm = - d.dm; de = d.de } else d in
1990
{proof…}
1991
assert { z -> dval sd = -. dval d };
1992
round_fin_same fm m z r (dval sd);
1993
assert { ediv (ext x) (ext y) = Fin r };
1994
assert { fp_div m x y = round_f fm m z (Fin r) };
1995
assert { round_f fm m z (Fin (dval sd)) = fp_div m x y };
1996
{qed}
1997
round_d fm m z sd
1998
end
1999
end

Square root

  Valid (130ms) (colibri2)
2003
let ghost
mul_lt_pos
(x y c: real) : unit
2004
requires { 0.0 <. c /\ x <. y }
2005
ensures { x *. c <. y *. c }
2006
= {proof…} assert { 0.0 <. (y -. x) *. c } {qed}

A dyadic number that rounds as sqrt (a * 2^e), a > 0

  Valid (899ms) (colibri2 60) (cvc5 8) (split_vc 15) (depth 5)
2009
let
sqrt_d
(fm: format) (a e: int) : dyadic
2010
requires { 0 < a }
2011
ensures { 0.0 <. dval result }
2012
ensures { forall m. round_mag fm m (dval result) =
2013
round_mag fm m (S.sqrt (from_int a *. pow2r e)) }
2014
= let ev = even e in
2015
let a1 = if ev then a else 2 * a in
2016
let e1 = if ev then e else e - 1 in
2017
let h = asr_int e1 1 in
2018
let n1 = numbits a1 in
2019
let l0 = fm.sb + 2 - asr_int n1 1 in
2020
let l = if l0 > 0 then l0 else 0 in
2021
let num = lsl_int a1 (2 * l) in
2022
let (s, rem) = Zarith.sqrt_rem num in
2023
let w = h - l in
2024
{proof…}
2025
asr_div e1 1; asr_div n1 1;
2026
assert { e1 = 2 * h };
2027
pow2r_succ e1;
2028
assert { from_int a *. pow2r e = from_int a1 *. pow2r e1 };
2029
numbits_lsl_le a1; lsl_mul 1 (n1 - 1); lsl_mul a1 (2 * l);
2030
assert { 1 <= n1 };
2031
let ghost g = fm.sb + 1 in
2032
assert { 2 * g <= n1 - 1 + 2 * l };
2033
assert { power 2 (n1 - 1 + 2 * l) = power 2 (n1 - 1) * power 2 (2 * l) };
2034
mul_le_r (power 2 (n1 - 1)) a1 (power 2 (2 * l));
2035
assert { power 2 (2 * g) <= power 2 (n1 - 1 + 2 * l) };
2036
assert { power 2 (2 * g) = power 2 g * power 2 g };
2037
assert { power 2 g * power 2 g <= num };
2038
if s < power 2 g then begin
2039
mul_le_r (s + 1) (power 2 g) (s + 1);
2040
mul_le_r (s + 1) (power 2 g) (power 2 g);
2041
assert { (s + 1) * power 2 g = power 2 g * (s + 1) };
2042
assert { false }
2043
end;
2044
assert { power 2 g <= s };
2045
let ghost c = pure { pow2r w } in
2046
pow2r_pos w;
2047
pow2r_add (2 * w) (2 * l); pow2r_int (2 * l); pow2r_add w w;
2048
assert { 2 * w + 2 * l = e1 };
2049
assert { from_int a1 *. pow2r e1 = from_int num *. (c *. c) };
2050
let ghost r = pure { S.sqrt (from_int a *. pow2r e) } in
2051
assert { r = S.sqrt (from_int num) *. c by
2052
S.sqrt (from_int num *. (c *. c)) = S.sqrt (from_int num) *. S.sqrt (c *. c)
2053
/\ S.sqrt (c *. c) = c };
2054
assert { from_int s <=. S.sqrt (from_int num) by
2055
S.sqrt (from_int (s * s)) = from_int s
2056
/\ S.sqrt (from_int (s * s)) <=. S.sqrt (from_int num) };
2057
assert { S.sqrt (from_int num) <. from_int (s + 1) by
2058
S.sqrt (from_int ((s + 1) * (s + 1))) = from_int (s + 1)
2059
/\ S.sqrt (from_int num) <=. S.sqrt (from_int ((s + 1) * (s + 1)))
2060
/\ (S.sqrt (from_int num) = from_int (s + 1) ->
2061
from_int num = from_int (s + 1) *. from_int (s + 1)
2062
by from_int num = S.sqr (S.sqrt (from_int num))) };
2063
scale_cmp 0 s c;
2064
pow2r_add w g; pow2r_int g;
2065
assert { pow2r (g + w) = from_int (power 2 g) *. c };
2066
scale_cmp (power 2 g) s c;
2067
assert { pow2r (g + w) <=. r };
2068
{qed}
2069
if rem = 0 then begin
2070
{proof…}
2071
assert { S.sqrt (from_int num) = from_int s by
2072
from_int num = from_int s *. from_int s };
2073
{qed}
2074
{ dm = s; de = w }
2075
end else begin
2076
{proof…}
2077
assert { from_int s <. S.sqrt (from_int num) by
2078
from_int s = S.sqrt (from_int num) ->
2079
from_int num = from_int s *. from_int s
2080
by from_int num = S.sqr (S.sqrt (from_int num)) };
2081
mul_lt_pos (from_int s) (S.sqrt (from_int num)) c;
2082
mul_lt_pos (S.sqrt (from_int num)) (from_int (s + 1)) c;
2083
assert { from_int s *. c <. r <. from_int (s + 1) *. c };
2084
pow2r_succ (w - 1);
2085
assert { pow2r (w - 1) = 0.5 *. c };
2086
assert { from_int (2 * s + 1) *. pow2r (w - 1) =
2087
(2.0 *. from_int s +. 1.0) *. (0.5 *. c) };
2088
assert { from_int (2 * s + 1) *. pow2r (w - 1) = (from_int s +. 0.5) *. c };
2089
assert { from_int s *. c <. (from_int s +. 0.5) *. c <. from_int (s + 1) *. c };
2090
round_mag_cell fm r (from_int (2 * s + 1) *. pow2r (w - 1)) s w (g + w);
2091
{qed}
2092
{ dm = 2 * s + 1; de = w - 1 }
2093
end
2094
2095
function
fp_sqrt
(m: mode) (x: t) : t =
2096
if is_nan x \/ (not is_positive x /\ not is_zero x) then not_a_number x.fmt
2097
else round_f x.fmt m (if is_positive x then false else true) (esqrt (ext x))
2098
Valid (324ms) (colibri2)
2099
let
sqrt
(m: mode) (x: t) : t
2100
ensures { result = fp_sqrt m x }
2101
= let fm = x.fmt in
2102
{proof…} finite_sign x; {qed}
2103
match x.value with
2104
| NaN | MinusInf -> mk fm NaN
2105
| PlusInf -> {proof…} t_ext x (fp_sqrt m x); {qed} x
2106
| Finite ng k ->
2107
if k = 0 then begin
2108
{proof…}
2109
assert { S.sqrt (0.0 *. 0.0) = 0.0 };
2110
round_zero fm m ng;
2111
t_ext x (fp_sqrt m x);
2112
{qed}
2113
x
2114
end else if ng then mk fm NaN
2115
else begin
2116
let d = to_dyadic x in
2117
{proof…} pow2r_pos d.de; assert { 0 < d.dm }; {qed}
2118
let sd = sqrt_d fm d.dm d.de in
2119
{proof…}
2120
assert { 0.0 <. S.sqrt (to_real x) by
2121
0.0 <=. S.sqrt (to_real x) /\
2122
(S.sqrt (to_real x) = 0.0 -> to_real x = S.sqr (S.sqrt (to_real x)) = 0.0) };
2123
round_fin_same fm m false (S.sqrt (to_real x)) (dval sd);
2124
{qed}
2125
round_d fm m false sd
2126
end
2127
end

The index, the successor, the predecessor and the middle

The index, and 0 for NaN

  Valid (57ms) (colibri2)
2132
let
index_t
(x: t) : int
2133
ensures { not is_nan x -> result = index x }
2134
= if is_nan x then 0 else index_p x
2135
Valid (144ms) (colibri2)
2136
let
of_index_p
(fm: format) (i: int) : t
2137
ensures { result = of_index fm i }
2138
= let nb = nb_sign_p fm in
2139
if 0 <= i && i < nb - 1 then mk fm (Finite false i)
2140
else if - nb < i && i < 0 then mk fm (Finite true (-1 - i))
2141
else if i = nb - 1 then mk fm PlusInf
2142
else if i = - nb then mk fm MinusInf
2143
else mk fm NaN
2144
2145
function
succ_dz
(x: t) : t = of_index x.fmt (index x + 1)
2146
function
pred_dz
(x: t) : t = of_index x.fmt (index x - 1)

Total: NaN and +inf are returned unchanged

  Valid (77ms) (colibri2)
2149
let
succ_diff_zero
(x: t) : t
2150
ensures { not is_nan x /\ not is_plus_infinity x -> result = succ_dz x }
2151
= match x.value with
2152
| NaN | PlusInf -> x
2153
| _ -> of_index_p x.fmt (index_p x + 1)
2154
end

Total: NaN and –inf are returned unchanged

  Valid (76ms) (colibri2)
2157
let
pred_diff_zero
(x: t) : t
2158
ensures { not is_nan x /\ not is_minus_infinity x -> result = pred_dz x }
2159
= match x.value with
2160
| NaN | MinusInf -> x
2161
| _ -> of_index_p x.fmt (index_p x - 1)
2162
end

Total: NaN when an argument is NaN or the formats differ

  Valid (80ms) (colibri2)
2165
let
mid_index
(x y: t) : t
2166
ensures { not is_nan x /\ not is_nan y /\ x.fmt = y.fmt ->
2167
result = of_index x.fmt (div (index x + index y) 2) }
2168
= if is_nan x || is_nan y || not (eq_format x.fmt y.fmt) then mk x.fmt NaN
2169
else begin
2170
{proof…} asr_div (index_p x + index_p y) 1; {qed}
2171
of_index_p x.fmt (asr_int (index_p x + index_p y) 1)
2172
end

The rounding of a rational

  Valid (88ms) (colibri2 14) (cvc5) (split_vc 2) (depth 2)
2176
let
round_q
(fm: format) (m: mode) (zneg: bool) (n d: int) : t
2177
ensures { 0 < d -> result = round_f fm m zneg (Fin (from_int n /. from_int d)) }
2178
= if d <= 0 then mk fm NaN
2179
else if n = 0 then begin
2180
{proof…} round_zero fm m zneg; assert { from_int n /. from_int d = 0.0 }; {qed}
2181
mk fm (Finite zneg 0)
2182
end else begin
2183
let a = if n < 0 then - n else n in
2184
let dd = div_d fm a d 0 in
2185
let sd = if n < 0 then { dm = - dd.dm; de = dd.de } else dd in
2186
{proof…}
2187
pow2r_int 0;
2188
let ghost r = pure { from_int n /. from_int d } in
2189
div_neg (from_int n) (from_int d);
2190
assert { from_int (- n) = -. from_int n };
2191
assert { from_int a /. from_int d *. pow2r 0 = from_int a /. from_int d };
2192
assert { 0 < n -> 0.0 <. r /\ r = from_int a /. from_int d };
2193
assert { n < 0 -> r <. 0.0 /\ -. r = from_int a /. from_int d };
2194
assert { n < 0 -> dval sd = -. dval dd };
2195
round_fin_same fm m zneg r (dval sd);
2196
{qed}
2197
round_d fm m zneg sd
2198
end

The rounding of a real between two close dyadic numbers

The rounding of every real strictly between n/2^k and (n+1)/2^k, when 2^-k <= 2^(qmin-1): the rounding of their midpoint (no float nor midpoint of two floats is strictly between them, round_cell)

  Valid (531ms) (colibri2 33) (cvc4) (cvc5 6) (split_vc 4) (depth 2)
2205
let
round_between
(fm: format) (m: mode) (n k: int) : t
2206
requires { 1 - qmin fm <= k }
2207
ensures { forall r. from_int n /. from_int (power 2 k) <. r <. from_int (n + 1) /. from_int (power 2 k) ->
2208
result = round_f fm m (r <. 0.0) (Fin r) }
2209
= let d = lsl_int 1 (k + 1) in
2210
let n2 = 2 * n + 1 in
2211
{proof…}
2212
lsl_mul 1 (k + 1);
2213
let ghost j = pure { k - (1 - qmin fm) } in
2214
let ghost e = pure { pow2r (- (k + 1)) } in
2215
let ghost g = pure { pow2r (qmin fm - 1) } in
2216
pow2r_pos (- (k + 1)); pow2r_int j; pow2r_int (j + 1);
2217
assert { 0 < power 2 k /\ power 2 (k + 1) = 2 * power 2 k /\ d = power 2 (k + 1) };
2218
assert { e = 1.0 /. from_int d };
2219
pow2r_succ (- (k + 1));
2220
assert { pow2r (- k) = 1.0 /. from_int (power 2 k) };
2221
assert { pow2r (- k) = 2.0 *. e };
2222
pow2r_add (j + 1) (- (k + 1));
2223
assert { j + 1 + (- (k + 1)) = qmin fm - 1 };
2224
assert { g = from_int (power 2 (j + 1)) *. e };
2225
let ghost c = pure { EuclideanDivision.div n (power 2 j) } in
2226
assert { 0 < power 2 j /\ power 2 (j + 1) = 2 * power 2 j };
2227
assert { n = c * power 2 j + EuclideanDivision.mod n (power 2 j) };
2228
assert { 0 <= EuclideanDivision.mod n (power 2 j) < power 2 j };
2229
assert { c * power 2 j <= n < (c + 1) * power 2 j };
2230
assert { c * power 2 (j + 1) = 2 * (c * power 2 j) };
2231
assert { (c + 1) * power 2 (j + 1) = 2 * ((c + 1) * power 2 j) };
2232
assert { c * power 2 (j + 1) <= 2 * n /\ 2 * n + 2 <= (c + 1) * power 2 (j + 1) };
2233
let ghost lo = pure { from_int n /. from_int (power 2 k) } in
2234
let ghost hi = pure { from_int (n + 1) /. from_int (power 2 k) } in
2235
let ghost r0 = pure { from_int n2 /. from_int d } in
2236
assert { lo = from_int n *. pow2r (- k) };
2237
assert { hi = from_int (n + 1) *. pow2r (- k) };
2238
assert { lo = from_int (2 * n) *. e };
2239
assert { hi = from_int (2 * n + 2) *. e };
2240
assert { r0 = from_int n2 *. e };
2241
scale_cmp (2 * n) n2 e; scale_cmp n2 (2 * n + 2) e;
2242
assert { from_int c *. g = from_int (c * power 2 (j + 1)) *. e };
2243
assert { from_int (c + 1) *. g = from_int ((c + 1) * power 2 (j + 1)) *. e };
2244
scale_cmp (c * power 2 (j + 1)) (2 * n) e;
2245
scale_cmp (2 * n + 2) ((c + 1) * power 2 (j + 1)) e;
2246
assert { lo <. r0 <. hi };
2247
assert { from_int c *. g <=. lo };
2248
assert { hi <=. from_int (c + 1) *. g };
2249
scale_cmp n2 0 e;
2250
assert { n2 < 0 <-> r0 <. 0.0 };
2251
let lemma pt (r: real) : unit
2252
requires { lo <. r <. hi }
2253
ensures { round_fin fm m (n2 < 0) r0 = round_f fm m (r <. 0.0) (Fin r) }
2254
= scale_cmp n 0 e; scale_cmp 0 (2 * n + 2) e;
2255
assert { (r <. 0.0) <-> n2 < 0 };
2256
round_cell fm m (n2 < 0) c r0 r in
2257
{qed}
2258
round_q fm m (n2 < 0) n2 d

The rounding of a real in a bracket

Every real r of [n1/d1, n2/d2] rounds to x (as to_fp of a real in SMT–LIB: a zero result is –0 when r < 0) when the two ends round to x. None when they round to different floats, or a denominator is not positive. F.of_a narrows the bracket of an algebraic number until it gives a float.

  Valid (354ms) (colibri2 15) (split_vc) (depth 1)
2267
let
round_bracket
(fm: format) (m: mode) (n1 d1 n2 d2: int) : option t
2268
ensures { match result with
2269
| None -> d1 <= 0 \/ d2 <= 0 \/
2270
round_f fm m (n1 < 0) (Fin (from_int n1 /. from_int d1))
2271
<> round_f fm m (n2 < 0) (Fin (from_int n2 /. from_int d2))
2272
| Some x -> forall r. from_int n1 /. from_int d1 <=. r <=. from_int n2 /. from_int d2 ->
2273
x = round_f fm m (r <. 0.0) (Fin r)
2274
end }
2275
= if d1 <= 0 || d2 <= 0 then None
2276
else begin
2277
let x1 = round_q fm m (n1 < 0) n1 d1 in
2278
let x2 = round_q fm m (n2 < 0) n2 d2 in
2279
{proof…}
2280
let ghost r1 = pure { from_int n1 /. from_int d1 } in
2281
let ghost r2 = pure { from_int n2 /. from_int d2 } in
2282
round_fin_facts fm m (n1 < 0) r1; round_fin_facts fm m (n2 < 0) r2;
2283
{qed}
2284
if le_diff_zero x1 x2 && le_diff_zero x2 x1 then begin
2285
{proof…}
2286
assert { 0.0 <. from_int d1 /\ 0.0 <. from_int d2 };
2287
assert { n1 < 0 -> r1 <. 0.0 };
2288
assert { 0 <= n1 -> 0.0 <=. r1 };
2289
assert { n2 < 0 -> r2 <. 0.0 };
2290
assert { 0 <= n2 -> 0.0 <=. r2 };
2291
assert { index x1 = index x2 };
2292
let lemma pt (r: real) : unit
2293
requires { r1 <=. r <=. r2 }
2294
ensures { x1 = round_f fm m (r <. 0.0) (Fin r) }
2295
= let y = round_fin fm m (r <. 0.0) r in
2296
round_fin_facts fm m (r <. 0.0) r;
2297
round_fin_le fm m (n1 < 0) (r <. 0.0) r1 r;
2298
round_fin_le fm m (r <. 0.0) (n2 < 0) r r2;
2299
assert { index y = index x1 };
2300
index_inj x1; index_inj y in
2301
{qed}
2302
Some x1
2303
end else None
2304
end

The fused multiply–add

The sign of a zero result: the sign of the exact result when it is not zero, else the rule of the addition with the sign of the product (IEEE 754 §6.3)

2311
function
fma_zneg
(m: mode) (x y z: t) (e: ereal) : bool =
2312
match e with
2313
| Fin r ->
2314
if r <. 0.0 then true else if 0.0 <. r then false
2315
else if (not mul_zneg x y) <-> is_positive z then mul_zneg x y
2316
else (if m = RTN then true else false)
2317
| _ -> false
2318
end
2319
2320
function
fp_fma
(m: mode) (x y z: t) : t =
2321
if is_nan x \/ is_nan y \/ is_nan z \/ (is_zero x /\ is_infinity y)
2322
\/ (is_infinity x /\ is_zero y)
2323
\/ opposite (emul (ext x) (ext y)) (ext z) then not_a_number x.fmt
2324
else
2325
let e = eadd (emul (ext x) (ext y)) (ext z) in
2326
round_f x.fmt m (fma_zneg m x y z e) e
2327
Valid (3.2s) (colibri2 18) (cvc4 2) (cvc5 3) (split_vc 5) (depth 5)
2328
let
fma
(m: mode) (x y z: t) : t
2329
ensures { x.fmt = y.fmt /\ x.fmt = z.fmt -> result = fp_fma m x y z }
2330
= let fm = x.fmt in
2331
if not (eq_format fm y.fmt && eq_format fm z.fmt) then mk fm NaN
2332
else if is_nan x || is_nan y || is_nan z then mk fm NaN
2333
else begin
2334
{proof…} finite_sign x; finite_sign y; finite_sign z; {qed}
2335
let pz = if is_positive x then not (is_positive y) else is_positive y in
2336
match x.value, y.value with
2337
| Finite _ _, Finite _ _ ->
2338
match z.value with
2339
| PlusInf | MinusInf -> z
2340
| _ ->
2341
let d = dadd (dmul (to_dyadic x) (to_dyadic y)) (to_dyadic z) in
2342
let rtn = match m with RTN -> true | _ -> false end in
2343
let same = if pz then not (is_positive z) else is_positive z in
2344
let zn = if d.dm < 0 then true else if d.dm > 0 then false
2345
else if same then pz else rtn in
2346
{proof…}
2347
pow2r_pos d.de;
2348
scale_cmp d.dm 0 (pow2r d.de); scale_cmp 0 d.dm (pow2r d.de);
2349
assert { zn = fma_zneg m x y z (Fin (dval d)) };
2350
{qed}
2351
round_d fm m zn d
2352
end
2353
| _ ->
2354
if is_zero x || is_zero y then mk fm NaN
2355
else begin
2356
let inf = if pz then MinusInf else PlusInf in
2357
match z.value with
2358
| PlusInf -> if pz then mk fm NaN else z
2359
| MinusInf -> if pz then z else mk fm NaN
2360
| _ -> mk fm inf
2361
end
2362
end
2363
end
2364
end

The next float up and down (IEEE 754 nextUp, nextDown)

2368
function
next_up_index
(i: int) : int = if i = -1 then 1 else i + 1
2369
function
next_down_index
(i: int) : int = if i = 0 then -2 else i - 1

Total: NaN and +inf are returned unchanged

  Valid (62ms) (colibri2)
2372
let
next_up
(x: t) : t
2373
ensures { not is_nan x /\ not is_plus_infinity x ->
2374
result = of_index x.fmt (next_up_index (index x)) }
2375
ensures { is_nan x \/ is_plus_infinity x -> result = x }
2376
= match x.value with
2377
| NaN | PlusInf -> x
2378
| _ -> let i = index_p x in of_index_p x.fmt (if i = -1 then 1 else i + 1)
2379
end

Total: NaN and –inf are returned unchanged

  Valid (57ms) (colibri2)
2382
let
next_down
(x: t) : t
2383
ensures { not is_nan x /\ not is_minus_infinity x ->
2384
result = of_index x.fmt (next_down_index (index x)) }
2385
ensures { is_nan x \/ is_minus_infinity x -> result = x }
2386
= match x.value with
2387
| NaN | MinusInf -> x
2388
| _ -> let i = index_p x in of_index_p x.fmt (if i = 0 then -2 else i - 1)
2389
end

The finite floats above or below a real

f is the rounding of a real r up (float_lo) or down (float_hi), with a zero result negative when r < 0; exact tells whether f is finite of value r. The result is the least (resp. greatest) float v with r <= v (resp. v <= r), or r < v (resp. v < r) when strict, among the finite floats: –0 (resp. +0) when r = 0, the next float when r is a float and strict, else f.

  Valid (1.4s) (colibri2 14) (cvc4 2) (cvc5 2) (split_vc) (depth 1)
2399
let
float_lo
(f: t) (strict exact: bool) : t
2400
ensures { result.fmt = f.fmt }
2401
ensures { forall r. f = round_f f.fmt RTP (r <. 0.0) (Fin r) ->
2402
(exact <-> is_finite f /\ to_real f = r) ->
2403
forall v. v.fmt = f.fmt -> is_finite v ->
2404
(if strict then r <. to_real v else r <=. to_real v) -> le_dz result v }
2405
= let g = if exact && is_zero f then mk f.fmt (Finite true 0) else f in
2406
let res = if exact && strict then next_up g else g in
2407
{proof…}
2408
let lemma pt (r: real) (v: t) : unit
2409
requires { f = round_f f.fmt RTP (r <. 0.0) (Fin r) }
2410
requires { exact <-> is_finite f /\ to_real f = r }
2411
requires { v.fmt = f.fmt /\ is_finite v }
2412
requires { if strict then r <. to_real v else r <=. to_real v }
2413
ensures { le_dz res v }
2414
= let fm = f.fmt in
2415
nb_sign_ge fm;
2416
round_fin_facts fm RTP (r <. 0.0) r;
2417
round_fin_up fm (r <. 0.0) r;
2418
if exact then begin
2419
assert { is_finite g /\ g.fmt = fm /\ to_real g = r };
2420
if strict then begin
2421
if pure { index v <= index g } then begin
2422
ext_le v g; absurd
2423
end;
2424
assert { index g < index v };
2425
if pure { index g = -1 } then begin
2426
if pure { index v = 0 } then begin
2427
assert { is_zero v }; vom_zero fm; absurd
2428
end
2429
end;
2430
of_index_range fm (next_up_index (index g))
2431
end else begin
2432
if pure { index v < index g } then begin
2433
if pure { is_zero v /\ is_zero g } then absurd;
2434
ext_lt v g; absurd
2435
end
2436
end
2437
end else begin
2438
round_f_exact RTP v;
2439
let zv = if is_positive v then false else true in
2440
if pure { is_zero f /\ is_zero v } then begin
2441
vom_zero fm;
2442
assert { to_real f = 0.0 /\ r <> 0.0 /\ r <. 0.0 }
2443
end;
2444
round_fin_le fm RTP (r <. 0.0) zv r (to_real v)
2445
end in
2446
{qed}
2447
res
2448
Valid (1.2s) (colibri2 14) (cvc4 2) (cvc5 2) (split_vc) (depth 1)
2449
let
float_hi
(f: t) (strict exact: bool) : t
2450
ensures { result.fmt = f.fmt }
2451
ensures { forall r. f = round_f f.fmt RTN (r <. 0.0) (Fin r) ->
2452
(exact <-> is_finite f /\ to_real f = r) ->
2453
forall v. v.fmt = f.fmt -> is_finite v ->
2454
(if strict then to_real v <. r else to_real v <=. r) -> le_dz v result }
2455
= let g = if exact && is_zero f then mk f.fmt (Finite false 0) else f in
2456
let res = if exact && strict then next_down g else g in
2457
{proof…}
2458
let lemma pt (r: real) (v: t) : unit
2459
requires { f = round_f f.fmt RTN (r <. 0.0) (Fin r) }
2460
requires { exact <-> is_finite f /\ to_real f = r }
2461
requires { v.fmt = f.fmt /\ is_finite v }
2462
requires { if strict then to_real v <. r else to_real v <=. r }
2463
ensures { le_dz v res }
2464
= let fm = f.fmt in
2465
nb_sign_ge fm;
2466
round_fin_facts fm RTN (r <. 0.0) r;
2467
round_fin_down fm (r <. 0.0) r;
2468
if exact then begin
2469
assert { is_finite g /\ g.fmt = fm /\ to_real g = r };
2470
if strict then begin
2471
if pure { index g <= index v } then begin
2472
ext_le g v; absurd
2473
end;
2474
assert { index v < index g };
2475
if pure { index g = 0 } then begin
2476
if pure { index v = -1 } then begin
2477
assert { is_zero v }; vom_zero fm; absurd
2478
end
2479
end;
2480
of_index_range fm (next_down_index (index g))
2481
end else begin
2482
if pure { index g < index v } then begin
2483
if pure { is_zero v /\ is_zero g } then absurd;
2484
ext_lt g v; absurd
2485
end
2486
end
2487
end else begin
2488
round_f_exact RTN v;
2489
let zv = if is_positive v then false else true in
2490
if pure { is_zero f /\ is_zero v } then begin
2491
vom_zero fm;
2492
assert { to_real f = 0.0 /\ r <> 0.0 /\ 0.0 <. r }
2493
end;
2494
round_fin_le fm RTN zv (r <. 0.0) (to_real v) r
2495
end in
2496
{qed}
2497
res
2498
end