



Programming & Packaging A place to discuss programming and packaging. 
17th March 2017, 06:02 AM

Registered User


Join Date: Oct 2010
Location: Canberra
Posts: 2,594


Re: Programming Challenge  list prime numbers
I knew about the extra 9 in bob's solution.
The error concerns the range, and for small limits there is an off by one error (which I have now fixed).
I edited bob's solution to remove the additional bookkeeping  it made no discernible difference.
__________________
Has anyone seriously considered that it might be turtles all the way down?
That's very old fashioned thinking.
The current model is that it's holographic nested virtualities of turtles, all the way down.

17th March 2017, 06:16 AM

Registered User


Join Date: Nov 2006
Location: Detroit
Posts: 6,608


Re: Programming Challenge  list prime numbers
Quote:
Originally Posted by ocratato
The error concerns the range, and for small limits there is an off by one error (which I have now fixed).

Your solution now no longer lists 9 as a prime number, but it still doesn't list 2 as a prime, and it still doesn't go up to the number you pass in. Those are easy things to fix.
__________________
OS: Fedora 26 x86_64  Machine: HP Pavilion a6130n  CPU: AMD 64 X2 DualCore 5000+ 2.6GHz  RAM: 7GB PC5300 DDR2  Disk: 400GB SATA  Video: ATI Radeon HD 4350 512MB  Sound: Realtek ALC888S  Ethernet: Realtek RTL8201N

17th March 2017, 06:35 AM

Registered User


Join Date: Jun 2013
Location: USA
Posts: 360


Re: Programming Challenge  list prime numbers
Quote:
Originally Posted by RupertPupkin
I think Octave is definitely worth installing. It's basically a free Matlab clone. But there are alternatives with smaller footprints.
IDL is one such alternative. Here's an IDL oneliner to list the first 10,000 primes (using GDL, a free GNU implementation of IDL, which is in the Fedora repos: dnf install gdl):
Code:
$ gdl q e 'print, primes(10000)'

Thank you!
__________________
Mind the gap.

17th March 2017, 06:45 AM

Registered User


Join Date: Jun 2013
Location: USA
Posts: 360


Re: Programming Challenge  list prime numbers
Quote:
Originally Posted by RupertPupkin
Takes just under 5 seconds to get the first 1 million primes, and just over 2 minutes to get the first 10 million primes:
Code:
$ time java getPrimes 1000000 > primes.log
real 0m4.912s
user 0m4.141s
sys 0m0.859s
$ time java getPrimes 10000000 > primes.log
real 2m8.225s
user 1m57.553s
sys 0m8.833s

Those are nice times. I like my tidy python scripts, but they sure can't compete in the big leagues when it comes to performance.
__________________
Mind the gap.

17th March 2017, 07:05 AM

Registered User


Join Date: Oct 2010
Location: Canberra
Posts: 2,594


Re: Programming Challenge  list prime numbers
Quote:
Originally Posted by RupertPupkin
Your solution now no longer lists 9 as a prime number, but it still doesn't list 2 as a prime, and it still doesn't go up to the number you pass in. Those are easy things to fix.

Done. I've edited the original post.
Code:
[brenton@acer primes]$ time ./primes3 1000000 > primes3.dat
real 0m0.022s
user 0m0.019s
sys 0m0.003s
[brenton@acer primes]$ time ./primes3 1000000000 > primes3.dat
real 0m19.494s
user 0m19.018s
sys 0m0.486s
[brenton@acer primes]$ ./primes3 29
Calculating primes up to: 29
2
3
5
7
11
13
17
19
23
29
__________________
Has anyone seriously considered that it might be turtles all the way down?
That's very old fashioned thinking.
The current model is that it's holographic nested virtualities of turtles, all the way down.

17th March 2017, 04:21 PM

Registered User


Join Date: Jun 2005
Location: Montreal, Que, Canada
Posts: 4,177


Re: Programming Challenge  list prime numbers
Quote:
Originally Posted by RupertPupkin
In fact, I just compiled and ran your program, and it doesn't quite do what it says:
Code:
$ ./getPrimes 11
Calculating primes up to: 11
3
5
7
9
So not only is the nonprime number 9 listed, but 11 is missing (so that it's not "up to" 11), and even 2 is missing!
Maybe you should do a little research before writing code, and not blindly copy code from Wikipedia.
Edit: To be fair, bobx001's program also wrongly lists 9 as a prime number and makes the same mistakes that yours does. His program does print out more info (like divisors), though, so the time comparisons are kind of apples to oranges.

[leslie@F26 tmp]$ ./getPrimes 5
Calculating primes up to: 5
3
4
Calculating primes up to: 12
3
5
7
9
11

17th March 2017, 05:10 PM

Registered User


Join Date: Dec 2012
Location: santa barbara, CA
Posts: 394


Re: Programming Challenge  list prime numbers
The idea is to see the code, not only the results, that way we all learn.

17th March 2017, 06:16 PM

Registered User


Join Date: Dec 2012
Location: santa barbara, CA
Posts: 394


Re: Programming Challenge  list prime numbers
Here is a more interesting version, made for a 4 core, or better, a dual cpu machine,
which:
1. does not use the greeks
2. forks out into 4 children (we could also make this 2+2, for dualcore boxes)
3. stores the calculated primes into 4 distinct "interleaves" in the same shared memory segment
4. properly finds 9 as a nonprime (the >>2 was replaced)
5. creates separated logs, and also lists all the dividers found for the other numbers
6. does not use semaphores as mutex since we are writing distinct memory locations for each child process
to get the complete sorted list of primes I will just add a small qsort at the end, or simply merge the outputs in a small easy loop, into a file. Will do this next to see the final list.
Code:
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <time.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#define LRS(a, b, c) ((a >> b) & c)
#define SHM_KEY_AUX 325000100
#define SHM_KEY_STORAGE 325000101
#define AUX_SIZE 2048
#define PRIMES_STORAGE_SIZE 8000000 /* 8 million bytes => storage for 1 million primes @64bit */
/* AUX format @offsets:
+0 total iterations
+1 total primes found > indicates offset on storage segment
+2 start time
+3 end time 1's
+4 end time 3's
+5 end time 7's
+6 end time 9's
+7 total primes found ending in 1
+8 total primes found ending in 3
+9 total primes found ending in 7
+10 total primes found ending in 9
+11 total iterations for primes ending in 1
+12 total iterations for primes ending in 3
+13 total iterations for primes ending in 7
+14 total iterations for primes ending in 9
STORAGE format @offsets:
@+(total_primes_found ending in 1 * 4) +0 > the primes ending in 1
@+(total_primes_found ending in 3 * 4) +1 > the primes ending in 3
@+(total_primes_found ending in 7 * 4) +2 > the primes ending in 7
@+(total_primes_found ending in 9 * 4) +3 > the primes ending in 9
*/
void attach_to_shm(VAD_AUX,VAD1)
long int *VAD_AUX, *VAD1;
{
int opperm=0666, opperm_flags;
int shmid, system_active;
int segment_size;
long int ADDR, *location;
opperm_flags = (opperm  IPC_CREAT);
segment_size=AUX_SIZE;
shmid= shmget(SHM_KEY_AUX, segment_size, opperm_flags);
ADDR= (long int)shmat(shmid, (void *)NULL, SHM_RND);
*VAD_AUX= (long int *)ADDR;
segment_size=PRIMES_STORAGE_SIZE;
shmid= shmget(SHM_KEY_STORAGE, segment_size, opperm_flags);
ADDR= (long int)shmat(shmid, (void *)NULL, SHM_RND);
*VAD1= (long int *)ADDR;
}
void detach_from_shm(VAD_AUX,VAD1)
long int *VAD_AUX, *VAD1;
{
shmdt((void *)VAD_AUX);
shmdt((void *)VAD1);
}
void reset_shm_variables()
{
register int i;
long int *VAD_AUX,*VAD1,getVAD_AUX,getVAD1,*location;
time_t curtime;
FILE *fw;
attach_to_shm(&getVAD_AUX,&getVAD1);
VAD_AUX=(long int *)getVAD_AUX;
for (i=0; i< 250; i++)
{
location=VAD_AUX+i;
*location=0;
}
VAD1=(long int *)getVAD1;
time(&curtime);
location=VAD_AUX+2; /* this is the starting time, seconds is good enough */
*location=(long int)curtime;
detach_from_shm(VAD_AUX,VAD1);
}
int calculate(n,limit)
int n;
register int limit;
{
char fname[32];
register int i, c, d,e=1, modulo,divider_found;
long int primes_found=0,calculations,total_calculations=0;
long int numprimes_offset,iterations_offset,offset,end_time_offset,storage_offset;
long int *VAD_AUX,*VAD1,getVAD_AUX,getVAD1,*location,*location2,*location3;
time_t curtime;
FILE *fa;
sprintf(fname,"output%d.txt", n);
fa=fopen(fname, "w");
attach_to_shm(&getVAD_AUX,&getVAD1);
VAD_AUX=(long int *)getVAD_AUX;
VAD1=(long int *)getVAD1;
switch(n)
{
case 1:
iterations_offset=11; storage_offset=0; numprimes_offset=7; end_time_offset=3;
break;
case 3:
iterations_offset=12; storage_offset=1; numprimes_offset=8; end_time_offset=4;
break;
case 7:
iterations_offset=13; storage_offset=2; numprimes_offset=9; end_time_offset=5;
break;
case 9:
iterations_offset=14; storage_offset=3; numprimes_offset=10; end_time_offset=6;
break;
default:
break;
}
location=VAD_AUX+iterations_offset;
location2=VAD_AUX+numprimes_offset;
for (i=n; i< limit; i+=10)
{
if ((i > 17) && e&1)
e=2;
d=i>>e;
modulo=1;
calculations=0;
for (c=3;(c<=d) && (modulo > 0);c+=2)
{
modulo=i%c;
divider_found=c;
calculations++;
(*location)++;
}
if (modulo)
{
offset=(4*(*location2)++) + storage_offset;
location3=VAD1+offset;
*location3=(long int)i;
fprintf(fa,"%lu is prime : calculations: %lu  primes found: %lu\n", i,calculations,*location2);
}
else
{
fprintf(fa,"Divider found for: %lu > %lu\n", i, divider_found);
}
}
location=VAD_AUX+end_time_offset;
time(&curtime);
*location=(long int)curtime; /* end time */
detach_from_shm(VAD_AUX,VAD1);
fclose(fa);
}
int main(int argc,char *argv[])
{
register int i,limit;
int finished=0;
long int *VAD_AUX,*VAD1,getVAD_AUX,getVAD1,*location,*location2,*location3,*location4,offset,total_primes_found=0,total_iterations=0;
time_t curtime,start_time,delta_time=0;
limit=abs(atoi(argv[1]));
reset_shm_variables();
if (!fork())
{
calculate(1,limit);
exit(0);
}
if (!fork())
{
calculate(3,limit);
exit(0);
}
if (!fork())
{
calculate(7,limit);
exit(0);
}
if (!fork())
{
calculate(9,limit);
exit(0);
}
attach_to_shm(&getVAD_AUX,&getVAD1);
VAD_AUX=(long int *)getVAD_AUX;
VAD1=(long int *)getVAD1;
while (!finished)
{
location=VAD_AUX+3;
location2=VAD_AUX+4;
location3=VAD_AUX+5;
location4=VAD_AUX+6;
if ((*location != 0) && (*location2 != 0) && (*location3 != 0) && (*location4 != 0))
finished=1;
else
sleep(1);
}
location=VAD_AUX+2;
start_time=*location;
location=VAD_AUX+3;
location2=VAD_AUX+4;
location3=VAD_AUX+5;
location4=VAD_AUX+6;
delta_time=*location;
if (*location2 > delta_time)
delta_time=*location2;
if (*location3 > delta_time)
delta_time=*location3;
if (*location4 > delta_time)
delta_time=*location4;
location=VAD_AUX+11; total_iterations+=*location;
location=VAD_AUX+12; total_iterations+=*location;
location=VAD_AUX+13; total_iterations+=*location;
location=VAD_AUX+14; total_iterations+=*location;
location=VAD_AUX+7; total_primes_found+=*location;
location=VAD_AUX+8; total_primes_found+=*location;
location=VAD_AUX+9; total_primes_found+=*location;
location=VAD_AUX+10; total_primes_found+=*location;
location2=VAD_AUX+1;
printf("FINISHED in %d seconds, num primes found: %lu , total calcs: %lu\n", delta_timestart_time,total_primes_found,total_iterations);
detach_from_shm(VAD_AUX,VAD1);
}
./primes_multi 1000000
FINISHED in 18 seconds, num primes found: 78497 , total calcs: 4701845834
I also still have the offending 5 on the inner loop of dividers, but I'll eventually get rid of that too.
Last edited by bobx001; 17th March 2017 at 06:24 PM.

18th March 2017, 04:44 AM

Registered User


Join Date: Nov 2006
Location: Detroit
Posts: 6,608


Re: Programming Challenge  list prime numbers
Here's an example in Fortran, for listing the first N >= 1 primes (N is passed as a command line parameter). It uses some features of Fortran 2003, included with the GCC gfortran compiler (dnf install gccgfortran).
Save this as getPrimes.for:
Code:
logical function isPrime(m)
integer :: m, i
logical :: res
res = .TRUE.
if (m > 3) then
if (mod(m, 3) == 0) then
res = .FALSE.
else
i = 5
do while (i*i <= m)
if ((mod(m, i) == 0) .or. (mod(m, i+2) == 0)) then
res = .FALSE.
exit
end if
i = i + 6
end do
end if
end if
isPrime = res
end function isPrime
program getPrimes
integer :: N, p = 3, counter = 1
logical :: isPrime
character(len=32) :: arg
call get_command_argument(1, arg)
read (arg, '(I32)') N
print *,2
do while (counter < N)
if (isPrime(p)) then
print *,p
counter = counter + 1
end if
p = p + 2
end do
stop
end program getPrimes
Compile and run:
Code:
$ gfortran Ofast ffreeform std=f2003 o getPrimes getPrimes.for
$ ./getPrimes 11
2
3
5
7
11
13
17
19
23
29
31
__________________
OS: Fedora 26 x86_64  Machine: HP Pavilion a6130n  CPU: AMD 64 X2 DualCore 5000+ 2.6GHz  RAM: 7GB PC5300 DDR2  Disk: 400GB SATA  Video: ATI Radeon HD 4350 512MB  Sound: Realtek ALC888S  Ethernet: Realtek RTL8201N

18th March 2017, 05:38 AM

Registered User


Join Date: Oct 2010
Location: Canberra
Posts: 2,594


Re: Programming Challenge  list prime numbers
I was just messing around with my solution and discovered that about a third of the total time (for a billion limit) was spent in the printf() function at the end. If I just count the number of primes it drops from 18 seconds to 10 seconds. I guess writing 50 million numbers take a while.
So I wrote my own little print function:
Code:
inline void print_int(int val)
{
static char outbuf[4096];
static int p = 0;
char chars[16];
int digits = 0;
if ( val < 0 )
{
fwrite(outbuf, 1, p, stdout );
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;
}
}
__________________
Has anyone seriously considered that it might be turtles all the way down?
That's very old fashioned thinking.
The current model is that it's holographic nested virtualities of turtles, all the way down.

18th March 2017, 09:10 AM

Registered User


Join Date: Dec 2012
Location: santa barbara, CA
Posts: 394


Re: Programming Challenge  list prime numbers
Now, if we want to use the greeks, we get:
Code:
time ./primes_greeks 1000000000 > LOG
real 0m22.571s
user 0m21.980s
sys 0m0.474s
on my 2012 Vaio Z
Code:
cat /proc/cpuinfo
processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 58
model name : Intel(R) Core(TM) i73520M CPU @ 2.90GHz
stepping : 9
microcode : 0x1c
cpu MHz : 1269.989
And a very Q&D, not optimized version of the proggy looks like:
Code:
#include <stdlib.h>
#include <stdio.h>
int main(int argc,char *argv[])
{
register int i,c, d, e, limit;
int finished=0,found;
char *da_array;
limit=abs(atoi(argv[1]));
da_array=(char*)calloc(limit, sizeof(char));
i=2;
printf("%lu\n",i);
while (!finished)
{
for (c=i; c< limit; c+=i)
da_array[c]=1;
found=0;
e=i+1;
while (!found)
{
if (!found)
{
d=da_array[e];
if (d == 0)
found=1;
else
e++;
}
}
printf("%lu\n",e);
i=e;
if (i >= limit)
finished=1;
}
free(da_array);
}
However, we don't get any extra science from the list, just the primes.
for a billion I am getting:
Code:
wc l LOG
50847535 LOG

18th March 2017, 12:16 PM

Registered User


Join Date: Oct 2010
Location: Canberra
Posts: 2,594


Re: Programming Challenge  list prime numbers
@bobx001  you might want to throw my print_int function into your program  it should chop about 5 seconds off the time.
I think I've found a method for doing a sieve with multiple threads.
It relies on the fact that the largest factor of numbers up to L is sqrt(L).
The idea is to divide the sieve into pages where the each page has a size of at least sqrt(L) and get the primes for the first page using the normal sieve routine. The remaining pages only need to be culled of the primes identified in the first page which is something that can be distributed over multiple threads.
If the page size fits in the L1 cache it should be quite fast.
__________________
Has anyone seriously considered that it might be turtles all the way down?
That's very old fashioned thinking.
The current model is that it's holographic nested virtualities of turtles, all the way down.

18th March 2017, 03:13 PM

Registered User


Join Date: Dec 2012
Location: santa barbara, CA
Posts: 394


Re: Programming Challenge  list prime numbers
Quote:
Originally Posted by ocratato
@bobx001  you might want to throw my print_int function into your program  it should chop about 5 seconds off the time.
I think I've found a method for doing a sieve with multiple threads.
It relies on the fact that the largest factor of numbers up to L is sqrt(L).
The idea is to divide the sieve into pages where the each page has a size of at least sqrt(L) and get the primes for the first page using the normal sieve routine. The remaining pages only need to be culled of the primes identified in the first page which is something that can be distributed over multiple threads.
If the page size fits in the L1 cache it should be quite fast.

Yeah, saw that, awesome, maybe we can make it even smaller !
The multicore idea for the sieve is awesome, but I am first going the bitwise ops. array manipulation, so that we can allocate the least amount of pages for the most amount of data. I will do some timings and post my results.

18th March 2017, 04:07 PM

Registered User


Join Date: Dec 2012
Location: santa barbara, CA
Posts: 394


Re: Programming Challenge  list prime numbers
On my slower Desktop PC (AMD 5300 dualcore)
I just ran a comparison between bitwise and standard char array,
and I come up with this:
Code:
[bobx@nova test]$ time ./primes_greeks 1000000000 > LOG
real 0m44.222s
user 0m42.700s
sys 0m0.862s
[bobx@nova test]$ time ./primes_greeks_old 1000000000 > LOG2
real 0m44.562s
user 0m41.811s
sys 0m1.281s
rhere the code difference is as follows, here the bitwise ops version, which utilizes 1/8 the ram as the other one:
Code:
#include <stdlib.h>
#include <stdio.h>
#define LRS(a, b, c) ((a >> b) & c)
int main(int argc,char *argv[])
{
register int i,c, d, e, f, limit;
char *da_array,dachar;
limit=abs(atoi(argv[1]));
da_array=(char*)calloc((limit>>3)+1, sizeof(char));
i=2;
printf("%lu\n",i);
while (1)
{
for (c=i; c<= limit; c+=i)
{
d=c%8;
e=c>>3;
da_array[e]=(1<<d);
}
e=i+1;
while (1)
{
c=e>>3;
i=e%8;
d=LRS(da_array[c],i,1);
if (d == 0)
break;
else
e++;
}
if (e >= limit)
break;
i=e;
printf("%lu\n",i);
}
free(da_array);
}
and the "old" version, with the standard char array:
Code:
#include <stdlib.h>
#include <stdio.h>
int main(int argc,char *argv[])
{
register int i,c, d, e, limit;
int finished=0,found;
char *da_array;
limit=abs(atoi(argv[1]));
da_array=(char*)calloc(limit, sizeof(char));
i=2;
printf("%lu\n",i);
while (!finished)
{
for (c=i; c< limit; c+=i)
da_array[c]=1;
found=0;
e=i+1;
while (!found)
{
if (!found)
{
d=da_array[e];
if (d == 0)
found=1;
else
e++;
}
}
printf("%lu\n",e);
i=e;
if (i >= limit)
finished=1;
}
free(da_array);
}

18th March 2017, 04:17 PM

Registered User


Join Date: Dec 2012
Location: santa barbara, CA
Posts: 394


Re: Programming Challenge  list prime numbers
And a small improvement optimizing the loop constraints:
Code:
time ./primes_greeks_old 1000000000 > LOG2
real 0m43.760s
user 0m41.506s
sys 0m1.289s
with the loop looking like:
Code:
while (1)
{
for (c=i; c< limit; c+=i)
da_array[c]=1;
found=0;
e=i+1;
while (1)
{
d=da_array[e];
if (d == 0)
break;
else
e++;
}
if (e >= limit)
break;
printf("%lu\n",e);
i=e;
}

Thread Tools 
Search this Thread 


Display Modes 
Linear Mode

Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off



Current GMTtime: 13:34 (Sunday, 20082017)







