PDA

View Full Version : A QBasic Program that calculates a range of prime numbers.



37818
12-20-2014, 05:33 PM
This program calculates a range of prime numbers:


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

Leonhard
12-21-2014, 10:01 AM
Why all the QBASIC?

37818
12-22-2014, 08:43 AM
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.

Leonhard
12-30-2014, 03:34 AM
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. :smile:

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.


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


(A& + 1) MOD 6 = 0

This is much cleaner, should run just as well and be faster.

Leonhard
12-31-2014, 04:05 AM
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.

Leonhard
12-31-2014, 05:02 AM
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.


# 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)

37818
12-31-2014, 08:36 PM
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.


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:

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.

Leonhard
01-01-2015, 07:01 AM
An Eratosthenes Sieve is by far the fastest way to obtain prime numbers.

It can be varied a lot, even multithreaded. :smile:


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.

37818
01-01-2015, 08:43 AM
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.]

37818
06-18-2016, 03:05 PM
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



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

fm93
06-18-2016, 04:46 PM
I only understood about 5% of this thread. :dizzy:

37818
06-18-2016, 07:13 PM
I only understood about 5% of this thread. :dizzy: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.

fm93
06-19-2016, 08:50 AM
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.

37818
06-19-2016, 09:15 AM
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.

37818
10-29-2017, 10:37 AM
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



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:


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.