loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2005 International Conference on Computer Design
Formal Verification of Parametric Multiplicative Division Implementations
San Jose, California
October 02-October 05
ISBN: 0-7695-2451-6
Nikhil Kikkeri, Southern Methodist University, Computer Science and Engineering Dallas, TX
Peter-Michael Seidel, Southern Methodist University, Computer Science and Engineering Dallas, TX

Back in the 60?s Goldschmidt presented a variation of Newton-Raphson iterations for division that is well suited for pipelining. The problem in using Goldschmidt?s division algorithm is to verify that the implementation meets the precision required for the quotient and provides correct rounding, in particular if hardware resources are to be used judiciously. Previous implementations relied on error analysis that were not quite tight and that were specific to one parameter setting and target precision. Our formal verification effort focuses on a parametric division implementation based on Goldschmidt?s algorithm for different parameter settings and target precisions. We formalize a tight and parametric error analysis of Goldschmidt?s division algorithm in PVS and prove its correctness. On this basis we propose formally verified parametric division implementations.

Citation:
Nikhil Kikkeri, Peter-Michael Seidel, "Formal Verification of Parametric Multiplicative Division Implementations," iccd, pp.599-602, 2005 International Conference on Computer Design, 2005
Usage of this product signifies your acceptance of the Terms of Use.