Calculating Anti-Primes

[Space_Ghost]

Can this be sped up?   The code below calculates the first 45 anti-primes in ~6.3 seconds on my W11 PC. 
Definition of anti-primes: A natural number that has more divisors (factors, not just prime factors) than any number less that it. For example, 6 has 4 factors, including 1 and itself, and this is more than 1,2,3 or 5 which have only the minimum of 2 factors and 4 which has 3 factors.

Code: (Select All)

'Anti-Primes: Calculate first 45 anti-primes

'date of code: 06 JUL 2023

'Space Ghost (modified QBasic 4.5 from Rosetta Code)



'HOUSEKEEPING -----------------------------------

$CONSOLE:ONLY

OPTION _EXPLICIT

CLS



'VARIABLE DECLARATIONS  -------------------------

DIM t AS DOUBLE

DIM tmp AS STRING

DIM AS INTEGER MaxAntiPrime, AntiPrimeCount

DIM AS LONG MaxDivisors, Divisors, n



'MAIN BLOCK  ------------------------------------

t = TIMER(0.001)



MaxAntiPrime = 45

n = 0

MaxDivisors = 0

AntiPrimeCount = 0



PRINT "The first 45 anti-primes are:"

PRINT



WHILE AntiPrimeCount < MaxAntiPrime

    n = n + 1

    Divisors = DivisorCount(n)

    IF Divisors > MaxDivisors THEN

        PRINT n;

        MaxDivisors = Divisors

        AntiPrimeCount = AntiPrimeCount + 1

    END IF

WEND



PRINT: PRINT

tmp = "Execution Time in secs:##.###"

PRINT USING tmp; TIMER(0.001) - t



END



'FUNCTIONS AND SUBROUTINES ----------------------

FUNCTION DivisorCount (v)

    DIM AS LONG total, count, n, p

    total = 1

    n = v

    WHILE n MOD 2 = 0

        total = total + 1

        n = n \ 2

    WEND

    p = 3

    WHILE (p * p) <= n

        count = 1

        WHILE n MOD p = 0

            count = count + 1

            n = n \ p

        WEND

        p = p + 2

        total = total * count

    WEND

    IF n > 1 THEN total = total * 2

    DivisorCount = total

END FUNCTION



'END OF PROGRAM  --------------------------------

CONSOLE OUTPUT
The first 45 anti-primes are: 1  2  4  6  12  24  36  48  60  120  180  240  360  720  840  1260  1680  2520  5040  7560  10080  15120  20160  25200  27720  45360  50400  55440  83160  110880  166320  221760  277200  332640  498960  554400  665280  720720  1081080  1441440  2162160  2882880  3603600  4324320  6486480

Execution Time in secs: 6.334

[bplus]

I don't know, can you find a formula? but your thing looks pretty fast! Have you looked at Rosetta Code this looks like a classic task for them.

Welcome to the forum!

Yes RC has it: https://rosettacode.org/wiki/Anti-primes#FreeBASIC
FreeBasic is usually a good one to compare with.

[mnrvovrfc]

Welcome to the forums.

I have never understood this need for speed, and even less, the desire to make the executable smaller. Because usually it comes from people needing to compare one thing to the other. Just use it, dude, if it's easy enough and convenient.

That comment wasn't aimed at the OP nor at anybody else in particular.

The program that I wrote to try to create prime palindromes out of 19-digit _INTEGER64, had performance that satisfied me. It had to search through an input file for possible candidates. For each candidate, it had to calculate if it were prime or not. I wasn't expecting the program to blaze through things with a lowly dual-core CPU and only 4GB RAM. The thing is I don't have time nor patience to "do" C++ to see if it could run faster and perhaps gobble up more RAM.

[Space_Ghost]

I don't know, can you find a formula? but your thing looks pretty fast! Have you looked at Rosetta Code this looks like a classic task for them.

Welcome to the forum!

Yes RC has it: https://rosettacode.org/wiki/Anti-primes#FreeBASIC
FreeBasic is usually a good one to compare with.

Yeah, this is actually a slightly modified version of the QBasic Rosetta Code post (I noted that at the top of the code block).  The formula is straightforward for a procedural type approach.

My main question (I should have been more clear) is: can I do anything else QB64 to tweak our some more speed.  If you take the number of anti-primes from 45 to 50 it gets closer to 27 seconds and just rockets up from there.

I changed everything I could to INTEGER types (the fastest for QB64 I believe), and only used the LONG type when needed.  This made a somewhat amazing/surprising increase in speed.

Short of a functional or vectorized approach, I am just looking if I am missing something obvious for speed....assuming no formula change.

Thanks again, and this was my first post and first reply on the forum!

[Space_Ghost]

Welcome to the forums.

I have never understood this need for speed, and even less, the desire to make the executable smaller. Because usually it comes from people needing to compare one thing to the other. Just use it, dude, if it's easy enough and convenient.

That comment wasn't aimed at the OP nor at anybody else in particular.

The program that I wrote to try to create prime palindromes out of 19-digit _INTEGER64, had performance that satisfied me. It had to search through an input file for possible candidates. For each candidate, it had to calculate if it were prime or not. I wasn't expecting the program to blaze through things with a lowly dual-core CPU and only 4GB RAM. The thing is I don't have time nor patience to "do" C++ to see if it could run faster and perhaps gobble up more RAM.

Hi and thanks for the feedback, greatly appreciated.  I should have noted that the time to execution increases exponentially (or something like that) as the number of anti-primes you desire goes up.  

I was asking the community to just take a quick look and see if I am missing any commands, functions, or features of QB64 that I could leverage.  I put a little more detail in my reply to bplus.  This would help greatly as we increase the number of anti-primes calculated.

Your prime app sounds very nice.

Thanks!

[bplus]

I am not seeing anything to improve speed, looks just fine to me. I think a slight advantage with calculations when all the numbers are of the same type and as I recall no advantage using Integers over Long because of 64 bit math. I tried everything Long and got about same time with 3 trials each way.

[Space_Ghost]

I am not seeing anything to improve speed, looks just fine to me. I think a slight advantage with calculations when all the numbers are of the same type and as I recall no advantage using Integers over Long because of 64 bit math. I tried everything Long and got about same time with 3 trials each way.

Thanks bplus !!! This is exactly what I was hoping to understand.  Also appreciate you running the combinatorics on the type options with a 64 bit system and sharing your findings!

[Jack]

@Space_Ghost
put this at the top of your program

Code: (Select All)

$checking:off

you may gain a second or two in performance

[Space_Ghost]

@Space_Ghost
put this at the top of your program

Code: (Select All)

$checking:off

you may gain a second or two in performance

Thanks Jack!

[Stuart]

@Space_Ghost : 

Just in case you're not aware of it, I'll mention that in the QB64 IDE under the "Options" menu, then "Compiler Settings" 

a page will be displayed where you can make changes that may (or may not) improve your program execution speed.

The first option : 
>> "Compile program with C++ optimization flag"
is what I'd try first -- (this is basically the same as using -O2 in the "C++ Compiler Flags" box.


Otherwise you could leave the option above unchecked and try the following values in the "C++ Compiler Flags" box.

-O2
-Os
-O3
(Note that this is the letter "O", not a zero.)

I personally find that -Os works better for me in a program that does a lot of repetitive math.

A more detailed description of these and more compiler options can be found here : 
https://doc.ecoscentric.com/gnutools/doc...tions.html

EDIT :
I just wanted to mention that each time the compiler options are changed the QB64 compiler files are purged and rebuilt which means that it will take longer to compile your program the first time, but after that it will take less time to compile (until the compiler settings are changed again).