Page 1 of 2 12 LastLast
Results 1 to 10 of 15

Thread: A QBasic Program that calculates a range of prime numbers.

  1. #1
    tWebber 37818's Avatar
    Join Date
    Jan 2014
    Location
    So. California
    Faith
    Nontraditional Christian
    Gender
    Male
    Posts
    5,185
    Amen (Given)
    815
    Amen (Received)
    442

    Lightbulb A QBasic Program that calculates a range of prime numbers.

    This program calculates a range of prime numbers:
    Code:
    PRINT "INPUT NUMBERS FOR A RANGE OF PRIMES"
    INPUT "FIRST NUMBER: ", F#
    INPUT "LAST NUMBER:  ", L#
    
    FOR A# = F# TO L#
    IF (A# + 1) / 6 = INT((A# + 1) / 6) THEN GOTO LBL2
    GOSUB LBL1
    IF INKEY$ <> "" THEN SYSTEM
    NEXT A#
    PRINT
    SYSTEM
    
    LBL2:
    F# = A#
    FOR A# = F# TO L# STEP 6
    GOSUB LBL1
    IF INKEY$ <> "" THEN SYSTEM
    A# = A# + 2
    GOSUB LBL1
    IF INKEY$ <> "" THEN SYSTEM
    A# = A# - 2
    NEXT A#
    PRINT
    SYSTEM
    
    
    LBL1:
    IF A# > 999999999999999# THEN PRINT "OUT OF RANGE": SYSTEM
    IF A# < 1 OR A# <> INT(A#) THEN SYSTEM
    IF A# = 2 OR A# = 3 THEN PRINT A#; : RETURN
    C# = (A# + 1) / 6
    IF C# = INT(C#) THEN GOSUB M
    C# = (A# - 1) / 6
    IF C# = INT(C#) THEN GOSUB P
    RETURN
    
    P:
    FOR B# = 1 TO C#
    A1# = (C# - B#) / (6 * B# + 1): A2# = (C# + B#) / (6 * B# - 1)
    IF B# > A1# AND B# > A2# THEN PRINT A#; : RETURN
    IF A1# = INT(A1#) OR A2# = INT(A2#) THEN RETURN
    NEXT B#
    RETURN
    
    M:
    FOR B# = 1 TO C#
    A1# = (C# + B#) / (6 * B# + 1): A2# = (C# - B#) / (6 * B# - 1)
    IF B# > A1# AND B# > A2# THEN PRINT A#; : RETURN
    IF A1# = INT(A1#) OR A2# = INT(A2#) THEN RETURN
    NEXT B#
    RETURN
    . . . the Gospel of Christ, for it is [the] power of God to salvation to every [one] believing, . . . -- Romans 1:16.

    . . . that Christ died for our sins according to the scriptures; And that he was buried, and that he rose again the third day according to the scriptures: . . . -- 1 Corinthians 15:3, 4.

    Whosoever believeth that Jesus is the Christ is born of God: . . . -- 1 John 5:1.

  2. #2
    tWebber Leonhard's Avatar
    Join Date
    Jan 2014
    Location
    Denmark - Jutland
    Faith
    Catholic
    Gender
    Male
    Posts
    4,831
    Amen (Given)
    889
    Amen (Received)
    2658
    Why all the QBASIC?

  3. #3
    tWebber 37818's Avatar
    Join Date
    Jan 2014
    Location
    So. California
    Faith
    Nontraditional Christian
    Gender
    Male
    Posts
    5,185
    Amen (Given)
    815
    Amen (Received)
    442
    Quote Originally Posted by Leonhard View Post
    Why all the QBASIC?
    A number of reasons. 1) I have been programming in BASIC 34 years. 2). That interpreter runs in a Windows OS. 3) It is both free to use and is readily available.
    . . . the Gospel of Christ, for it is [the] power of God to salvation to every [one] believing, . . . -- Romans 1:16.

    . . . that Christ died for our sins according to the scriptures; And that he was buried, and that he rose again the third day according to the scriptures: . . . -- 1 Corinthians 15:3, 4.

    Whosoever believeth that Jesus is the Christ is born of God: . . . -- 1 John 5:1.

  4. #4
    tWebber Leonhard's Avatar
    Join Date
    Jan 2014
    Location
    Denmark - Jutland
    Faith
    Catholic
    Gender
    Male
    Posts
    4,831
    Amen (Given)
    889
    Amen (Received)
    2658
    Quote Originally Posted by 37818 View Post
    A number of reasons. 1) I have been programming in BASIC 34 years. 2). That interpreter runs in a Windows OS. 3) It is both free to use and is readily available.
    That's alright, though I really, really, really, recommend you pick up Python or C. As it is I do remember learning QBASIC as my first language.

    Just glancing through the code there's a possible bug. You use doubles. I understand why you do so, but it comes with problems, especially when you get near the limit, where the rounding off trick you do won't work well. I suggest using Long (&) [up to 2147483647] or _INTEGER64 (&&) [up to 9223372036854775807]. The latter will provide more than enough for any prime ranges mortal computer can output.

    I see you use a trick to check whether a number has a modulo remainer of zero.

    Code:
    (A# + 1) / 6 = INT((A# + 1) / 6)
    Now A#, F# and L# are floats, but they will represent small integers fairly well and allow for the decimal fractions you want for that trick. However its a little bit ugly, and it will probably get you into trouble later when you get closer to the round-off errors, ...52345.0 + 1 might return ...52345.999... instead and so you'd evaluate true even when you shouldn't. The same error could occur during division as well.

    So I suggest you use BASICS built-in way for calculating modulo remainders, and of course use Long Integers.

    Code:
    (A& + 1) MOD 6 = 0
    This is much cleaner, should run just as well and be faster.
    Last edited by Leonhard; 12-30-2014 at 11:36 AM.

  5. #5
    tWebber Leonhard's Avatar
    Join Date
    Jan 2014
    Location
    Denmark - Jutland
    Faith
    Catholic
    Gender
    Male
    Posts
    4,831
    Amen (Given)
    889
    Amen (Received)
    2658
    Code:
    999999999999999#
    Given that this isn't a variable, does it even make sense to write the asterix at the end? I don't know enough about q64 to see if that would even run?

    So far I haven't been able to get your code to run.

  6. #6
    tWebber Leonhard's Avatar
    Join Date
    Jan 2014
    Location
    Denmark - Jutland
    Faith
    Catholic
    Gender
    Male
    Posts
    4,831
    Amen (Given)
    889
    Amen (Received)
    2658
    Here's some python that accomplishes the same, albiet not with the same algorithm. Since I can't get your code to work 37818 I can't time it against yours. However, timing this using the unix time command gives me that it spent 3.2 seconds calculating all primes up to 1000000 and subsequently printing them. The majority of that time arguably spent printing them.

    Code:
    # Get User Input
    print "Input numbers for a range of primes"
    first = int(input("First Number: "))
    last = int(input("Last Number: "))
    
    # Calculate primes using simple Eratosthenes Sieve
    p = [2] + range(3, last + 1);
    n = 0
    while (p[n]**2 <= last):
        p = [i for i in p if (i == p[n]) or (i%p[n] != 0)]
        n += 1
    
    # Print all primes larger than first
    while p:
        if (p[0] >= first):
            print p[0]
        p.pop(0)
    Last edited by Leonhard; 12-31-2014 at 12:07 PM.

  7. #7
    tWebber 37818's Avatar
    Join Date
    Jan 2014
    Location
    So. California
    Faith
    Nontraditional Christian
    Gender
    Male
    Posts
    5,185
    Amen (Given)
    815
    Amen (Received)
    442
    An Eratosthenes Sieve is by far the fastest way to obtain prime numbers.

    Again my choice of Qbasic is because it is, for me, an easy high level programming language to use. Most programming as you know, is done with high level languages with better low level access to memory and cpu.

    The 999999999999999# is the double precision number format in Qbasic.

    Now the algorithm used in my program was chosen because it was that algorithm. Not that it was fast. It has too many operators/calculations.

    That algorithm is based on two sets of numbers. 5 incremented by 6. And 7 incremented by 6. All the non-prime numbers in each set also can be factored by a number in the same set. The 5 set being the (number + 1) / 6 sets. And the 7 sets being the (number - 1) / 6 sets. Anyway that is part of what is behind the algorithm.

    Code:
    INPUT A#
    IF A#>999999999999999 THEN PRINT "OUT OF RANGE":SYSTEM
    IF A# <= 1 OR A# <> INT(A#) THEN SYSTEM
    GOSUB S
    IF A# = 2 OR A# = 3 THEN PRINT A#; "IS A PRIME NUMBER.": GOSUB S: SYSTEM
    C# = (A# + 1) / 6
    IF C# = INT(C#) THEN GOTO M
    C# = (A# - 1) / 6
    IF C# = INT(C#) THEN GOTO P
    PRINT A#; "IS NOT A PRIME NUMBER.": GOSUB S: SYSTEM
    
    P:
    FOR B# = 1 TO C#
    A1# = (C# - B#) / (6 * B# + 1): A2# = (C# + B#) / (6 * B# - 1)
    IF B# > A1# AND B# > A2# THEN PRINT A#; "IS A PRIME NUMBER.": GOSUB S: SYSTEM
    IF A1# = INT(A1#) OR A2# = INT(A2#) THEN PRINT A#; "IS NOT A PRIME NUMBER.": GOSUB S: SYSTEM
    NEXT B#
    
    M:
    FOR B# = 1 TO C#
    A1# = (C# + B#) / (6 * B# + 1): A2# = (C# - B#) / (6 * B# - 1)
    IF B# > A1# AND B# > A2# THEN PRINT A#; "IS A PRIME NUMBER.": GOSUB S: SYSTEM
    IF A1# = INT(A1#) OR A2# = INT(A2#) THEN PRINT A#; "IS NOT A PRIME NUMBER.": GOSUB S: SYSTEM
    NEXT B#
    
    S:
    PRINT TIME$
    RETURN
    Now a faster increment by 6 and then 2 method:
    Code:
    INPUT N#
    IF N# > 999999999999999# THEN PRINT "OUT OF RANGE": SYSTEM
    GOSUB T
    IF N# < 2 OR N# <> INT(N#) THEN GOSUB T: SYSTEM
    IF N# / 2# = INT(N# / 2#) OR N# / 3# = INT(N# / 3#) THEN PRINT N#; "IS NOT A PRIME NUMBER.": GOSUB T: SYSTEM
    C# = INT(SQR(N#))
    FOR B# = 5# TO C# STEP 6#
    IF N# / B# = INT(N# / B#) OR N# / (B# + 2#) = INT(N# / (B# + 2#)) THEN PRINT N#; "IS NOT A PRIME NUMBER.": GOSUB T: SYSTEM
    NEXT B#
    PRINT N#; "IS A PRIME NUMBER.": GOSUB T: SYSTEM
    T:
    PRINT TIME$
    RETURN
    This one should be easier to convert.
    Last edited by 37818; 01-01-2015 at 03:57 AM. Reason: fix some grammar
    . . . the Gospel of Christ, for it is [the] power of God to salvation to every [one] believing, . . . -- Romans 1:16.

    . . . that Christ died for our sins according to the scriptures; And that he was buried, and that he rose again the third day according to the scriptures: . . . -- 1 Corinthians 15:3, 4.

    Whosoever believeth that Jesus is the Christ is born of God: . . . -- 1 John 5:1.

  8. #8
    tWebber Leonhard's Avatar
    Join Date
    Jan 2014
    Location
    Denmark - Jutland
    Faith
    Catholic
    Gender
    Male
    Posts
    4,831
    Amen (Given)
    889
    Amen (Received)
    2658
    Quote Originally Posted by 37818 View Post
    An Eratosthenes Sieve is by far the fastest way to obtain prime numbers.
    It can be varied a lot, even multithreaded.

    Again my choice of Qbasic is because it is, for me, an easy high level programming language to use. Most programming as you know, is done with high level languages with better low level access to memory and cpu.
    Its debatable how often high level languages are used, I find I'm using C far more often than python, then again I tend to write stuff where low-level access is a good thing. Though it depends on what you're developing.

    QBASIC however is not a good language. It was meant as a simple educational tool, easy to learn. Its way, way outdated by now. Its hard to read, and it relies on gotos, basically, in order to perform the work of functions and subroutines.

    It makes for spaghetti code.

    And saying you're doing it because that's what's done in the business... do you code QBASIC for a company on a regular basis or is this a hobby thing? I kinda find the former hard to imagine.

    Even if you're a hobby coder, seriously, learn Python. Its not hard, and you'll be learning real high-level programming concepts, like list comprehension, object oriented programming... What QBASIC offers is... low-level language, but interpreted like a high-level language. Which means it looks kinda like assembler, yet it performs worse than Python. About the only advantage I can see is that you don't have to worry about memory management (Java and Python have this though), you can dynamically declare variables (Python is even better at this). However you can't declare functions, there's only one global scope for the namespace, there's no cross platform compatibility (unlike Python right out of the bat).

    The 999999999999999# is the double precision number format in Qbasic.
    Alright, just couldn't get it to work in the interpreter I attempted to run.

    Now the algorithm used in my program was chosen because it was that algorithm. Not that it was fast. It has too many operators/calculations.
    In that case I think its better just to write the algorithm in pseudocode. You can test out an implementation of it in another language just fine, even QBASIC, but if you want others to look at your algorithm then that's what you'd do.

    Though maybe you wanted feedback on your QBASIC implementation?

    My criticism of using floats still stands. Please don't do that, you're setting yourself up for bugs! Its probably safe for the small integers you'll be calculating with this, but its really not a safe thing to do, and you're forced to use ugly hacks like "N# / 2# = INT(N# / 2#)" instead of the superior "N& MOD 2 = 0", which instantly makes sense to the eyes and is bugfree. My other concern is that you tend to use abstract labels which obscure the purpose of the code. LBL1 (Label 1), LBL2 (Label 2), P and M? I premuse these are set up simple to test primality of the numbers they get, but this could have been indicated in the names. The code is also uncommented, again, something that doesn't help with readability.
    Last edited by Leonhard; 01-01-2015 at 02:03 PM.

  9. #9
    tWebber 37818's Avatar
    Join Date
    Jan 2014
    Location
    So. California
    Faith
    Nontraditional Christian
    Gender
    Male
    Posts
    5,185
    Amen (Given)
    815
    Amen (Received)
    442
    You are very correct, BASIC was intended for beginners. But permits what is deemed very poor unstructured programming habits. As you said, "Spaghetti code." Again, self descriptive variable names are easier to follow than simple single letter variables. [I have been programming using BASIC now over 30 some years. And some assembly language.]
    . . . the Gospel of Christ, for it is [the] power of God to salvation to every [one] believing, . . . -- Romans 1:16.

    . . . that Christ died for our sins according to the scriptures; And that he was buried, and that he rose again the third day according to the scriptures: . . . -- 1 Corinthians 15:3, 4.

    Whosoever believeth that Jesus is the Christ is born of God: . . . -- 1 John 5:1.

  10. Amen Leonhard amen'd this post.
  11. #10
    tWebber 37818's Avatar
    Join Date
    Jan 2014
    Location
    So. California
    Faith
    Nontraditional Christian
    Gender
    Male
    Posts
    5,185
    Amen (Given)
    815
    Amen (Received)
    442
    A test program for factoring Mersenne numbers. Where 2prime - 1 = to a value. This test version can only do up to 259 - 1 = 179951 * 3203431780337

    Code:
    INPUT p#
    IF p# = 2# OR p# = 3# THEN GOTO lbl
    IF (p# - 1#) / 6# <> INT((p# - 1#) / 6#) AND (p# + 1#) / 6# <> INT((p# + 1#) / 6#) THEN PRINT p#; "is not prime.": SYSTEM
    IF p# > 59# THEN PRINT "out of range.": SYSTEM
    
    lbl:
    x1# = -2#
    x2# = -1#
    x# = 0
    m# = 2# ^ p# - 1#
    c# = (m# - 1#) / (2# * p#)
    IF p# = 2# THEN GOTO lbla
    IF c# <> INT(c#) THEN PRINT p#; "is not prime.": SYSTEM
    IF (p# - 5) / 6 = INT((p# - 5) / 6) THEN GOTO lbla
    IF (p# - 7) / 6 = INT((p# - 7) / 6) THEN GOTO lblb
    
    
    lbla:
    x1# = x1# + 3#
    x# = x# + 3#
    y1# = (c# - x1#) / (2# * x1# * p# + 1#)
    IF x1# > y1# THEN GOTO lblz
    IF y1# = INT(y1#) THEN c# = y1#: GOSUB lblw: GOTO lbla
    y# = (c# - x#) / (2# * x# * p# + 1#)
    IF x# > y# THEN GOTO lblz
    IF y# = INT(y#) THEN c# = y#: GOSUB lbly: GOTO lbla
    IF y1# <> INT(y1#) AND y# <> INT(y#) THEN GOTO lbla
    GOTO lbla
    
    lblb:
    x2# = x2# + 3#
    x# = x# + 3#
    y2# = (c# - x2#) / (2# * x2# * p# + 1#)
    IF x2# > y2# THEN GOTO lblz
    IF y2# = INT(y2#) THEN c# = y2#: GOSUB lblx: GOTO lblb
    y# = (c# - x#) / (2# * x# * p# + 1#)
    IF x# > y# THEN GOTO lblz
    IF y# = INT(y#) THEN c# = y#: GOSUB lbly: GOTO lblb
    IF y2# <> INT(y2#) AND y# <> INT(y#) THEN GOTO lblb
    GOTO lblb
    
    lblz:
    PRINT (2# * c# * p# + 1#)
    SYSTEM
    lblw:
    PRINT (2# * x1# * p# + 1#)
    RETURN
    lblx:
    PRINT (2# * x2# * p# + 1#)
    RETURN
    lbly:
    PRINT (2# * x# * p# + 1#)
    RETURN
    Last edited by 37818; 06-18-2016 at 10:17 PM. Reason: typed 8 for 9
    . . . the Gospel of Christ, for it is [the] power of God to salvation to every [one] believing, . . . -- Romans 1:16.

    . . . that Christ died for our sins according to the scriptures; And that he was buried, and that he rose again the third day according to the scriptures: . . . -- 1 Corinthians 15:3, 4.

    Whosoever believeth that Jesus is the Christ is born of God: . . . -- 1 John 5:1.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •