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

171–180 of 189 posts

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

#171

Post by ChrisLomont »

thomasahle wrote: post #107
nemo1618 wrote: post #52

Earlier quoted context omitted.

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.

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, the answer is something like F(n) is ((1+sqrt5)/2)^n + ((1-sqrt5)/2)^n.

Then you can only compute part of the first term, the second is small.

Then use the bits of n similar to power mod to compute powers in log n steps.

You only need something like log n precision along the way.

This should reach O(n) easily, perhaps below.

Quick check shows O(log n) steps in standard constant time ops.

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

#172

Post by ChrisLomont »

vessenes wrote: post #67
Sharlin wrote: post #61

Earlier quoted context omitted.

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.

I 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…

This 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.

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

#173

Post by kadoban »

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?

There may be more of a security risk with PDFs, hard to say though. This was likely more of an issue back when using an external program to view them was a requirement.

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

#174

Post by bmm6o »

chii wrote: post #169
cevi wrote: post #142

An example of a tricky case: which is bigger, sqrt(1000000) + sqrt(1000018) + sqrt(1000036) + sqrt(1000059) + sqrt(1000083), or sqrt(1000003) + sqrt(1000011) + sqrt(1000048) + sqrt(1000050) + sqrt(1000084)? (They agree to more than 20 decimal digits of precision!)

i wonder if you can use logs to do this faster: 1. simplify the sqrt by log of each number, i.e. log(sqrt(x)) = 1/2 * log(x) 2. since sum of logs is the log of the products, i.e., log(a) + log(b) = log(ab) you can simplify the whole expression by multiplying all the numbers, taking the log of the product once (which i presume is much faster), then multiplying by 1/2 since logs are strictly increasing, the resulting n…

I think the + and × are backwards from the way that would be helpful. But if you think it would work, try writing it out in detail.

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

#175

Post by chii »

bmm6o wrote: post #174
chii wrote: post #169

Earlier quoted context omitted.

i wonder if you can use logs to do this faster: 1. simplify the sqrt by log of each number, i.e. log(sqrt(x)) = 1/2 * log(x) 2. since sum of logs is the log of the products, i.e., log(a) + log(b) = log(ab) you can simplify the whole expression by multiplying all the numbers, taking the log of the product once (which i presume is much faster), then multiplying by 1/2 since logs are strictly increasing, the resulting n…

I think the + and × are backwards from the way that would be helpful. But if you think it would work, try writing it out in detail.

let met try, for [a, b, c], and [d, e, f]

1. Take the log of all terms (allowed, because log keeps the sum monotonic):

log(sqrt(a)) + log(sqrt(b)) + log(sqrt(c))

2. pull out the sqrt from the log:

1/2 * log(a) + 1/2 * log(b) +1/2 * log(c)

3. factor out the 1/2:

1/2 * (log(a) + log(b) + log(c))

4. sum of logs can be rewritten as a log of product:

1/2 * log (a * b * c)

5. compute log of (a * b * c), and halve it. Ditto with log of (d * e * f). This should give a number which is proportional to the original sum of sqrt.

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

#176

Post by jakear »

chii wrote: post #175
bmm6o wrote: post #174

Earlier quoted context omitted.

I think the + and × are backwards from the way that would be helpful. But if you think it would work, try writing it out in detail.

let met try, for [a, b, c], and [d, e, f] 1. Take the log of all terms (allowed, because log keeps the sum monotonic): log(sqrt(a)) + log(sqrt(b)) + log(sqrt(c)) 2. pull out the sqrt from the log: 1/2 * log(a) + 1/2 * log(b) +1/2 * log(c) 3. factor out the 1/2: 1/2 * (log(a) + log(b) + log(c)) 4. sum of logs can be rewritten as a log of product: 1/2 * log (a * b * c) 5. compute log of (a * b * c), and halve it. Ditto…

> Take the log of all terms (allowed, because log keeps the sum monotonic)

It seems you're employing a + b log(a) + log(b) (the real rule is a * b log(a) + log(b) log(a * b)

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

#177

Post by 3PS »

chii wrote: post #175
bmm6o wrote: post #174

Earlier quoted context omitted.

I think the + and × are backwards from the way that would be helpful. But if you think it would work, try writing it out in detail.

let met try, for [a, b, c], and [d, e, f] 1. Take the log of all terms (allowed, because log keeps the sum monotonic): log(sqrt(a)) + log(sqrt(b)) + log(sqrt(c)) 2. pull out the sqrt from the log: 1/2 * log(a) + 1/2 * log(b) +1/2 * log(c) 3. factor out the 1/2: 1/2 * (log(a) + log(b) + log(c)) 4. sum of logs can be rewritten as a log of product: 1/2 * log (a * b * c) 5. compute log of (a * b * c), and halve it. Ditto…

This doesn't work. Even if you assume sqrt(a) + sqrt(b) > sqrt(c) + sqrt(d), that doesn't necessarily mean that log(sqrt(a)) + log(sqrt(b)) > log(sqrt(c)) + log(sqrt(d)). For example, let a = 1, b = 100, c = 25, d = 25. Then

> sqrt(1) + sqrt(100)

11.0

> sqrt(25) + sqrt(25)

10.0

> log(sqrt(1)) + log(sqrt(100))

2.302585092994046

> log(sqrt(25)) + log(sqrt(25))

3.2188758248682006

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

#178

Post by chii »

jakear wrote: post #176
chii wrote: post #175

Earlier quoted context omitted.

let met try, for [a, b, c], and [d, e, f] 1. Take the log of all terms (allowed, because log keeps the sum monotonic): log(sqrt(a)) + log(sqrt(b)) + log(sqrt(c)) 2. pull out the sqrt from the log: 1/2 * log(a) + 1/2 * log(b) +1/2 * log(c) 3. factor out the 1/2: 1/2 * (log(a) + log(b) + log(c)) 4. sum of logs can be rewritten as a log of product: 1/2 * log (a * b * c) 5. compute log of (a * b * c), and halve it. Ditto…

> Take the log of all terms (allowed, because log keeps the sum monotonic) It seems you're employing a + b log(a) + log(b) (the real rule is a * b log(a) + log(b) log(a * b)

ahh, that is where i tripped up! Good to see!

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

#179

Post by eurasiantiger »

samyrasmy wrote: post #166

Here is my attempt at proving that this can be done in P-time. I am using the fact that square roots can be expressed as periodic continued fractions, and that there is an upper bound on the period of these fractions which must thus be unique. Please tell me if there are any issues! I hope this holds :) The period of the square root of n is less than k1 * (sqrt(n) log (log (log (n))) ) = Lm(n) We can find this period…

Can we get a validity test and benchmark comparing this solution to the generally accepted one?

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

#180

Post by fdej »

tgflynn wrote: post #163
fdej wrote: post #84

Earlier quoted context omitted.

Yes, the worst-case complexity is exponential in N, but the wording in the article could lead you to believe that no explicit exponential bound is known, which is false.

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 polynomial.

Post reply on HN