计算机科学

计算机科学 ›› 2026, Vol. 53 ›› Issue (10): 367-375.doi: 10.11896/jsjkx.250700073

• 计算机软件 • 上一篇    下一篇

基于分层搜索与分区间分析的浮点表达式误差检测

牛梦锦, 王磊, 张旭林, 梁军达   

  1. 中原工学院网络空间安全学院 郑州 450007
  • 收稿日期:2025-07-14 修回日期:2025-09-29 发布日期:2026-10-13
  • 通讯作者: 王磊(wl1167@163.com)
  • 作者简介:(15539425108@163.com)
  • 基金资助:
    基于高性能计算的基础数学库软件研发(22001742)

Floating-point Expression Error Detection Based on Hierarchical Search and Interval Partitioning Analysis

NIU Mengjin, WANG Lei, ZHANG Xulin, LIANG Junda   

  1. School of Cyberspace Security,Zhongyuan University of Technology,Zhengzhou 450007, China
  • Received:2025-07-14 Revised:2025-09-29 Online:2026-10-13
  • About author:NIU Mengjin,born in 1999,postgraduate.Her main research interests include high performance computing and code security.
    WANG Lei,born in 1977,professor,is a member of CCF(No.12516M).His main research interests include high performance computing and domestic independent and controllable basic software.
  • Supported by:
    Research and Development of Basic Mathematical Library Software Based on High-Performance Computing(22001742).

PDF (PC)

75

摘要： 计算机用有限的二进制位表示实数,其固有的舍入误差在计算过程中可能会造成累积,在某些情况下,还会导致严重的错误。检测浮点误差对于确保程序正确输出至关重要。理论上,检测浮点误差最准确的方法是穷举搜索所有可能的浮点输入,但由于搜索空间巨大,该方法在实践中是不可行的。而浮点误差具有稀疏性,只有有限数量的输入值会导致严重的错误,如何有效地检测这些输入并选择合适的搜索技术,对于检测最大浮点误差是一项艰巨的挑战。为了应对这一挑战,基于分层搜索与分区间分析,设计并实现了一种针对浮点表达式进行误差检测的工具HSIBA。HSIBA修改双精度浮点数的尾数部分,通过模拟不同精度进行分层搜索结合分区间分析,检测可能的浮点误差极大值及对应的输入并报告。从FPBench标准测试集中选取28个表达式作为测试用例,并将HSIBA与先进检测工具PSOED和ATOMU进行对比。实验结果中,HSIBA有16个测试用例的检测效果优于PSOED,有20个测试用例的检测效果优于ATOMU。同时,PSOED耗费的平均时间是HSIBA的3.15倍,而HSIBA的性能不如ATOMU。

关键词: 浮点运算, 舍入错误, 错误检测, 分层搜索, 分区间分析

Abstract: Computers represent real numbers using finite-precision binary formats,where inherent rounding errors may accumulate during computation and,in certain scenarios,lead to severe or even catastrophic failures.Floating-point error detection is cri-tical for ensuring the correctness of program outputs.Theoretically,the most accurate method for detecting floating-point errors is exhaustive search over all possible floating-point inputs.However,due to the enormous search space,this approach is practically infeasible.Given the sparsity of floating-point errors-where only a limited number of input values trigger significant errors－efficiently detecting these inputs and selecting appropriate search techniques poses a substantial challenge for maximum floating-point error detection.To address this challenge,a tool called HSIBA for error detection in floating-point expressions has been designed and implemented,based on hierarchical search and interval partitioning analysis.HSIBA employs hierarchical search by manipulating the mantissa of double-precision floating-point numbers to simulate varying precisions,combined with interval partitioning analysis.This approach detects potential maxima of floating-point errors and their corresponding inputs,which are then reported.Evaluation uses 28 expressions from the FPBench standard benchmark suite as test cases,and HSIBA is compared with the advanceddetection tools PSOED and ATOMU.Experimental results demonstrate that HSIBA outperforms PSOED on 16 test cases and ATOMU on 20 test cases.Furthermore,PSOED requires 3.15 times longer on average than HSIBA,while HSIBA exhibits inferior performance compared to ATOMU.

Key words: Floating-point operations, Rounding errors, Error detection, Hierarchical search, Interval partitioning analysis

中图分类号: 

  • TP311
[1] QI H,XU J,GUO S.Detection of the maximum error of mathematical functions[J].The Journal of Supercomputing,2018,74(11):6275-6290.
[2] XIAO A X,ZHANG S X,TANG E Y,et al.An empirical libra-ry-guided floating-point program optimization acceleration strategy[J].Chinese Journal of Computers,2022,45(9):2014-2028.
[3] HAO J W,YANG H R,XIA Y Y,et al.A floating-point expression precision optimization method based on multiple types of computation rewriting[J].Computer Science,2024,51(4):86-94.
[4] ZOU D M,ZENG M H,XIONG Y F,et al.Detecting floating-point errors via atomic conditions[C]//Proceedings of the ACM on Programming Languages.2019:1-27.
[5] CHIANG W F,GOPALAKRISHNAN G,RAKAMARIC Z,et al.Efficient search for inputs causing high floating-point errors[C]//Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.2014:43-52.
[6] YI X,CHEN L,MAO X,et al.Efficient automated repair ofhigh floating-point errors in numerical libraries[C]//Procee-dings of the ACM on Programming Languages(POPL).2019.
[7] WANG Z,YI X,YU H,et al.Detecting High Floating-Point Errors via Ranking Analysis[C]//2022 29th Asia-Pacific Software Engineering Conference(APSEC).2022:397-406.
[8] YAND H,XU J,HAO J,et al.Detecting Floating-Point Ex-pression Errors Based Improved PSO Algorithm[J].IET Software,2023,2023(1):6681267.
[9] POLI R,KENNEDY J,BLACKWELL T.Particle swarm optimization:An overview[J].Swarm Intelligence,2007,1:33-57.
[10] MULLER J M,BRUNIE N,DE DINECHIN F,et al.Handbook of floating-point arithmetic[M].Basel,Switzerland:Birkhäuser,2018.
[11] IEEE Computer Society.IEEE Standard for Floating Point Arithmetic:IEEE Std 754-2008[S].Piscataway,NJ:IEEE,2008:1-70.
[12] MULLER J M.On the definition of ulp(x)[R].Montbonnot,Saint Martin,France:Laboratoire de l’Informatique du Parallélisme,2005.
[13] GOLDBERG D.What every computer scientist should know about floating-point arithmetic[J].ACM Computing Surveys,1991,23(1):5-48.
[14] BAO T,ZHANG X.On-the-fly detection of instability problems in floating-point program execution[C]//Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages &Applications(OOPSLA).2013:817-832.
[15] DAMOUCHE N,MARTEL M,PANCHEKHA P,et al.To-ward a Standard Benchmark Format and Suite for Floating-Point Analysis[C]//International Workshop on Numerical Software Verification.Cham:Springer International Publishing,2016:63-77.
[16] ZOU D,WANG R,XIONG Y,et al.A genetic algorithm for detecting significant floating-pointinaccuracies[C]//2015 IEEE/ACM 37th IEEE International Conference on Software Engineering.IEEE,2015:529-539.
[17] BENZ F,HILDEBRANDT A,HACK S.A dynamic program analysis to find floating-point accuracy problems[J].ACM SIGPLAN Notices,2012,47(6):453-462.
[18] PANCHEKHA P,SANCHEZ-STERN A,WILCOX J R,et al.Automatically improving accuracy for floating point expressions[J].ACM SIGPLAN Notices,2015,50(6):1-11.
[19] GUO H,RUBIO-GONZÁLEZ C.Efficient generation of error-inducing floating-point inputs via symbolic execution[C]//Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering.2020:1261-1272.
[20] COUSOTP,COUSOT R.Abstract interpretation:past,present and future[C]//Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic(CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science(LICS)(CSLLICS’14).Association for Computing Machinery,2004:1-10.
[21] HICKEY T,JU Q,VAN EMDEN M H.Interval arithmetic:From principles to implementation[J].Journal of the ACM,2001,48(5):1038-1068.
[22] BALDONI R,COPPA E,D’ELIAD C,et al.A Survey of Symbolic Execution Techniques[C]//ACM Computing Surveys.2018.
[23] DARULOVA E,IZYCHEVA A,NASIR F,et al.Daisy-frame-work for analysis and optimization of numerical programs(Tool Paper)[C]//Tools and Algorithms for the Construction and Analysis of Systems:24th International Conference(TACAS 2018),Held as Part of the European Joint Conferences on Theory and Practice of Software(ETAPS 2018).Springer International Publishing,2018:270-287.
[24] SOLOVYEV A,BARANOWSKI M S,BRIGGS I,et al.RigorousEstimation of Floating-Point Round-Off Errors with Symbolic Taylor Expansions[J].ACM Transactions on Programming Languages and Systems(TOPLAS),2018,41(1):1-39.
[25] DARULOVA E,KUNCAK V.Towards a compiler for reals[J].ACM Transactions on Programming Languages and Systems(TOPLAS),2017,39(2):1-28.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市两江新区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发