In many practical problems, it is important to take into account that our computational and measuring resources are limited. In this paper, we overview main resource limitations for diferent types of computers, and we provide two case studies explaining how to best take this resource limitation into account. What are the goals of science and engineering. We want to know what will happen in the future, and we want to decide what to do to make this future better. In a nutshell: • predicting the future is what science is about, and • deciding what to do is more the area of engineering.
• to predict where the tornado will do in the next 15 minutes, we need to spend several hours on a high-performance computer; • by that time, the tornado has already moved and caused damage.
Our resources are limited. In principle, for the same computational problem, we may have diferent algorithms. Which algorithm should we select?
Traditional approach of theoretical computer science uses asymptotic analysis to compare diferent algorithms. For example, we analyze how the computation time grows with the size of the input, and we select an algorithm that leads to the shortest possible time for large . This analysis implicitly assumes that we can have an unlimited amount of resources: • we can have inputs of arbitrary large size , • we can have an arbitrary large memory to store this data and to store all needed intermediate results, • we can perform an arbitrary large number of computations, etc.
In practice, our resources are limited. It is therefore important to consider how this limitation afect computations and measurements.
• we provide a brief overview of the corresponding resource limitations, and • we also present two case studies explaining, in some detail, how to take these resource limitations into account.
Comment. In most cases, we focus on our own related results – although, of course, in each of these problems, there are many other results and techniques. The reason for this selection is that the results that we cite are usually mathematically reasonably simple – this is why we selected them: for our own results, we know how we can simplify these results into easy-to-follow not-too-complex ones.
We believe that overall, these results provide a good introduction to the great variety of related problems.
• traditional (white-box) computing and • practically important black-box computing.
White-box computing corresponds to the usual analysis of theoretical computer science, when we know, step-by-step, what our algorithms are doing. This corresponds to: • situations when we write our own code “from scratch”, and • situations when we only use open-source software.
In practice, however, we often use proprietary code, i.e., a code that its producer does not explain. We can use it, but we are not allowed to see the algorithm – we only see the results. Similarly, in defense applications, we may need to use classified code – e.g., the code used to control the corresponding devices. Three types of situations. In our analysis, we will distinguish between three diferent computational situations.
• One such situation is regular-scale computing, when we perform computations on a usual computer, be it a single laptop of an afordable computer cluster. • Regular-size computations work well in many cases, but, as we have mentioned earlier, there are many practical situations where regular-scale computing is not suficient, where we need large-scale computing – what is usually called high-performance computing. • For some situations, the opposite is true: we do not need even the full computational power of a regular laptop, it is suficient to use limited computational power of an easierto-carry smaller device such as a cell phone or a smart watch. It is natural to call such situations small-scale computing.
Let us describe what are the typical resource limitations of these three types of situations – and what can we do to best takes these resource limitations into account.
Resource limitations of small-scale computing: energy. For small-scale computing – such as computing on cell phones – by definition, computational ability is not a problem. The main need for such small-scale devices comes from the fact that regular computers are not very portable: it is easier to carry a cell phone than a computer.
This portability is a problem: to perform computations, we need energy. For a more or less stationary device like a regular computer, this is not a problem: we just plug in the computer, and get the energy non-stop. For portable devices, energy is a problem: we can only plug it in once in a while, and in a small volume, we can only a limited amount of energy. So, for such devices, the main resource limitation is energy.
This require a serious change in algorithms – since most traditional algorithms are designed
to minimize computation time, without taking into account energy limitations. In particular,
this means that energy-needing auxiliary procedures like garbage collection – that periodically
frees the no-longer-used part of computer memory – have to be performed only based on need,
and not, as in usual computers, periodically or whenever this leads to faster computations; see,
e.g., [
For example, a regular laptop usually updates when it is idle, when it is not doing any computations: • this preserves its computational speed when it is used, and • no matter how many updates we make, it does not afect its computing abilities. For portable devices, any such procedure uses some portion of stored energy, so it needs to be performed as rarely as possible.
The corresponding optimization of computations is a very challenging task, especially taking
into account that some operating systems running on this devices are proprietary. Since the
operating system uses a significant amount of energy, we thus face a partly-black-box problem
even when the computational algorithms that we run on these devices are white-box ones; see,
e.g., [
Resource limitations of regular-size computing: cost and cloud computing. For regularsize computing, computational ability is not a problem – otherwise, we would have needed a high-performance computer. As we have mentioned earlier, for such computers, energy is also not a problem: we just plug in. So is there any limited resource? Yes, a very mundane one: money.
The possibility to save money comes from the fact that the amount of needed computations changes with time: • we have daily fluctuations, since most computations are performed at daytime, • we have seasonal computations – e.g., a tax-advising company needs a lot of computations before the taxes deadline, stores need to perform more computations before Christmas, when many people are shopping for Christmas gifts, etc.
• we can buy as many computers that we need at peak times, or
• we can buy fewer computers and at peak time, rent computation time on other computers.
Computations involving rented computation time are known as cloud computing; see, e.g., [
So how much computing power should we buy and how much should we rent? Detailed
answers to this question can be found in [
• the cost 0 per computational step of in-house computations (including the corresponding part of the cost of buying the computers), • the cost 1 > 0 per computational step of rented out-of-house computations, and • probability distribution of the future computer needs , which can be described, e.g., by the probability density function (pdf) ( ).
Based on this information, we need to select the optimal amount 0 of computational power that we should buy.
For each value > 0, we rent the missing amount − 0 of the computational power. Thus, the overall expected cost of all these computations is equal to 0 ⋅ 0 + 1 ⋅ ∫
1 ⋅ ( − 0) ⋅ ( ) .
∞ 0 ( 0) = 1 − 0 1 , To find the optimal value 0, we can diferentiate this expression with respect to 0 and equate the derivative to 0. As a result, we get the equation where ( ) is the cumulative distribution function corresponding to the given pdf. This equation described the optimal amount of computing power that we should buy.
Comment. In [
Resource limitations of large-scale computing: energy again. For large-scale computing, as we have mentioned earlier, one of the main problems is that some important practical problems still cannot be solved on such computers – computer engineers are working on this. For the existing computers, what is the main limitation? Somewhat surprisingly, the main limitation is again energy, the same as for small-scale computing. Indeed, we can simply plug in a regular-size computer, but a usual company-wide or university-wide connection can only support a limited number of such plugged-in computers.
For a high-performance computer – which, crudely speaking, consists of hundreds and thousands of usual computers – we need to build a special power station, and even this may not be suficient. How can we minimize the power needed for computations?
• When we design a high-performance computer, we want to maximize the overall number of computations per second. From this viewpoint, a seemingly natural idea is to run all the processors at their maximum speed. • It turns out that from the viewpoint of energy consumption, this is not the best arrangement.
To be more precise, if the power used by each processor was exactly proportional to this processor’s computation speed – i.e., to the number of computational operations per second, this would not matter: • if = ⋅ , • then, no matter how we distribute the task between processors, the overall power would be similarly proportional to the overall number of computational steps per second: = ⋅ .
In practice, however, the linear dependence of on is only a rough approximation, the actual dependence = ( ) is non-linear.
As a result, instead of having all the processor work at their maximal speed, a better idea is: possible, and • to have each processor work at the speed at which the ratio = ( ) is the smallest • to use more processors if needed.
If at some point, the task requires a smaller overall computation speed , then, to minimize energy consumption: • we make some processors idle, while • others will work at their optimal speed (optimal in terms of energy consumption). Quantum computing and its resource limitations. As we have mentioned several times, there is a practical need to increase computation speed beyond what we can do now. This need faces a fundamental physical limitation: that, according to relativity theory, the speed of all processes is limited by the speed of light. As a result: • for a usual laptop of approximately 30 cm size, it takes 1 nanosecond for the light to travel from one side of the computer to another, and • during this time, even the cheapest 4-GHz laptop performs 4 operations.
To drastically speed up processing, we need to drastically decrease the computer size – and this means to make memory cells drastically smaller. Already each cell consists of thousands of molecules. With further size decrease, we will get to the level of individual molecules – and at this level, we have to take into account physical laws of the micro-world – the law of quantum physics.
Computations that take quantum efects into account are know as quantum computing; see,
e.g., [
⋅ √ = √ . This amount: we reach the case = ). should add to 1 – which explains the above condition on the values , ′ , . . .
If we measure, in this superposition state, a classical variable , then we get the value ( ) with probability | |2, the value ( ′) with probability | ′ |2, etc. The sum of all these probabilities
In particular, a quantum analogue of the usual bit – i.e., an element that can be in two possible states 0 and 1 – is a quantum bit (qubit, for short), i.e., the state of the type
There are many eficient quantum algorithms, e.g., Grover’s algorithm [
array in time proportional to √ . • This algorithm enables to find an element with a given property in an unsorted -element • On the other hand, for non-quantum algorithms, not to miss the desired element, we need to look at all elements, so we need at least computational steps, and ≫ √ .
Grover’s algorithm requires -qubit states. At this moment, the number of available qubits is the main limitation to quantum computing, the main limited resource. What happens if we only have <
qubits, i.e., if we can only implement -qubit states? In this case, we can:
• divide the -element array into / fragments of size , and
• apply Grover’s algorithms to each fragment; see, e.g., [
For each fragment, Grover’s algorithm requires √ steps, so the overall computation time will • is still smaller than the time needed in the non-quantum case, and • decreases as the resource bound increases (and reaches the Grover’s value ∼ when √ 3. Black-Box Computing: Related Resource Limitations General case. For black-box computing, when computations include calls to a “black-box” (proprietary or classified) program, a natural idea is to minimize the number of such calls: • For proprietary programs, when we often need to pay for each class, this minimizes the overall costs.
time. • For classified programs, when each call is an extra vulnerability, this minimizes the risk. • For programs that take a long time to compute, this also minimizes the overall computation What can we compute in this manner? Usually, commercial software provides a turn-key solution to the corresponding problem, a solution that does not require additional programming. There exist commercial software for deep learning, for solving partial diferential equations, etc.
This software produces the result
= ( 1, … , ) of processing the inputs 1, … , , but what is usually does not do is produce the accuracy of this result. To be more precise, most black-box packages compute the result implicitly assuming that the inputs are exactly known. In practice, the inputs come from measurements, and measurements are never absolutely accurate: the result ̃ of measuring the -th input are, in general, diferent from the actual (unknown) value of this input. of this computation will be, in general, diferent from the desired value = ( 1, … , ) :
to the measurement results ̃ , the result ̃ ̃ = ( ̃1, … , ̃ ) ≠ = ( 1, … , ).
An important question is: how accurate is the computation result? In other words, how big can the diference Δ def
= ̃ = be? learned that the given area contains ̃ = 200 million tons, then:
This question is very practically important. For example, if we are prospecting for oil and we • if this amount is 200 ± 20, this is good news and we should start drilling, but • if it is 200 ± 300, then maybe there is no oil at all, and it is better to perform additional measurements before we spend a large amount of money on possibly useless drilling. ̃ − expression Let us formulate this problem in precise terms. Usually, the measurement errors Δ are relatively small. So, taking into account that = ̃ − Δ , we can expand the def = Δ = ( ̃1, … , ̃ ) − ( ̃1 − Δ 1, … , ̃ − Δ ) in Taylor series and keep only linear terms in this expansion. As a result, we get the expression Δ = ∑ ⋅ Δ ,
=1 where =
def .
What do we know about the measurement errors?
see, e.g., [
=1
Δ ? Seemingly natural idea. If we know the values , then, e.g., for the normal distribution, we can conclude that the linear combination
∑ ⋅ Δ is also normally distributed, with mean 0 and standard deviation =
In case of upper bounds, when each measurement error Δ can take any value from the interval [−Δ , Δ ], the largest possible value of the sum ∑ ⋅ Δ is attained when each term ⋅ Δ in this sum is the largest possible. =1 its largest value Δ . The corresponding largest value of the -th term is ⋅ Δ . • For ≥ 0, the term ⋅ Δ is increasing, so its largest value is attained when Δ attains • For ≤ 0, the term ⋅ Δ is decreasing, so its largest value is attained when Δ attains its smallest value −Δ . The corresponding largest value of the -th term is − ⋅ Δ . equal to In both cases, the largest value of the -th term is | | ⋅ Δ , so the largest value Δ of the sum Δ is =1 Δ = ∑ | | ⋅ Δ .
Straightforward approach and its limitations. If we knew the values , then we could use the above formulas and find the desired characteristic or Δ of the approximation error Δ .
The algorithm
( 1, … , ) is given as a black box, we do not know the corresponding expression and thus, we cannot simply diferentiate this expression. However, what we can do is use numerical diferentiation, according to which, for suficiently small value ℎ , we have = ≈ ( ̃1, … , ̃ + ℎ , ̃ +1, … , ̃ ) − ̃ ℎ ifrst call to compute ̃ and then more calls to compute partial derivatives .
This way, we get the desired expressions for and Δ – but we need to make + 1 calls to : the require minutes or even hours, so this is not a very feasible idea. What can we do?
In many data processing algorithms, we use thousands of inputs, and each call to may Case of probability distributions: Monte-Carlo simulations. In situations when we know the probability distributions, the answer is well known: use Monte-Carlo simulations. Namely, for some integer , we:
distribution of the corresponding measurement errors Δ , and then • times simulate the variables ( ),
= 1, … , , whose distribution is the same as the • compute the values ( ) = ( ̃1, … , ̃ ) − ( ̃1 − 1( ), … , ̃ − ( )).
=1 ( ) = ∑ ⋅ ( ).
approximation errors Δ .
Since the values that the distribution of the values ( ) is exactly the same as the desired distribution of the ( ) have the same distribution as the measurement errors Δ , we can conclude ≈ √ 1
⋅ ∑ ( =1 ( ))2.
Good news is that the accuracy of this estimation is proportional to √1 (see, e.g., [
For example, if we want to find with accuracy √1
straightforward estimation.
and thus, 25 calls for the program – which is much smaller than thousands of calls needed for
What if we only know the upper bounds? At first glance, in this case the situation is
hopeless: we do not know what distribution to use. However, interestingly, a Monte-Carlo
approach is possible in this case as well; see, e.g., [
1 ⋅ Δ ⋅ 1
1 + (Δ ) 2
The use of Cauchy distribution is based on the following property of this distribution: • if independent random variables Δ 1, . . . , Δ are Cauchy-distributed with parameters Δ , • then the linear combination
∑ ⋅Δ of these random variables is also Cauchy-distributed, =1 =1 with parameter Δ = ∑| | ⋅ Δ .
Δ
: • we simulate • then the values ( ) to be Cauchy-distributed with parameter Δ ;
( ) = ( ̃1, … , ̃ ) − ( ̃1 − 1( ), … , ̃ − ( ))
value Δ by applying, e.g., the Maximum Likelihood method [
are Cauchy-distributed with the desired value of the parameter Δ. We can then find this How quantum computing can help. Sometimes, some parts of the input are irrelevant. For example, to predict tomorrow’s weather, if the wind blows from the North, then what was to the south of this area does not matter. If we could find such irrelevant bits and not process them, this will make our computations faster. How can we find such irrelevant bits?
Here, quantum computing can help in the following way. In the simplest case, in which the input is just one bit, and we consider one bit ( ) of the output, the question is whether the input is relevant at all, i.e., whether (0) = (1).
• In non-quantum computing, we can only have inputs 0 or 1. So, to check the equality
(0) = (1), we need to call twice: for = 0 and for = 1.
• It turns out that in quantum computing, we can check this property by using only one
call to – but in this call, the input should be a superposition of 0 and 1; see, e.g., [
4. Measurements under Limited Resources: Two Case Studies Two types of situations. In addition to limited resources for computations, we can (and do) also have limited resources for measurements. In this section, we consider case studies covering two possible types of situations: when we can only measure individual quantities, and when we can measure combinations of diferent quantities.
Measuring individual quantities: general description and the case study of a robotic boat. Measurements require even more resources than computations: they require time, they require energy. It is therefore desirable to minimize the number of measurements that we need to describe some spatial or temporal-spatial phenomenon with a given accuracy.
In some cases, we need to develop a measurement schedule at the very beginning. For this case, general ideas on how to minimize the number of measurements, see, e.g., [23, 24, 25] and references therein. Further minimization can be achieved if we make the measurement plan adaptive: we will decide what to measure next based on the results of previous measurements. In this section, let us concentrate on the case of a single passive measuring device: e.g., a spaceship following a given trajectory or a robotic boat floating along the river.
This choice of examples may need some explanation. Probably no one will wonder why we need measurements performed by a spaceship, but why do we need a floating robotic boat? The answer to this question is very straightforward: with planes, satellites, and drones, most of the Earth’s surface has been accurately mapped. We know the elevations at diferent locations, we know how much plants are there. Similarly, we have a reasonable understanding of the oceans, and of major rivers. The least explored geographic objects are small rivers. To get a complete picture of Earth’s geography, we need to describe their depths and flows at diferent locations. This is important for ecological studies, this is important to understand how water circulates – since big rivers are usually fed by smaller ones. To get a good description of a small river, the usual way is to traverse the river and measure the corresponding parameters as we go. The problem is that there are many small rivers, and it is not realistic to expect human researchers to traverse all of them.
To solve this problem, researchers are working on designing robotic boats; see, e.g., [26] and references therein. The idea is to place this boat at the origin of the small river and let is flow along the river and measure the corresponding parameters. The problem is that measurements and transmission of the resulting data use some energy, and since boat is autonomous, it can only carry a limited amount of energy. So, the question is: how to get the desired map of the river by using the smallest possible number of measurements.
• when we are passing through a part of the trajectory where the depth (or any other quantity of interest) is approximately constant, then there is no sense of measuring this quantity too frequently; but • when we come to the part of the trajectory where the quantity starts changing, then we must measure it with the highest possible frequency.
Let us describe the corresponding problem in precise terms. We know reasonably well the trajectory followed by a spaceship or the trajectory followed by a floating robotic boat or by another similar device. Let be the parameter describing the device’s location on this trajectory – e.g., the length of the path that it has already covered along this trajectory. At some values , we perform some measurements. We may want to measure some quantity in its location – e.g., the depth at this location. We may want to measure some quantity that depends not only , but also on some other parameters 1, …. For example, for the boat, we may want, by sending a signal in several directions, to measure the depths not only right beneath the boat, but also on other locations (, 1) on the line orthogonal to the trajectory.
In general, based on the measurements, we want to find the while dependence (, 1, …) of the measured quantity on all these parameters, and we want to measure all these values with accuracy . How can we reach this goal by using the smallest possible number of measurements?
(, 1, …) = 1 ⋅ 1(, 1, …) + … + ⋅ (, 1, …) to describe the local behavior of the corresponding field. In this approximation: • the functions 1(, 1, …), . . . , (, 1, …) are fixed, and • the parameters 1, … , change from location to location.
functions. For example, if we are interested in the depth ( ) at diferent points along the trajectory, then we can use approximations ( ) ≈ 1 + 2 ⋅ or take ( ) ≈ 1 + 2 ⋅ + 3 ⋅ 2. • In the first case, = 2, 1( ) = 1, and 2( ) = .
• In the second case, = 3, 1( ) = 1, 2( ) = , and 3( ) = 2.
• whether we know the probability distribution of the measurement error – e.g., Gaussian with standard deviation – or • whether we only know the bound Δ on the measurement error. 1 ( ), . . . , where = 1, 2, … , + 1. Let ( ) be the corresponding measurement results.
In both cases, we first perform + 1 (or more) measurements corresponding to the values ( ), (1) ≈ 1 ⋅ 1 ( (1), 1(1), …)+ … + ⋅ ( (1), 1(1), …);
… ( +1) ≈ 1 ⋅ 1 ( ( +1), 1 ( +1), …)+ … + ⋅ ( ( +1), 1 ( +1), …).
We can use the usual Least Squares method (see, e.g., [
As long as this value is smaller than or equal to the desired accuracy , we do not perform any additional measurements. The next group of measurements is performed at the first future value at which the standard deviation becomes equal to .
In the case of upper bounds, for each future value and for all possible values of the two optimization problems. To find the upper bound variables 1, …, we find the range [ , ] of possible values
(, , we maximize the expression
1, …) by solving the following 1 ⋅ 1(, 1, …) + … + ⋅ (, 1, …) under the constraints (1) − Δ ≤ 1 ⋅ 1 ( (1), 1(1), …)+ … + ⋅ ( (1), 1(1), …) ≤ (1) + Δ; ( +1) − Δ ≤ 1 ⋅ 1 ( ( +1), 1 ( +1), …)+ … + ⋅ ( ( +1), 1
( +1), …) ≤ …
( +1) + Δ.
− = 2.
, we minimize the same expression under the same constraints. In both optimization problems, we optimize a function which is linear in terms of the unknowns 1, … , under constraints which are also linear in terms of the unknowns. Such optimization problems are known as linear programming problems. There exist eficient algorithms for solving such problems; see, e.g., [27].
The next measurement is performed at a location for which the prediction accuracy is , i.e., for which the interval [ , ] has the form [ ̃ − , ̃ + ] for some ̃, i.e., equivalently, for which Measuring combinations of quantities: general description and the case study of Covid19 testing. When we measure, we are interested in some property. In some situations, only a few objects have the property of interest. In such situations, the possibility to measure combinations of quantities corresponding to individual objects can save on the number of measurements.
possible location, we perform some measurements of the area as a whole and only drill in those areas which, according to these combined measurements, have oil.
Another example is Covid-19 testing. In the ideal world we should test everybody, but the required number of tests kits – since: number of available test kits is limited. If instead of testing all apply the test to a mixture of samples from a group of several ( 1) people, we can decrease the people from a given area, we • we can dismiss all the groups where no one was Covid-positive, and
1 • we need to continue testing only folks from the remaining groups; see, e.g., [28, 29, 30].
In [30], we considered the arrangement when after the group testing, we individually test everyone from still-suspicious groups. However, if there are many such folks, a reasonable idea is to combine these remaining folks into new groups of size 2 < 1, and test each new group, etc., until, after such stages, on the following stage + 1, we test all remaining possibly-positive folks individually. Let us analyze what is the optimal approach to such multi-stage group testing.
Let denote the proportion of people in a given area that test Covid-positive. This number can be (and is) estimated based on the preliminary random testing. Thus, overall, we have ⋅ have ⋅ ⋅ possibly-positive folks.
The value is small, so for suficiently small group sizes , the probability that we have two
On the first stage, we test folks. After stages, we have ⋅ ⋅ possibly positive folks. We divide them into groups of size +1. Thus, on the ( + 1)-st stage, we get ⋅ ⋅ testing groups. Hence, on the ( + 1)-st stage, we need to perform ⋅ ⋅ tests. The overall number +1 of tests is therefore equal to 1 + ⋅ ⋅ 1 2
+ … +
⋅ ⋅ −1 + ⋅ ⋅ + …
that minimize this overall number of tests. the overall number of tests with respect to minimize the overall number of tests with respect to . Diferentiating the above expression for and equating the derivative to 0, we conclude that
Let us first select an integer > 1 and − ⋅ ⋅ −1 + ⋅ Dividing both sides by ⋅ , multiplying both sides by , and moving the negative term to the other side, we conclude that
= −1 . This is true for all , so the value is the same common ratio . for all . Let us denote this ratio b+y1 . Th us, the values form a geometric p ro+g1ression with
At the end, we check individually, so +1 = 1. Thus, we get = , −1 = 2, . . . , until we get 1 = . Thus, = log ( 1) =
ln( 1) . For these values , each term ⋅ ⋅ in the expression for the overall number of tests is equal to
⋅ ⋅ , and there are stages in the testing procedure. Thus, the overall number of tests is equal to s uc+h1 terms – as many as 1 ln( ) + ⋅ ⋅ ⋅ = + ln( ) ln( 1) ⋅ ⋅ ⋅ . other side, we conclude that 1 =
Minimizing this expression with respect to means minimizing the ratio . Diferentiating this expression with respect to and equating the derivative to 0, we conclude that ln( )− ⋅ = 0, ln( ) 1 i.e., that ln( ) = 1 and thus, = .
For = , the above expression for the overall number of tests takes the form ln( 1). There is only one parameter left undetermined – the value 1. Diferentiatin g1 the above + ⋅ ⋅ ⋅ expression with respect to 1 and equating the derivative t 0, we get − 2 + ⋅ ⋅ ⋅ Multiplying both sides by 12, dividing both sides by ⋅ ⋅ , and moving n1egative terms to the 1
= 0. 1 Optimal testing schedule. We first combine folks into groups of size 1 = combined samples from each group. All the people from groups whose combined sample tested negative are Covid-negative and thus, do not need any additional testing.
The remaining folks are combined in groups of size 2 = from each group. All the people from groups whose combined sample tested negative are 1 . We test combined samples
The remaining folks are combined in groups of size 3 = stage at which +1 ≈ 1, i.e., where the remaining folks need to2be individually tested. 1 , etc. At the end, we reach the How many tests do we need for the optimal testing schedule. Substituting the expression 1 , and test ⋅ 1 =
1 ⋅ ln( 1) = | ln( )| − 1, we conclude that we need
into the formula for the overall number of tests, and taking into account that i.e., we need 1 + ⋅ ⋅ ⋅ ln( 1) = ⋅ ⋅ + ⋅ ⋅ ⋅ (| ln( )| − 1),
⋅ ⋅ | ln( )| ⋅
Is this method optimal? This is indeed the best we can do – at least asymptotically the best. Indeed, we need to find ⋅ elements out of . The number of such possible arrangement is
= ( ⋅ ) ( ⋅ )! ⋅ ((1 − ) ⋅ )! . get all
( ⋅ )
Each test has 2 possible results, so after tests, we have 2 possible combinations of results. To possible answers, we need to have 2 ≥
( ⋅ ) , i.e., we need ≈ log2 ( ⋅ ).
Asymptotically, for each integer , we have ! ≈ (
log2( !) ≈ ⋅ (log2( ) − log2( )) = ⋅ log2( ) − ⋅ log2( ). ≈ log2 ( ⋅ )
= log2( !) − log2(( ⋅ )!) − log2((1 − ) ⋅ )!) = ⋅ log2( ) − ⋅ log2( ) − ⋅ ⋅ log2( ⋅ ) + ⋅ ⋅ log2( )−
(1 − ) ⋅ ⋅ log2((1 − ) ⋅ ) + (1 − ) ⋅ ⋅ log2( ). the product is equal to the sum of logarithms, we get Terms proportional to log2( ) cancel each other. So, taking into account that the logarithm of ! , so ) Terms proportional to ⋅ log2( ) cancel each other, so For small , we have 1 − ≈ 1 and log2(1 − ) ∼ , so ≈ ⋅ log2( ) − ⋅ ⋅ log2( ) − ⋅ ⋅ log2( )− (1 − ) ⋅ ⋅ log2( ) − (1 − ) ⋅ ⋅ log2(1 − ).
≈ − ⋅ ( ⋅ log2( ) + (1 − ) ⋅ log2(1 − )). thus the smallest possible number of tests is indeed proportional to (1 − ) ⋅ log2(1 − ) ∼ ≪ ⋅ log2( ), ⋅ ⋅ | log2( )| = ⋅ ⋅ | ln( )| ln(2) . multiplicative constant, our method is indeed asymptotically optimal.
This expression difers from our number of tests by a factor ⋅ ln(2) ≈ 1.88; so, modulo a small 5. Acknowledgments This work was supported in part by the National Science Foundation grants 1623190 (A Model of Change for Preparing a New Generation for Professional Practice in Computer Science), and HRD-1834620 and HRD-2034030 (CAHSI Includes).
The authors are greatly thankful to the conference organizers for their encouragement and support, and to Laura Alvarez for helpful discussions.