Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A surprisingly hard CS problem: sums of square roots (2018)

shlegeris.com

Post reply on HN
Print view View original

181–189 of 189 posts

Re: A surprisingly hard CS problem: sums of square roots (2018)

#181

Post by tgflynn »

bshlgrs wrote: post #152
umvi wrote: post #44

It's hard to solve "generally", sure, but "practically", is there any application where extreme correctness of the algorithm would actually matter? Seems like if two huge lists sum to almost the exact same thing for tons of decimal places, then you can effectively treat them as equal. Sort of like how you only need like 5 or 6 digits of pi to get into orbit around the moon, etc.

(Author here) As far as I know, there are no cases where this actually matters.

In your post you say that a PSPACE algorithm exists. Do you have a reference for that algorithm ?

Another commenter here is saying the problem has an explicit exponential or worse lower bound.

If both of those claims are true that would prove P != PSPACE, which would be a very important result.

Re: A surprisingly hard CS problem: sums of square roots (2018)

#182

Post by tgflynn »

fdej wrote: post #180
tgflynn wrote: post #163

Earlier quoted context omitted.

Do you have a reference for that claim ?

Correcting myself, the bound is worse than exponential (so read "at least exponential in N"), but the point I wanted to make is that it is explicit. Again, this follows from the general theory of algebraic numbers: the degree and height of a sum, product or root of algebraic numbers can be bounded explicitly (resultants + Mignotte bound for factors), and finally root separation bounds can be applied to the resulting…

The author says that this problem is in PSPACE. That's not obvious to me because I don't know how you sum arbitrarily long binary numbers in polynomial space.

However if you and he are both right that would suffice to prove P != PSPACE, so this problem is potentially very important. Unfortunately I don't even know what this kind of problem is called, which makes googling a bit difficult.

Re: A surprisingly hard CS problem: sums of square roots (2018)

#183

Post by jepler »

ChrisLomont wrote: post #171
thomasahle wrote: post #107

Earlier quoted context omitted.

The Master's argument would imply Ω(n) time, The matrix exponentiation algorithm would take O(nlogn) time, since you have to multiply large numbers, and this takes nlogn with the best known algorithms (FFT). I don't think there are any O(n) algorithms.

There are closed forms for F(n), and even faster ways to get it without needing to compute the sequence. You're conflating n power with requiring n digit multiplications. This isn't true. The size of needed numbers is smaller for most problems of this type. And special structure is likely exploitable. A simple proof is to write the recurrence as a matrix, take powers, diagonalize and read off the result. If I recall,…

gmp uses a particular recurrence relation to exactly compute fib(x) in about log(x) steps[0]. Of course, the digits of the numbers it has to multiply also increase. It's fast-ish up to fib(128 million) or so but soon after that you run into the limit of the size of numbers in gmp, which are limited to being less than 2^31 * 32 bits long or something.

[0]: https://gmplib.org/manual/Fibonacci-Numbers-Algorithm

Re: A surprisingly hard CS problem: sums of square roots (2018)

#184

Post by varelse »

zodiac wrote: post #170
varelse wrote: post #80

Earlier quoted context omitted.

Sure and there are a lot of simple ways to improve the accuracy of the simple approach before you go for the pure math sledgehammer here. It's all a question of how accurate the answer needs to be. For example, It's pretty easy to come up with an FP64 error bound on the sum. And if the difference between the two sums is greater than that error bound you don't need to do anything more complicated. Where this would get…

I think people are downvoting you because you seem like you're attacking a strawman. We all agree that 1) it's an interesting math problem 2) for real-life instances, the FP64 solution is good enough. For e.g. when you say "anything beyond that is likely unnecessary gold plating", I know you mean "exact algorithms (like the PSPACE algorithm) are unnecessary for solving real-life instances", but without context it sou…

Back in the day, the downvotes here would flow like a river at the suggestion that an engineering career behooved one to understand Calculus and Linear Algebra with Statistics and Differential Equations if possible thrown in for good measure because Peter Thiel said college degrees were worthless and he was even offering $100K to some lucky winners to prove his point. Admittedly, I would have probably taken that offer had I been 18 and then gone to college afterwards, but it seemed to deliver mixed results.

For the above math comes up again and again writing software. Pure math like real analysis, graduate level algebra, number theory and topology not so much. I'm guessing the rise of AI demonstrated the previous mindset against math was poppycock all along so now we've gone to the opposite extreme and made it a religion? I think people are bringing their own biases into that interpretation and you are right about which biases.

But, also, not my problem. My personal bias is that I recognize this problem as exactly the sort of thing that gets brought up as a gotcha interview question by people who couldn't come up with that exact solution themselves yet understand it just enough to use it to make an interviewee squirm.

Re: A surprisingly hard CS problem: sums of square roots (2018)

#185

Post by thomasahle »

ChrisLomont wrote: post #171
thomasahle wrote: post #107

Earlier quoted context omitted.

The Master's argument would imply Ω(n) time, The matrix exponentiation algorithm would take O(nlogn) time, since you have to multiply large numbers, and this takes nlogn with the best known algorithms (FFT). I don't think there are any O(n) algorithms.

There are closed forms for F(n), and even faster ways to get it without needing to compute the sequence. You're conflating n power with requiring n digit multiplications. This isn't true. The size of needed numbers is smaller for most problems of this type. And special structure is likely exploitable. A simple proof is to write the recurrence as a matrix, take powers, diagonalize and read off the result. If I recall,…

You seem to be saying that if we don't want to compute F(n), but just some numbers a, e such that F(n) ~ a*10^e, then we can do it faster than nlogn time. That's of course true.

However, that's a different problem than actually computing the n digits of F(n). Even computing the first n digits of ((1+sqrt5)/2)^n probably takes nlogn time.

You say "use the bits of n similar to power mod". I suppose you mean repeated squaring. But what happens in the last of the logn steps of that procedure?: You multiply two n/2 bit numbers.

Re: A surprisingly hard CS problem: sums of square roots (2018)

#186

Post by ChrisLomont »

thomasahle wrote: post #185
ChrisLomont wrote: post #171

Earlier quoted context omitted.

There are closed forms for F(n), and even faster ways to get it without needing to compute the sequence. You're conflating n power with requiring n digit multiplications. This isn't true. The size of needed numbers is smaller for most problems of this type. And special structure is likely exploitable. A simple proof is to write the recurrence as a matrix, take powers, diagonalize and read off the result. If I recall,…

You seem to be saying that if we don't want to compute F(n), but just some numbers a, e such that F(n) ~ a*10^e, then we can do it faster than nlogn time. That's of course true. However, that's a different problem than actually computing the n digits of F(n). Even computing the first n digits of ((1+sqrt5)/2)^n probably takes nlogn time. You say "use the bits of n similar to power mod". I suppose you mean repeated sq…

No, I am not saying that. I am saying we can compute F(n) exactly in O(log n) time. All the digits. That Fibonacci identity I posted allows computing exactly every single integer digit by rounding at the end, because the other term goes to zero as n goes to infinity, and that other term is always less than 1.

There are papers showing the complexity I claimed is true. For example, [1]. Algorithm 3.7, on page 15, and I quote: "Hence, with constant time arithmetic, the time complexity is O(lg n). The space complexity is also logarithmic in n." It uses the same ideas as the algorithm I suggested.

Also the two algorithms in section 3.8 achieve the same. The algorithm in section 11 achieves the same.

These use, as I used above, as is common for algorithms, what is called constant time arithmetic. This is how pretty much every textbook you will find uses these terms. Otherwise, even simple things like Quick Sort are no longer O(n log n) in the number of items, because as those items grow without bound, if the arithmetic does also, you end up with (often) more factors of n or log n in your final complexity.

For example, here is the bit complexity of quicksort [2], which is O(n log n log n) instead of the usual O(n log n). This concept is used so rarely that I don't think I've ever heard another person state it. People state the O(n log n) complexity, which is the standard for constant time arithmetic.

>You multiply two n/2 bit numbers.

You keep mixing your ideas for complexity. To specify the problem for computing F(n) you need not n bits - you need log n bits. So the input for this problem is not n, it is log n. Thus if you take your claim, and at the end multiply two (log n)/2 sized numbers, what do you get?

For example, if I tell you that you should compute F(1024), you do not need 1024 bits to tell you that. You need 10 = log 1024 bits to specify the problem. To describe the input to compute F(1,000,000) you do not need 1 million bits. You need 20.

Thus you do not multiply out n/2 bit numbers at the last step.

[1] https://arxiv.org/pdf/1803.07199.pdf

[2] https://www.ams.jhu.edu/~fill/papers/BitsQuickxabs.pdf

Re: A surprisingly hard CS problem: sums of square roots (2018)

#187

Post by xxpor »

FabHK wrote: post #141
xxpor wrote: post #136

Earlier quoted context omitted.

Multiple people have said they prefer not getting surprise PDFs. Could you elaborate on why? It's never something I've ever thought about. PDFs open in the browser now for most people, so it seems like it shouldn't make much difference?

I was going to add that some people on slow connections might not want to download large PDFs. However, in today's web, the html page with the abstract (one paragraph) was a 2.5 MB download, while the 15 page paper including a figure was just 800 kB.

That's honestly an incredible indictment of today's web, isn't it?

Re: A surprisingly hard CS problem: sums of square roots (2018)

#188

Post by doetoe »

xxpor wrote: post #136
JadeNB wrote: post #92

Earlier quoted context omitted.

Personally, I prefer not to get surprise PDFs; but that's just personal. A better reason is that linking to the abstract page lets you navigate easily around the arXiv from there, including to the PDF if you desire; but there is no 1-click way to get from the PDF back to the abstract. (Of course, it's an easy matter of address munging, but even easier is not to have to do the munging.) A perhaps less satisfying reaso…

Multiple people have said they prefer not getting surprise PDFs. Could you elaborate on why? It's never something I've ever thought about. PDFs open in the browser now for most people, so it seems like it shouldn't make much difference?

In my particular case PDFs linked from hacker news (accessed through the nextcloud feed reader) end up in my phone's downloads, which in that way fills up with PDFs I only wanted to read once.

Re: A surprisingly hard CS problem: sums of square roots (2018)

#189

Post by saagarjha »

bshlgrs wrote: post #151
amelius wrote: post #139

> comparing sums of square roots is actually kind of a common subtask in eg computational geometry, so a bunch of their problems (including “shortest path through a graph in Euclidean space”!) are as-far-as-we-know extremely hard. But the question then arises: do we always need to solve these problems to their fullest precision? Can we perhaps leave some ambiguity, and let the system gracefully deal with it? E.g. I d…

Yeah, afaik this problem is totally unimportant in practice.

Wait until it ends up being used in some other important field of math.
Post reply on HN