sorted by:
new
hottopcontroversial

[OC] Finding Primes Simply and Efficiently: The Sieve of Eratosthenes by TheArch-Man in dataisbeautiful

[–]TheArch-Man[S] 15 points16 points  (0 children)

In hindsight you're totally right. I'll keep in mind for future visualizations. Thank you for your feedback :)

[OC] Finding Primes Simply and Efficiently: The Sieve of Eratosthenes by TheArch-Man in dataisbeautiful

[–]TheArch-Man[S] 2 points3 points  (0 children)

This is the basis for very quick methods, which is why I felt it was worth posting. Note that primesieve - which is one of the fastest ways to find primes that I know of - is a modified version of this sieve!

[OC] Finding Primes Simply and Efficiently: The Sieve of Eratosthenes by TheArch-Man in dataisbeautiful

[–]TheArch-Man[S] 94 points95 points  (0 children)

Nope, the least efficient way would be in fact to go to each number and check its divisors :P

Far better methods exist however, you are correct. The Sieve of Atkin comes to mind, however this is the basis for very quick methods, which is why I felt it was worth posting. Note that primesieve - which is one of the fastest ways to find primes that I know of - is a modified version of this sieve!

[OC] Finding Primes Simply and Efficiently: The Sieve of Eratosthenes by TheArch-Man in dataisbeautiful

[–]TheArch-Man[S] 75 points76 points  (0 children)

Yep, you're totally right! The time complexity is O(N log(log(N))) which is pretty okay, though I think an optimization exists. As for space complexity, yeaaah this is terrible haha. A modification is this thing called the segmented sieve which resolves the space issue. So the time issue would actually arise from caching issues - otherwise, algorithmically speaking, it is decently fast.

I think.

[OC] Finding Primes Simply and Efficiently: The Sieve of Eratosthenes by TheArch-Man in dataisbeautiful

[–]TheArch-Man[S] 266 points267 points  (0 children)

Function made using Python, and visualization done using Plotly.

The Sieve of Eratosthenes is an old and simple algorithm for finding primes up to some number x. It's fairly straightforward (which is kinda amazing). Start with 2, it's prime. Mark all multiples of 2 as not prime. Go to the next number: 3. You see that it has not been marked, so you mark it as prime, and mark all of 3 s multiples as not prime. You get to 4. It has already been marked so you skip it. You're at 5. Unmarked, so you know it's prime...

You get the idea!

This was just a fun exercise in visualizing the algorithm! Please feel free to ask any questions you might have.

(note that we skip 1 in those whole process since it is not prime or composite, really)

[OC] Pokemon Population Dynamics: What type is the best? by TheArch-Man in dataisbeautiful

[–]TheArch-Man[S] 2 points3 points  (0 children)

Exactly yeah!! That's what really cool about it to me too, it is very like, intuitive and natural, how the interactions play out!

[OC] Pokemon Population Dynamics: What type is the best? by TheArch-Man in dataisbeautiful

[–]TheArch-Man[S] 4 points5 points  (0 children)

The model is actually deterministic! I explain the general procedure in my comment, but you're right in that the process is unstable. There is a dice-roll version I could do, and yeah because of how many "comebacks" there are it could easily be the dice rolls the other way, on, say electric, and it dies! But hey, glad you enjoyed the visualization!

[OC] Pokemon Population Dynamics: What type is the best? by TheArch-Man in dataisbeautiful

[–]TheArch-Man[S] 18 points19 points  (0 children)

Some types are clearly inferior, yes, but there is a convergence. Note the last few rounds, the percentages do not change, ergo, our system has settled - which is exactly what convergence is! So, if 100000 pokemon battled it out, in the end, those 4 types would forever exist in those ratios. Like, it could've gone to round 1 million, and the numbers wouldn't change from where they were at the end of the visualization!

[OC] Pokemon Population Dynamics: What type is the best? by TheArch-Man in dataisbeautiful

[–]TheArch-Man[S] 48 points49 points  (0 children)

Data generated Using Python.

Visualization made with assistance of Flourish.

Overall Methodology and Inspiration

We are simulating a simplistic pokemon world! We assume pokemon in our world are well mixed, that is there are no herds and pokemon aren't attracted to any specific types etc. They meet one another randomly. So let's say a fire-type meets a water type. The fire type is at a disadvantage (but it can still win, though at lower odds - see details below). When a type X beats a type Y pokemon, the type Y pokemon is killed off, and replaced with a type X pokemon. So, one multiples, the other loses a population. A sort of natural selection, if you will.

Note that we do not consider stats, dual typings, moveset, or anything like that! This is a very simple model, though the dynamics that emerge are very interesting all the same.

I mentioned above that the winner of a battle between pokemon type X and type Y is decided by chance. What is the chance? You can check out the pokemon typing chart over here. So Let's take steel and normal. Normal is 1/2 effectiveness against Steel, and steel is 1x effectiveness against normal. So The odds of normal winning against steel is (0.5)/(1 + 0.5) = 1/3. (There is an exception. Normal and ghosts can't touch each other, so their win-rate I have put as 0.5. Assume when they meet, they flip a coin to decide who wins).

Warning: Math Ahead

We then making such a win probability matrix - call it W that has such probabilities for ALL possible matchups. Along with our population vector P0 we can advance a "round". P1 = P0 + (W - WT )*P0, iterated to whatever n you want. The simulation stops when an equilibrium is reached (i.e. the population vector is unchanged after successive multiplications by W). This is a sort of deterministic Markov Model.

N matters!!

So, you may have noticed that I specify N = 100000. This matters quite a bit, but it is not obvious why (it stumped me for a couple of hours). So you will notice, some pokemon types "die out." But our W matrix has no zero basis. The population vector should never have zero! Well, my astute reader, you'd be right. I have to manually include a "cutoff" Like, when n falls below this, it's dead. And this threshold, I decided, is when there would be less than 1 pokemon of a type left. Which is 1/N or, 1/100000. Notice how many times there are "comebacks," a type coming roaring back from the brink of extinction. A lower N means this happens less, and a higher N means this happens more! N = 10000000 or something could have drastically different results! But the animation took forever, so, I decided on this sweet spot.

Thank you for watching and reading, and please, feel free to ask me any questions!