patternModerate
Efficient sampling from all positive integers to find the largest integer below a transition for f(n)
Viewed 0 times
theallsamplingefficientpositiveintegerslargesttransitionbelowfind
Problem
Let's say we want to find the smallest positive integer x for which some property A holds. We know that such an integer exists. However, we have no knowledge about the scale of x (i.e. x could be 7 or 5'142 or 17 Quadrillion or whatever).
We have a function f that returns true when evaluated at values larger or equal to x, f returns false when evaluated at values strictly smaller than x. Let's assume evaluating f at n has a runtime complexity of $O(n^2)$.
What is a reasonable (or even optimal) way of selecting integers to evaluate f at in order to find x while reducing runtime?
How would the answer change when the runtime complexity of f is different?
My thoughts:
Usually I would calculate the expected number of calculations needed and try to minimize that value. However, without any knowledge about the size of x I could not wrap my head around how I would do that since a uniform distribution over all positive does not make a lot of sense. Is there another type of distribution that can be used in such cases?
Further it does not make sense to me to evaluate every integer in increasing order until x is found. Intuitively, I would probably evaluate powers of 10 (i.e. f(10), f(100), f(1000)), but this is surely not optimal.
Any thoughts are appreciated, even just the keyword that would lead to successful google results.
We have a function f that returns true when evaluated at values larger or equal to x, f returns false when evaluated at values strictly smaller than x. Let's assume evaluating f at n has a runtime complexity of $O(n^2)$.
What is a reasonable (or even optimal) way of selecting integers to evaluate f at in order to find x while reducing runtime?
How would the answer change when the runtime complexity of f is different?
My thoughts:
Usually I would calculate the expected number of calculations needed and try to minimize that value. However, without any knowledge about the size of x I could not wrap my head around how I would do that since a uniform distribution over all positive does not make a lot of sense. Is there another type of distribution that can be used in such cases?
Further it does not make sense to me to evaluate every integer in increasing order until x is found. Intuitively, I would probably evaluate powers of 10 (i.e. f(10), f(100), f(1000)), but this is surely not optimal.
Any thoughts are appreciated, even just the keyword that would lead to successful google results.
Solution
Linear search is $0,1,2,3,4,\cdots k,\cdots$. ($O(n)$ steps to pass $n$.)
Exponential search is $1,2,4,8,16,\cdots2^k,\cdots$. ($O(\lg(n))$ steps to pass $n$.)
Doubly exponential search is $2,4,16,256,65536,\cdots2^{2^k},\cdots$. ($O(\lg(\lg(n)))$ steps to pass $n$.)
And so on.
After you have found a $\text{true}$, you can continue with dichotomic searches at the previous growth levels.
If you expect truly huge numbers, you can use even faster growing sequences, such as $2\uparrow^k2$. ($O(\lg^*(n))$ steps to pass $n$.)
There is no theoretical optimum.
Exponential search is $1,2,4,8,16,\cdots2^k,\cdots$. ($O(\lg(n))$ steps to pass $n$.)
Doubly exponential search is $2,4,16,256,65536,\cdots2^{2^k},\cdots$. ($O(\lg(\lg(n)))$ steps to pass $n$.)
And so on.
After you have found a $\text{true}$, you can continue with dichotomic searches at the previous growth levels.
If you expect truly huge numbers, you can use even faster growing sequences, such as $2\uparrow^k2$. ($O(\lg^*(n))$ steps to pass $n$.)
There is no theoretical optimum.
Context
StackExchange Computer Science Q#153516, answer score: 12
Revisions (0)
No revisions yet.