Algorithmic efficiency How can we improve the speed of a (deterministic) primality test?
- I have a report now that they are sending a new rover to Mars,
- and we are responsible for doing one thing –
- which is programming the algorithm inside the rover
- which checks if numbers are prime.
- Because let's say our rover is communicating using RSA.
- It needs an algorithm inside that can do a primality test.
- Now, when you a design a rover,
- or anything to go into space, you have to
- be very efficient in <i>every</i> way.
- So the components used have to be very light,
- the amount of power every subsystem uses has to be minimal.
- You have to be saving energy and mass at
- every point in the design process.
- So, we have our work cut out for us
- because we have to be able to deal with numbers
- up to this size...
- ... and it has to do it very fast.
- So if we give it a very small input, let's say just 90 –
- it should be able to calculate that almost as fast
- as this entire number.
- So as the input grows, we don't want to see
- any of this noticeable slow-down.
- Now, I want to analyze the user questions,
- or the ideas users had, which were really good.
- From a mathematical standpoint.
- We are checking if <i>n</i> is <i>prime</i> or <i>composite</i>.
- So given some number <i>n</i>, think of
- the space of all possible <i>n</i>s,
- and say if <i>n</i> is 100, then this space
- is 2 to 100.
- And what our algorithm is doing,
- is it's searching this space.
- Okay, so you can think of algorithms as searching a space,
- and at each point it's asking – think of it as a step –
- – a primitive step – it's asking a question.
- And it's actually a composite test, the question...
- so say we're at number <i>a</i>, we would say in the
- trial division method is <i>n</i> divided by <i>a</i>?,
- and we just try this, we drop <i>a</i> here and
- we try if <i>n</i> divides <i>a</i> and we see
- if the remainder is zero, which means <i>a</i> is a divisor of <i>n</i>
- then we can say,
- "Ah! We are 100% sure it's composite."
- Otherwise, at each step, we aren't quite sure –
- it might be prime, but we're not sure –
- so we continue searching until we hit the end.
- And remember our wall in this case was at the square root of <i>n</i>.
- The worst case situation occurs when <i>n</i>'s prime,
- we search all the way to the square root of <i>n</i>
- and then we can say,
- "Ah! It is prime! And we are 100% sure."
- So in the case where <i>n</i> is even a multiple of two primes,
- so 7
- so 7 • 7
- so 7 • 7 = 49
- If we throw 49 into our algorithm,
- the worst case occurs, we go all the way until
- the square root of <i>n</i>.
- So the first set of questions,
- from, for example, TheFourthDimension asks:
- *"Once we rule out 2 as not divisible, then*
- *all multiples of 2 could be ruled out.*
- *The same for 3*
- *The same for 3, 4*
- *The same for 3, 4, 5*
- *The same for 3, 4, 5, etc.*
- So that's a really great point –
- our old algorithm was stepping along one at a time,
- but we could be using patterns we know about composite numbers
- such as, we know, for sure, that if a number's divisible by 2,
- then it's composite –
- if it's greater than 2, so 2's prime,
- but then we can say,
- 4 is composite...
- Oh, I missed 5 here, sorry about that.
- 4, 6
- 4, 6, 8
- 4, 6, 8, 10 ...
- And instead, we can take a step like this:
- 3, 5
- 3, 5, 7
- 3, 5, 7, 9 ...
- So, one category of questions –
- they all try to reduce this space,
- so if we eliminate all the even numbers,
- now the check space, instead of being up to the square root of <i>n</i>,
- is the square root of <i>n</i> divided by 2.
- And, we can find other patterns in composite numbers
- to try to make this even smaller.
- The other type of question concerns the case
- where we find a composite witness,
- that is we find an <i>a</i> that allows us to say we know <i>n</i> is composite.
- lola said,
- *"Wouldn't leaving the loop as soon we find*
- *primeCheck == false cut down on some of the time?"*
- And yes, that's totally correct, and
- it's something we want to do.
- As soon as we are searching along using some step,
- defined by whatever pattern you're using,
- we find a composite witness,
- that means it passes our test and we say 100% composite,
- we should halt early.
- We stop and say, "Uh, we're done."
- We won't continue searching.
- And, this halting early is great, except
- it doesn't help us in the worst case,
- which is: if <i>n</i> is prime,
- then the early halting won't help us.
- And now we can visualize how these improvements
- allow us to reduce the space, thus preventing
- as many checks happening inside the computer
- (which, depending on our computer)
- will reduce the amount of <i>time</i> it takes.
- So now I can show you the visualization I've set up below,
- which allows us to compare two algorithms based on
- how many steps occur during their execution.
- On the left is Algorithm A, which is trial division,
- which checks from 2 to the square root of <i>n</i>.
- And on the right is Algorithm B, which is,
- let's just say our "improved algorithm,"
- and in this case, I've applied the check if it's divisible by 2,
- so we only do half as many steps,
- and I also terminate early in this Algorithm B.
- So it's not perfect, I've just applied a few user modifications,
- so we can see what happens, and now I'm gonna
- just play with this to show you it.
- Here we can see, as I scroll, we see Algorithm A.
- We have the output, whether it's composite or prime,
- and at the bottom, you'll see the number of steps.
- So the first thing to notice is on the right-hand side,
- every other number takes only one step,
- and we know why that is, because if it's an even number,
- such as this, it will quit.
- So our old algorithm took 314 steps,
- and our new algorithm only took 1 step
- because it checked if it was divisible by 2,
- so that seems like a really nice optimization.
- However, as we build our input, you'll notice
- the steps increase and the bar grows
- and turns red once we approach the region
- where we're going to crash.
- So this red line up here is **STEP LIMIT** –
- if your bar hits there, we fail,
- which means our rover would break,
- and in this case, the browser will actually crash,
- so I'll try to get close to it.
- So I'm close to it now, and it's running very slow,
- I can feel that my browser is just about to crash
- and give me the circle of death.
- But notice our improved algorithm took only 2 steps in that case,
- but remember the worst case.
- So I have a few large prime numbers saved here for example.
- We have to be able to handle any case,
- we don't know what we're throwing at our algorithm.
- So if I throw a large prime at it, look what happens:
- Algorithm B, as we know, is taking
- half as many steps in the worst case,
- but it's still taking many steps here.
- Because it's the worst case, right?
- So, we're getting close to crashing here,
- and this is not a very long prime.
- We're still way under 15 digits.
- And when I put this 12 digit prime into our algorithm
- let's see what happens:
- It's lagging; maybe it's going to crash...
- look what happened:
- both algorithms went <i>way</i> overboard,
- so it didn't work.
- Our improved algorithm is not good enough yet.
- But now we have an understanding of
- what we're trying to improve,
- which is "number of steps in the worst case."
- And we also have this cool tool, which allows us to
- visualize how fast it's growing –
- how fast the number of steps grows as our input grows.
- And below, I'll explain how I set this up,
- so you can set up your algorithm
- and compare it with the base case,
- and see how much better you can do.
Be specific, and indicate a time in the video:
At 5:31, how is the moon large enough to block the sun? Isn't the sun way larger?
Have something that's not a question about this content?
This discussion area is not meant for answering homework questions.
Share a tip
When naming a variable, it is okay to use most letters, but some are reserved, like 'e', which represents the value 2.7831...
Thank the author
This is great, I finally understand quadratic functions!
Have something that's not a tip or thanks about this content?
This discussion area is not meant for answering homework questions.
At 2:33, Sal said "single bonds" but meant "covalent bonds."
For general discussions about Khan Academy, visit our Reddit discussion page.
Here are posts to avoid making. If you do encounter them, flag them for attention from our Guardians.
- disrespectful or offensive
- an advertisement
- low quality
- not about the video topic
- soliciting votes or seeking badges
- a homework question
- a duplicate answer
- repeatedly making the same post
- a tip or thanks in Questions
- a question in Tips & Thanks
- an answer that should be its own question