Kahan's algorithm for a correct discriminant computation at last formally proven - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Journal Articles IEEE Transactions on Computers Year : 2009

Kahan's algorithm for a correct discriminant computation at last formally proven

Abstract

This article tackles Kahan's algorithm to compute accurately the discriminant whatever the inputs. This is a known difficult problem and this algorithm leads to an error bounded by 2 ulps of the result. The proofs involved are long and tricky and even trickier than expected as the test involved may give an unexpected result. We give here the total demonstration of the validity of this algorithm and we provide sufficient conditions to guarantee neither Overflow, nor Underflow will jeopardize the result. The program was annotated using the Caduceus tool and the proof obligations were done using the Coq automatic proof checker.
Fichier principal
Vignette du fichier
boldo.pdf (629.21 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

inria-00171497 , version 1 (12-09-2007)
inria-00171497 , version 2 (24-11-2009)

Identifiers

Cite

Sylvie Boldo. Kahan's algorithm for a correct discriminant computation at last formally proven. IEEE Transactions on Computers, 2009, 58 (2), pp.220-225. ⟨10.1109/TC.2008.200⟩. ⟨inria-00171497v2⟩
417 View
741 Download

Altmetric

Share

Gmail Facebook X LinkedIn More