prime numbers searcher in QB

User projects written in or related to FreeBASIC.
ron77
Posts: 8
Joined: Feb 21, 2019 19:24

prime numbers searcher in QB

Postby ron77 » Aug 18, 2019 10:25

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
Posts: 385
Joined: Feb 01, 2007 16:54
Location: usa

Re: prime numbers searcher in QB

Postby integer » Aug 22, 2019 2:39

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
Posts: 385
Joined: Feb 01, 2007 16:54
Location: usa

HOW & WHY does cpp Optimize better than FreeBasic?

Postby integer » Jan 15, 2020 17:52

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

at this website
https://www.codeproject.com/Tips/5254588/Simple-Prime-Number-Calculator-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
Posts: 7949
Joined: May 28, 2005 3:28

Re: prime numbers searcher in QB

Postby D.J.Peters » Jan 15, 2020 18:22

"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
Posts: 9477
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: prime numbers searcher in QB

Postby fxm » Jan 15, 2020 19:01

26 seconds on my PC intel CORE i7 (gas win32).
srvaldez
Posts: 2239
Joined: Sep 25, 2005 21:54

Re: prime numbers searcher in QB

Postby srvaldez » Jan 15, 2020 22:35

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
Posts: 385
Joined: Feb 01, 2007 16:54
Location: usa

Re: prime numbers searcher in QB

Postby integer » Jan 17, 2020 8:45

@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
Posts: 6163
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: prime numbers searcher in QB

Postby dodicat » Jan 17, 2020 11:21

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
Posts: 385
Joined: Feb 01, 2007 16:54
Location: usa

Re: prime numbers searcher in QB

Postby integer » Jan 18, 2020 6:31

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
Posts: 6163
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: prime numbers searcher in QB

Postby dodicat » Jan 18, 2020 16:01

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

Return to “Projects”

Who is online

Users browsing this forum: No registered users and 3 guests