Benchmark

non-incremental/QF_BV/brummayerbiere3/isqrtaddinvalidvc.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 uses "add" instead of "or" in the loop.

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

Contributed by Robert Brummayer (robert.brummayer@gmail.com)
Benchmark
Size5105
Compressed Size1263
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 5097
Compressed Size1275
Max. Term Depth57
Asserts 1
Declared Functions0
Declared Constants1
Declared Sorts 0
Defined Functions0
Defined Recursive Functions 0
Defined Sorts0
Constants0
Declared Datatypes0

Symbols

ite50 not1 =18 let49
bvnot1 bvand1 bvor1 bvadd33
bvmul2 bvsub15 bvult2 bvule16
bvlshr31 zero_extend2

Evaluations

Evaluation Rating Solver Variant Result Wallclock CPU Time
SMT-COMP 2010 CVC3 CVC3 2.3 sat ✅ 0.80000 —
SONOLAR SONOLAR r252 sat ✅ 0.10000 —
STP simplifyingSTP sat ✅ 171.60000 —
SMT-COMP 2011 Boolector Boolector 1.5.23-833 sat ✅ 12.00000 —
CVC3 CVC3 v2.4 sat ✅ 0.80000 —
MathSAT MathSAT5 sat ✅ 96.70000 —
SONOLAR SONOLAR sat ✅ 117.60000 —
STP simplifyingSTP sat ✅ 172.60000 —
STP2 sat ✅ 6.60000 —
Z3 Z3 sat ✅ 243.80000 —
SMT Evaluation 2013 4Simp 4Simp-SMT-COMP-2012 default sat ✅ 27.05790 —
Abziz abziz_portfolio_2011_minfeatures_2 default sat ✅ 62.79250 —
abziz_portfolio_2011_solvers_2 default sat ✅ 63.80890 —
abziz_portfolio_2012_minfeatures default sat ✅ 700.03100 —
abziz_portfolio_2012_solvers default sat ✅ 32.38030 —
AbzizPortfolio-SMT-COMP-2012 default sat ✅ 9.02463 —
Boolector Boolector-1.5.118-SMT-EVAL-2013 default sat ✅ 27.87510 —
Boolector-SMT-COMP-2011 default sat ✅ 3.97097 —
Boolector-SMT-COMP-2012 default sat ✅ 16.52600 —
CVC3 CVC3-SMT-COMP-2010 default sat ✅ 0.42202 —
CVC3-SMT-COMP-2011 default sat ✅ 0.38449 —
CVC3-SMT-COMP-2012 default sat ✅ 0.39467 —
CVC4 CVC4-SMT-COMP-2012-Resubmission default sat ✅ 0.12074 —
CVC4-SMT-EVAL-2013 default sat ✅ 0.17287 —
MathSAT MathSAT5-5.2.6-SMT-EVAL-2013 default sat ✅ 1025.59000 —
MathSAT5-HeavyBV-SMT-COMP-2012 default sat ✅ 102.68400 —
MathSAT5-SMT-COMP-2011 default sat ✅ 58.23210 —
MathSAT5-SMT-COMP-2012 default sat ✅ 95.49050 —
SONOLAR SONOLAR-2013-05-15-SMT-EVAL-2013 default sat ✅ 13.49310 —
SONOLAR-SMT-COMP-2010 default sat ✅ 0.08225 —
SONOLAR-SMT-COMP-2011 default sat ✅ 35.65370 —
SONOLAR-SMT-COMP-2012 default sat ✅ 66.87600 —
STP STP2-SMT-COMP-2011 default sat ✅ 10.05190 —
STP2-SMT-COMP-2012 default sat ✅ 37.09050 —
simplifyingSTP-SMT-COMP-2010 default sat ✅ 6.58483 —
Z3 Z3-4.3.2.a054b099c1d6-x64-debian-6.0.6-SMT-EVAL-2013 default sat ✅ 434.19900 —
Z3-SMT-COMP-2011 default sat ✅ 669.33500 —
SMT-COMP 2014 4Simp 4Simp - 2014 default sat ✅ 10.98370 10.97130
Abziz abziz_portfolio_all_features default sat ✅ 5.25063 5.16296
abziz_portfolio_min_features default sat ✅ 66.18810 66.12670
Boolector Boolector boolector sat ✅ 59.25020 59.26400
CVC4 CVC4 f7118b2 default sat ✅ 0.22129 0.40894
MathSAT MathSAT-5.2.12-Main default sat ✅ 320.60500 320.63900
SONOLAR sonolar_smtcomp-2014 default sat ✅ 28.64640 28.64160
STP stp-cryptominisat4 default sat ✅ 0.60391 0.60291
Yices2 Yices-2.2.1-smtcomp2014 default sat ✅ 1.59847 1.59076
Z3 Z3-4.3.2.a054b099c1d6-x64-debian-6.0.6-SMT-COMP-2014 default sat ✅ 84.29550 84.31920
SMT-COMP 2015 Boolector Boolector SMT15 QF_BV final boolector_qf_bv sat ✅ 4.25138 4.25235
CVC4 CVC4-master-2015-06-15-9b32405-main default sat ✅ 0.23465 0.44993
CVC4-experimental-2015-06-15-ff5745a-main default sat ✅ 0.22208 0.42693
MathSAT MathSat 5.3.6 main smtcomp2015_main sat ✅ 298.14400 298.26600
SMT-RAT SMT-RAT-final default sat ✅ 2097.03000 2097.69000
STP stp-cryptominisat4 default sat ✅ 4.76348 4.76327
stp-cmsat4-v15 default sat ✅ 6.51634 6.51801
stp-cmsat4-mt-v15 default unknown ❌ 0.07167 0.07099
stp-minisat-v15 default sat ✅ 14.52360 14.52880
Yices2 Yices default sat ✅ 10.73460 10.73640
Z3 z3 4.4.0 default sat ✅ 758.36300 758.67800
SMT-COMP 2016 ABC ABC_default default_abc sat ✅ 1.70450 1.70547
ABC_glucose glucose sat ✅ 38.91450 38.92680
Boolector Boolector boolector sat ✅ 16.53500 16.54430
Boolector preprop boolector sat ✅ 16.46520 16.47520
CVC4 CVC4-master-2016-05-27-cfef263-main default sat ✅ 0.21060 0.40525
MapleSTP MapleSTP default sat ✅ 132.63700 132.71300
MapleSTP-mt default sat ✅ 34.27040 135.79900
MathSAT mathsat-5.3.11-linux-x86_64-Main default sat ✅ 34.90800 34.92900
MinkeyRink Minkeyrink 2016 default sat ✅ 51.12490 201.94600
Q3B Q3B default sat ✅ 26.43420 78.98000
STP stp-cms-exp-2016 default sat ✅ 169.72800 169.82600
stp-cms-mt-2016 default sat ✅ 2.64591 10.30930
stp-cms-st-2016 default sat ✅ 90.01540 90.06060
stp-minisat-st-2016 default sat ✅ 119.22000 119.28900
Yices2 Yices-2.4.2 default sat ✅ 7.09339 7.09793
Z3 z3-4.4.1 default sat ✅ 395.62100 395.83200
SMT-COMP 2017 Boolector Boolector+CaDiCaL SMT17 final boolector sat ✅ 9.55825 9.55651
Boolector SMT17 final boolector sat ✅ 13.47410 13.47230
CVC4 CVC4-smtcomp2017-main default sat ✅ 0.23681 0.45461
MathSAT mathsat-5.4.1-linux-x86_64-Main default sat ✅ 111.84100 111.83800
MinkeyRink MinkeyRink 2017.3a default sat ✅ 6.95499 8.87000
Q3B Q3B default sat ✅ 26.98080 80.49000
STP stp_st default sat ✅ 52.15480 52.15600
stp_mt default sat ✅ 2.72225 10.61330
Yices2 Yices2-Main default sat ✅ 6.96806 6.96685
Z3 z3-4.5.0 default sat ✅ 467.23100 467.20200
SMT-COMP 2018 Boolector Boolector_default sat ✅ 11.80250 11.80160
CVC4 master-2018-06-10-b19c840-competition-default_default sat ✅ 33.83820 33.83860
MathSAT mathsat-5.5.2-linux-x86_64-Main_default sat ✅ 194.67000 194.65000
MinkeyRink Minkeyrink MT_mt sat ✅ 1.81895 7.01221
Minkeyrink ST_st sat ✅ 4.64414 4.64240
STP STP-CMS-st-2018_default-no-stderr sat ✅ 5.28917 5.28875
STP-CMS-mt-2018_multicore-no-stderr sat ✅ 0.82090 3.02690
STP-Riss-st-2018_riss-no-stderr sat ✅ 3.66416 3.66328
Yices2 Yices 2.6.0_default sat ✅ 3.97716 3.97711
Z3 z3-4.7.1_default sat ✅ 1171.48000 1171.41000
SMT-COMP 2019 Boolector Boolector-wrapped-sq_default sat ✅ 0.05162 0.05162
Poolector-wrapped-sq_default sat ✅ 0.17513 0.15594
Boolector-ReasonLS boolector-ReasonLS-wrapped-sq_default sat ✅ 19.61670 19.61510
CVC4 CVC4-2019-06-03-d350fe1-wrapped-sq_default sat ✅ 6.68808 6.68593
MinkeyRink MinkeyRink MT-wrapped-sq_default sat ✅ 2.64575 10.24260
MinkeyRink ST-wrapped-sq_default sat ✅ 9.63492 9.63461
Par4 Par4-wrapped-sq_default sat ✅ 4.02357 11.91000
STP STP-2019-wrapped-sq_default sat ✅ 5.09921 5.09918
stp-mergesat-fixed-wrapped-sq_default sat ✅ 5.73343 5.73348
stp-minisat-wrapped-sq_default sat ✅ 18.76490 18.76540
stp-mt-wrapped-sq_default sat ✅ 0.78857 2.88707
stp-portfolio-fixed-wrapped-sq_default sat ✅ 18.86480 29.74800
stp-riss-wrapped-sq_default unknown ❌ 0.06462 0.06483
Yices2 Yices 2.6.2-wrapped-sq_default sat ✅ 4.23291 4.23284
Yices 2.6.2 Cadical-wrapped-sq_default sat ✅ 19.08070 19.08160
Yices 2.6.2 Cryptominisat-wrapped-sq_default sat ✅ 62.16990 62.16790
Yices 2.6.2 MCSAT BV-wrapped-sq_default sat ✅ 0.02656 0.02654
Yices 2.6.2 new bvsolver-wrapped-sq_default sat ✅ 4.55829 4.55823
Z3 z3-4.8.4-d6df51951f4c-wrapped-sq_default sat ✅ 78.84900 78.83840
SMT-COMP 2021 Bitwuzla Bitwuzla-fixed_default sat ✅ 0.07144 0.07139
MathSAT mathsat-5.6.6_default sat ✅ 558.52400 558.48000
STP STP 2021.0_default sat ✅ 0.37771 1.30095
Z3 z3-4.8.11_default sat ✅ 0.22413 0.22411
SMT-COMP 2023 0.17 (5/6) Bitwuzla Bitwuzla-fixed_default sat ✅ 0.05446 0.05441
cvc5 cvc5-default-2023-05-16-ea045f305_sq sat ✅ 0.44344 0.44269
STP STP 2022.4_default sat ✅ 0.06434 0.06436
STP 2022.4_default sat ✅ 0.06346 0.06347
UltimateEliminator UltimateIntBlastingWrapper+SMTInterpol_default unknown ❌ 4.31350 11.68080
Yices2 Yices 2 for SMTCOMP 2023_default sat ✅ 4.16599 4.16588
Z3-Owl z3-Owl-Final_default sat ✅ 91.75360 91.74850
z3-Owl-Final_default sat ✅ 2.25498 2.25483
SMT-COMP 2025 0.11 (8/9) Bitwuzla Bitwuzla sat ✅ 0.30218 0.17750
Bitwuzla-MachBV-base sat ✅ 0.26226 0.14825
Bitwuzla-MachBV Bitwuzla-MachBV sat ✅ 0.36958 0.23717
BVDecide bv_decide sat ✅ 1.17052 0.99021
bv_decide-nokernel sat ✅ 1.16110 0.98780
cvc5 cvc5 sat ✅ 3.13226 3.01343
SMTInterpol SMTInterpol unknown ❌ 2.40813 6.61669
Yices2 Yices2 sat ✅ 0.32757 0.20353
Z3alpha Z3-alpha sat ✅ 21.16619 83.32367
Z3 Z3-alpha-base sat ✅ 10.37592 10.25322
Z3-Owl-base sat ✅ 45.78322 45.64160
z3siri-base sat ✅ 11.00783 10.88488
Z3-Owl Z3-Owl sat ✅ 43.92060 43.79724