Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

Register Log in
  • Congratulations strongm on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

QBASIC Processing time

pya

pya

Technical User
Dec 18, 2020
48
AU
Hi Mikrom,

This QBASIC program searches for the kth Prime Number and prints the Prime Number and k value.
I have tested it on a site for checking Primes.

Is there any way I can speed up the processing time?

Your help appreciated.

pa99
 
Sort by date Sort by votes
Hi pya,

but you forgot to post the source code of your program
 
Upvote 0 Downvote
Hi pya,

With this code you posted
Code: 
10 REM  Kth Prime Identifier - v7.1
20 DIM P AS _UNSIGNED _INTEGER64
30 DIM N AS _UNSIGNED _INTEGER64
40 DIM K AS _UNSIGNED _INTEGER64
50 INPUT "K "; K
65 START = TIMER
60 COUNT = 1
70 FOR P = 2 TO 9999999999999999
    80 FOR N = 2 TO SQR(P)
        90 IF P MOD N = 0 GOTO 130
    100 NEXT N
    110 IF COUNT = K GOTO 140
    120 COUNT = COUNT + 1
130 NEXT P
140 PRINT "The"; K; "th Prime is "; P
150 ELAPSED = TIMER - START
160 PRINT "elapsed time is "; ELAPSED, "seconds"
170 GOTO 50
999 END

i got on my PC the million-th prime in about 35 seconds:
ksnip_20250319-222533.png

I changed the program so, that it first checks division by 2 and then it only checks division by odd numbers:
Code: 
Rem  Kth Prime Identifier - v7.x
Dim P As _Unsigned _Integer64
Dim N As _Unsigned _Integer64
Dim K As _Unsigned _Integer64

begin: Input "K "; K

START = Timer

If K = 1 Then
    P = 2
    GoTo result
End If

COUNT = 2
For P = 3 To 9999999999999999
    If P Mod 2 = 0 GoTo next_loop
    For N = 3 To Sqr(P) Step 2
        If P Mod N = 0 GoTo next_loop
    Next N
    If COUNT = K GoTo result
    COUNT = COUNT + 1
next_loop: Next P
result: Print "The"; K; "th Prime is "; P
ELAPSED = Timer - START
Print "elapsed time is "; ELAPSED, "seconds"
GoTo begin
End

Now the inner loop runs with step=2 and the computation takes approximately a half, i.e. about 16 seconds:
ksnip_20250319-223922.png

In the program code, I replaced the line numbers in the GoTos with labels because I find it clearer.
 
Upvote 0 Downvote
pya said:
Hi Mikrom,

This QBASIC program searches for the kth Prime Number and prints the Prime Number and k value.
I have tested it on a site for checking Primes.

Is there any way I can speed up the processing time?

Your help appreciated.

pa99
Click to expand...
Hi Mikrom,

Thanx for your help.
Your code has reduced processing time by over 50%. Very happy. (See below).
I can now test large Primes.

One more question:
For very large Primes where K = 22,000,000, the program either a) stalls or b) takes an inordinate amount of time, after which I just make a hard EXIT.

Is there a way of inserting a Trace that tells me the code is still running and not just crashed?
For example, inserting an output of K and P, every a) every 2 minutes or b) every 100,000 loops of K?

Your help appreciated.

Regards & Thanx

pa99

KV7.2V8.1 (Mikrom)
TIME sTIME s
1,000,000
7,777,7772211
8,888,887533249
9,111,111642306
9,555,555692319
9,999,999345
10,333,333367
11,000,000386
16,000,000422
20,000,000780
 
Upvote 0 Downvote
pya said:
Hi Mikrom,

This QBASIC program searches for the kth Prime Number and prints the Prime Number and k value.
I have tested it on a site for checking Primes.

Is there any way I can speed up the processing time?

Your help appreciated.

pa99
Click to expand...
You can speed up the processing by using a more efficient algorithm like the Sieve of Eratosthenes to generate primes up to the kth prime. Also, checking divisibility only up to the square root of a number can improve performance. Consider optimizing your loop logic to avoid redundant checks.
 
Upvote 0 Downvote
Hi pya,
Is there a way of inserting a Trace that tells me the code is still running and not just crashed?
For example, inserting an output of K and P, every a) every 2 minutes or b) every 100,000 loops of K?
Click to expand...
You can show progress on a screen position you want, using LOCATE and PRINT - see the screenshots:

ksnip_20250322-122103.png
ksnip_20250322-122502.png

But printing takes a time, so i made on the beginning of the program a switch show_progress which you could set to 1 to show the progress or to 0 if you don't want to show it.

Here is tho code:
Code: 
Rem  Kth Prime Identifier - v7.x 
Dim P As _Unsigned _Integer64 
Dim N As _Unsigned _Integer64 
Dim K As _Unsigned _Integer64 
 
' set this to 1 to show progress 
show_progress = 1 
progress_text$ = "computing prime for k =" 
 
begin_pgm: Input "K "; K 
 
If K = 0 GoTo end_pgm 
 
START = Timer 
 
If K = 1 Then 
    P = 2 
    GoTo result 
End If 
 
If show_progress = 1 Then 
    row = CsrLin - 1 
    col = 25 
End If 
 
COUNT = 2 
For P = 3 To 9999999999999999 
    If show_progress = 1 Then 
        If COUNT Mod 1000 = 0 Then 
            Locate row, col 
            Print progress_text$, COUNT 
        End If 
    End If 
 
    If P Mod 2 = 0 GoTo next_loop 
    For N = 3 To Sqr(P) Step 2 
        If P Mod N = 0 GoTo next_loop 
    Next N 
 
    If COUNT = K GoTo result 
 
    COUNT = COUNT + 1 
 
next_loop: Next P 
result: Print "The"; K; "th Prime is "; P 
Rem locate row, col: print(" ") 
ELAPSED = Timer - START 
Print "elapsed time is "; ELAPSED, "seconds" 
 
GoTo begin_pgm 
 
end_pgm: Print ("Bye.") 
End

Now it shows the progress on every 1000 iteration of COUNT.
If you want to show it every 100.000, then change the condition:
Code: 
If COUNT Mod 1000 = 0 Then 
   ...
 
Upvote 0 Downvote
mikrom said:
Hi pya,

You can show progress on a screen position you want, using LOCATE and PRINT - see the screenshots:

View attachment 1945
View attachment 1947

But printing takes a time, so i made on the beginning of the program a switch show_progress which you could set to 1 to show the progress or to 0 if you don't want to show it.

Here is tho code:
Code: 
Rem  Kth Prime Identifier - v7.x
Dim P As _Unsigned _Integer64
Dim N As _Unsigned _Integer64
Dim K As _Unsigned _Integer64
 
' set this to 1 to show progress
show_progress = 1
progress_text$ = "computing prime for k ="
 
begin_pgm: Input "K "; K
 
If K = 0 GoTo end_pgm
 
START = Timer
 
If K = 1 Then
    P = 2
    GoTo result
End If
 
If show_progress = 1 Then
    row = CsrLin - 1
    col = 25
End If
 
COUNT = 2
For P = 3 To 9999999999999999
    If show_progress = 1 Then
        If COUNT Mod 1000 = 0 Then
            Locate row, col
            Print progress_text$, COUNT
        End If
    End If
 
    If P Mod 2 = 0 GoTo next_loop
    For N = 3 To Sqr(P) Step 2
        If P Mod N = 0 GoTo next_loop
    Next N
 
    If COUNT = K GoTo result
 
    COUNT = COUNT + 1
 
next_loop: Next P
result: Print "The"; K; "th Prime is "; P
Rem locate row, col: print(" ")
ELAPSED = Timer - START
Print "elapsed time is "; ELAPSED, "seconds"
 
GoTo begin_pgm
 
end_pgm: Print ("Bye.")
End

Now it shows the progress on every 1000 iteration of COUNT.
If you want to show it every 100.000, then change the condition:
Code: 
If COUNT Mod 1000 = 0 Then
   ...
Click to expand...
Thanx Mikrom.

I will try to understand your code and test it in a few days time.

Your help is much appreciated.

pa99
 
Upvote 0 Downvote
Hi Mikrom,

I tested your latest version with the counter but after about 17 minutes the program stops at 1.676E+07 and does not go up to the 20,000,000th Prime!
I am sure this could be a limitation of either 1) my old DELL 15 laptop or 2) QBASIC.

Would you be able to shed some light please?

pa99
 
Upvote 0 Downvote
I found the Error : I did not have a DIM statement for COUNT.

the 20,000,000th Prime is 373587883 and it took 1187 s.

pa99
 
Upvote 0 Downvote
Hi pya,

Congratulation!
And what data type did you declare COUNT as? As an unsigned Integer64 like this, or something else?
Code: 
Dim COUNT As _Unsigned _Integer64
 
Upvote 0 Downvote
Hi Mikrom,

Yes, I set COUNT as As _Unsigned _Integer64 and it worked.

I have now identified the 200,000,000th Prime. The program ran from21:30 till 08.20 approx 11 hours!

However, the attached screen shows a strange negative number for Elapsed Time!

Any idea what this is?

pa99200M Prime Output v9.JPG
 
Upvote 0 Downvote
Hi pya,

The negative number you received is the result of subtracting two values returned by the TIMER function.
The value returned at 8:20 was smaller than the value returned at 21:30.

See the description of the function TIMER at https://qb64.com/wiki/TIMER

The TIMER function returns the number of seconds past the previous midnite down to an accuracy of 1/18th of a second.
..
TIMER return values range from 0 at midnight to 86399!
 
  • Like
Reactions: pya
Upvote 0 Downvote
Hi Mikrom,

Thanx for all your help on this issue.

I will now give programming a rest (and give you some peace also).
Till I come across a suitable interesting problem to solve.
I will try to solve it myself first, then try again, then probably fail and then finally in desperation I will contact you for help.
Hope you don't mind my requests for help.

QBASIC is a solution in search of problems.
As I mention to my friends, I have discovered a hammer; now I am in search of a nail!

Regards

pya
 
Upvote 0 Downvote
You must log in or register to reply here.

Similar threads

pya
  • Locked
  • Question
Data Type Mismatch in QBASIC 1
Replies
7
Views
582
mikrom
mikrom
pya
  • Locked
  • Question
Travelling Salesman Problem in QBasic 1
Replies
14
Views
612
mikrom
mikrom
Murugank
  • Locked
  • Question
Get source code from a QBasic exe
Replies
1
Views
468
mikrom
mikrom
Serhiy79
  • Locked
  • Question
QBasic convert to VB.NET or C# 3
Replies
4
Views
325
Serhiy79
Serhiy79
Shift838
  • Locked
  • Question
Message base with QBasic
Replies
6
Views
296
edfair
edfair

Part and Inventory Search

Sponsor

Back
Top