Benchmark

non-incremental/QF_BV/brummayerbiere3/isqrt.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 show that if the most significant bit of x is zero, then 
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
Size5050
Compressed Size1247
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 unsat
Inferred Status unsat
Size 5042
Compressed Size1248
Max. Term Depth58
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
extract1 bvnot3 bvand1 bvor34
bvadd1 bvmul2 bvsub15 bvult2
bvule16 bvlshr31 zero_extend2

Evaluations

Evaluation Rating Solver Variant Result Wallclock CPU Time
SMT-COMP 2011 0.33 (4/6) Boolector Boolector 1.5.23-833 unsat ✅ 238.60000 —
CVC3 CVC3 v2.4 unknown ❌ 1200.10000 —
MathSAT MathSAT5 unknown ❌ 1200.00000 —
SONOLAR SONOLAR unsat ✅ 425.70000 —
STP simplifyingSTP unsat ✅ 130.30000 —
STP2 unsat ✅ 398.80000 —
Z3 Z3 unsat ✅ 157.70000 —
SMT Evaluation 2013 0.11 (8/9) 4Simp 4Simp-SMT-COMP-2012 default unsat ✅ 49.89160 —
Abziz abziz_portfolio_2011_minfeatures_2 default unsat ✅ 343.73700 —
abziz_portfolio_2011_solvers_2 default unsat ✅ 1083.17000 —
abziz_portfolio_2012_minfeatures default unsat ✅ 92.90850 —
abziz_portfolio_2012_solvers default unsat ✅ 54.24360 —
AbzizPortfolio-SMT-COMP-2012 default unsat ✅ 207.20600 —
Boolector Boolector-1.5.118-SMT-EVAL-2013 default unsat ✅ 110.83000 —
Boolector-SMT-COMP-2011 default unsat ✅ 202.42700 —
Boolector-SMT-COMP-2012 default unsat ✅ 140.53400 —
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 unsat ✅ 166.06800 —
CVC4-SMT-EVAL-2013 default unsat ✅ 185.96200 —
MathSAT MathSAT5-5.2.6-SMT-EVAL-2013 default unsat ✅ 1357.70000 —
MathSAT5-HeavyBV-SMT-COMP-2012 default unsat ✅ 165.92100 —
MathSAT5-SMT-COMP-2011 default unsat ✅ 1009.36000 —
MathSAT5-SMT-COMP-2012 default unsat ✅ 1060.75000 —
SONOLAR SONOLAR-2013-05-15-SMT-EVAL-2013 default unsat ✅ 531.69700 —
SONOLAR-SMT-COMP-2010 default unsat ✅ 1238.19000 —
SONOLAR-SMT-COMP-2011 default unsat ✅ 324.14300 —
SONOLAR-SMT-COMP-2012 default unsat ✅ 410.05800 —
STP STP2-SMT-COMP-2011 default unsat ✅ 351.25600 —
STP2-SMT-COMP-2012 default unsat ✅ 44.24850 —
simplifyingSTP-SMT-COMP-2010 default unsat ✅ 95.37290 —
Z3 Z3-4.3.2.a054b099c1d6-x64-debian-6.0.6-SMT-EVAL-2013 default unsat ✅ 98.11670 —
Z3-SMT-COMP-2011 default unsat ✅ 91.45680 —
SMT-COMP 2014 4Simp 4Simp - 2014 default unsat ✅ 66.66730 66.67690
Abziz abziz_portfolio_all_features default unsat ✅ 51.51110 51.44190
abziz_portfolio_min_features default unsat ✅ 171.93400 171.89100
Boolector Boolector boolector unsat ✅ 139.70500 139.75200
CVC4 CVC4 f7118b2 default unsat ✅ 363.32900 729.17300
MathSAT MathSAT-5.2.12-Main default unsat ✅ 1390.03000 1390.69000
SONOLAR sonolar_smtcomp-2014 default unsat ✅ 88.04090 88.05760
STP stp-cryptominisat4 default unsat ✅ 111.35500 111.38700
Yices2 Yices-2.2.1-smtcomp2014 default unsat ✅ 825.27000 825.44800
Z3 Z3-4.3.2.a054b099c1d6-x64-debian-6.0.6-SMT-COMP-2014 default unsat ✅ 96.80620 96.71000
SMT-COMP 2015 0.14 (6/7) Boolector Boolector SMT15 QF_BV final boolector_qf_bv unsat ✅ 199.67500 199.77500
CVC4 CVC4-master-2015-06-15-9b32405-main default unsat ✅ 328.48500 659.56200
CVC4-experimental-2015-06-15-ff5745a-main default unsat ✅ 146.78500 294.32700
MathSAT MathSat 5.3.6 main smtcomp2015_main unsat ✅ 282.85200 282.94400
SMT-RAT SMT-RAT-final default unknown ❌ 2400.01000 2400.93000
STP stp-cryptominisat4 default unsat ✅ 111.89400 111.91900
stp-cmsat4-v15 default unsat ✅ 74.04900 74.07470
stp-cmsat4-mt-v15 default unknown ❌ 0.07209 0.07099
stp-minisat-v15 default unsat ✅ 263.60900 263.74200
Yices2 Yices default unsat ✅ 909.94000 910.31000
Z3 z3 4.4.0 default unsat ✅ 89.02130 89.06650
SMT-COMP 2016 ABC ABC_default default_abc unsat ✅ 287.43000 287.61900
ABC_glucose glucose unsat ✅ 60.24080 60.27350
Boolector Boolector boolector unsat ✅ 176.62600 176.72600
Boolector preprop boolector unsat ✅ 176.25000 176.35300
CVC4 CVC4-master-2016-05-27-cfef263-main default unsat ✅ 164.34600 329.77600
MapleSTP MapleSTP default unsat ✅ 103.12100 103.16400
MapleSTP-mt default unsat ✅ 75.08020 297.88500
MathSAT mathsat-5.3.11-linux-x86_64-Main default unsat ✅ 308.46600 308.60800
MinkeyRink Minkeyrink 2016 default unsat ✅ 53.36050 210.57000
Q3B Q3B default unsat ✅ 725.24000 2176.45000
STP stp-cms-exp-2016 default unsat ✅ 97.11310 97.17730
stp-cms-mt-2016 default unsat ✅ 55.21680 219.26300
stp-cms-st-2016 default unsat ✅ 66.32540 66.35870
stp-minisat-st-2016 default unsat ✅ 2147.61000 2148.72000
Yices2 Yices-2.4.2 default unsat ✅ 458.26800 458.55200
Z3 z3-4.4.1 default unsat ✅ 90.40850 90.45660
SMT-COMP 2017 0.25 (6/8) Boolector Boolector+CaDiCaL SMT17 final boolector unsat ✅ 212.43600 212.42300
Boolector SMT17 final boolector unsat ✅ 173.87200 173.87700
CVC4 CVC4-smtcomp2017-main default unsat ✅ 164.94200 330.75700
MathSAT mathsat-5.4.1-linux-x86_64-Main default unsat ✅ 341.99400 341.94300
MinkeyRink MinkeyRink 2017.3a default unsat ✅ 92.13490 181.02000
Q3B Q3B default unknown ❌ 600.01800 1799.18000
STP stp_st default unsat ✅ 79.35990 79.35200
stp_mt default unsat ✅ 93.63870 245.17200
Yices2 Yices2-Main default unknown ❌ 600.01800 599.90500
Z3 z3-4.5.0 default unsat ✅ 90.12790 90.12260
SMT-COMP 2018 Boolector Boolector_default unsat ✅ 226.44700 226.45100
CVC4 master-2018-06-10-b19c840-competition-default_default unsat ✅ 102.51100 102.49700
MathSAT mathsat-5.5.2-linux-x86_64-Main_default unsat ✅ 378.30000 378.27300
MinkeyRink Minkeyrink MT_mt unsat ✅ 61.31300 242.89800
Minkeyrink ST_st unsat ✅ 95.81400 95.80700
STP STP-CMS-st-2018_default-no-stderr unsat ✅ 84.64970 84.64550
STP-CMS-mt-2018_multicore-no-stderr unsat ✅ 62.36480 247.83100
STP-Riss-st-2018_riss-no-stderr unsat ✅ 83.02950 83.02900
Yices2 Yices 2.6.0_default unsat ✅ 303.42100 303.42900
Z3 z3-4.7.1_default unsat ✅ 125.91200 125.90100
SMT-COMP 2019 Boolector Boolector-wrapped-sq_default unsat ✅ 87.44880 87.45300
Poolector-wrapped-sq_default unsat ✅ 90.29400 356.31000
Boolector-ReasonLS boolector-ReasonLS-wrapped-sq_default unsat ✅ 104.51900 104.51200
CVC4 CVC4-2019-06-03-d350fe1-wrapped-sq_default unsat ✅ 75.11150 75.10160
MinkeyRink MinkeyRink MT-wrapped-sq_default unsat ✅ 60.48650 240.12800
MinkeyRink ST-wrapped-sq_default unsat ✅ 106.27200 106.26700
Par4 Par4-wrapped-sq_default unsat ✅ 118.72300 355.97000
STP STP-2019-wrapped-sq_default unsat ✅ 92.96720 92.96110
stp-mergesat-fixed-wrapped-sq_default unsat ✅ 61.43440 61.42870
stp-minisat-wrapped-sq_default unsat ✅ 176.37400 176.34700
stp-mt-wrapped-sq_default unsat ✅ 66.15330 262.63100
stp-portfolio-fixed-wrapped-sq_default unsat ✅ 174.26900 330.82600
stp-riss-wrapped-sq_default unknown ❌ 0.06346 0.06364
Yices2 Yices 2.6.2-wrapped-sq_default unsat ✅ 324.14400 324.09200
Yices 2.6.2 Cadical-wrapped-sq_default unsat ✅ 56.22360 56.22240
Yices 2.6.2 Cryptominisat-wrapped-sq_default unsat ✅ 73.62540 73.61900
Yices 2.6.2 MCSAT BV-wrapped-sq_default unknown ❌ 2400.09000 2399.78000
Yices 2.6.2 new bvsolver-wrapped-sq_default unsat ✅ 75.36800 75.37040
Z3 z3-4.8.4-d6df51951f4c-wrapped-sq_default unsat ✅ 72.18250 72.17590
SMT-COMP 2020 0.22 (7/9) Bitwuzla Bitwuzla-fixed_default unsat ✅ 79.58370 79.58380
Boolector Boolector-wrapped-sq_default unsat ✅ 80.43890 80.43680
Poolector-wrapped-sq_default unsat ✅ 80.82740 319.81000
CVC4 CVC4-sq-final_default unsat ✅ 67.48820 67.48560
LazyBV2Int LazyBV2Int20200523_default.sh unknown ❌ 1200.02000 1199.90000
MathSAT MathSAT5_default.sh unsat ✅ 672.34400 672.21700
MinkeyRink MinkeyRink Solver 2020.3.1_default unknown ❌ 0.06805 0.06829
MinkeyRink Solver 2020.3_default unsat ✅ 95.21420 378.28700
STP STP_default unsat ✅ 85.23920 338.32500
STP ++ Mergsat v1_default unsat ✅ 96.15580 96.13830
Yices2 Yices 2.6.2 bug fix_default unsat ✅ 47.55690 47.54900
Z3 z3-4.8.8_default unknown ❌ 1200.04000 1199.92000
SMT-COMP 2021 Bitwuzla Bitwuzla-fixed_default unsat ✅ 77.82210 77.79750
MathSAT mathsat-5.6.6_default unsat ✅ 624.18900 624.15200
STP STP 2021.0_default unsat ✅ 112.20100 445.39000
Z3 z3-4.8.11_default unsat ✅ 84.63680 84.63200
SMT-COMP 2022 Bitwuzla Bitwuzla-fixed_default unsat ✅ 80.08640 80.07900
Bitwuzla-wrapped_default unsat ✅ 83.21560 83.21790
cvc5 cvc5-default-2022-07-02-b15e116-wrapped_sq unsat ✅ 76.46390 76.38000
MathSAT MathSAT-5.6.8_default unsat ✅ 626.91700 626.80600
STP STP 2022.4_default unsat ✅ 63.67610 63.67630
Yices2 Yices 2.6.2 for SMTCOMP 2021_default unsat ✅ 44.42260 44.41970
Z3++BV z3++bv_0702_default unsat ✅ 81.76220 81.75270
Z3 z3-4.8.17_default unsat ✅ 80.20260 80.18710
SMT-COMP 2023 0.17 (5/6) Bitwuzla Bitwuzla-fixed_default unsat ✅ 94.49200 94.48720
cvc5 cvc5-default-2023-05-16-ea045f305_sq unsat ✅ 79.50370 79.50820
STP STP 2022.4_default unsat ✅ 63.52070 63.51830
STP 2022.4_default unsat ✅ 63.22240 63.21570
UltimateEliminator UltimateIntBlastingWrapper+SMTInterpol_default unknown ❌ 4.65902 12.72380
Yices2 Yices 2 for SMTCOMP 2023_default unsat ✅ 330.66800 330.62700
Z3-Owl z3-Owl-Final_default unsat ✅ 239.60100 239.59000
z3-Owl-Final_default unsat ✅ 73.37670 73.37010
SMT-COMP 2024 0.17 (5/6) Bitwuzla Bitwuzla unsat ✅ 40.50971 40.39070
cvc5 cvc5 unsat ✅ 71.55520 71.44457
SMTInterpol SMTInterpol unknown ❌ 1201.74184 1238.70765
STP STP unsat ✅ 62.39843 62.27011
Yices2 Yices2 unsat ✅ 33.97448 33.87347
Z3alpha Z3-alpha unsat ✅ 281.58756 281.48350
SMT-COMP 2025 0.11 (8/9) Bitwuzla Bitwuzla unsat ✅ 36.13348 36.00284
Bitwuzla-MachBV-base unsat ✅ 34.24593 34.12119
Bitwuzla-MachBV Bitwuzla-MachBV unsat ✅ 37.86211 37.73565
BVDecide bv_decide unsat ✅ 137.91588 137.76046
bv_decide-nokernel unsat ✅ 118.18308 118.03179
cvc5 cvc5 unsat ✅ 58.20918 58.06958
SMTInterpol SMTInterpol unknown ❌ 58.24598 71.73950
Yices2 Yices2 unsat ✅ 29.40601 29.28206
Z3alpha Z3-alpha unsat ✅ 96.94533 386.54771
Z3 Z3-alpha-base unsat ✅ 54.77842 54.64043
Z3-Owl-base unsat ✅ 229.13946 228.98238
z3siri-base unsat ✅ 56.73551 56.60850
Z3-Owl Z3-Owl unsat ✅ 149.48169 149.32596