Main content

## Primality test

# Time space tradeoff

## Video transcript

Voiceover: I have a new update. I contacted the engineering
department at NASA and found out the new rover is using the same memory platform
used on curiosity. And the curiosity rover was equipped with two computers,
but only one was active at a time and it had the following specs. Two gigabytes of flash memory, 256 megabytes of random access memory, and 256 kilobytes of read only memory, which held core system routines. We want to be able to store our entire program in RAM, however
because we have to share this space with other
programs, we are allocated 5% of RAM, which is
the maximum we can use. This is about 12.8 megabytes total. I bring this up because I
want to introduce the idea of time space trade off,
or space time trade off, a commonly used term in computer science. I was looking at a program done by IV46 and they had a million prime array so that there algorithm could step along on primes only, as far as possible, when doing a trial
division primality test. It begs the question, why
just not store all the primes we need, up to some limit in an array instead of calculating them on the fly? We mentioned in a previous video that this would be optimal for a
trial division algorithm. Although you may see
his algorithm does not use many steps, it
began to run very slowly and eventually crashed before
hitting the step limit. So it wasn't able to
quickly solve the problem for the sizes I defined earlier. And in this case, they
were trading off time in the form of repeated divisibility tests at the expense of space, which is memory to hold the array. Now, why didn't this work? Well, let's do a rough calculation using what we've learned to
find out if this method is possible using our memory limit. Remember, we must be able to deal with numbers up to just
over 9 quadrillion. Our trial division
algorithms only need to check for factors up to the
square root of a number, and if it hits that point
with no factors found, it can say 100% whether or
not the number is prime. Now, how many primes up to the square root of this limit, where the square root of 9 quadrillion is 94.9 million? How many primes under 95 million? Well, luckily we have
learned a mathematical solution to approximate this answer using the prime number theorem. So how many primes are there under x? Well, it's x divided by
the natural logarithm of x. And if x is just over 94.9 million, we find the number of primes is approximately 5.1 million. Now because we are storing these primes, we need to know the size
of the largest prime, or in this case, the 5.1
millionth prime approximately, which we know will be some number less than 94.9 million. Now, I double checked
the table, and the actual value of this prime, the
largest prime we would need to store under the
square root of our limit, is 89,078,611. Now how much memory does this single large prime number require? Well, to find out,
let's convert the number into binary notation,
which is how the computer will store the number using
tiny switches in memory. We learned about this in
the computer memory video. In bits, the largest
prime looks like this, which is 24 bits or 3 bytes needed to store this single number. So let's say we want to
store each number in memory and since we know the largest number requires 24 bits, we can
just imagine a long list of 24 bit blocks storing
each prime number. So how many bits are needed
for this entire list? Well the memory needed
is the number of values, or the number of primes,
times the space per value. So we have around 5.1 million values times 24 bits per value,
which is just over 124 million bits, or if
we convert it into bytes, it's about 14.7 million bytes. Call this almost 15 megabytes. So it is not possible to store even a list of these numbers in
memory using our limit. This is just a toy example. It's actually an underestimation of what you'd really need. For example, an array needs space for a pointer to each
item, and each pointer on a 32 bit machine is 4 bytes. So the actual amount of memory needed is much more than 15 megabytes. That being said, we know
that storing all primes up to the square root of
our relatively small limit is not even possible
with our memory limit. We can't do it this way. Okay, well, what about when prices drop by a factor of a
thousand, or ten thousand. Modern day cryptographic
systems use 512 bit, or even larger numbers, making search and enumeration impossible. Now for example, if someone
asks you to make a list of all prime numbers up to primes which are 200 digits in
length, you shouldn't even consider it because the
hard drive needed to store all these primes would be heavier than the mass of the observable universe. I'll leave the calculations for you to try next time you're at a restaurant with crayons and paper all over the table. But remember, there are around 10 to the 80 atoms in
the observable universe. That's an 80 digit number. Realize now, there is a fundamental limit for how much space or
memory we have access to. Nevermind how much time it would take, but there is always this push and pull between using space or
time to solve our problems. So to solve this problem
of testing for primality quickly using a small amount of space, and a small amount of
time, we are going to have to approach it in an entirely new way.