Announcement

Collapse

Computer Lab Guidelines

Here in the computer lab, we talk about cool tech, the newest coolest gadgets, and tackle your toughest tech questions.

If you need to refresh yourself on the decorum, now would be a good time. Forum Rules: here
See more
See less

A QBasic Program that calculates a range of prime numbers.

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • 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 unto salvation to every one that believeth; . . . -- Romans 1:16 KJV

    . . . 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 KJV

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

  • #2
    Why all the QBASIC?

    Comment


    • #3
      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 unto salvation to every one that believeth; . . . -- Romans 1:16 KJV

      . . . 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 KJV

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

      Comment


      • #4
        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, 06:36 AM.

        Comment


        • #5
          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.

          Comment


          • #6
            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, 07:07 AM.

            Comment


            • #7
              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; 12-31-2014, 10:57 PM. Reason: fix some grammar
              . . . the gospel of Christ: for it is the power of God unto salvation to every one that believeth; . . . -- Romans 1:16 KJV

              . . . 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 KJV

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

              Comment


              • #8
                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, 09:03 AM.

                Comment


                • #9
                  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 unto salvation to every one that believeth; . . . -- Romans 1:16 KJV

                  . . . 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 KJV

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

                  Comment


                  • #10
                    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, 05:17 PM. Reason: typed 8 for 9
                    . . . the gospel of Christ: for it is the power of God unto salvation to every one that believeth; . . . -- Romans 1:16 KJV

                    . . . 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 KJV

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

                    Comment


                    • #11
                      I only understood about 5% of this thread.
                      Learn to do right; seek justice. Defend the oppressed. Take up the cause of the fatherless; plead the case of the widow.--Isaiah 1:17

                      I don't think that all forms o[f] slavery are inherently immoral.--seer

                      Comment


                      • #12
                        Originally posted by fm93 View Post
                        I only understood about 5% of this thread.
                        OK.

                        From what you did understand. Ask a question where this discussion went off from what you did understand. Where you are interested of course.
                        . . . the gospel of Christ: for it is the power of God unto salvation to every one that believeth; . . . -- Romans 1:16 KJV

                        . . . 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 KJV

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

                        Comment


                        • #13
                          Originally posted by 37818 View Post
                          OK.

                          From what you did understand. Ask a question where this discussion went off from what you did understand. Where you are interested of course.
                          No, no, I was just making a self-deprecating remark about my knowledge of computer science. Carry on.
                          Learn to do right; seek justice. Defend the oppressed. Take up the cause of the fatherless; plead the case of the widow.--Isaiah 1:17

                          I don't think that all forms o[f] slavery are inherently immoral.--seer

                          Comment


                          • #14
                            Originally posted by fm93 View Post
                            No, no, I was just making a self-deprecating remark about my knowledge of computer science. Carry on.
                            Oh. I thought maybe you would like to discuss something regarding this. I know I left much unsaid.
                            . . . the gospel of Christ: for it is the power of God unto salvation to every one that believeth; . . . -- Romans 1:16 KJV

                            . . . 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 KJV

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

                            Comment


                            • #15
                              Originally posted by 37818 View Post
                              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
                              Here is an improved edit:
                              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:
                              x# = 0
                              k# = 0
                              m# = 2# ^ p# - 1#
                              c# = (m# - 1#) / (p#)
                              IF c# <> INT(c#) THEN PRINT p#; "is not prime.": SYSTEM
                              IF p# = 2# THEN GOTO lbla
                              IF p# MOD 6# = 5# THEN GOTO lbla
                              IF p# MOD 6# = 1# THEN GOTO lblb
                              
                              lbla:
                              IF k# = 2# THEN k# = 4# ELSE k# = 2#
                              x# = x# + k#
                              y# = (c# - x#) / (x# * p# + 1#)
                              IF x# > y# THEN GOTO lblz
                              IF y# <> INT(y#) THEN GOTO lbla
                              IF y# = INT(y#) THEN c# = y#: GOSUB lbly: GOTO lbla
                              GOTO lblz
                              
                              lblb:
                              IF k# = 4# THEN k# = 2# ELSE k# = 4#
                              x# = x# + k#
                              y# = (c# - x#) / (x# * p# + 1#)
                              IF x# > y# THEN GOTO lblz
                              IF y# <> INT(y#) THEN GOTO lblb
                              IF y# = INT(y#) THEN c# = y#: GOSUB lbly: GOTO lblb
                              GOTO lblz
                              
                              
                              lblz:
                              PRINT (c# * p# + 1#)
                              SYSTEM
                              lbly:
                              PRINT (x# * p# + 1#)
                              RETURN
                              Yes, further improvements can be made. Needs to be written in an assembly code with less limited number lengths.
                              Last edited by 37818; 10-29-2017, 12:39 PM.
                              . . . the gospel of Christ: for it is the power of God unto salvation to every one that believeth; . . . -- Romans 1:16 KJV

                              . . . 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 KJV

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

                              Comment

                              Related Threads

                              Collapse

                              Topics Statistics Last Post
                              Started by Christian3, 03-15-2024, 10:15 AM
                              8 responses
                              36 views
                              0 likes
                              Last Post Ronson
                              by Ronson
                               
                              Working...
                              X