Why does my Loop end after 11 Loops?

[SMcNeill]

@Dimster Recursion isn't going to help you one whit.  Let me highlight what the problem is for you, in a nutshell:

Code: (Select All)

SCREEN _NEWIMAGE(800, 600, 32)
DIM AS _UNSIGNED LONG a, b


t# = TIMER + 10
DO
    b = b + 1
    PRINT b
LOOP UNTIL TIMER > t#

a = 44 * 44 * 44 * 44 * 44 * 44
PRINT a '2,961,346,560
PRINT USING "################.## seconds to print #,###,###,### times on the screen."; (a / b) * 10, a 'times 10 as we counted for 10 seconds
PRINT USING "################.## minutes to print #,###,###,### times on the screen."; (a / b) / 6, a
PRINT USING "################.## hours to print #,###,###,### times on the screen."; (a / b) / 360, a

PRINT "Press <ANY KEY> for a different test by Steve(tm)!"
SLEEP

DIM AS _UNSIGNED LONG i, iLimit, count, count1
iLimit = 2961346560
t# = TIMER + 10
FOR i = 0 TO iLimit - 1
    count = count + 1
    printNums i
    IF TIMER > t# THEN EXIT FOR
NEXT
PRINT USING "################.## seconds to print #,###,###,### times on the screen."; (a / count) * 10, a
PRINT USING "################.## minutes to print #,###,###,### times on the screen."; (a / count) / 6, a
PRINT USING "################.## hours to print #,###,###,### times on the screen."; (a / count) / 360, a


PRINT "Press <ANY KEY> for a final test by Steve(tm)!"
SLEEP


t# = TIMER + 10
count1 = 0
FOR TNa = 1 TO 44
    FOR TNb = 2 TO 45
        FOR TNc = 3 TO 46
            FOR TNd = 4 TO 47
                FOR TNe = 5 TO 48
                    FOR TNf = 6 TO 49
                        PRINT TNa; TNb; TNc; TNd; TNe; TNf
                        count1 = count1 + 1
                        IF TIMER > t# THEN GOTO finishedfors
                    NEXT
                NEXT
            NEXT
        NEXT
    NEXT
NEXT

finishedfors:
PRINT USING "################.## seconds to print #,###,###,### times on the screen."; (a / count1) * 10, a
PRINT USING "################.## minutes to print #,###,###,### times on the screen."; (a / count1) / 6, a
PRINT USING "################.## hours to print #,###,###,### times on the screen."; (a / count1) / 360, a
PRINT "**************"
PRINT "**************"
PRINT "Final results:"
PRINT "Straight print in hours:"; (a / b) / 360
PRINT "Math print in hours:"; (a / count) / 360
PRINT "For print in hours:"; (a / count1) / 360
PRINT
PRINT
PRINT "And, to do the same calculations WITHOUT a PRINT statement?"
PRINT "...."

t# = TIMER + 10
count2 = 0
FOR TNa = 1 TO 44
    FOR TNb = 2 TO 45
        FOR TNc = 3 TO 46
            FOR TNd = 4 TO 47
                FOR TNe = 5 TO 48
                    FOR TNf = 6 TO 49
                        'PRINT TNa; TNb; TNc; TNd; TNe; TNf
                        count2 = count2 + 1
                        IF TIMER > t# THEN GOTO finishedfors2
                    NEXT
                NEXT
            NEXT
        NEXT
    NEXT
NEXT

finishedfors2:
PRINT "NO printin hours:"; (a / count2) / 360&&


SUB printNums (nValue AS _UNSIGNED LONG)
    STATIC AS _UNSIGNED LONG n, n1, n2, n3, n4, n5, n6
    DIM AS _UNSIGNED LONG r, r1, r2, r3, r4, r5, r6
    IF NOT n THEN
        n = 1
        n1 = 44
        n2 = n1 * 44
        n3 = n2 * 44
        n4 = n3 * 44
        n5 = n4 * 44
        n6 = n5 * 44
    END IF
    r = nValue
    r5 = r MOD n6
    r5 = (r MOD n5) \ n4
    r5 = (r MOD n4) \ n3
    r5 = (r MOD n3) \ n2
    r5 = (r MOD n2) \ n1
    r6 = r MOD n1
    PRINT r1 + 1, r2 + 2, r3 + 3, r4 + 4, r5 + 5, r6 + 6
END SUB

Now you've got 6 loops running 44 times each.  (loop 1 is 1 to 44, loop 2 is 2 to 45, loop 3 is 3 to 46, but they're all running 44 times each -- just with a different start and end value)

That's 2,961,346,560 times total.  (44 * 44 * 44 * 44 * 44 * 44)

The above demo runs 3 times for us, and tries to calculate how long it'd take to run the full count, if we let it.  

First, it does a simple count from 1 to 2,961,346,560 and sees how high it can count in 10 seconds.  It then uses that 10 second count to estimate the time to do the whole count.

Then it tries to bypass the nested looping and do some math for its counting.  It sees how high it can count in 10 seconds and then estimates us a finished time.

Then it goes to the default method which you posted, and does that same style counting and estimation, and then it displays the various results for comparison.

And while you're looking at the results and seeing that NONE of the changes really make much of a difference, it runs in the background and tries to calculate how long it'd take to do the process WITHOUT any PRINT statement being involved...

The final results on my laptop (which was also trying to do windows updates in the background) were:

   


We're talking 5 or 6 days from start to finish to print all those values to the screen...
Half an hour, if we skip the print process and just do the calculations...

I think it's rather obvious where the bottleneck is, and it isn't in the nested FOR...NEXT loops.

[Dimster]

Hi Steve. I don't think I have a Print statement in my actual code however I am going to do a thorough search thru it to make sure. I believe you are pointing out, if I can structure a Recursive Loops which does the same thing as the For Looping, then the speed would likely be the same?

[bplus]

https://www.youtube.com/watch?v=8FftI0oRg2M

Code: (Select All)

_Title "Burn out" ' b+2023-02-13
recur 1, 2, 3, 4, 5, 6

'For TNa = 1 To 44
'    For TNb = 2 To 45
'        For TNc = 3 To 46
'            For TNd = 4 To 47
'                For TNe = 5 To 48
'                    For TNf = 6 To 49
'                        Print TNa; TNb; TNc; TNd; TNe; TNf
'                    Next
'                Next
'            Next
'        Next
'    Next
'Next

Sub recur (a, b, c, d, e, f)
    Print a; b; c; d; e; f; "press a key to continue..."
    Sleep
    f = f + 1
    If f > 49 Then
        f = 6
        e = e + 1
        If e > 48 Then
            e = 5
            d = d + 1
            If d > 47 Then
                d = 4
                c = c + 1
                If c > 46 Then
                    c = 3
                    b = b + 1
                    If b > 45 Then
                        b = 2
                        a = a + 1
                        If a > 44 Then Print "Has the sun burnt out yet?": Exit Sub
                    End If
                End If
            End If
        End If
    End If
    ' what? still here then
    recur a, b, c, d, e, f
End Sub

LOL shows you how bored I am!

[Dimster]

Boring???? That's fascinating bplus. Terry gave me a real good example of how he stacked recursive calls. Your If..EndIf is nested similar to the For..Next nesting, and I'm coming to the realization that your example may be the closest to nesting recursion calls. The structure I had in mind was:

Sub Recur

   Recur
     Recur
        Recur
          Do Stuff
        End Sub
     End Sub
  End Sub

End Sub

As Terry has demonstrated you can do

Sub Recur
  Recur
  Recur
  Recur
End Sub

In your example, I would nest the routine and not the Recur call. The Recur call however would need parameters. A recurring nested routine would take a lot longer to process (Time to Process =  does the sun still shine). One of my attempts at nesting a recursive call was similar to your code however I used Select Case but it actually turned out to be more like stacking as Terry's example. I'm going to abandon Nesting Recursion. Stacking obviously is the way to go (if it turns out to be as accurate and faster than what I'm using right now). Also, I'm abandoning it because I'm depressed my team did not win the Super Bowl.

[Kernelpanic]

Hi Steve. I don't think I have a Print statement in my actual code however I am going to do a thorough search thru it to make sure. I believe you are pointing out, if I can structure a Recursive Loops which does the same thing as the For Looping, then the speed would likely be the same?

No it is not! I already mentioned that above. A recursion can never be as fast or even faster than an iteration because of the stack usage.
If you still have an old PC with an 80268/80368 CPU, you can try it out there. Calculate the Fibonacci number iteratively once, and then recursively. The iterative result is there immediately, the recursive result took over 30 seconds at n = 33. This no longer works today, the CPUs are too fast for that. You need bigger things.

@Dimster, I think you still don't understand the difference between iteration and recursion. I have several books in which recursion is explained in a very understandable way, but of course it's all in German.

There should also be problems that cannot (yet) be solved iteratively, i.e. only recursively. But I know more where I read that.

For 80286 fans (The recursive variant is above.):

Code: (Select All)

'Fibonacci iterativ - 13. Feb. 2022

Option _Explicit

Dim x, y As Long
Dim i, n As Integer

x = 1: y = 1: i = 1
Cls
Locate 3, 3
Print "Berechnet iterativ die Fibonaccizahl."

Locate 5, 3
Input "Geben Sie eine Zahl ein: ", n

Locate 7, 3
If n > 33 Then
  Beep: Print "Nur Eingaben bis 33!"
  GoTo Ende
End If

While i < n
  x = x + y: y = x - y: i = i + 1
Wend

Locate 7, 3
Print Using "Die Fibonaccizahl von ## ist: ###,#####"; n, x

Ende:
End

[mnrvovrfc]

If you expect "X" to be LONG as well you need to say "DIM AS LONG X, Y" instead of "DIM X, Y AS LONG" because it's defining "X" variable as SINGLE. The same with the other line with "DIM".

If you want to assign a bunch of variables in a single "DIM" statement other than SINGLE precision you have to start with "DIM AS (whatever)", otherwise you have to list each variable "AS (whatever)" individually like we had to do before QB64 hit version 1.

With the code supplied, try assigning to "X" involving a regular division rather than integer division, and you'll notice it.

[Kernelpanic]

This is a program from May 2022. I no longer do it this way after someone pointed it out to me. Maybe it was you? Just adjusted it.

But well that you pointed it out again in case someone tries it.

[Dimster]

Hello Kernelpanic -  yes you know I haven't delved deeply into iteration v's recursion but it seems they both use a control or set of instruction to repeat something. An iterative routine can take place in the main modula while recursion appears to need Sub call or maybe a function call.

Do you feel with todays modern chips and buses there will still be a speed difference between iteration and recursion?

[Kernelpanic]

Do you feel with todays modern chips and buses there will still be a speed difference between iteration and recursion?

That depends on what you want to do. I have checked again now, and for certain programs, recursion can actually be faster than iteration; apparently when it comes to floating point arithmetic.
The program is written in C, and I have to try it first, then I can try to write it in Basic. If one want, one can try it oneself; see the screenshot*).

The book also reminded me that there are different types of recursion.
A) Direct recursion (faculty program)
B) Indirect recursion (program A calls B, and B calls A again)
C) Tail recursion
D) True recursion (Meant to state that it cannot be replaced by an iterative function)

The German translation of "tail recursion" is a gag:
C) Schwanzrecursion is in English: "cock recursion". 

Yes, some things often only look simple at first glance!
The book: Leendert Ammeraal, Program design and algorithms in C, 2nd edition 1998

*)PS: I also made a PDF of it to copy the text, but it doesn't work. I can't copy the text from the file. No idea why not

[mnrvovrfc]

The simplest iteration doesn't need any loop construct. In the least it requires a counting variable that could be tested with "IF" and then just use "GOTO" to go back to the beginning of the loop. The same cannot be said about recursion, not only is any variable needed to test but the other undesireable performance and memory-use overhead.

QB64(PE) is clever enough to somehow translate "WHILE... WEND" or "DO... LOOP" into C++ code so that it doesn't even require any more memory consumption than at least one variable that has to trigger a condition, either to keep the loop going or to stop it, up to the programmer to decide. Then there are other tools like "EXIT DO" and "_CONTINUE. Recursion doesn't offer any of that stuff and is the same hog in any programming language including LISP. Without recursion, some routines would become complicated such as the famous Quicksort. Otherwise it must be used where it's absolutely necessary.