prime numbers searcher in QB

[ron77]

hi all i'm new here...

here is a code i've written for searching prime numbers from 2 to one million:

Code: Select all

'$lang:"qb"
'2019-08-17 - developed by ron77 & stxaxtic mod B+
'_TITLE "PRIME NUMBER FINDER"
DO
    PRINT "press ESC key while program running to exit search"
    INPUT "Choose Upper value to search up to 1,000,000: ", n
    IF n > 1000000 THEN n = 1000000
    count = 0
    pause = 0
    total = 0
    FOR l = 2 TO n
        f = -1
        k$ = INKEY$
        total = total + 1
        FOR m = 2 TO INT(SQR(l))
            IF l / m = l \ m THEN
                f = 0
                EXIT FOR
            END IF
        NEXT
        IF f THEN
            count = count + 1
            PRINT STR$(l) + ", ";
            pause = pause + 1
            IF pause = 100 THEN PRINT: PRINT: PRINT "TOTAL NUMBERS SCAN SO FAR: " + STR$(total) + " PRIME NUMBERS FOUND SO FAR: " + STR$(count): PRINT: SLEEP (4): pause = 0 'OK better reset and do increments of 100
        END IF
        IF k$ = CHR$(27) THEN EXIT FOR
    NEXT
    PRINT
    PRINT: PRINT "TOTAL NUMBERS SCAN :" + STR$(total) + " TOTAL PRIME NUMBERS FOUND: " + STR$(count): PRINT
    PRINT
LOOP

[integer]

Welcome to the site.

I do not recall seeing the double divide before: the floating point & whole number division. That is a different approach.
Most would use the shorter (quicker) mod instruction.
Nice attempt. Keep up the good work.

If speed is what you would like to see, several members have written fast prime number generators.
One of the routines generated 10 million primes in about 3 seconds.

[integer]

@admins: if the attached is too close to a copyright violation, PLEASE delete the code portion.

at this website
https://www.codeproject.com/Tips/525458 ... -Cplusplus
Fabrizio Civetta stated that his cpp program can generate the primes less that 2million is about 6 seconds.
When I converted his cpp program to FreeBasic it required about 90 seconds to compute the primes less that 2 million.
This is the cpp code converted to FreeBasic:
to avoid direct copyright infringement, the variables were renamed (somewhat) and I replaced the 'GOTO' with a DO/LOOP structure.

Code: Select all

    dim as long mx = 2000000    ''= 2 million takes 90seconds
    dim as long w(mx)
    dim as long wn(mx)
    dim as long cnt = 1
    dim as long wi = 0
    dim as long i
    dim as double t2, t1
    t1 = timer
    DO
        cnt = cnt + 2
        for i = 1 to wi
            if (w(i) < cnt) THEN w(i) +=  wn(i)
            if (w(i) = cnt) then CONTINUE DO
        next i
        if (cnt > mx) THEN exit do
        wi += 1
        wn(wi) = cnt
        w(wi) = cnt
    LOOP    
    t2 = timer
    print t2-t1;" seconds to generate Primes below ";mx
    for i=0 to 20
        print wn(i);" ";
    next i
    getkey

My question is: How can cpp optimize the code to run in 6 seconds while FB code requires 90 seconds?
The specific algorithm here is not as fast as some code posted previously on this forum.
That other code will generate the prime numbers less that 1.2 BILLION is about 1/2 minute.
The quickness of the method is not what bothers me.

Is there any one who can give a hint as to how cpp does such a fantastic optimization?
I do not know and cannot guess as to how it is possible.
FreeBasic: 90 seconds
cpp: 6 seconds

[D.J.Peters]

"2.000.000 of numbers in 6 seconds on single core I7 3 Ghz."
may be should be:
"2.000.000 of numbers in 60 seconds on single core I7 3 Ghz."

FreeBASIC. 51 seconds !

note: C/CPP array's are pointers not an struct like a FreeBASIC array !

Joshy

[fxm]

26 seconds on my PC intel CORE i7 (gas win32).

[srvaldez]

after changing the cpp _int64 to __int64 and using -O2 the runtime is 7 seconds
changing the FB code from long to longint and compiling with FBx64 -gen gcc -O 2 the runtime is 4.5 seconds

[integer]

@D.J.Peters
@fxm
@srvaldez

So, instead of a working class race horse on my desk, I have a mule.
Your response is very much appreciated.

Thank you.

[dodicat]

Hi integer.
Over there in a classless society where you can aspire to great heights by merit alone, (The land of the free e..t.c. ...), a working class horse I believe can become a racehorse.
Over here in this class ridden pit a working class horse is condemned to pulling a plough from dawn til disk, or sent to the city to work for for some ruthless rag and bone merchant or condemned for life to some other back breaking trade.
Race horses over here are born into wealthy stables, fed with silver embroidered nosebags, and very many achieve great status.
(This is completely off topic and has little to do with prime numbers, so I apologise).

Here is a quick generator, not as quick as the Sieve of Eratosthenes, but it extends into ulongint if required.

Code: Select all

Function isprime(n As Ulongint) As integer
    If (n=2) Or (n=3) Then Return -1
    If n Mod 2 = 0 Then return 0
    If n Mod 3 = 0 Then return 0
    Dim As Ulongint limit=Sqr(N)+1
    For I As Ulongint = 6 To limit Step 6
        If N Mod (i-1) = 0 Then return 0
        If N Mod (i+1) = 0 Then return 0
    Next I
    Return -1
End Function

dim as double t1=timer,t2
dim as long num=2000000,counter

redim as ulongint primes(1 to num\2)

for n as long=1 to num
    if isprime(n) then
        counter+=1
        primes(counter)=n
    end if
next n
redim preserve primes(1 to counter)
t2=timer
for n as long=1 to 20
    print primes(n)
next
print ". . ."
print ". . ."
for n as long=ubound(primes)-20 to ubound(primes)
    print primes(n)
next
print
print t2-t1
sleep

 

If you step n by 2 (as usual for primes by division), then it is slower for some strange reason, and of course misses out 2.

[integer]

If you step n by 2 (as usual for primes by division), then it is slower for some strange reason, and of course misses out 2.

If it steps by two, there is no call/return to the function -- it should be faster. But it is not.

Over here, we have a bunch of donkeys and mules, who have no class what so ever,
who are trying to convince everyone that they are race horses worthy of coronation.
Obviously, that is an observation about computer science and programming.
There are some who may misunderstand that comment to imply something else.

Your code (that finds the primes less than 2 million) runs in 0.56 seconds on my PC (ok snail)

[dodicat]

Integer.
Your c++ code takes 73 seconds here:

Code: Select all

Started! to:2000000
2000003
Wall time passed: 73 s.
Press any key to continue . . . 

Your translation to fb takes about 45 seconds.
I used Dev c++, g++ from Mingw wouldn't compile it.
I had to add
#include <stdlib.h>
#define _int64 long long
#define nullptr 0
to the C++ code.
Here is a standard Sieve of Eratosthenes.
(Been coded many times before in fb in slightly different ways)

Code: Select all

 


Sub generateprimes(primes() as integer,nmax as integer)
    redim primes(1 to nmax)
   var np = 0
    Dim As Integer i, k
    For k = 2 To nmax
        If primes(k) = 0 Then
            np += 1
            primes(np) = k
            For i = 2*k To nmax Step k
                primes(i) = 1
            Next i
        End If
    Next k
    Redim Preserve primes(1 to np)
End Sub

dim as double t1=timer,t2
redim as integer p()
generateprimes(p(),2000000)
t2=timer
for n as long=1 to 20
    print p(n)
next
print ". . ."
print ". . ."
for n as long=ubound(p)-20 to ubound(p)
    print p(n)
next
print
print t2-t1


sleep
 

Thanks for your original code ron77

[Kuene]

My submission:

Code: Select all

Dim As LongInt i,i2,i3,a,pll,isqrt 'pll = prime list length
Dim shared As LongInt primelist(150000)
Dim As boolean prime
Dim As Double t
t = Timer
primelist(1) = 2
primelist(2) = 3
pll = 2
For i = 6 To 1999998 Step 6
	For i2 = -1 To 1 Step 2
		prime = TRUE
		a = i+i2
		isqrt = Int(Sqr(a))
		For i3 = 1 To pll
			If primelist(i3) > isqrt Then Exit For
			If a Mod primelist(i3) = 0 Then prime = FALSE:Exit For
		Next
		If prime = TRUE Then
			pll += 1
			primelist(pll) = a
		End If
	Next
Next
?Timer - t
?pll
View Print 3 To 30
For i = (pll-100) To pll
	?i;
	?primelist(i)
	Sleep
next

I kind of cheated because I manually added the first two primes because 2 and 3 don't neatly fit into the algorithm. takes about .254 seconds on my computer.

[Kuene]

Curiously, if I change

Code: Select all

For i2 = -1 To 1 Step 2

to

Code: Select all

	For i2 = -1 To 1' Step 2
		If i2 = 0 Then i2 = 1

It runs in about 73% of the time. I absolutely never would have guessed that. I only made the change because I wanted to see how much slower it would run. But it got faster!

Code: Select all

Dim As Integer i,i2,i3,a,pll,isqrt 'pll = prime list length
Dim shared As integer primelist(150000)
Dim As boolean prime
Dim As Double t = Timer
primelist(1) = 2
primelist(2) = 3
pll = 2
For i = 6 To 2000000 Step 6
	For i2 = -1 To 1' Step 2
		If i2 = 0 Then i2 = 1
		prime = TRUE
		a = i+i2
		isqrt = Int(Sqr(a))
		For i3 = 1 To pll
			If primelist(i3) > isqrt Then Exit For
			If a Mod primelist(i3) = 0 Then prime = FALSE:Exit For
		Next
		If prime = TRUE Then
			pll += 1
			primelist(pll) = a
		End If
	Next
Next
?Timer - t
?pll
View Print 3 To 30
For i = (pll-100) To pll
	?i;
	?primelist(i)
	Sleep
Next

[systemctl]

How did you measure the execution time? You put a timer inside your code? I think it's not fair and will not work if your application is multithreaded.

[Kuene]

As far as I can tell, I set up the timer the same as everyone else. And honestly I'm not sure if it's single or multithreaded. Of course I would like for this to as fair as possible.

[systemctl]

As far as I can tell, I set up the timer the same as everyone else. And honestly I'm not sure if it's single or multithreaded. Of course I would like for this to as fair as possible.

Your code is definitely single threaded so everything is fine. My statement is for general case and I think using a wrapper shell script is more accurate. Sorry because it's a bit unclear and caused confusion.