-: In this video we're gonna be exploring
how we can use ChatGPT in algorithms.
So let's just go ahead
and start with a simple example of prime numbers.
So hey ChatGPT,
could you write me a Python script slash algorithm
to generate all the prime numbers
up until a given number X?
So hopefully it creates some sort of definition
for a function in Python that takes in X as an argument.
And sure enough, that's exactly what it does.
It labels this as a Python script.
It's a function called generate primes,
takes in X as an argument and look at that.
It's even documenting the code that it's writing.
So this is going to be an algorithm that uses
the Sieve of Eratosthenes,
I don't know if I'm saying that correctly,
but Eratosthenes's algorithm to generate all prime numbers
up until given number X.
So we can kind of test that for correctness
in the sense of kind of just running it.
Maybe we're not gonna be able to like
completely fact check it,
'cause as a famous computer scientist once said,
"like test cases or kind of checking certain inputs
and certain outputs can only show the presence of bugs
but does not prove the non-existence of bugs
or like the absence of bugs."
So I don't know if this is completely robust,
but we can try to check it with some numbers
and see if it works, right?
So this is Python code.
Let's actually go over to VS code.
And in my terminal I actually have a,
I have Python installed on my system.
So let's actually go and run Python.
So here I'm actually in the Python terminal.
Let me actually zoom in a bit.
So this is a Python terminal.
Just by running Python on my command line
because I have it installed.
And I can actually go ahead and type in this code.
So we type that in,
paste that in.
We're actually gonna see that there's an unexpected indent.
So let's actually go ahead
and create a file for this instead
just to make things easier.
So let's call this primes.py.
And if I copy that code, this is the function declaration.
So like they said down here, there's an example usage
of the function that generate all the prime numbers
up until 20.
So it's definitely gonna consist of a function call
to generate primes 20
and then it prints the output.
And sure enough, that does make a lot of sense, right?
These are the prime numbers up until 20.
So if you actually go ahead and run that,
if I quit my terminal
and then run that file using py.primes,
we can see that that's actually the output, right?
We can try it for a larger number.
Let's go crazy and put a million
and hopefully that doesn't take too long.
But yeah, that's a lot of output right there.
I guess my computer is pretty fast at that,
as computers are.
So yeah, that's a lotta numbers.
I don't know off the top of my head
if these are the prime numbers,
but I think this algorithm is pretty true and tested.
And that's one thing that ChatGPT's gonna be good at, right,
is if you ask it for a well-established algorithm,
that's gonna be something that's very well documented
and proven and that's gonna be code
that's already out there.
So this is stuff that it's probably
not gonna be getting wrong
because there is a good robust explanation
for how this stuff works.
And there's actually other algorithms
used for generating prime.
So it's interesting that ChatGPT happened to give me one
that was quite well known and efficient.
Could you use an algorithm
other than the Sieve of Eratosthenes?
If I can spell that correctly.
Hopefully I did.
And certainly, here's an implementation
of the trial division algorithm
to generate all prime numbers up until
a given number X and Python.
So this is going to be
a completely different function definition,
but it's probably gonna give us the same output
in terms of generating all the
primes up until a given number.
But yeah, let's go ahead and give that a try too
while we're at it.
So up here we've got the definition
for the Sieve of Eratosthenes.
Let's prefix this function, call it sieve,
so that we don't call it.
So here we're gonna be calling
our new generate primes function.
And if we call it with 20,
it should give us the same output:
2, 3, 5, 7, 11, 13, 17, 19.
So if I go ahead and run that, sure enough,
yep, that's exactly what it's giving us.
So an interesting thing about algorithms,
if you're not familiar with computer science
and the study of sort of Reddit code
and these algorithms in the first place
is that they have ways to be measured.
So those two things are space and time complexity.
So let's actually ask, so this is actually a footnote here
that they include.
"Note that the trial division algorithm is less efficient
than the Sieve for generating prime numbers,
especially for large values of X.
So let's actually go ahead and try that out, right?
'Cause like earlier we went ahead
and ran a million on the Sieve version of this function.
So let's try to run that with Generate Primes.
And oh, you can see that that's taking a little longer
to come out, right?
So it's giving us the same answer, surely,
however you can see that my computer
did actually stall up for like a second or two.
So let's actually ask GPT why that is.
And the way you would phrase that is,
well you could probably ask why is one slower.
So that would be the sort of naive question.
But if you're familiar with the theory behind algorithms,
you could ask it what are the space,
what are the time complexities of both of these algorithms?
So let's see if it can tell us that.
Time complexity of the Sieve of Eratosthenes algorithms
to generate all of the prime numbers up to a given number X
is big O of X times log
of the log of X in the worst case scenario.
So if you don't understand what this means,
the big O notation is a way
of describing the runtime complexity of algorithms
and there's a lot of sort of understanding
that needs to be done there.
But we see here
that the trial division algorithm has a complexity of O of X
to the power of 1.5 in the worst case.
And that's considerably worse, right?
So if you think about the graphs of both of these, right?
So if you kind of view a graph with having function
as a function of the size of your input
and the number of time
that it takes for the algorithm to complete,
this one is going to grow substantially slower
than this one, right?
So this one's gonna blow up.
So as your X increases, the amount of time that it takes
for the algorithm to complete is going to,
could sorta skyrocket because it's like exponential, right?
It's to the power of something.
So yeah, we could see like why that is,
like why did one take longer than the other?
If you want to know more about this,
we can probably continue the conversation with ChatGPT
and just continue asking questions, right?
Like this stuff is gonna work super well if you're like
curious about learning and just know what to ask.