On 2014-01-07 16:18:48 +0000, Joseph S. Myers wrote: > On Tue, 7 Jan 2014, Vincent Lefevre wrote: > > > For some of them, this is proved. Here's a summary of the current > > status: > > > > http://tamadiwiki.ens-lyon.fr/tamadiwiki/images/c/c1/Lefevre2013.pdf > > Thanks for the details. What's the current state of the art on the > asymptotic cost of the exhaustive searches?
The theoretical bound is O(N^(2/3+epsilon)), where N is the number of inputs. In practice, for binary128 (N ~ 2^128), this is already unfeasible. -- Vincent Lefèvre <vinc...@vinc17.net> - Web: <http://www.vinc17.net/> 100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/> Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
