Benchmark

non-incremental/QF_BV/brummayerbiere3/isqrtnoifinvalidvc.smt2 

Integer square root algorithm isqrt(x), where x is an unsigned 32 bit integer.
From the book "Hacker's delight" by Henry S. Warren, Jr., page 210
We use a variant of the algorithm that does not use an "if" inside the loop.

We try to show the invalid verification condition:
y^2 == x or (y^2 < x and (y+1)^2 > x), where y is the result.

Contributed by Robert Brummayer (robert.brummayer@gmail.com)
Benchmark
Size4685
Compressed Size1115
License Creative Commons Attribution 4.0 International (CC-BY-4.0)
Categorycrafted
First Occurrence2009-08-02
Generated By—
Generated On—
Generator—
Dolmen OK1
strict Dolmen OK1
check-sat calls1
Query 1
Status sat
Inferred Status sat
Size 4677
Compressed Size1106
Max. Term Depth56
Asserts 1
Declared Functions0
Declared Constants1
Declared Sorts 0
Defined Functions0
Defined Recursive Functions 0
Defined Sorts0
Constants0
Declared Datatypes0

Symbols

ite3 not1 =2 let48
bvnot17 bvand32 bvor49 bvadd1
bvmul2 bvsub31 bvult2 bvlshr31
bvashr16 zero_extend3

Evaluations

Evaluation Rating Solver Variant Result Wallclock CPU Time
SMT-COMP 2009 0.38 (5/8) Beaver beaver-smtcomp-2009 sat ✅ 4.30000 —
Boolector Boolector sat ✅ 26.90000 —
Boolector 1.2 sat ✅ 495.00000 —
CVC3 CVC3 2.0 unknown ❌ 900.00000 —
MathSAT MathSAT 4.3 sat ✅ 0.10000 —
OpenSMT OpenSMT 0.2 unknown ❌ 900.00000 —
STP STP #101 unknown ❌ 900.00000 —
SWORD sword-1.0 sat ✅ 111.90000 —
Yices2 Yices 2 proto sat ✅ 0.90000 —
SMT-COMP 2010 0.33 (2/3) CVC3 CVC3 2.3 unknown ❌ 1200.00000 —
SONOLAR SONOLAR r252 sat ✅ 43.00000 —
STP simplifyingSTP sat ✅ 4.60000 —
SMT-COMP 2011 0.17 (5/6) Boolector Boolector 1.5.23-833 sat ✅ 187.60000 —
CVC3 CVC3 v2.4 unknown ❌ 1200.00000 —
MathSAT MathSAT5 sat ✅ 196.70000 —
SONOLAR SONOLAR sat ✅ 0.70000 —
STP simplifyingSTP sat ✅ 121.10000 —
STP2 sat ✅ 0.50000 —
Z3 Z3 sat ✅ 31.60000 —
SMT Evaluation 2013 1.00 (0/9) 4Simp 4Simp-SMT-COMP-2012 default unknown ❌ — —
Abziz abziz_portfolio_2011_minfeatures_2 default unknown ❌ — —
abziz_portfolio_2011_solvers_2 default unknown ❌ — —
abziz_portfolio_2012_minfeatures default unknown ❌ — —
abziz_portfolio_2012_solvers default unknown ❌ — —
AbzizPortfolio-SMT-COMP-2012 default unknown ❌ — —
Boolector Boolector-1.5.118-SMT-EVAL-2013 default unknown ❌ — —
Boolector-SMT-COMP-2011 default unknown ❌ — —
Boolector-SMT-COMP-2012 default unknown ❌ — —
CVC3 CVC3-SMT-COMP-2010 default unknown ❌ — —
CVC3-SMT-COMP-2011 default unknown ❌ — —
CVC3-SMT-COMP-2012 default unknown ❌ — —
CVC4 CVC4-SMT-COMP-2012-Resubmission default unknown ❌ — —
CVC4-SMT-EVAL-2013 default unknown ❌ — —
MathSAT MathSAT5-5.2.6-SMT-EVAL-2013 default unknown ❌ — —
MathSAT5-HeavyBV-SMT-COMP-2012 default unknown ❌ — —
MathSAT5-SMT-COMP-2011 default unknown ❌ — —
MathSAT5-SMT-COMP-2012 default unknown ❌ — —
SONOLAR SONOLAR-2013-05-15-SMT-EVAL-2013 default unknown ❌ — —
SONOLAR-SMT-COMP-2010 default unknown ❌ — —
SONOLAR-SMT-COMP-2011 default unknown ❌ — —
SONOLAR-SMT-COMP-2012 default unknown ❌ — —
STP STP2-SMT-COMP-2011 default unknown ❌ — —
STP2-SMT-COMP-2012 default unknown ❌ — —
simplifyingSTP-SMT-COMP-2010 default unknown ❌ — —
Z3 Z3-4.3.2.a054b099c1d6-x64-debian-6.0.6-SMT-EVAL-2013 default unknown ❌ — —
Z3-SMT-COMP-2011 default unknown ❌ — —
SMT-COMP 2014 4Simp 4Simp - 2014 default sat ✅ 2.00104 1.99270
Abziz abziz_portfolio_all_features default sat ✅ 5.15766 5.08498
abziz_portfolio_min_features default sat ✅ 119.47200 119.39800
Boolector Boolector boolector sat ✅ 8.82868 8.82266
CVC4 CVC4 f7118b2 default sat ✅ 0.13249 0.22596
MathSAT MathSAT-5.2.12-Main default sat ✅ 34.65440 34.65870
SONOLAR sonolar_smtcomp-2014 default sat ✅ 56.51780 56.53440
STP stp-cryptominisat4 default sat ✅ 13.80800 13.80290
Yices2 Yices-2.2.1-smtcomp2014 default sat ✅ 0.30960 0.30095
Z3 Z3-4.3.2.a054b099c1d6-x64-debian-6.0.6-SMT-COMP-2014 default sat ✅ 4.79360 4.77827
SMT-COMP 2015 0.14 (6/7) Boolector Boolector SMT15 QF_BV final boolector_qf_bv sat ✅ 1.74033 1.73973
CVC4 CVC4-master-2015-06-15-9b32405-main default sat ✅ 0.99133 1.96770
CVC4-experimental-2015-06-15-ff5745a-main default sat ✅ 0.72222 1.43078
MathSAT MathSat 5.3.6 main smtcomp2015_main sat ✅ 75.75230 75.78250
SMT-RAT SMT-RAT-final default unknown ❌ 2400.01000 2401.15000
STP stp-cryptominisat4 default sat ✅ 2.47636 2.47562
stp-cmsat4-v15 default sat ✅ 0.81136 0.81088
stp-cmsat4-mt-v15 default unknown ❌ 0.07869 0.07699
stp-minisat-v15 default sat ✅ 1.95629 1.95570
Yices2 Yices default sat ✅ 0.29983 0.29895
Z3 z3 4.4.0 default sat ✅ 24.13120 24.14130
SMT-COMP 2016 ABC ABC_default default_abc sat ✅ 1.57946 1.58068
ABC_glucose glucose sat ✅ 15.49250 15.49990
Boolector Boolector boolector sat ✅ 3.96322 3.96546
Boolector preprop boolector sat ✅ 3.97821 3.98040
CVC4 CVC4-master-2016-05-27-cfef263-main default sat ✅ 0.71890 1.42704
MapleSTP MapleSTP default sat ✅ 0.11063 0.11065
MapleSTP-mt default sat ✅ 0.12793 0.30615
MathSAT mathsat-5.3.11-linux-x86_64-Main default sat ✅ 28.20400 28.22110
MinkeyRink Minkeyrink 2016 default sat ✅ 0.60145 0.91231
Q3B Q3B default sat ✅ 55.90360 167.31000
STP stp-cms-exp-2016 default sat ✅ 4.03349 4.03547
stp-cms-mt-2016 default sat ✅ 0.35030 1.17447
stp-cms-st-2016 default sat ✅ 1.63749 3.17677
stp-minisat-st-2016 default sat ✅ 15.21710 15.22720
Yices2 Yices-2.4.2 default sat ✅ 0.28636 0.28649
Z3 z3-4.4.1 default sat ✅ 19.42840 19.44090
SMT-COMP 2017 Boolector Boolector+CaDiCaL SMT17 final boolector sat ✅ 0.20594 0.20447
Boolector SMT17 final boolector sat ✅ 2.43115 2.42745
CVC4 CVC4-smtcomp2017-main default sat ✅ 0.78341 1.52834
MathSAT mathsat-5.4.1-linux-x86_64-Main default sat ✅ 28.64750 28.64320
MinkeyRink MinkeyRink 2017.3a default sat ✅ 8.85032 12.77000
Q3B Q3B default sat ✅ 116.17800 273.61000
STP stp_st default sat ✅ 13.97970 13.97910
stp_mt default sat ✅ 4.02463 7.18232
Yices2 Yices2-Main default sat ✅ 0.28887 0.28689
Z3 z3-4.5.0 default sat ✅ 7.74758 7.74732
SMT-COMP 2018 Boolector Boolector_default sat ✅ 0.01332 0.01327
CVC4 master-2018-06-10-b19c840-competition-default_default sat ✅ 4.69275 4.69266
MathSAT mathsat-5.5.2-linux-x86_64-Main_default sat ✅ 134.19000 134.19600
MinkeyRink Minkeyrink MT_mt sat ✅ 2.58740 9.94380
Minkeyrink ST_st sat ✅ 110.80400 110.78600
STP STP-CMS-st-2018_default-no-stderr sat ✅ 14.82320 14.82270
STP-CMS-mt-2018_multicore-no-stderr sat ✅ 0.56185 2.01750
STP-Riss-st-2018_riss-no-stderr sat ✅ 2.41817 2.41795
Yices2 Yices 2.6.0_default sat ✅ 0.28278 0.28256
Z3 z3-4.7.1_default sat ✅ 11.09750 11.09780
SMT-COMP 2019 Boolector Boolector-wrapped-sq_default sat ✅ 0.15739 0.15737
Poolector-wrapped-sq_default sat ✅ 0.28259 0.26094
Boolector-ReasonLS boolector-ReasonLS-wrapped-sq_default sat ✅ 14.58130 14.57400
CVC4 CVC4-2019-06-03-d350fe1-wrapped-sq_default sat ✅ 6.39479 6.39506
MinkeyRink MinkeyRink MT-wrapped-sq_default sat ✅ 0.33317 1.06459
MinkeyRink ST-wrapped-sq_default sat ✅ 106.79100 106.78000
Par4 Par4-wrapped-sq_default sat ✅ 0.02182 0.00475
STP STP-2019-wrapped-sq_default sat ✅ 0.62830 0.62870
stp-mergesat-fixed-wrapped-sq_default sat ✅ 30.69890 30.67500
stp-minisat-wrapped-sq_default sat ✅ 1.09767 1.09744
stp-mt-wrapped-sq_default sat ✅ 0.63358 2.27706
stp-portfolio-fixed-wrapped-sq_default sat ✅ 30.88570 32.43110
stp-riss-wrapped-sq_default unknown ❌ 0.06818 0.06834
Yices2 Yices 2.6.2-wrapped-sq_default sat ✅ 0.13914 0.13899
Yices 2.6.2 Cadical-wrapped-sq_default sat ✅ 3.17463 3.17460
Yices 2.6.2 Cryptominisat-wrapped-sq_default sat ✅ 8.81101 8.81061
Yices 2.6.2 MCSAT BV-wrapped-sq_default sat ✅ 24.81720 24.81520
Yices 2.6.2 new bvsolver-wrapped-sq_default sat ✅ 15.52740 15.52620
Z3 z3-4.8.4-d6df51951f4c-wrapped-sq_default sat ✅ 262.32400 262.26900
SMT-COMP 2022 0.14 (6/7) Bitwuzla Bitwuzla-fixed_default sat ✅ 0.08687 0.08681
Bitwuzla-wrapped_default sat ✅ 0.26167 0.26160
cvc5 cvc5-default-2022-07-02-b15e116-wrapped_sq sat ✅ 0.21248 0.21302
MathSAT MathSAT-5.6.8_default sat ✅ 15.33850 15.33750
STP STP 2022.4_default sat ✅ 0.07267 0.07272
Yices2 Yices 2.6.2 for SMTCOMP 2021_default sat ✅ 12.99040 12.98740
Z3++BV z3++bv_0702_default sat ✅ 0.08175 0.08164
Z3 z3-4.8.17_default unknown ❌ 1200.01000 1199.74000
SMT-COMP 2025 0.11 (8/9) Bitwuzla Bitwuzla sat ✅ 0.29842 0.17173
Bitwuzla-MachBV-base sat ✅ 0.27828 0.15952
Bitwuzla-MachBV Bitwuzla-MachBV sat ✅ 0.38471 0.25697
BVDecide bv_decide sat ✅ 0.98431 0.82370
bv_decide-nokernel sat ✅ 0.99368 0.83901
cvc5 cvc5 sat ✅ 9.78839 9.65932
SMTInterpol SMTInterpol unknown ❌ 1201.48424 1243.36979
Yices2 Yices2 sat ✅ 9.79143 9.67310
Z3alpha Z3-alpha sat ✅ 1.80785 5.81783
Z3 Z3-alpha-base sat ✅ 0.38483 0.26254
Z3-Owl-base sat ✅ 0.67763 0.55463
z3siri-base sat ✅ 0.38490 0.25150
Z3-Owl Z3-Owl sat ✅ 1.67285 1.55378