5 ms·

An example of a tricky case: which is bigger, sqrt(1000000) + sqrt(1000018) + sqrt(1000036) + sqrt(1000059) + sqrt(1000083), or sqrt(1000003) + sqrt(1000011) +

by cevi 5y ago

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!)

kccqzy 5y ago
The second is bigger, but only by ~2.3 * 10^(-13). Very good illustration indeed.
chii 5y ago
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 number is still going to be bigger if it originally was going to be bigger, and now you don't need to have performed all those sqrts. Now you've reduced the problem to computing 1 log to an arbitrary precision...not sure how one does that actually...
- bmm6o 5y ago
  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.
  - chii 5y ago
    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.
    - jakear 5y ago
      > Take the log of all terms (allowed, because log keeps the sum monotonic) It seems you're employing a + b < c <=> log(a) + log(b) < log(c), which doesn't hold (consider 10, 10, and 20). (the real rule is a * b < c <=> log(a) + log(b) < log(c)), because log(a) + log(b) <=> log(a * b)
      - chii 5y ago
        ahh, that is where i tripped up! Good to see!
    - 3PS 5y ago
      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

by cevi 5y ago

kccqzy 5y ago

The second is bigger, but only by ~2.3 * 10^(-13). Very good illustration indeed.

chii 5y ago

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 number is still going to be bigger if it originally was going to be bigger, and now you don't need to have performed all those sqrts. Now you've reduced the problem to computing 1 log to an arbitrary precision...not sure how one does that actually...

bmm6o 5y ago
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.
- chii 5y ago
  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.
  - jakear 5y ago
    > Take the log of all terms (allowed, because log keeps the sum monotonic) It seems you're employing a + b < c <=> log(a) + log(b) < log(c), which doesn't hold (consider 10, 10, and 20). (the real rule is a * b < c <=> log(a) + log(b) < log(c)), because log(a) + log(b) <=> log(a * b)
    - chii 5y ago
      ahh, that is where i tripped up! Good to see!
  - 3PS 5y ago
    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