{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,22]],"date-time":"2026-03-22T02:27:30Z","timestamp":1774146450411,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,12,8]],"date-time":"2020-12-08T00:00:00Z","timestamp":1607385600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2021,3,31]]},"abstract":"<jats:p>We identify a class of root-searching methods that surprisingly outperform the bisection method on the average performance while retaining minmax optimality. The improvement on the average applies for any continuous distributional hypothesis. We also pinpoint one specific method within the class and show that under mild initial conditions it can attain an order of convergence of up to 1.618, i.e., the same as the secant method. Hence, we attain both an improved average performance and an improved order of convergence with no cost on the minmax optimality of the bisection method. Numerical experiments show that, on regular functions, the proposed method requires a number of function evaluations similar to current state-of-the-art methods, about 24% to 37% of the evaluations required by the bisection procedure. In problems with non-regular functions, the proposed method performs significantly better than the state-of-the-art, requiring on average 82% of the total evaluations required for the bisection method, while the other methods were outperformed by bisection. In the worst case, while current state-of-the-art commercial solvers required two to three times the number of function evaluations of bisection, our proposed method remained within the minmax bounds of the bisection method.<\/jats:p>","DOI":"10.1145\/3423597","type":"journal-article","created":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T23:11:26Z","timestamp":1607555486000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality"],"prefix":"10.1145","volume":"47","author":[{"given":"I. F. D.","family":"Oliveira","sequence":"first","affiliation":[{"name":"Institute of Science, Engineering and Technology, Federal University of the Valleys of Jequitinhonha and Mucuri, Brazil"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0814-6314","authenticated-orcid":false,"given":"R. H. C.","family":"Takahashi","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Federal University of Minas Gerais, Brazil"}]}],"member":"320","published-online":{"date-parts":[[2020,12,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2013.04.001"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/14.4.422"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/355656.355659"},{"key":"e_1_2_1_4_1","unstructured":"S. C. Chapra and R. P. Canale. 2010. Numerical Methods for Engineers (6th ed.). McGraw-Hill Higher Education New York NY 202--220. S. C. Chapra and R. P. Canale. 2010. Numerical Methods for Engineers (6th ed.). McGraw-Hill Higher Education New York NY 202--220."},{"key":"e_1_2_1_5_1","first-page":"2","article-title":"A modified regula falsi method for computing the root of an equation","volume":"11","author":"Dowell M.","year":"1971","unstructured":"M. Dowell and P. Jarratt . 1971 . A modified regula falsi method for computing the root of an equation . ACM Trans. Math. Softw. 11 , 2 (June 1971), 168--174. M. Dowell and P. Jarratt. 1971. A modified regula falsi method for computing the root of an equation. ACM Trans. Math. Softw. 11, 2 (June 1971), 168--174.","journal-title":"ACM Trans. Math. Softw."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2701.2705"},{"key":"e_1_2_1_7_1","volume-title":"Improved Algorithms of Illinois\u2014Type for the Numerical Solution of Nonlinear Equations. Department of Computer Science Report","author":"Ford J. A.","unstructured":"J. A. Ford . 1995. Improved Algorithms of Illinois\u2014Type for the Numerical Solution of Nonlinear Equations. Department of Computer Science Report . University of Essex. J. A. Ford. 1995. Improved Algorithms of Illinois\u2014Type for the Numerical Solution of Nonlinear Equations. Department of Computer Science Report. University of Essex."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(77)90074-7"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01396051"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/29380.29862"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1953-0055639-3"},{"key":"e_1_2_1_12_1","first-page":"855","article-title":"On binary searching with nonuniform costs","volume":"31","author":"Laber Eduardo S.","year":"2012","unstructured":"Eduardo S. Laber , Ruy L. Milidi\u00fa , and Artur A. Pessoa . 2012 . On binary searching with nonuniform costs . SIAM J. Comput. 31 , 4 (2012), 855 -- 864 . Eduardo S. Laber, Ruy L. Milidi\u00fa, and Artur A. Pessoa. 2012. On binary searching with nonuniform costs. SIAM J. Comput. 31, 4 (2012), 855--864.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0906016"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/214408.214416"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2011.11.015"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.2307\/2001916"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0771-050X(76)90017-6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/214392.214396"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(89)90022-8"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1993.1003"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2307\/2153369"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359557"},{"key":"e_1_2_1_23_1","volume-title":"Numerical Recipes: The Art of Scientific Computing","author":"Press W. H.","year":"2007","unstructured":"W. H. Press , S. A. Teukolsky , W. T. Vetterling , and B. P. Flannery . 2007 . Numerical Recipes: The Art of Scientific Computing ( 6 th ed.). Cambridge University Press , Cambridge, UK , 442--486. W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery. 2007. Numerical Recipes: The Art of Scientific Computing (6th ed.). Cambridge University Press, Cambridge, UK, 442--486.","edition":"6"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCS.1979.1084580"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01832985"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958376.1958380"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1985-0771037-8"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01459080"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(85)90011-1"},{"key":"e_1_2_1_31_1","first-page":"1","article-title":"Comments on an improvement to the Brent\u2019s method","volume":"4","author":"Stage S. A.","year":"2013","unstructured":"S. A. Stage . 2013 . Comments on an improvement to the Brent\u2019s method . Int. J. Experim. Algor. 4 , 1 (2013), 1 -- 16 . S. A. Stage. 2013. Comments on an improvement to the Brent\u2019s method. Int. J. Experim. Algor. 4, 1 (2013), 1--16.","journal-title":"Int. J. Experim. Algor."},{"key":"e_1_2_1_32_1","first-page":"550","article-title":"Iterative methods for the solution of equations","volume":"8","author":"Traub J. F.","year":"1963","unstructured":"J. F. Traub . 1963 . Iterative methods for the solution of equations . Bell Tel. Lab. 8 , 4 (1963), 550 -- 551 . J. F. Traub. 1963. Iterative methods for the solution of equations. Bell Tel. Lab. 8, 4 (1963), 550--551.","journal-title":"Bell Tel. Lab."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/50063.51906"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/j.amc.2004.04.120","article-title":"Improved Muller method and bisection method with global and asymptotic superlinear convergence of both point and interval for solving nonlinear equations","volume":"166","author":"Wu X.","year":"2005","unstructured":"X. Wu . 2005 . Improved Muller method and bisection method with global and asymptotic superlinear convergence of both point and interval for solving nonlinear equations . Appl. Math. Comput. 166 , 2 (2005), 299 -- 311 . X. Wu. 2005. Improved Muller method and bisection method with global and asymptotic superlinear convergence of both point and interval for solving nonlinear equations. Appl. Math. Comput. 166, 2 (2005), 299--311.","journal-title":"Appl. Math. Comput."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 17th Symposium on Foundations of Computer Science. IEEE","author":"Yao A. C.","unstructured":"A. C. Yao and F. F. Yao . 1976. The complexity of searching an ordered random table . In Proceedings of the 17th Symposium on Foundations of Computer Science. IEEE , Houston, TX, 173--177. A. C. Yao and F. F. Yao. 1976. The complexity of searching an ordered random table. In Proceedings of the 17th Symposium on Foundations of Computer Science. IEEE, Houston, TX, 173--177."},{"key":"e_1_2_1_36_1","article-title":"An improvement to the Brent\u2019s method","volume":"2","author":"Zhang Z.","year":"2011","unstructured":"Z. Zhang . 2011 . An improvement to the Brent\u2019s method . Int. J. Experim. Algor. 2 , 1 (2011). Z. Zhang. 2011. An improvement to the Brent\u2019s method. Int. J. Experim. Algor. 2, 1 (2011).","journal-title":"Int. J. Experim. Algor."}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3423597","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3423597","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:50Z","timestamp":1750197710000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3423597"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,8]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,3,31]]}},"alternative-id":["10.1145\/3423597"],"URL":"https:\/\/doi.org\/10.1145\/3423597","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,8]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}