4 ms·

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

by jerf 5y ago

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 representation of the shortest of the two numbers. Our IEEE-based intuition sees that and goes wha? But you can also build a separate intuition based on the arbitrary representation that would make this easy to both understand and intuit. It's really easy to get into PSPACE with arbitrary precision. Heck, it's pretty easy to get into EXPSPACE and almost any other prefix to "SPACE" you want, because it's easy to stipulate very close numbers and transforms on those very close numbers that require obscene precision to be sure you're correct. If you work in this sort of mind space all the time, it's perfectly precise to talk about arbitrary-precision numbers. But the real universe we live in bottoms out at 10^-35 meters or so, our practical ability to be precise a dozen or two orders of magnitude sooner than that at a minimum (and often another dozen for macroscopic work), and the practical impact of this is minimal because in practice, the first Haskell solution in that post is essentially correct in our real universe 99.9% of the time, even though it is glaringly wrong mathematically, because in the real universe we never have hundreds of digits of precision, and that's where our intuition is built.

nemo1618 5y ago
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!"
- thomasahle 5y ago
  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.
  - ChrisLomont 5y ago
    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.
    - jepler 5y ago
      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 https://gmplib.org/manual/Fibonacci-Numbers-Algorithm
    - thomasahle 5y ago
      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.
      - ChrisLomont 5y ago
        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 https://arxiv.org/pdf/1803.07199.pdf [2] https://www.ams.jhu.edu/~fill/papers/BitsQuickxabs.pdf https://www.ams.jhu.edu/~fill/papers/BitsQuickxabs.pdf
pdonis 5y ago
> the real universe we live in bottoms out at 10^-35 meters or so We don't actually know this. It's a plausible speculation in quantum gravity, but we have no evidence either way. This length scale is about 18 orders of magnitude smaller than the smallest scale we can probe with experiments, so we're highly unlikely to get any evidence either way any time soon.

by jerf 5y ago

nemo1618 5y ago

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

thomasahle 5y ago
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.
- ChrisLomont 5y ago
  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.
  - jepler 5y ago
    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 https://gmplib.org/manual/Fibonacci-Numbers-Algorithm
  - thomasahle 5y ago
    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.
    - ChrisLomont 5y ago
      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 https://arxiv.org/pdf/1803.07199.pdf [2] https://www.ams.jhu.edu/~fill/papers/BitsQuickxabs.pdf https://www.ams.jhu.edu/~fill/papers/BitsQuickxabs.pdf

pdonis 5y ago

> the real universe we live in bottoms out at 10^-35 meters or so We don't actually know this. It's a plausible speculation in quantum gravity, but we have no evidence either way. This length scale is about 18 orders of magnitude smaller than the smallest scale we can probe with experiments, so we're highly unlikely to get any evidence either way any time soon.