<---- template headericclude ----->
Programming Challenge - list prime numbers - Page 3
FedoraForum.org - Fedora Support Forums and Community
Page 3 of 4 FirstFirst 1234 LastLast
Results 31 to 45 of 60
  1. #31
    Join Date
    Nov 2006
    Location
    Detroit
    Posts
    8,750
    Mentioned
    63 Post(s)
    Tagged
    0 Thread(s)

    Re: Programming Challenge - list prime numbers

    Here's an example in Julia. It only lists all primes up to the number N, so it's comparable to the examples other people here have given. It requires Julia 0.5.0, which is in the F25 repos (dnf install julia).

    Save this as getPrimes.jl:
    Code:
    import Primes
    println(primes(2, parse(Int64, ARGS[1])))
    Sample output:
    Code:
    $ julia getPrimes.jl 100
    [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
    Takes under 2 seconds to get all primes up to 1 million, and under 40 seconds for up to 1 billion:
    Code:
    $ time julia getPrimes.jl 1000000 > primes.log
    
    real    0m1.634s
    user    0m1.471s
    sys     0m0.250s
    
    $ time julia getPrimes.jl 1000000000 > primes.log
    
    real    0m38.366s
    user    0m30.577s
    sys     0m2.235s
    OS: Fedora 39 x86_64 | Machine: Lenovo ThinkCentre M91P | CPU: Intel Core i5-2500 (4)@3.30GHz | RAM: 32GB PC3-12800 DDR3 | Disks: Seagate Barracuda ST500DM002 500GB SATA, Seagate Constellation ES.3 ST1000NM0033 1TB SATA | Video: Intel HD Graphics 2000 128MB | Sound: Turtle Beach Santa Cruz CS4630 | Ethernet: Intel 82579LM

  2. #32
    Join Date
    Dec 2005
    Location
    North Carolina
    Age
    34
    Posts
    1,162
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Re: Programming Challenge - list prime numbers

    This is in Python 3. Mine is not as performant as the latest examples, but I just thought I would share.

    Code:
    #!/usr/bin/env python3
    import sys
    
    
    def eratosthenes_sieve(n):
        our_list = []
        marks = []
        for e in range(2, n+1):
            our_list.append(e)
            marks.append(None)
    
        i = 0
        while i < len(our_list) / 2:
            if marks[i] is None:
                j = 2
                while j * our_list[i] <= our_list[-1]:
                    marks[(j*our_list[i])-2] = True
                    j += 1
            i += 1
    
        new_list = []
        i = 0
        while i < len(marks):
            if marks[i] is None:
                new_list.append(our_list[i])
            i += 1
    
        return new_list
    
    
    if __name__ == '__main__':
        print(eratosthenes_sieve(int(sys.argv[1])))
    Laptop: Lenovo ThinkPad T410, CPU: Intel Core i5 520M, Ram: 8GB DDR3, Hard Drive: 320GB, Graphics: Intel HD, OS: Windows 7 / Arch Linux x86_64
    Desktop: Motherboard: ASRock Fatal1ty AB350 Gaming K4, CPU: AMD Ryzen 3 1200, RAM: 8GB DDR4, Storage: Samsung 850 Pro 256GB, Graphics: Asus Radeon RX 550 4GB, OS: Arch Linux x86_64

  3. #33
    Join Date
    Nov 2006
    Location
    Detroit
    Posts
    8,750
    Mentioned
    63 Post(s)
    Tagged
    0 Thread(s)

    Re: Programming Challenge - list prime numbers

    Flounder, I'm surprised you didn't do a Perl example. Here's one that lists all the primes (hit Ctrl-c to stop):
    Code:
    $ perl -e '$|++;(1 x$_)!~/^1?$|^(11+?)\1+$/&&print"$_ "while ++$_'
    OS: Fedora 39 x86_64 | Machine: Lenovo ThinkCentre M91P | CPU: Intel Core i5-2500 (4)@3.30GHz | RAM: 32GB PC3-12800 DDR3 | Disks: Seagate Barracuda ST500DM002 500GB SATA, Seagate Constellation ES.3 ST1000NM0033 1TB SATA | Video: Intel HD Graphics 2000 128MB | Sound: Turtle Beach Santa Cruz CS4630 | Ethernet: Intel 82579LM

  4. #34
    Join Date
    Oct 2010
    Location
    Canberra
    Posts
    3,899
    Mentioned
    14 Post(s)
    Tagged
    1 Thread(s)

    Re: Programming Challenge - list prime numbers

    Quote Originally Posted by RupertPupkin
    Flounder, I'm surprised you didn't do a Perl example. Here's one that lists all the primes (hit Ctrl-c to stop):
    Code:
    $ perl -e '$|++;(1 x$_)!~/^1?$|^(11+?)\1+$/&&print"$_ "while ++$_'
    Sorry, can you post that again - I seem to have just got line noise.

    I have many ideas, even some I haven't thought of yet.

  5. #35
    Join Date
    Oct 2010
    Location
    Canberra
    Posts
    3,899
    Mentioned
    14 Post(s)
    Tagged
    1 Thread(s)

    Re: Programming Challenge - list prime numbers

    This is encouraging.
    Prior to splitting the processing across threads I modified the algorithm to use a vector of bitset rather than a vector of bool. The bitsets are 200K bits and will be the pages that are to be processed by the threads.
    The good news is that despite the additional overhead of handling pages the result is a second faster (13 secs for a billion).
    About 3 seconds of the total is printing the results, so with 4 cores I hope to get under 6 seconds for the total.

    I have many ideas, even some I haven't thought of yet.

  6. #36
    Join Date
    Dec 2012
    Location
    santa barbara, CA
    Posts
    1,292
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Re: Programming Challenge - list prime numbers

    Quote Originally Posted by ocratato
    This is encouraging.
    Prior to splitting the processing across threads I modified the algorithm to use a vector of bitset rather than a vector of bool. The bitsets are 200K bits and will be the pages that are to be processed by the threads.
    The good news is that despite the additional overhead of handling pages the result is a second faster (13 secs for a billion).
    About 3 seconds of the total is printing the results, so with 4 cores I hope to get under 6 seconds for the total.
    Awesome. I'll get back on the boat on Tue. On another project atm.
    Question, did you use byte alignment (char array) for the bit pools or long ints ?

  7. #37
    Join Date
    Nov 2006
    Location
    Detroit
    Posts
    8,750
    Mentioned
    63 Post(s)
    Tagged
    0 Thread(s)

    Re: Programming Challenge - list prime numbers

    Here's an example in Scheme to get the primes up to N>=1, using the Guile interpreter (dnf install guile).

    Save this as getPrimes.scm:
    Code:
    (define (primes n)
       (let ((bits (make-vector (+ n 1) #t)))
          (let loop ((p 2) (ps '()))
             (cond ((< n p) (reverse ps))
                ((vector-ref bits p)
                   (do ((i (+ p p) (+ i p))) ((< n i))
                      (vector-set! bits i #f))
                   (loop (+ p 1) (cons p ps)))
                (else (loop (+ p 1) ps))))))
    (define (main args) (display (primes (string->number (cadr args))))(newline))
    Sample output:
    Code:
    $ guile --no-auto-compile -e main -s getPrimes.scm 101
    (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101)
    OS: Fedora 39 x86_64 | Machine: Lenovo ThinkCentre M91P | CPU: Intel Core i5-2500 (4)@3.30GHz | RAM: 32GB PC3-12800 DDR3 | Disks: Seagate Barracuda ST500DM002 500GB SATA, Seagate Constellation ES.3 ST1000NM0033 1TB SATA | Video: Intel HD Graphics 2000 128MB | Sound: Turtle Beach Santa Cruz CS4630 | Ethernet: Intel 82579LM

  8. #38
    Join Date
    Oct 2010
    Location
    Canberra
    Posts
    3,899
    Mentioned
    14 Post(s)
    Tagged
    1 Thread(s)

    Re: Programming Challenge - list prime numbers

    Here is my multi-threaded C++ version:
    Code:
    // a multithreaded seive of Eratosthenes
    //
    #include <cstdio>
    #include <cstdlib>
    #include <vector>
    #include <bitset>
    #include <thread>
    #include <cmath>
    
    
    using namespace std;
    typedef unsigned long int ul64;
    
    //
    // Use a bitset to hold the flags indicating if we
    // have found a prime. 
    // The size should be small enough to fit in a CPU cache (32KB)
    // given that the bitset stores 8 bits per byte.
    const ul64 BITSETSZ = 200000;
    typedef bitset<BITSETSZ> Bits;
    
    // Ideally this would be determined at run time.
    const int NumThreads = 4;
    
    // ------------------------------------------------
    
    // Provide our own alternative to printf that is dedicated to
    // printing integers and buffers its results to reduce I/O overhead.
    //
    inline void print_int(ul64 val)
    {
    	static char outbuf[4096];
    	static int p = 0;
    
    	char chars[16];
    	int digits = 0;
    
    	//
    	// Pass zero to flush the buffer.
    	if ( val == 0 )
    	{
    		fwrite(outbuf, 1, p, stdout );
    		p = 0;
    		return;
    	}
    
    	do
    	{
    		chars[digits++] = ((val % 10) + 0x30);
    		val /= 10;
    	} while (val && digits < 16);
    
    
    	while (digits>0)
    	{
    		outbuf[p++] = chars[--digits];
    	}
    	outbuf[p++] = '\n';
     
    	if ( p > 4080 )
    	{
    		fwrite(outbuf, 1, p, stdout );
    		p = 0;
    	}
    }
    
    // ------------------------------------------------
    
    //
    // Print the prime numbers.
    //
    void print_results( vector<Bits> & primes, ul64 limit )
    {
    	ul64 numPages = primes.size();
    	Bits & primeSetZero = primes[0];
    
    	//
    	// If there is only one page then it will be starting at 2
    	// and ending at limit.
    	// Otherwise the first page starts a 2 and the last page
    	// ends at limit. All other pages print the entire range.
    	//
    
    	if ( numPages == 1 )
    	{
    		for( ul64 i=2; i<=limit; i++ )
    		{
    			if( primeSetZero[i] ) print_int( i );
    		}
    	}
    	else
    	{
    		for(ul64 i=2; i<BITSETSZ; i++)
    		{
    			if( primeSetZero[i] ) print_int( i );
    		}
    		for( ul64 p=1; p<numPages-1; p++ )
    		{
    			ul64 x = p * BITSETSZ;
    			Bits & primeSet = primes[p];
    			for(ul64 i=0; i<BITSETSZ; i++)
    			{
    				if( primeSet[i] ) print_int( x + i );
    			}
    		}
    
    		ul64 x = (numPages-1) * BITSETSZ;
    		for( ul64 i=0; (x+i)<=limit; i++ )
    		{
    			if( primes[numPages-1][i] ) print_int( x+i );
    		}
    	}
    	print_int(0); // flush the buffer
    }
    
    // ------------------------------------------------
    
    void cull_pages( vector<Bits> & primes, int thread )
    {
    	//
    	// cull out the multiples of each prime on each page
    	ul64 numPages = primes.size();
    	Bits & primeSetZero = primes[0];
    
    	for( ul64 p=thread; p<numPages; p += NumThreads )
    	{
    		Bits & primeSet = primes[p];
    		// loop over the primes in the first page
    		for( ul64 i=2; i<BITSETSZ; i++)
    		{
    			if( primeSetZero[i] )
    			{
    				// calculate the offset of this prime on this page
    				ul64 k = (p * BITSETSZ) % i;
    				if ( k ) k = i - k;
    				//
    				// cull out the multiples
    				while( k < BITSETSZ )
    				{
    					primeSet[k] = false;
    					k += i;
    				}
    			}
    		}
    	}
    }
    
    // ------------------------------------------------
    
    int main(int argc,char *argv[])
    {
            ul64 limit=atoll(argv[1]);
            printf("Calculating primes up to: %lu\n",limit);
    	//
    	// make sure we include the end in our seive
    	limit++;
    
    	//
    	// The largest factor of limit is sqrt(limit)
    	ul64 range = sqrt(limit);
    	if ( BITSETSZ < range )
    	{
    		// 
    		// Limit ourselves to 40 billion
    		ul64 n = BITSETSZ*BITSETSZ;
    		printf( "max range for program is %lu\n", n );
    		return 1;
    	}
    
    	//
    	// Now we need enough bitsets to hold the entire range
    	// (Later - odd numbers only).
    	vector< Bits > primes( limit / BITSETSZ +1);
    	//
    	// initialise to set;
    	for( auto &b : primes) b.set();
    
    	//
    	// first we calc the primes for the first page
    	Bits & primeSetZero = primes[0];
    	for( ul64 i=2; i<BITSETSZ; i++)
    	{
    		if( primeSetZero[i] )
    		{
    			ul64 k = i*i;
    			while( k < BITSETSZ )
    			{
    				primeSetZero[k] = false;
    				k += i;
    			}
    		}
    	}
    
    	//
    	// Then we cull the remaining pages.
    	// start the threads
    	std::thread threads[NumThreads];
    	for (int t=0; t<NumThreads; t++ )
    	{
    		// std::ref is our promise that primes will hang around
    		// until the thread finishes.
    		threads[t] = std::thread( cull_pages, std::ref(primes), t+1 );
    	}
    
    	//
    	// Wait until they are done
    	for (int t=0; t<NumThreads; t++ )
    	{
    		threads[t].join();
    	}
    
    	print_results( primes, limit );
    	
    	return 0;
    }
    Code:
    [brenton@acer primes]$ g++ -Ofast -std=c++11 primes4.cpp -o primes4 -lpthread
    [brenton@acer primes]$ time ./primes4 1000000000 > primes4.dat
    
    real	0m8.233s
    user	0m17.938s
    sys	0m0.708s
    Last edited by ocratato; 21st March 2017 at 01:10 AM.

    I have many ideas, even some I haven't thought of yet.

  9. #39
    Join Date
    Dec 2005
    Location
    North Carolina
    Age
    34
    Posts
    1,162
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Re: Programming Challenge - list prime numbers

    Quote Originally Posted by RupertPupkin
    Flounder, I'm surprised you didn't do a Perl example. Here's one that lists all the primes (hit Ctrl-c to stop):
    Code:
    $ perl -e '$|++;(1 x$_)!~/^1?$|^(11+?)\1+$/&&print"$_ "while ++$_'
    I actually don't know Perl. I've thought about learning it at some point, but right now I'm trying to focus on getting stuff done rather than learning more languages.

    Here's another example in Rust that I did when starting off CIS198.

    eratosthenes.rs
    Code:
    use std::env;
    
    /// Find all prime numbers less than `n`.
    /// For example, `sieve(7)` should return `[2, 3, 5]`
    pub fn sieve(n: u32) -> Vec<u32> {
        let mut ns: Vec<u32> = Vec::new();
        let mut marks: Vec<bool> = Vec::new();
        let mut primes: Vec<u32> = Vec::new();
        let mut i = 2;
    
        // Populate the vector with numbers 2..n
        while i <= n {
            ns.push(i);
            marks.push(false);
            i += 1;
        }
    
        // mark all non-prime numbers
        let mut i: usize = 0;
        while i < ns.len() {
            if marks[i] == false {
                let step = ns[i] as usize;
                let mut j = i + step;
                primes.push(step as u32);
                while j < marks.len() {
                    marks[j] = true;
                    j += step;
                }
            }
            i += 1;
        }
    
        // Should be only primes now
        primes
    }
    
    fn main() {
        let args: Vec<_> = env::args().collect();
    
        if args.len() > 1 {
            let n: u32 = args[1].parse().unwrap();
            let primes = sieve(n);
            for x in primes {
                print!("{} ", x);
            }
            print!("\n");
        }
    }
    Compile with:
    Code:
    rustc eratosthenes.rs
    You can get rustc either through rustup or the repos.

    Writing a Haskell example is going to be a bit tricky, but I think I can get similar performance to Python with it.
    Laptop: Lenovo ThinkPad T410, CPU: Intel Core i5 520M, Ram: 8GB DDR3, Hard Drive: 320GB, Graphics: Intel HD, OS: Windows 7 / Arch Linux x86_64
    Desktop: Motherboard: ASRock Fatal1ty AB350 Gaming K4, CPU: AMD Ryzen 3 1200, RAM: 8GB DDR4, Storage: Samsung 850 Pro 256GB, Graphics: Asus Radeon RX 550 4GB, OS: Arch Linux x86_64

  10. #40
    Join Date
    Nov 2006
    Location
    Detroit
    Posts
    8,750
    Mentioned
    63 Post(s)
    Tagged
    0 Thread(s)

    Re: Programming Challenge - list prime numbers

    Quote Originally Posted by Flounder
    I actually don't know Perl.
    Oh yeah, that's right - you're the Python guy. I got you mixed up with ah7013, the Perl guy.
    OS: Fedora 39 x86_64 | Machine: Lenovo ThinkCentre M91P | CPU: Intel Core i5-2500 (4)@3.30GHz | RAM: 32GB PC3-12800 DDR3 | Disks: Seagate Barracuda ST500DM002 500GB SATA, Seagate Constellation ES.3 ST1000NM0033 1TB SATA | Video: Intel HD Graphics 2000 128MB | Sound: Turtle Beach Santa Cruz CS4630 | Ethernet: Intel 82579LM

  11. #41
    Join Date
    Nov 2006
    Location
    Detroit
    Posts
    8,750
    Mentioned
    63 Post(s)
    Tagged
    0 Thread(s)

    Re: Programming Challenge - list prime numbers

    Quote Originally Posted by ocratato
    Here is my multi-threaded C++ version:
    Code:
    // a multithreaded seive of Eratosthenes
    //
    #include <cstdio>
    #include <cstdlib>
    #include <vector>
    #include <bitset>
    #include <thread>
    #include <cmath>
    
    
    using namespace std;
    typedef unsigned long int ul64;
    
    //
    // Use a bitset to hold the flags indicating if we
    // have found a prime. 
    // The size should be small enough to fit in a CPU cache (32KB)
    // given that the bitset stores 8 bits per byte.
    const ul64 BITSETSZ = 200000;
    typedef bitset<BITSETSZ> Bits;
    
    // Ideally this would be determined at run time.
    const int NumThreads = 4;
    
    // ------------------------------------------------
    
    // Provide our own alternative to printf that is dedicated to
    // printing integers and buffers its results to reduce I/O overhead.
    //
    inline void print_int(ul64 val)
    {
    	static char outbuf[4096];
    	static int p = 0;
    
    	char chars[16];
    	int digits = 0;
    
    	//
    	// Pass zero to flush the buffer.
    	if ( val == 0 )
    	{
    		fwrite(outbuf, 1, p, stdout );
    		p = 0;
    		return;
    	}
    
    	do
    	{
    		chars[digits++] = ((val % 10) + 0x30);
    		val /= 10;
    	} while (val && digits < 16);
    
    
    	while (digits>0)
    	{
    		outbuf[p++] = chars[--digits];
    	}
    	outbuf[p++] = '\n';
     
    	if ( p > 4080 )
    	{
    		fwrite(outbuf, 1, p, stdout );
    		p = 0;
    	}
    }
    
    // ------------------------------------------------
    
    //
    // Print the prime numbers.
    //
    void print_results( vector<Bits> & primes, ul64 limit )
    {
    	ul64 numPages = primes.size();
    	Bits & primeSetZero = primes[0];
    
    	//
    	// If there is only one page then it will be starting at 2
    	// and ending at limit.
    	// Otherwise the first page starts a 2 and the last page
    	// ends at limit. All other pages print the entire range.
    	//
    
    	if ( numPages == 1 )
    	{
    		for( ul64 i=2; i<=limit; i++ )
    		{
    			if( primeSetZero[i] ) print_int( i );
    		}
    	}
    	else
    	{
    		for(ul64 i=2; i<BITSETSZ; i++)
    		{
    			if( primeSetZero[i] ) print_int( i );
    		}
    		for( ul64 p=1; p<numPages-1; p++ )
    		{
    			ul64 x = p * BITSETSZ;
    			Bits & primeSet = primes[p];
    			for(ul64 i=0; i<BITSETSZ; i++)
    			{
    				if( primeSet[i] ) print_int( x + i );
    			}
    		}
    
    		ul64 x = numPages * BITSETSZ;
    		for( ul64 i=0; (x+i)<=limit; i++ )
    		{
    			if( primes[numPages-1][i] ) print_int( x+i );
    		}
    	}
    	print_int(0); // flush the buffer
    }
    
    // ------------------------------------------------
    
    void cull_pages( vector<Bits> & primes, int thread )
    {
    	//
    	// cull out the multiples of each prime on each page
    	ul64 numPages = primes.size();
    	Bits & primeSetZero = primes[0];
    
    	for( ul64 p=thread; p<numPages; p += NumThreads )
    	{
    		Bits & primeSet = primes[p];
    		// loop over the primes in the first page
    		for( ul64 i=2; i<BITSETSZ; i++)
    		{
    			if( primeSetZero[i] )
    			{
    				// calculate the offset of this prime on this page
    				ul64 k = (p * BITSETSZ) % i;
    				if ( k ) k = i - k;
    				//
    				// cull out the multiples
    				while( k < BITSETSZ )
    				{
    					primeSet[k] = false;
    					k += i;
    				}
    			}
    		}
    	}
    }
    
    // ------------------------------------------------
    
    int main(int argc,char *argv[])
    {
            ul64 limit=atoll(argv[1]);
            printf("Calculating primes up to: %lu\n",limit);
    	//
    	// make sure we include the end in our seive
    	limit++;
    
    	//
    	// The largest factor of limit is sqrt(limit)
    	ul64 range = sqrt(limit);
    	if ( BITSETSZ < range )
    	{
    		// 
    		// Limit ourselves to 40 billion
    		ul64 n = BITSETSZ*BITSETSZ;
    		printf( "max range for program is %lu\n", n );
    		return 1;
    	}
    
    	//
    	// Now we need enough bitsets to hold the entire range
    	// (Later - odd numbers only).
    	vector< Bits > primes( limit / BITSETSZ +1);
    	//
    	// initialise to set;
    	for( auto &b : primes) b.set();
    
    	//
    	// first we calc the primes for the first page
    	Bits & primeSetZero = primes[0];
    	for( ul64 i=2; i<BITSETSZ; i++)
    	{
    		if( primeSetZero[i] )
    		{
    			ul64 k = i*i;
    			while( k < BITSETSZ )
    			{
    				primeSetZero[k] = false;
    				k += i;
    			}
    		}
    	}
    
    	//
    	// Then we cull the remaining pages.
    	// start the threads
    	std::thread threads[NumThreads];
    	for (int t=0; t<NumThreads; t++ )
    	{
    		// std::ref is our promise that primes will hang around
    		// until the thread finishes.
    		threads[t] = std::thread( cull_pages, std::ref(primes), t+1 );
    	}
    
    	//
    	// Wait until they are done
    	for (int t=0; t<NumThreads; t++ )
    	{
    		threads[t].join();
    	}
    
    	print_results( primes, limit );
    	
    	return 0;
    }
    Code:
    [brenton@acer primes]$ g++ -Ofast -std=c++11 primes4.cpp -o primes4 -lpthread
    [brenton@acer primes]$ time ./primes4 1000000000 > primes4.dat
    
    real	0m8.233s
    user	0m17.938s
    sys	0m0.708s
    Hmm, it looks like your program has a serious error. For example, the 20,000th prime number is 224737, so your program should find it if you pass it the number 224738 on the command line. But it doesn't:
    Code:
    $ ./getPrimes2 224738 | grep 224737
    $
    In fact, your program doesn't show 2016 of the first 20,000 primes:
    Code:
    $ ./getPrimes2 224738 | tail -n +2 | wc -l
    17984
    That number should be 20000, not 17984. So it's missing over 10% of the first 20,000 primes!

    Look at the last 10 primes before 224738 that it finds:
    Code:
    $ ./getPrimes2 224738 | tail
    199873
    199877
    199889
    199909
    199921
    199931
    199933
    199961
    199967
    199999
    That list should look like this:
    Code:
     224629
     224633
     224669
     224677
     224683
     224699
     224711
     224717
     224729
     224737
    Similar errors occur for larger numbers of primes. So your program is fast, but just not accurate.
    OS: Fedora 39 x86_64 | Machine: Lenovo ThinkCentre M91P | CPU: Intel Core i5-2500 (4)@3.30GHz | RAM: 32GB PC3-12800 DDR3 | Disks: Seagate Barracuda ST500DM002 500GB SATA, Seagate Constellation ES.3 ST1000NM0033 1TB SATA | Video: Intel HD Graphics 2000 128MB | Sound: Turtle Beach Santa Cruz CS4630 | Ethernet: Intel 82579LM

  12. #42
    Join Date
    Oct 2010
    Location
    Canberra
    Posts
    3,899
    Mentioned
    14 Post(s)
    Tagged
    1 Thread(s)

    Re: Programming Challenge - list prime numbers

    @RupertPupkin Thanks for spotting that. My tests happened to be multiples of the page size so they didn't test the printing of the last page of the results. A rather large off-by-one error - now fixed in the original post.

    I am using an Intel i5 processor: i5-2430M CPU @ 2.40GHz
    This has two cores with "hyper-threading". This has some interesting consequences. I created three versions of my program with 1, 2 and 4 threads and got the following times:
    Code:
    [brenton@acer primes]$ time ./primes4-1 1000000000 > primes4.dat
    
    real	0m12.807s
    user	0m12.315s
    sys	0m0.495s
    [brenton@acer primes]$ time ./primes4-2 1000000000 > primes4.dat
    
    real	0m8.871s
    user	0m12.899s
    sys	0m0.503s
    [brenton@acer primes]$ time ./primes4-4 1000000000 > primes4.dat
    
    real	0m8.025s
    user	0m17.899s
    sys	0m0.503s
    Since about 20% of the total processing is spent in the single threaded print_results routine the drop in real time for the two thread version looks to be near optimum. However, when going to 4 threads there is a jump of 5 seconds in the user time and only a very minor improvement in the real time. My conclusion is that "hype-rthreading" doesn't really live up to its name.

    Further Improvements
    If I come back to this program, there are some more improvements that could be made:
    • Get rid of the even numbers. This will speed it up and also double the size of the sieve that can be handled.
    • Have the threads work on contiguous blocks of pages rather than the interleaved approach currently used. This would allow the removal of most of the modulo operations since the end of one page could be used to set up the next page.
    • Have the threads write the results of each page as it is completed. If they each write to their own file we can significantly reduce the total time. A cat can merge the results into a single file if required.
    • Writing the pages as we go means we no longer need the entire sieve in memory, so the vector<bitset> can be dropped. This could mean handling far greater limits - but I suspect the running time might get a bit too long to be practical.

    I have many ideas, even some I haven't thought of yet.

  13. #43
    Join Date
    Nov 2006
    Location
    Detroit
    Posts
    8,750
    Mentioned
    63 Post(s)
    Tagged
    0 Thread(s)

    Re: Programming Challenge - list prime numbers

    Here's an example in Ada for listing the first N >= 1 primes. You can get Ada from the F25 repos (dnf install gcc-gnat libgnat-devel).

    Save this as getPrimes.adb:
    Code:
    with Ada.Text_IO, Ada.Command_Line; use Ada.Text_IO, Ada.Command_Line;
    Procedure getPrimes is
       Arg : String := Argument(1);
       N : Integer := Integer'Value(Arg); P : Integer := 3; Counter : Integer := 1;
       Function isPrime (Odd : Integer) Return Boolean is
          Result : Boolean := True; I : Integer := 5;
       Begin
          If Odd > 3 Then
             If Odd Mod 3 = 0 Then
                Result := False;
             Else
                While I*I <= Odd Loop
                   If (Odd Mod I = 0 Or Odd Mod (I+2) = 0) Then
                      Result := False;
                      Exit;
                   End If;
                   I := I + 6;
                End Loop;
             End If;
          End If;
          Return Result;
       End isPrime;
    Begin
       Put_Line (Integer'Image(2));
       While Counter < N Loop
          If isPrime(P) Then
             Put_Line (Integer'Image(P));
             Counter := Counter + 1;
          End If;
          P := P + 2;
       End Loop;
    End getPrimes;
    Compile like this:
    Code:
    $ gnatmake -gnatws getPrimes
    Sample time for the first million primes:
    Code:
    $ time ./getPrimes 1000000 > primes.log
    
    real    0m6.715s
    user    0m5.855s
    sys     0m0.794s
    OS: Fedora 39 x86_64 | Machine: Lenovo ThinkCentre M91P | CPU: Intel Core i5-2500 (4)@3.30GHz | RAM: 32GB PC3-12800 DDR3 | Disks: Seagate Barracuda ST500DM002 500GB SATA, Seagate Constellation ES.3 ST1000NM0033 1TB SATA | Video: Intel HD Graphics 2000 128MB | Sound: Turtle Beach Santa Cruz CS4630 | Ethernet: Intel 82579LM

  14. #44
    Join Date
    Dec 2005
    Location
    North Carolina
    Age
    34
    Posts
    1,162
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Re: Programming Challenge - list prime numbers

    It would be nice to see how our results compare against each other in terms of time and space on one machine. I know Rupert has done time ranking in other threads, and I don't want to ask him to manually curate that as a computer should be able to do it. Maybe that should be a programming challenge; to setup something that can scrape the thread for our code and rank it.
    Laptop: Lenovo ThinkPad T410, CPU: Intel Core i5 520M, Ram: 8GB DDR3, Hard Drive: 320GB, Graphics: Intel HD, OS: Windows 7 / Arch Linux x86_64
    Desktop: Motherboard: ASRock Fatal1ty AB350 Gaming K4, CPU: AMD Ryzen 3 1200, RAM: 8GB DDR4, Storage: Samsung 850 Pro 256GB, Graphics: Asus Radeon RX 550 4GB, OS: Arch Linux x86_64

  15. #45
    Join Date
    Nov 2006
    Location
    Detroit
    Posts
    8,750
    Mentioned
    63 Post(s)
    Tagged
    0 Thread(s)

    Re: Programming Challenge - list prime numbers

    Here's an example in Smalltalk for listing the first N >= 1 primes, using GNU Smalltalk (dnf install gnu-smalltalk).

    Save this as getPrimes.st:
    Code:
    isPrime := [ :m |
       |res i|
       res := true.
       i := 5.
       (m > 3) ifFalse:[res := true] ifTrue:[
          (m\\3 == 0) ifTrue:[
             res := false] ifFalse:[
                [(i*i <= m) & res] whileTrue:[
                   ((m\\i == 0) | (m\\(i+2) == 0)) ifTrue:[res := false].
                   i := i+6.]]].
       res.
    ].
    
    N := (Smalltalk arguments at:1) asInteger.
    p := 3.
    counter := 1.
    '2' display.
    [counter < N] whileTrue:[
       (isPrime value:p) ifTrue:[
          (', ', p asString) display.
          counter := counter+1.
       ].
       p := p+2.
    ].
    '' displayNl.
    Running the program to list the first 100 primes:
    Code:
    $ gst -q getPrimes.st -a 100
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
    79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,
     167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251,
     257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
     353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
     449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541
    OS: Fedora 39 x86_64 | Machine: Lenovo ThinkCentre M91P | CPU: Intel Core i5-2500 (4)@3.30GHz | RAM: 32GB PC3-12800 DDR3 | Disks: Seagate Barracuda ST500DM002 500GB SATA, Seagate Constellation ES.3 ST1000NM0033 1TB SATA | Video: Intel HD Graphics 2000 128MB | Sound: Turtle Beach Santa Cruz CS4630 | Ethernet: Intel 82579LM

Page 3 of 4 FirstFirst 1234 LastLast

Similar Threads

  1. Replies: 7
    Last Post: 12th May 2019, 04:50 AM
  2. A programming challenge.
    By lsatenstein in forum Programming & Packaging
    Replies: 3
    Last Post: 4th January 2015, 04:04 AM
  3. Programming Challenge: Comparing Numbers in a String
    By Flounder in forum Programming & Packaging
    Replies: 23
    Last Post: 10th January 2014, 03:53 PM
  4. [BASH]: Prime Numbers
    By sea in forum Guides & Solutions (Not For Questions)
    Replies: 14
    Last Post: 21st November 2012, 10:18 AM
  5. Program to find prime numbers
    By renkinjutsu in forum Programming & Packaging
    Replies: 9
    Last Post: 4th September 2011, 07:40 AM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
[[template footer(Guest)]]