2
$\begingroup$

I am trying to solve this problem listing all prime numbers less than an integer but using the smallest amount of memory.

Is it possible to solve this problem using a smaller amount of memory?

int main () 
{
    int n = 10000;
    for (int i=2; i<n; i++) 
        for (int j=2; j*j<=i; j++)
        {
            if (i % j == 0) 
                break;
            else if (j+1 > sqrt(i)) {
                cout << i << " ";
            }
        }       
    return 0;
}
$\endgroup$
  • $\begingroup$ How much space does your algorithm need? What does the literature say? $\endgroup$ – Raphael Nov 21 '18 at 11:36
  • $\begingroup$ Community votes: too broad? This question either comes down to debugging/tweaking the given code, or a literature survey. Neither works really well here. $\endgroup$ – Raphael Nov 21 '18 at 11:36
  • 1
    $\begingroup$ This question is a conceptual question in disguise. What I mean is the important and the critical part of the question is how to define the memory used by the program. One simple definition is the extra space or temporary space used, excluding the input and output. Using that definition, the smallest amount of memory for this algorithm is 3 for $n$, $i$ and $j$ in the usual model of computation for daily programming. The call to sqrt(n) can be eliminated. $\endgroup$ – Apass.Jack Nov 21 '18 at 17:35
  • 1
    $\begingroup$ In the above sense, this question has little to do with debugging or survey since the answer is pretty simple. $\endgroup$ – Apass.Jack Nov 21 '18 at 17:42
  • $\begingroup$ @Apass.Jack I don't see any evidence that the question is "What is a good definition of the amount of space an algorithm uses?" The question doesn't say anything at all about that. $\endgroup$ – David Richerby Nov 22 '18 at 11:34
0
$\begingroup$

Yes, but only after we have stated what is considered memory used by an algorithm or program.

For this particular problem, I would like to use one of the simplest choices. The memory used by the program is the extra or temporary space used excluding the input and output. Furthermore, each variable (that does not share its storage with others) uses a unit of space. One might argue the output should count towards memory usage. My point is to let us choose a usage model so that we can concentrate on the most relevant and interesting part, although in another situation, how to reduce the memory used by the output might be the more significant part.

Here is the snippet that use 3 units of memory, where I remove the call to sqrt(i). Each of $n$, $i$, $j$ uses 1 unit of memory. I comment out the output code to make it clear that its memory usage is not considered.

int n = N; // N should be given elsewhere
for (int i=2; i<n; i++) 
    for (int j=2;; j++)
    {
        if ( j*j > i) {
            // cout << i << " ";
        }  else if (i % j == 0) 
            break;
    }       

But wait, how can we check j*j > i? Even if we assume the computing machine can compute j*j magically without using extra memory, it still needs to store the result of j*j so as to compare with i. So it is only reasonable that we add 1 or more unit of memory usage here. Then how about i % j? We would like add 1 or more unit of memory usage here.

If we dig deeper, we will ask whether those 2 and 0 in the program count towards memory or not. We may have to ask during the program execution, doesn't it need to use some space to remember where it is executing and how to jump around? If those memory are needed, can we reuse them during different execution time?

The more we study this way, the more uncertain the answer becomes. This is, in fact, the truth. It is almost impossible to get an accurate usage of memory theoretically unless we have an accurate model of storage and computation specified down to the bit. When we do have that accurate model, an accurate analysis to the bit may become so tedious and distracting we might lose the big picture.

The way out to get a healthy picture is the big $O$ or $\Theta$ notation. We will simply say that this program use $O(1)$ or $\Theta(1)$ memory. That is, for a reasonable model of storage and computation, there is a constant $C$, for any give $N$, the program will use less than $C$ units of memory. In practice, we usually mean a small or reasonable $C$.


By the way, the program in the question misses primes 2 and 3.

$\endgroup$

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.