2 ms·
However, it would be interesting to find some pathological examples of pairs of lists whose sums of square roots compare almost equal if only approximated to so
by Sharlin 5y ago
However, it would be interesting to find some pathological examples of pairs of lists whose sums of square roots compare almost equal if only approximated to some reasonable precision, but diverge absurdly if the fully general algorithm is used, if such pairs even exist.
- vessenes 5y agoI am reasonably sure that this won’t happen, or said another way, a function that returns the minimum delta between any finite pairs of lists is a reasonably well behaved function wrt the length of the list and the size of the integers and doesnt just zoom off to infinitely close to zero ever. Said yet another way, the ways in which real numbers are dense is spooky and almost totally untied to how rationals work, and i do not believe you can get there from here using square roots.
- ChrisLomont 5y agoThis isn't true, which is why the problem lies in the complexity class listed in the article. Arbitrarily bad pathologies exist even for simple inputs.