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

101–110 of 189 posts

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

#101

Post by readams »

tzs wrote: post #95

I wonder if comparing powers of sums would help? Suppose one of the sequences was 3, 7, 15, 30, and consider s = √[3] + √7 + √15 + √30. Then s^2 = 55 + 30 √2 + 6 √5 + 6 √10 + 2 √21 + 2 √105 + 2 √210. s^3 = 159 √3 + 90 √6 + 151 √7 + 90 √14 + 135 √15 + 105 √30 + 18 √35 + 18 √70. ... s^30 = 1679613741139712617544067791402275 + 1187666266098277047375460186425450 √2 + 750901847525954802822187362608010 √5 + 530967788407084…

If you can immediately come up with an algorithm for a well-studied computer science problem, then it's very likely the approach isn't going to work out.

Notably in your case you've just converted high-precision floating point into even-higher-precision integer math. So the problem here that's inherent, which it that you might have to look at a very large number of bits of precision to find the differences, hasn't been sidestepped.

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

#102

Post by PaulHoule »

ted_dunning wrote: post #86
PaulHoule wrote: post #9

It reminds me of this problem. When you plot the motion of conservative dynamical systems, say this one https://en.wikipedia.org/wiki/Standard_map you get these chaotic areas that look like television static on the map. I was reading an 1987 article from Byte magazine that reminded me of a conversation I had when I was working on my PhD, which is that every plot like this you see is wrong because these are done with…

Yes. every plot of a chaotic system is grossly wrong. But the cool thing is that it is imperceptibly different from another plot that is correct. this is a consequence of the shadowing theorem that says that while any finitely computed sequence has unavoidable errors, there is a sequence arbitrarily close to the numbers you do compute. (don't hold me to rigorous statements here, it has been many years) (the gist is r…

My understanding is the shadowing lemma is controversial. For instance it applies to the chaotic orbits but not the stable orbits that are embedded in them.

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

#103

Post by kadoban »

munificent wrote: post #100

> I’m going to update towards thinking that integers and square roots are much scarier, richer objects than I’d thought. I’ve updated to being more scared of real numbers than I used to be—they have all these sketchy properties like “almost none of them have finite descriptions”. Real numbers, and sets, and logical statements, have all started feeling to me like Cthuluesque monstrosities whose appearances are only to…

> Maybe this is just me knowing very little about the field.

Can't tell if pun. Either way, it's pretty good.

https://en.wikipedia.org/wiki/Field_(mathematics)

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

#104

Post by ogogmad »

munificent wrote: post #100

> I’m going to update towards thinking that integers and square roots are much scarier, richer objects than I’d thought. I’ve updated to being more scared of real numbers than I used to be—they have all these sketchy properties like “almost none of them have finite descriptions”. Real numbers, and sets, and logical statements, have all started feeling to me like Cthuluesque monstrosities whose appearances are only to…

Looks like Presburger Arithmetic [1] versus Peano Arithmetic [2].

[1] - https://en.wikipedia.org/wiki/Presburger_arithmetic

[2] - https://en.wikipedia.org/wiki/Peano_axioms

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

#105

Post by ted_dunning »

SilasX wrote: post #73

Stupid questions: 1) It seems like all the difficulty is from the fact that the representation of the square roots involves a non terminating sequence of digits requiring high precision. So don’t you have this problem with all irrational functions, not just square root? Eg logarithm, sine, exponent from irrational base. (Does it make a difference that sine is bounded?) 2) Do you have the same problem (difficulty bein…

1) Not all representations of square roots have non-terminating form.

Continued fractions, for instance, reach a repetitive cycle.

Other irrational functions have other patterns.

2) No. If you are just doing sums, the cost is O(N) in time and space where N is the total number of bits in the input. If the inputs are large (i.e. N is big) then you have more time to compute the answer.

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

#106

Post by pvg »

JadeNB wrote: post #92
balnaphone wrote: post #91

Earlier quoted context omitted.

May I ask, for what reason, please?

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…

These are fine but pretty idiosyncratic. HN doesn't have citation rules so the 'always' seems overstated. People linking papers are already going the extra mile for the benefit of others and we don't really need to berate them about how they're holding their generosity wrong.

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

#107

Post by thomasahle »

nemo1618 wrote: post #52
jerf wrote: post #24

Earlier quoted context omitted.

I would say that imprecision is somewhat artificially induced by the fact we so thoroughly use IEEE floats that we tend to assume that they are the only numbers. When invoking arbitrary-precision floats (or equivalent), pretty much all numerical calculations get a lot harder than we intuit instantly. So much as comparing one number to another without taking a square root goes from O(1) to O(n) for n = the representat…

Good example of this: What is the complexity of the fastest algorithm that prints the nth Fibonacci number? Novice: "O(n), because you have to iterate from 0..n." Expert: "O(log n), because we can use matrix exponentiation." Master: "O(n), because F(n) has O(n) digits to print!"

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.

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

#108

Post by yccs27 »

readams wrote: post #101
tzs wrote: post #95

I wonder if comparing powers of sums would help? Suppose one of the sequences was 3, 7, 15, 30, and consider s = √[3] + √7 + √15 + √30. Then s^2 = 55 + 30 √2 + 6 √5 + 6 √10 + 2 √21 + 2 √105 + 2 √210. s^3 = 159 √3 + 90 √6 + 151 √7 + 90 √14 + 135 √15 + 105 √30 + 18 √35 + 18 √70. ... s^30 = 1679613741139712617544067791402275 + 1187666266098277047375460186425450 √2 + 750901847525954802822187362608010 √5 + 530967788407084…

If you can immediately come up with an algorithm for a well-studied computer science problem, then it's very likely the approach isn't going to work out. Notably in your case you've just converted high-precision floating point into even-higher-precision integer math. So the problem here that's inherent, which it that you might have to look at a very large number of bits of precision to find the differences, hasn't be…

I guess you’re right in your first sentence, but it often helps to study some (semi-)obvious algorithms and analyze why that approach won‘t work.

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

#109

Post by JadeNB »

pvg wrote: post #106
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…

These are fine but pretty idiosyncratic. HN doesn't have citation rules so the 'always' seems overstated. People linking papers are already going the extra mile for the benefit of others and we don't really need to berate them about how they're holding their generosity wrong.

I didn't mean to come across as berating, but rather as suggesting a better way to link. I hoped that 'request' and 'please' would set the proper tone, but am certainly open to better ways of wording it. I meant 'always' to indicate that I specifically wasn't just complaining pointlessly about the present case, but rather talking about future links; but I can see how it came across like the scolding 'always' as in a phrase "you always do this."
Post reply on HN