Benchmark

non-incremental/QF_BV/brummayerbiere3/isqrtaddnoif.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,
and uses "add" on m instead of "or".

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
Size4817
Compressed Size1154
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 4809
Compressed Size1167
Max. Term Depth57
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
extract1 bvnot19 bvand32 bvor18
bvadd33 bvmul2 bvsub31 bvult2
bvlshr31 bvashr16 zero_extend3

Evaluations

Evaluation Rating Solver Variant Result Wallclock CPU Time
SMT Evaluation 2013 0.11 (8/9) 4Simp 4Simp-SMT-COMP-2012 default unsat ✅ 118.03300 —
Abziz abziz_portfolio_2011_minfeatures_2 default unsat ✅ 229.76400 —
abziz_portfolio_2011_solvers_2 default unsat ✅ 229.16100 —
abziz_portfolio_2012_minfeatures default unsat ✅ 170.17200 —
abziz_portfolio_2012_solvers default unsat ✅ 68.21210 —
AbzizPortfolio-SMT-COMP-2012 default unsat ✅ 432.29900 —
Boolector Boolector-1.5.118-SMT-EVAL-2013 default unsat ✅ 150.22100 —
Boolector-SMT-COMP-2011 default unsat ✅ 224.81700 —
Boolector-SMT-COMP-2012 default unsat ✅ 165.62100 —
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 unsat ✅ 278.02400 —
MathSAT MathSAT5-5.2.6-SMT-EVAL-2013 default unsat ✅ 197.55200 —
MathSAT5-HeavyBV-SMT-COMP-2012 default unsat ✅ 170.27900 —
MathSAT5-SMT-COMP-2011 default unsat ✅ 200.78900 —
MathSAT5-SMT-COMP-2012 default unsat ✅ 228.96600 —
SONOLAR SONOLAR-2013-05-15-SMT-EVAL-2013 default unsat ✅ 534.94600 —
SONOLAR-SMT-COMP-2010 default unsat ✅ 822.84500 —
SONOLAR-SMT-COMP-2011 default unsat ✅ 398.38800 —
SONOLAR-SMT-COMP-2012 default unsat ✅ 480.69000 —
STP STP2-SMT-COMP-2011 default unsat ✅ 245.27200 —
STP2-SMT-COMP-2012 default unsat ✅ 62.29100 —
simplifyingSTP-SMT-COMP-2010 default unsat ✅ 133.47600 —
Z3 Z3-4.3.2.a054b099c1d6-x64-debian-6.0.6-SMT-EVAL-2013 default unsat ✅ 292.64200 —
Z3-SMT-COMP-2011 default unsat ✅ 278.01100 —
SMT-COMP 2014 0.11 (8/9) 4Simp 4Simp - 2014 default unsat ✅ 82.28010 82.30050
Abziz abziz_portfolio_all_features default unsat ✅ 66.62050 66.58060
abziz_portfolio_min_features default unsat ✅ 82.76980 82.72620
Boolector Boolector boolector unknown ❌ 2399.21000 2400.06000
CVC4 CVC4 f7118b2 default unsat ✅ 259.12500 520.16200
MathSAT MathSAT-5.2.12-Main default unsat ✅ 227.45600 227.52800
SONOLAR sonolar_smtcomp-2014 default unsat ✅ 96.86690 96.89330
STP stp-cryptominisat4 default unsat ✅ 111.92600 111.93800
Yices2 Yices-2.2.1-smtcomp2014 default unsat ✅ 425.98500 426.14600
Z3 Z3-4.3.2.a054b099c1d6-x64-debian-6.0.6-SMT-COMP-2014 default unsat ✅ 301.73300 301.83800
SMT-COMP 2015 0.14 (6/7) Boolector Boolector SMT15 QF_BV final boolector_qf_bv unsat ✅ 1909.00000 1909.84000
CVC4 CVC4-master-2015-06-15-9b32405-main default unsat ✅ 204.27500 410.35100
CVC4-experimental-2015-06-15-ff5745a-main default unsat ✅ 229.55600 460.48100
MathSAT MathSat 5.3.6 main smtcomp2015_main unsat ✅ 107.17500 107.19900
SMT-RAT SMT-RAT-final default unknown ❌ 2400.02000 2400.58000
STP stp-cryptominisat4 default unsat ✅ 124.94100 124.99200
stp-cmsat4-v15 default unsat ✅ 101.73400 101.75400
stp-cmsat4-mt-v15 default unknown ❌ 0.08281 0.08199
stp-minisat-v15 default unsat ✅ 253.59900 253.69700
Yices2 Yices default unsat ✅ 404.66500 404.82400
Z3 z3 4.4.0 default unsat ✅ 352.50900 352.64800
SMT-COMP 2016 ABC ABC_default default_abc unsat ✅ 299.30900 299.47500
ABC_glucose glucose unsat ✅ 58.65160 58.67720
Boolector Boolector boolector unsat ✅ 1844.86000 1845.91000
Boolector preprop boolector unsat ✅ 1841.25000 1842.47000
CVC4 CVC4-master-2016-05-27-cfef263-main default unsat ✅ 264.99800 532.05500
MapleSTP MapleSTP default unsat ✅ 70.06500 70.10170
MapleSTP-mt default unsat ✅ 59.89820 237.92000
MathSAT mathsat-5.3.11-linux-x86_64-Main default unsat ✅ 114.83100 114.89100
MinkeyRink Minkeyrink 2016 default unsat ✅ 47.09630 185.77900
Q3B Q3B default unsat ✅ 1709.30000 5129.99000
STP stp-cms-exp-2016 default unsat ✅ 92.99420 93.04480
stp-cms-mt-2016 default unsat ✅ 84.06930 333.85700
stp-cms-st-2016 default unsat ✅ 88.20560 88.25620
stp-minisat-st-2016 default unsat ✅ 2073.00000 2074.05000
Yices2 Yices-2.4.2 default unsat ✅ 226.97300 227.11800
Z3 z3-4.4.1 default unsat ✅ 292.18600 292.36900
SMT-COMP 2017 0.25 (6/8) Boolector Boolector+CaDiCaL SMT17 final boolector unknown ❌ 600.02700 599.94800
Boolector SMT17 final boolector unknown ❌ 600.01600 599.98200
CVC4 CVC4-smtcomp2017-main default unsat ✅ 292.99100 589.10900
MathSAT mathsat-5.4.1-linux-x86_64-Main default unsat ✅ 153.78500 151.51400
MinkeyRink MinkeyRink 2017.3a default unsat ✅ 110.10500 215.12000
Q3B Q3B default unknown ❌ 600.11300 1012.48000
STP stp_st default unsat ✅ 100.53000 100.52800
stp_mt default unsat ✅ 125.69800 332.66200
Yices2 Yices2-Main default unsat ✅ 396.36300 396.38200
Z3 z3-4.5.0 default unsat ✅ 366.21800 366.21500
SMT-COMP 2018 Boolector Boolector_default unsat ✅ 252.63300 252.61200
CVC4 master-2018-06-10-b19c840-competition-default_default unsat ✅ 231.70900 231.70100
MathSAT mathsat-5.5.2-linux-x86_64-Main_default unsat ✅ 107.42400 107.41700
MinkeyRink Minkeyrink MT_mt unsat ✅ 70.92880 281.85800
Minkeyrink ST_st unsat ✅ 93.35230 93.35360
STP STP-CMS-st-2018_default-no-stderr unsat ✅ 88.96900 88.96110
STP-CMS-mt-2018_multicore-no-stderr unsat ✅ 61.35700 243.67800
STP-Riss-st-2018_riss-no-stderr unsat ✅ 106.02200 106.01000
Yices2 Yices 2.6.0_default unsat ✅ 249.31100 249.28000
Z3 z3-4.7.1_default unsat ✅ 414.58700 414.58600
SMT-COMP 2022 0.14 (6/7) Bitwuzla Bitwuzla-fixed_default unsat ✅ 102.96500 102.94900
Bitwuzla-wrapped_default unsat ✅ 98.41860 98.41280
cvc5 cvc5-default-2022-07-02-b15e116-wrapped_sq unsat ✅ 253.21200 253.21300
MathSAT MathSAT-5.6.8_default unsat ✅ 185.01600 184.99500
STP STP 2022.4_default unsat ✅ 80.69780 80.66340
Yices2 Yices 2.6.2 for SMTCOMP 2021_default unsat ✅ 60.11380 60.11600
Z3++BV z3++bv_0702_default unsat ✅ 71.78780 71.77060
Z3 z3-4.8.17_default unknown ❌ 1200.02000 1199.88000