Vi presenterar den automatiska formella verifieringen av en toppmodern algoritm från GMP-biblioteket som beräknar kvadratroten av ett 64-bitars heltal. Även om det använder bara heltal operationer, är det bästa sättet att förstå programmet att se det som en fast punkt aritmetisk algoritm som implementerar Newton metod. C-koden är kort men invecklad, med magiska konstanter och avsiktliga aritmetiska överflöd. Vi har verifierat algoritmen med hjälp av Why3-verktyget och automatiserade lösare som Gappa.
År 2019, Melquiond et al. presenterade ett dokument om den formella verifieringen av GMP-bibliotekets algoritm för att beräkna kvadratroten av ett 64-bitars heltal med hjälp av Why3 REF.
Formal Verification of a State-of-the-Art Integer Square Root
{'venue': '2019 IEEE 26th Symposium on Computer Arithmetic (ARITH)', 'journal': '2019 IEEE 26th Symposium on Computer Arithmetic (ARITH)', 'mag_field_of_study': ['Computer Science']}