Common — library colibrilib.stdq — module PowRound

The powers and the roundings to a smaller number

655
module PowRound
656
use int.Int
657
use int.Power as IP
658
use real.RealInfix
659
use real.FromInt
660
use real.PowerInt as RP
661
use mach.int.Int63
662
use colibrilib.zarith.Z as Z
663
use colibrilib.zarith.Q as Q
664
use colibrilib.zarith.Zbit as Zbit
665
use colibrilib.zbit.ZbitInt
666
use int.EuclideanDivision as E
667
use StdQ'impl
668
use colibrilib.spec.Value
669
Valid (175ms) (colibri2)
670
let rec ghost
from_int_power
(a:int) (n:int) : unit
671
requires { 0 <= n }
672
ensures { from_int (IP.power a n) = RP.power (from_int a) n }
673
variant { n }
674
= if n > 0 then begin
675
from_int_power a (n - 1);
676
assert { IP.power a n = a * IP.power a (n - 1) };
677
assert { RP.power (from_int a) n = from_int a *. RP.power (from_int a) (n - 1) }
678
end
679
Valid (352ms) (colibri2)
680
let rec ghost
power_div
(x y:real) (n:int) : unit
681
requires { 0 <= n }
682
requires { y <> 0. }
683
ensures { RP.power (x /. y) n = RP.power x n /. RP.power y n }
684
ensures { RP.power y n <> 0. }
685
variant { n }
686
= if n > 0 then begin
687
power_div x y (n - 1);
688
assert { RP.power (x /. y) n = (x /. y) *. RP.power (x /. y) (n - 1) };
689
assert { RP.power x n = x *. RP.power x (n - 1) };
690
assert { RP.power y n = y *. RP.power y (n - 1) }
691
end

The power q^n (Std.Q.pow)

  Valid (101ms) (colibri2 23) (split_vc) (depth 1)
694
let
pow
(q:Q.t) (n:int63) : Q.t
695
requires { 0 <= n \/ Q.real q <> 0. }
696
requires { -0x4000000000000000 < n }
697
ensures { value1 Q.real (fun x -> if 0 <= n then RP.power x n else 1. /. RP.power x (- n)) q result }
698
= let ghost x = from_int q.Q.num in
699
let ghost y = from_int q.Q.den in
700
if n < 0 then begin
701
let m = - n in
702
assert { q.Q.num <> 0 };
703
let a = Z.pow q.Q.den m in
704
let b = Z.pow q.Q.num m in
705
from_int_power q.Q.den (to_int m);
706
from_int_power q.Q.num (to_int m);
707
power_div x y (to_int m);
708
power_div y x (to_int m);
709
assert { RP.power x m <> 0. by x <> 0. };
710
assert { b <> 0 by from_int b = RP.power x m };
711
let r = Q.make a b in
712
assert { RP.power (y /. x) m = 1. /. RP.power (x /. y) m
713
by RP.power (y /. x) m = RP.power y m /. RP.power x m
714
/\ RP.power (x /. y) m = RP.power x m /. RP.power y m
715
/\ RP.power y m <> 0. };
716
r
717
end else begin
718
let a = Z.pow q.Q.num n in
719
let b = Z.pow q.Q.den n in
720
from_int_power q.Q.num (to_int n);
721
from_int_power q.Q.den (to_int n);
722
power_div x y (to_int n);
723
assert { b <> 0 by from_int b = RP.power y n };
724
Q.make a b
725
end

A positive integer with fewer bits than den (Std.Q.smaller_den); the test 0 < r never fails, it gives the positivity without the bits

  Valid (99ms) (colibri2)
729
let
smaller_den
(max_size_bit:int) (den:int) : int
730
requires { 0 < den }
731
ensures { 0 < result }
732
= let s = Zbit.numbits den in
733
let remaining =
734
if s > max_size_bit then E.div max_size_bit 4 else E.div s 4 in
735
if remaining = 0 then 1
736
else
737
let r = ZbitInt.asr_int den (s - remaining) in
738
if r > 0 then r else 1

A number below q with a smaller denominator (Std.Q.round_down_to_small_number when q is big)

  Valid (393ms) (colibri2 4) (cvc5) (split_vc) (depth 1)
742
let
round_down_to_small
(max_size_bit:int) (q:Q.t) : Q.t
743
ensures { Q.real result <=. Q.real q }
744
= let d = smaller_den max_size_bit q.Q.den in
745
assert { Gcd.gcd 1 d = 1 by D.divides (Gcd.gcd 1 d) 1 /\ Gcd.gcd 1 d <> 0 };
746
round_down_to q (Q.make_exact 1 d)
747
Valid (391ms) (colibri2 4) (cvc5) (split_vc) (depth 1)
748
let
round_up_to_small
(max_size_bit:int) (q:Q.t) : Q.t
749
ensures { Q.real q <=. Q.real result }
750
= let d = smaller_den max_size_bit q.Q.den in
751
assert { Gcd.gcd 1 d = 1 by D.divides (Gcd.gcd 1 d) 1 /\ Gcd.gcd 1 d <> 0 };
752
round_up_to q (Q.make_exact 1 d)
753
end