Given a function of real numbers f(x), I can create approximations to arbitrary precision using Taylor polynomials.

Is there something equivalent in the discrete case when I have a sequence of integers that I want to approximate to arbitrary precision.

  • 1
    $\begingroup$ Do you know more things about the sequence? Is it bounded? Does it have many instances of the same entry? Is it monotone? Perhaps you can compute some discrete Fourier transform, and use the big coefficientsvsomehow? $\endgroup$ – Per Alexandersson Jul 21 '18 at 11:37
  • $\begingroup$ Yes, it has many many instances of the same entry. Every value is small. It is not monotone. I would say every value is in the 0-255 range. $\endgroup$ – IKnowNothing Jul 22 '18 at 0:02
  • $\begingroup$ Do you know the sequence (if so, how do you compute it), or are you looking for a pseudo-random number generator? $\endgroup$ – Per Alexandersson Jul 22 '18 at 6:38
  • $\begingroup$ There are no random numbers in the sequence. The sequence, due to the size, is not knowable in practice. That is why I am looking to create increasingly better approximations. A good approximation can be used to compute mostly correct values. In theory, the entire sequence could be computed and stored, but there is not enough storage and computing power in the world. $\endgroup$ – IKnowNothing Jul 23 '18 at 14:13

One reason for approximating a real function by Taylor polynomials is to use properties of polynomials (and the real numbers) to estimate the function at an unknown value. In order for this to be useful, f has to behave consistently with the assumptions needed to use the approximations. In particular, f has to be a certain kind of continuous (normal or Hoelder, say). Or one assumes f is differentiable, and then uses the derivative of the approximation. Or one assumes f is bounded on an interval, but is increasing and larger than the input outside the interval. The key thing is to choose a property that you want f to have or believe it to have, then you use the tools and components which support that property or set of properties.

One often has something similar with sequences. As two examples, there is the one-complexity of an integer which has somewhat erratic behaviour, but has logarithmic lower and upper bounds, and whose value at certain integers is known exactly, and at other integers there are quickly computed approximations with provably small error. Another function is the sequence of prime gaps, which grows less slowly, more erratically, and on which much computation has been done, but approximations are poor still. We can say there are lots of n for which $ p_{n+1} - p_n $ is equal to 30, and even have an idea of how many, but we can't tell you which n have that value unless n is less than 10^19, and even then there is the issue of computational energy and retrieval energy involved.

So yes, there are methods, but you have to use a property that your sequence has or that you believe it has. Until I know of those properties, I can't tell you a wise way to proceed.

Gerhard "Wisdom Comes Only After Experiencing" Paseman, 2018.07.23.

  • $\begingroup$ Thank you for the answer. Unfortunately the sequence does not have nice properties and I have concluded that trying to approximate it will be futile. $\endgroup$ – IKnowNothing Jul 30 '18 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.