andreaferretti / emmy Goto Github PK
View Code? Open in Web Editor NEWLicense: Apache License 2.0
License: Apache License 2.0
This repo's implementation of sieveUpTo
called by primesUpTo*
has got to be one of the slowest and most wasteful of memory implementation of the Sieve of Eratosthenes of any I have seen...
The problems are as follows:
IntSet
as it's base storage, it uses multiple bytes per stored composite entry, which memory use is so high that it can't sieve even up to a billion as it consumes Gigabytes of memory over that range as it uses many bytes per entry for every composite number over the range.It has the single advantage of being short. However, it can't sieve to a billion using a reasonably amount of RAM memory and even if it could it would take about a minute or so.
A much better short implementation which greatly reduces the memory consumption such that very large ranges can be sieved (although still somewhat slowly due to the hashing) is as follows:
# compile with "-d:release -d:danger"
import tables
type PrimeType = uint64
proc primesHashTable(): iterator(): PrimeType {.closure.} =
iterator output(): PrimeType {.closure.} =
# some initial values to avoid race and reduce initializations...
yield 2.PrimeType; yield 3.PrimeType; yield 5.PrimeType; yield 7.PrimeType
var h = initTable[PrimeType,PrimeType]()
var n = 9.PrimeType
let bps = primesHashTable()
var bp = bps() # advance past 2
bp = bps(); var q = bp * bp # to initialize with 3
while true:
if n >= q:
let inc = bp + bp
h.add(n + inc, inc)
bp = bps(); q = bp * bp
elif h.hasKey(n):
var inc: PrimeType
discard h.take(n, inc)
var nxt = n + inc
while h.hasKey(nxt): nxt += inc # ensure no duplicates
h.add(nxt, inc)
else: yield n
n += 2.PrimeType
output
# tested as...
from times import epochTime
let limit = 100_000_000.PrimeType
let start = epochTime()
let iter = primesHashTable()
var count = 0
for p in iter():
if p > limit: break else: count.inc
let elpsd = (epochTime() - start) * 1000.0
echo "Found ", count, " primes up to ", limit, " in ", elpsd, " milliseconds."
This is an "incremental" Odds-Only Sieve of Eratosthenes and only stores a hash entry for each of the base primes up to the square root of the current iteration value (determined automatically by the recursive secondary base primes feed). It still takes about a minute to count the number of primes to a billion, but at least it doesn't take an excessive amount of memory to do so. Its output also doesn't consume memory as it is just an iterator over the "incrementally" found primes.
If being so short isn't a consideration, the Page Segmented Bit-Packed Odds-Only Unbounded Sieve of Eratosthenes from RosettaCode is fast as in only taking about a second to sieve to a billion, consumes even less memory, and can even relatively easily have multi-threading added, but is over a hundred lines of code.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.