Exiting FOR NEXT, maybe a bug? Version 4.1.0 on Linux

[Circlotron]

Had a go at calculating some Perfect Numbers. If I EXIT the FOR NEXT and print the number and the sum of it's factors (which should be equal) it works just fine. (After the first four it might take forever because it is a big number.) But if I print the number and the sum of it's factors just before I EXIT the FOR NEXT as well as after then I get several extra unrelated numbers. The line that causes the issue is commented out, but put it in and things go bad. I would have thought that it made no difference except for printing the numbers twice. What's going on? 

Code: (Select All)

ChDir startdir$ + "perfect numbers/"



Dim number As _Integer64

Dim trial As _Integer64

Dim div_total As _Integer64



number = 4 'start even and add 2 per pass

top:

div_total = 0



For trial = 1 To ((number / 2) + 1)

    If number Mod trial = 0 Then div_total = div_total + trial

    'If div_total = number Then Print number, div_total, "x": Exit For

Next trial



If div_total = number Then Print number, div_total

number = number + 2

GoTo top

[SMcNeill]

Had a go at calculating some Perfect Numbers. If I EXIT the FOR NEXT and print the number and the sum of it's factors (which should be equal) it works just fine. (After the first four it might take forever because it is a big number.) But if I print the number and the sum of it's factors just before I EXIT the FOR NEXT as well as after then I get several extra unrelated numbers. The line that causes the issue is commented out, but put it in and things go bad. I would have thought that it made no difference except for printing the numbers twice. What's going on? 

Code: (Select All)

ChDir startdir$ + "perfect numbers/"



Dim number As _Integer64

Dim trial As _Integer64

Dim div_total As _Integer64



number = 4 'start even and add 2 per pass

top:

div_total = 0



For trial = 1 To ((number / 2) + 1)

    If number Mod trial = 0 Then div_total = div_total + trial

    'If div_total = number Then Print number, div_total, "x": Exit For

Next trial



If div_total = number Then Print number, div_total

number = number + 2

GoTo top

False positives found by not adding all the numbers up completely.

For example, you're getting 24 as a result.  Its factors are 1, 2, 3, 4, 6, 8, 12.
1 + 2 + 3 + 4 + 6 + 8 = 24   <-- Inside the loop, it would see this as being a FALSE positive result.

By letting the loop run completely, it also adds that 12 and gets:
1 + 2 + 3 + 4 + 6 + 8 + 12 = 36, which is NOT a perfect number of 24.

If you want an early exit condition, check for if the div_total > number, then you can stop checking any further as you know it's not going to work.

[SMcNeill]

Another trick for speed would be to adjust your upper limit as you go

To start, you know 1 and 2 are going to work (as all the numbers you are checking are even numbers.)  This gives you an upper limit of (number /2 - 1), which can also go into the total.

StartingTotal = (1 + 2 + number /2)

endPoint = (number/2 -1) 'no need to check past this number as we know it's already there.
startPoint = 3 'no need to check 1 or two as they're already assumed to be in there

Then while running the routine, update the endPoint with each match you make

For example with 24, you start knowing this:  1 + 2 + 12

You now check the values from 3 to 11.
When you find 3 is a match, that also gives you 8.   (3 * 8) = 24.   Your total is now 1 + 2 + 3 + 8 + 12 = 26.
At this point, your total is now greater than 24.   You don't need to check any further!  It's not a match!

IF the total had been less than 24, you still gained valuable information there, as your endpoint is now 7.  You've already found 8 and 12 as factors, so there's no reason to look that high any longer.  Instead of a loop from 3 to 11, it's now limited to a range from 3 to 7...

Each value you find would reduce the endpoint of what you need to check for, saving you a ton of loops and speeding the process up considerably.

[SMcNeill]

Code: (Select All)

Dim number As _Integer64

Dim trial As _Integer64

Dim div_total As _Integer64



number = 6 'start even and add 2 per pass

top:



Do

    div_total = 3 + number \ 2

    start = 3

    finish = number \ 2 - 1

    Do Until start >= finish

        If number Mod start = 0 Then

            start_partner = number \ start

            div_total = div_total + start + start_partner

            finish = start_partner - 1

        End If

        If div_total > number Then Exit Do

        start = start + 1

    Loop

    If div_total = number Then Print number

    number = number + 2

Loop

That's about the best I can see off the top of my head for speeding things up, and that's still not fast, but it's doing a lot of math each pass like this.

[Circlotron]

Oh yeah, I get it now. Not letting the loop try every relevant trial value.
That End if looks useful too. Makes things a lot tidier. Only just getting back into BASIC after a 25 year hiatus and there are a few things I had forgotten. Look back at some old code and wonder however did I manage that?!