50 Million Primes In 5 Seconds - Segmented Sieve of Eratosthenes
ฝัง
- เผยแพร่เมื่อ 11 ก.พ. 2021
- Making the Sieve of Eratosthenes faster.
We start with code that we wrote in a previous video and progressively make it faster and faster.
― mCoding with James Murphy (mcoding.io)
Source code: github.com/mCodingLLC/prime_s...
Previous video: • Finding Primes in Pyth...
PyPI library: pypi.org/project/prime-sieve/
SUPPORT ME ⭐
---------------------------------------------------
Patreon: / mcoding
Paypal: www.paypal.com/donate/?hosted...
Other donations: mcoding.io/donate
BE ACTIVE IN MY COMMUNITY 😄
---------------------------------------------------
Discord: / discord
Github: github.com/mCodingLLC/
Reddit: / mcoding
Facebook: / james.mcoding - วิทยาศาสตร์และเทคโนโลยี
"hey everyone, in this video we're going to see how to commit 50 million crimes in 5 seconds"
Why is computing a prime a crime!?
@@JFdowsley damn that's a weird thought.
@@mCoding I actually know this one, a bunch of algorithms, including dvd encryption, Blu-ray, CD, etc are based off large prime numbers, knowing the number cracks the algorithm and helps decrypts the source
en.wikipedia.org/wiki/Illegal_prime
@Clayton Cronk 🤪world is bonkers 🙃
@@Azurath100 a prime example of our greed
It would be cool to do a video showing how you profiled the Python code to find that the numpy resize was taking a long time.
Great suggestion! I'll cover profiling at some point for sure.
PyCharm (which is the IDE he's using) makes this very easy. Instead of right clicking the script and selecting "run", select "profile".
@@spaghettihair only in professional version
on linux you can use a package called memray
Hi. I saw this and was inspired to try to beat the 5 seconds. Firstly I wrote the code to sieve the 1,000,000,000 numbers to find the primes and got this down to slightly over 5 seconds. Then I decided to use multiple threads to process each segment - so I have 100 threads each processing a segment of 10,000,000. Sadly this didn't reduce the overall processing time. So I thought about it and decided that there might be a significant number of cache misses slowing the whole processor down so within each thread I sub-divided the segment into 10 "mini" segments of 1,000,000 each which were run sequentially. This seemed to do the trick and now I am computing 50,000,000 primes in 375ms on a Ryzen 3950X processor. Thanks for the video and the challenge.
Awesome!
can i see your code?
@@mrlectus Yes if I can find somewhere to put it.
@@londonbobby thanks
add spaces to the link and past just put it in a form that it wouldn't look like a url
For a second, i was really confused that the video is longer than 5 secs...
Perhaps expecting prime numbers to whiz by at 60 fps?
@@mCoding It'd have to be at 10 million FPS to see all of them
@@linus6718 Not if you cram 1 million of them on every frame
What’s more is I think it’s extremely likely the C++ code could have been faster and simpler if you used the very first python approach with std::vector. Even if every element was 1 byte (it’s not, std::vector uses a bitset under the hood) you would only be using 1GB of RAM which is feasible. Python’s booleans are at least 24 bits long if I remember correctly (hence the huge memory consumed)
Yep
Phew, I dodged a bullet there by manually mallocing 4gb of ram, if I wanted to use bitset I would have typed bitset.
Really great vid!
Great video. You should try the Euler function or one of the methods of finding the distribution of primes or maybe their gaps. Also, a video on Diophantine equations of degree 1 or 2 could be a great idea.
Fun fact, I wrote this sieve exactly to numerically view pi(x) versus x/log x versus Li(x)-Li(2). I got too distracted reading the proof that pi(x)-Li(x) swaps signs infinitely often. Cool stuff!
@@mCoding You should check out David Burton's Elementary number theory, it's got a lot of great ideas. Yuri Manin's intro to number theory is also a great ressource. Cheers!
I going blind, or do you need to bump that font size a pixel or two? Great video otherwise lol
Sorry to mobile users! I made all these videos before I even had 100 views, so I had no idea how many mobile users there are. This will be kept in mind for the future!
@@mCoding no problem lol it also helps for ultrawide monitors where the window is a mile away.
@@JeremyStover Lmfao yeah some code videos on my 34” monitor are pretty hard to read. I can’t imagine like a proper 49” ultrawide lol.
@@mCoding that's okay, I read the class as PrimeListSteve which only added to the video!
@@BillyAtmoreGray The Steve of Eratosthenes 😅
"5 seconds"
C++ buddy here started laughing hysterically
And a machine code coder laughs at the c++ coder
And the quantum programmer laughs at the c++ coder and machine code coder multiple times at the same time (groan)
Yup, Python is garbage for speed.
My C++ prime finder can find the 50,847,534'th prime in 3.5 seconds.
@@MichaelPohoreski you realize your cpu is different from mcoding's? provide your python run time as well
@@Kitulous Sorry, I don't use shit languages.
@@MichaelPohoreski
> "Sorry, I don't use shit languages."
> Uses С++
LOL
Amazing video! What do you think of the lru_cache decorator in python? Would love to see how fast it performs with it. Although using c++ is the fastest way but have you considered using Cython in any of your programs, would love to see a video on that too. Thanks! :D
Thank you !
When you said the profiler identified the array resizing as the most time consuming part, I was immediately assuming you would solve this by preallocating the required array. Not sure why you are using bunches of multiple segments instead.
So I downloaded the code tried this out. With the original code, computing primes below 1e9 takes about 14 seconds on my laptop. When reducing the segment count to 1 again and instead using preallocation, it went down to 11 seconds.
The original question was "I want n primes", but the code instead answers "I want all primes below N". The first question should directly be able to use preallocation, while the second would require to estimate n from N, but I think there are approximations for that.
@mCoding Hi, at 1:02 shouldn't it be for i in range(2, isqrt(n) + 1). I think you forgot to include +1
since python doesn't count until isqrt(n). Let's say n = 10, the list returned would be [2, 3, 5, 7, 9], but 9 is not prime! Hope this helps!
Did not expect the last approach 😂😂
i would have loved to see a generator based approach
Concurrent Sieve? That gets very slow, though.
@@lawrencedoliveiro9104 it wouldn't have to be concurrent. The advantage of generators is that you dont need to store very long lists, ever.
@@laundmo For the Sieve, you do have to store an ever-growing list of generator contexts.
I really like Python, but C or C++ are much better suited to this type of problem. (Ah, I wrote that just before you said you wrote it in C++).
Is the C++ version a logic-copy from the Python one? If not, does it have a easier-to-come-up-with logic? Thanks!
It is a logic copy to the extent possible.
EDITED COMMENT: Hi everyone, turns out I just jumped to write a comment before thinking it through and testing everything. I mixed up "primes up to N" and "N primes". Thus I mistakenly wrote that my code could compute "200 million primes in around 1.3s" which is simply not true. I'm sincerely sorry for this. After testing it properly, my code computes 50 million primes in roughly 8 seconds, which is slower than what @mCoding did with the C++. I'll try to match that speed in C and will edit this comment one final time to reflect my success. Again, I'm sorry for the misleading original comment, I hope you'll have a nice day!
Original comment: Fun fact, we had an assignment at uni to compute 200 million primes in C (Eratosthenes using bit fields) and my code with -O2 compiler optimizations can do it in around 1.3 seconds. That's just absolutely insane.
Edit: Just now I'm realizing I meant "primes up to 200 million" not "200 million primes", which would take (my rough estimate based on π(x) function) about half a minute. I'll update again when I'll test it.
Nice. I was solving the similar problem a week ago and was wondering about the benchmark. 200 million primes that is almost all primes that fit in 32 bits. My results including writting them on a disk were a bit less than 1 minute. I am glad to know more optimizations can be performed. Can you share your code?
@@linuxgaminginfullhd60fps10 Hi, I'm glad you're interested. Sure I could, but I'd need to clean it up a bit (and also translate some variable names and stuff, not a native). I'll reply with a github link once I've sorted it out :)
Great, I'd love to see as well!
i had an assignment (i major in electrical engineering) to write a function checks if a number is prime. i use that function in a for loop. at first it was waaay too slow. took like 45 minutes to calculate until 10^5(9592). after 8 or 9 updates to the code now it takes 9 minutes to calculate until 10^8(50.761.455)(version1.3 or 1.4 took 9 hours). i thought i was decent enough. man i was so wrong :D could i take a glance at your code too?
Not sure if anyone is interested, but I have written a C# method that returns the first 58 million primes in 3.5 seconds. Amazingly it's only 16 lines of readable code long.
I haven't actually found any C# implementation which is faster, let alone as concisely written.
Bare in mind that number is when compiling AOT and with a Ryzen 5950x
How about using a sparse data structure? Currently you are starting with a billion “False” values, but if you had a structure where you only stored the “True” elements, then you would end up needing storage for only about 50 million elements at the end.
I'm not storing a billion false values, I'm only storing false values for a range [p^2, q^2] where p,q are within 100 primes of each other, which for primes in the range we calculated would not nearly be a billion. A sparse way to store values would be cool, but I'm not sure how I would use a sparse data structure because of the way a sieve works. There are non-sieve ways of finding primes, of course, but a sieve by definition stores false values and then gives you what's left.
Is there a way to share common digit chunk like making a tree of shared digit in prime numbers so when stored it used less memory?
Have you tried using wheel factorisation to speed this up? A very fast c++ sieve called primesieve uses this quite well and I'm trying to make something like this in python.
Personally i have not implemented wheel factorization, but i am very much aware of it and recommend others who want to learn faster methods look into it!
I liked the part where you used C++.
Your videos have great content that forced me to watch them but the font size is so small that I trouble seeing it even on my pc. Please if you increase the font a bit it would be great
Matt Parker Math Puzzles number 19 is showing up again. I did eventually go up to 1.408 x 10^12, or the first 52278098188 prime numbers. I pre-made a list of the prime numbers up to 2^32, enough to test all numbers in unsigned 64-bit integers. And yes, I did store the numbers in files (hdf-5 with compression). If you need a list…
That's a lot of primes! How big is the filesize after compression? And how long does it take to load from disk?
I was able to get up to 2^39 (5.5x10^11) To make the leap to 2^40 would've required ~45GB RAM.
@@mCoding The total file size is about 60 GB. Compression in hdf-5 is remarkably effective. I have the files on a NAS, one file for each 10^9 numbers, a total of 1408 now. Since the files are on a network I'm not sure this is the most representative for access speed, but it is workable for the Matt Parker challenge, although the sum of the squares of hte primes quickly go beyond the range of unsigned 64-bit integers.
Very nice
How long did it take your machine to generate this list ?
@@AvinoAm 16 days, if I can trust the file creation dates on my computer. The pre-made list up to 2^32 was a few hours if I recall correctly. It is stored in a bunch of hdf-5 files. Total file size is about 35 GB (with compression).
Can someone suggest fast algorithm to generate primes which are approx 10^300? I tried to implement this as fast as I could but it's still very slow. My implementation can generate primes of order of 10^100, and compile time vary from 2 to 90 seconds
5000 primes
...
5000 primes...
5 seconds
Ok I need to buy an ultra wide monitor with one mile inches to watch this video
I've become more aware of text size in my recent videos, everything after the first dataclasses video should be good about this!
Was this video your tongue in cheek way of saying use a faster language?
Wait, couldn't we just check every number after and before a multiple of six with the previous primes?
I found out this function to print out 100 million primes for about 4 seconds (without using numpy or sympy)
def primes(n):
n, correction = n - n % 6 + 6, 2 - (n % 6 > 1)
sieve = [True] * (n // 3)
for i in range(1, int(n ** 0.5) // 3 + 1):
if sieve[i]:
k = 3 * i + 1 | 1
sieve[k * k // 3::2 * k] = [False] * ((n // 6 - k * k // 6 - 1) // k + 1)
sieve[k * (k - 2 * (i & 1) + 4) // 3::2 * k] = [False] * (
(n // 6 - k * (k - 2 * (i & 1) + 4) // 6 - 1) // k + 1)
return [2, 3] + [3 * i + 1 | 1 for i in range(1, n // 3 - correction) if sieve[i]]
print(primes(100_000_000))
Does anyone have any faster way to share?
May I correct you ?
Your n = 100_000_000 , that n is just roof = it's not the count of primes, the roof number of 100_000_000 return only 5_761_455 primes.
But i rly like your approach, thank you for share.
PS: For 50_847_534 primes, you need 1_000_000_000 roof number.
Apparently my 2013 laptop can do this in 2 seconds according to cpubenchmark. That's probably in C or C++ though. The upper limit of speed. It would probably take dozens of seconds to do this test.
I'm not certain because I can't see all the code but is the Python code and or the C++ code trying each option (like i++) if that's the case we could just check odd numbers and skip the even numbers saving quite a bit of time.
The "Sieve of Sundaram" takes that approach.
Been loving your videos, but we need to get you a new mic!
I got a new microphone all my new videos should have better audio quality!
@@mCoding That’s awesome! Can’t wait till exams are over so I can watch some more of your videos
That's just C with lots of #define to make it look like python.
In py it would be the other way around: 5 primes in 50 million secs.
You are not wrong...
more like 250 secs
or just use cache from functools lol
Hey, are you going to release the C++ code? I feel kinda cheated, you showed off 50 million primes in 5 seconds but didn't share the source 😂
Hmm... I'll consider it.
C# - 3.74s No optimisation. Just used stock .Net. 1 subroutine.
Can you share the repo?
This is why we need a more modern C. We shouldn't need to load libraries that use another language all the time because python or whatever language we are using is so slow and inefficient. You either need to know both languages in case you need to make changes or might as well use C right away because having to learn how some library works when there is a bug or something needs to be changed will cost you a ton of time.
It's not like people haven't tried to make a more modern C. There's C++, D, Zig, and also Rust, which a lot of people love. The thing is, C is familiar, well understood, has compilers for every architecture (including really obscure ones), and it has a ton of libraries which people just need no matter what. No language is ever going to replace C even if it's objectively superior in every possible aspect. Even newer versions of the C standard have trouble replacing old ones.
maybe returning generator instead of making a list will be better (in first example)
Bro it would be great if you could zoom in in the editor in the future similar videos, I am watching from my phone and I can't see anything 😕
This has been pointed out to me now and I'm taking it into account for future videos!
Why so low quality? Why so small?
Last place I expexted to hear sea shanty lol
You are the first one to notice that I've heard!
Code is too small, can’t see anything
i agree
Store an array with previously calculated primes. Get the next largest number, check if any elements in the array divide it if not add to array.
that would be slower
yeah thats slow because then the last one would have to check if 50 million numbers divide it
That's slow for 2 reasons.
1. Complexity. It is at least quadratic. The Sieve thing is around (n log n).
2. Division is an expensive operation, while multiplications and additions are cheap.
yeah i thinks its (n^2 + n) / 2
May someone explain the function of list[int] at 2:22 line 10?
It's just a static compile-time(if that can even be applied to python) type checking. It makes sure that self.primes is a list of integers, but it only does anything in development/on interpreter's correctness pass, as far as I know.
Handy for developers to prevent them from shooting their foot, but does absolutely nothing in runtime.
Great video. I just wanna know, what ( n: int ) --> list[int] mean & how usually it's called?
It's my first time seeing it
You probably know this by this point, but for anyone wondering the same, it's type hinting. I don't think it does anything performance-wise, instead it makes it more clear to other people reading/using your code what your methods are supposed to represent or work on. : int means is supposed to be an int (but no errors will be thrown if that's not the case) and def sample_method() -> int means that sample_method() should return an int
I feel like youtube hates me. I just spent days writing code that generated 50 million primes in 24 hours
is there a a repo for your C++ version?
You lied. It's eleven minutes thirty-eight seconds long, not five seconds.
Can you give as the implementation for C++? @mCoding
Please make code alone bigger size letters
I'll keep that in mind for future vids!
yeah the sieve if eratosthenes is cool to show off how to compute primes but it'S not really practical for seeing if a number is a prime which is one of the main aspects in cryptographics where most prime math is actually used would be cool to have some coding on those matters
Indeed, the purpose of a sieve is not to check if a single number is prime, but to find all the primes!
maybe you could have gone only up to 10**7 and tested the speed for various n parameters to find the best one?
Great idea! And secretly behind the scenes I did exactly that, it just didn't make it into the video.
@@mCoding what value did you end up with?
Why'd you make this video? Just use pip install prime-sieve
\s
Some day...
Easy! just find a website that lists the first 50 million primes, make python download the file and print it. I bet it takes less than 5 seconds. (this is a joke)
Pls zoom IDE /code little bit .. watching in mobile code looks like a lines.
This is an old video, I'm much more aware of mobile viewers in newer videos!
I don't think you are calculating the "50 million primes" if your print out is any indication. The 50 millionth prime is 982,451,653
the print is the count of primes smaller than n, where the n used in this video is 1,000,000,000 so 50,847,534 means there are 50,847,534 prime numbers between 1 and n (where n is 1,000,000,000) so he is in fact not only calculating 50 million primes but also 847,534 more. The actual prime numbers are not printed out.
Thanks for explaining, exactly this!
So we learned: first we spend a couple of hours doing it in Python. As this totally too slow we start using Python code to wrap around a C++ library. Then we do it again in real C++ (without the need for any additional libraries, just using the std lib) and it runs 10 times faster with the same amount of code an no additional complexity (and typically C++ code is much easier to read as compared to Python). Overall, the net benefit of Python is minus a couple of hours of wasted time. Lesson learned is next time, don't waste time in Python and do it in C++ right away.
i do totally agree with you that in practice, this should not be implemented in python, but you have to admit that demonstrating this algorithm for beginners is easier done in python than in c++, python by itself can be a very good way to learn programming quickly.
@@imadhamaidi I disagree regarding easier to learn. My feeling is that Python is always second best. The only advantage was: the interpreter / runtime is free. But that only used to be an advantage. Java, C# and even C++ can be compiled / executed for free. And they are just as complex to learn as Python. But they are all WAY more powerful, mature and just as easy to use. The times when something in C# needed more lines as compared to Python are long over... So don't waist time leaning something that you have to replace later. Admitting: a LOT of code for AI and Big Data is written in Python. If you specialize in these domains learning Python can be a good idea.
i wonder how people can code like that. why make it that complicated? ive learned python for years and cant read this code at all.
Getting speed out of code is often at odds with making it readable!
@@mCoding thx for answering. its probably just me being too comfortable with the basics. but theyre enough for my personal projects.
Keep at it and you will become more experienced and more comfortable with these!
Using classes and some external shit with weird names like "smallest_multiple_of_n_geq_m" is absolute fkn overkill, this should all be done with 10 lines of code so even a kid could understand this
What can you say for 2,000,000,000 in 3s?
Look for the MMSieve method ...
I can say you're not using Python anymore 😉
@@mCoding You're right. Python is not my way of programming. I prefer java. An implementation of the MMSieve sieve in Python would be interesting. Maybe you will undertake?:-)
@@mCoding Latest C ++ implementation 2,000,000,000 in 1.3s. (Very standard PC)
5:09 of course it's inefficient. You could've just used the bisect module for binary search.
I installed it and when importing it upon running I get an error in line 2 of the library of some print a
Step 1: Install Numba
Step 2: Fail because numba is bad at dealing with large numbers
@@usualunusualkid7149 Step3: Use small numbers
@@tomowen8932 50 million is a large number
@@usualunusualkid7149 then don’t use 50 million
@@tomowen8932 The title of the video literally says "finding 50 million primes in 5 seconds", if numba can't handle 50 million then why would you recommend it for this video?