Home / Docs / Specification / 29. Numerics
29.8 Verification
-
The encoding is exact. An
F64is the SMT-LIB sort(_ FloatingPoint 11 53),Float64, with the rounding modeRNE. The theory has one NaN and two zeros, asF64has, so the encoding is the run-time semantics, not an approximation of it:Una SMT-LIB a float literal, nan(),infinity()(fp #b<sign> #b<exponent> #b<significand>), the exact bits+,-,*,/, unary-fp.add RNE,fp.sub RNE,fp.mul RNE,fp.div RNE,fp.negsqrt,absfp.sqrt RNE,fp.abs==SMT =, identity<,<=the defined functions i!lt!F64,i!le!F64: totalOrderieee_eq,ieee_lt,ieee_le,ieee_gt,ieee_ge,ieee_nefp.eq,fp.lt,fp.leq,fp.gt,fp.geq,(not (fp.eq a b))is_nan,is_finite,is_infinite,is_sign_negativefp.isNaN;(not (or (fp.isNaN x) (fp.isInfinite x)));fp.isInfinite;(and (fp.isNegative x) (not (fp.isNaN x)))is_zero,is_positive_zero,is_negative_zerofp.isZero; withfp.isPositive; withfp.isNegativen.to_f64(),nof a fixed-width type of widthw(ite (in range) ((_ to_fp 11 53) RNE ((_ int2bv w) n)) <the form of Int>),to_fp_unsignedfor an unsigned type: the narrow form only wherenlies in its type's range, since a term computed exactly (areflectbody, a clause) may lie beyond it; a conversion in ordinary code keeps the narrow form unguarded, since its operand is a value of its type by construction (a parameter, a field, a result with anoverflowobligation)n.to_f64(),nofIntthe same at width 64 for -2^63 <= n < 2^63, and the uninterpretedi!to_f64!Intbeyond -
The refinement language (spec/03 §3) gains, over
F64: float literals other than in the forms of §5 rules 5 and 6,nan()andinfinity(),+,-,*,/and unary-between any twoF64terms,==,!=,<,<=,>,>=, the IEEE comparisons,abs(),sqrt(), the classifications,is_zero(),is_positive_zero(),is_negative_zero(), andto_f64()of an integer term. Every operation rounds as the code's does:ensures result == a + bstates the rounded sum. The other methods are code only: U2014 in a clause. -
Which queries change. A query without an
F64term is unchanged, byte for byte, inQF_UFLIA. A query with one declares the logicALLand is sent with the step budget 5,000,000, a constant of the encodinguna-smt-1, whateverstep_budgetthe lock sets.verification.lockkeepslogic = "QF_UFLIA", the logic of every query without anF64term. -
The cone. The hypotheses of an obligation are split into their conjuncts. A conjunct without an
F64term is kept. A conjunct with one is kept when it is connected to the goal'sF64terms through sharedF64binders, transitively (a union-find, O(|Π| α(|Π|))). Of the others, a selfifiedletwith anF64term, a definition, is dropped, and every other one, a constraint (a branch condition, a refinement, anensures, a field equation of a construction), is kept with each float atom, a maximalBoolsubterm with anF64argument, replaced by a freshBool. Each step only weakens Π. -
Order. The pipeline of spec/12 §5 runs on the cone query.
provenandunknownare final.refutedis final when nothing was dropped, or when only definitions were dropped whose binders occur in no kept hypothesis and not in the goal, and no ground fact of a dropped term is left out. Otherwise the pipeline runs again on the full query, the obligation's query with every hypothesis of Π, whose status is the obligation's; when it isunknown, the reason says that the refutation holds unless floating-point facts make the path unreachable. The weighted bound below applies to every query sent, re-solves included. -
The weighted bound. The weight of a query is taken over its distinct terms:
fp.mul,fp.div,fp.sqrtand a conversion of a value that is not a literal weigh 4 (the two forms of one integer's conversion together),fp.addandfp.subweigh 1, everything else nothing; each distinct application of areflectpredicate weighs its body's weight, as if inlined. A query of weight more than 4 is not sent: it is U5002, with the reason "this obligation needs floating-point reasoning of weight N, more than the 4 the verifier decides" and its repairs (a checked boundary, a split contract, a weaker property). Anunknownon a float query is U5002 with the float reason. -
What is expected to verify: a bound by constants on the result of one operation over inputs bounded by constants; finiteness and not-NaN of one operation; up to four additions; a conversion from an integer of modest range; comparison-only facts over a handful of binders. Not expected, and U5002: a result compared with an input of the same operation, two multiplications in a chain, dot products, norms, a fact about the result of a loop.
-
Counterexamples (spec/12 §7). An
F64binding shows its rendering of §7, as a JSON string ("0.1","-0.0","nan"). A refutation whose query usesi!to_f64!Int, in its hypotheses or in the facts of a loop's first iteration, is solved once more with every argument of the conversion in-2^63 <= n < 2^63, where the encoding is exact: a model of that query is an execution, and the obligation stays refuted with it; a conversion in areflectpredicate's definition is pinned at each application, its argument instantiated; otherwise it isunknown(U5002), with a reason that asks for a range refinement or a fixed-width type. So no counterexample ever rests on a value of the uninterpreted conversion. -
Generic code. A comparison of a type parameter instantiated with
F64in a callee's contract isi!lt!F64andi!le!F64.