[Beach_Coder]

I need some guidance on a little program I'm making (one that I thought would take a couple of hours from start to finish, it's been days now ...) that determines all of the proper divisors of any given number up to the maximum value of a UInt32.

First I started with a happy little loop; it worked great on small numbers. I want to be able to run it for any positive Integer, but I figured I would work within the limits of a UInt32 until I got it going. Going through the loop to test all possible proper divisors of the number 24,000,000 took nearly 7 minutes, so 4 billion would take ...

Time to focus and get a grasp on using a Parallel.For loop. All this thread stuff is a little beyond me (not as much as a couple of days ago though) but I had success using a simple parallel.for loop. The same 24,000,000 took only about 1 minute to do its business. Pretty good, and much better than 7 minutes. Let's try it out on a real number. It didn't work: Out of Memory Exception Error. It happened sometimes when trying 5,000,000, sometimes 40,000,000, and in between the rest of the time.

So, I endeavored to split up the numbers I was processing into groups. I set the program to calculate all of the proper divisors of 4,200,000,000, then have it create arrays for segments thereof (1 to 5,000,000, then 5,000,001 to 10,000,000). If figured I was just trying to make it do too much at once. It helped a little, but not a lot. This tells me I took an ineffective approach to the problem. I added in lines to clear the array at the end of each segment, make the garbage collector collect, make the parallel range be nothing. This took it from running out of memory after 10 loops to 13.

I though of a) putting something in to monitor system resources and deal with running out of memory before it actually did run out of memory or B) forget about determining the proper divisors the old fashioned way and simply using the formula. With option a, I couldn't think of anything to do with such a warning if I had one, and with option b, I don't remember the formula, and I'm not entirely convinced I knew it when I actively studied math, and further, I wouldn't be surprised if the existence of such a formula is either unknown or one that could not possibly be calculated in Visual Basic.

In any event, maybe someone can give me a hint on a way to handle the evaporation of memory from trying to use a parallel.for loop 2 billion times.

Windows XP Pro SP3
x86
Visual Basic 2010 Express SP1
Option Explicit On
Option Strict On
Option Infer On

Imports System.Collections.Concurrent
Imports System.Threading.Tasks
Imports System.Collections
Imports System.Console

Module Module1

    Sub Main()

	CursorSize = 100
        ForegroundColor = ConsoleColor.Green
        BackgroundColor = ConsoleColor.Black
        TreatControlCAsInput = False
        WindowHeight = CInt(Math.Truncate(LargestWindowHeight * 0.98))
        WindowWidth = CInt(Math.Truncate(LargestWindowWidth * 0.98))
        WindowTop = 0
        WindowLeft = 0
	'
	'
	'
	Dim Big_Number As UInt32 = 4200000000              

        Dim Limit As Integer = 5000000

        Dim Max_Number As Integer

        If Math.IEEERemainder(CDbl(Big_Number), 2) = 0 Then
            Max_Number = CInt(Big_Number / 2)
        ElseIf Math.IEEERemainder(CDbl(Big_Number), 2) = 1 Then
            Max_Number = CInt(Math.Truncate(Big_Number / 2)) + 1
        End If

        Dim R As Integer
        Dim Q As Integer
        Q = CInt(Math.DivRem(Max_Number, Limit, R))

        Dim NumberofSegments As Integer '= Q
        If R = 0 Then
            NumberofSegments = Q - 1
        Else
            NumberofSegments = Q
        End If

        Dim Range_Segments(NumberofSegments, 1) As Integer
        For i = 0 To NumberofSegments
            Range_Segments(i, 0) = 1 + i * Limit
            If i < NumberofSegments Then
                Range_Segments(i, 1) = i * Limit + Limit
            ElseIf i = NumberofSegments Then
                Range_Segments(i, 1) = Max_Number
            End If
        Next

        Dim Source() As Integer
        Dim Remainder As Integer
        Dim Loop_Count As Integer = 0
        Dim Output As New List(Of Integer)
	Dim Happy_Result_String As String
        Writeline()
        CursorVisible = False


        Try

Loop_Start:

        Source = Enumerable.Range(Range_Segments(Loop_Count, 0), Range_Segments(Loop_Count, 1)).ToArray

        Dim RangePartitioner = Partitioner.Create(0, Source.Length)

            Parallel.ForEach(RangePartitioner, Sub(Range, LoopState)
                                                   For i As Integer = Range.Item1 To Range.Item2 - 1
                                                      Remainder = CInt(Math.IEEERemainder(Big_Number, CDbl(Source(i))))
                                                       If Remainder = 0 Then
                                                           Output.Add(Source(i))
                                                       End If
                                                   Next
                                               End Sub)

            Array.Clear(Source, 0, UBound(Source))
            Source = Nothing
            RangePartitioner = Nothing
	    GC.Collect()
            Loop_Count = Loop_Count + 1

            WriteLine("LOOPING ..." & Loop_Count)
         
            If Loop_Count <= NumberofSegments Then
                GoTo Loop_Start
            End If

            If Loop_Count > NumberofSegments Then
                GoTo Generate_Output
            End If

        Catch ex As OutOfMemoryException
            WriteLine()
            WriteLine("OUT OF MEMORY EXCEPTION AT:")
            WriteLine("Loop Count " & Loop_Count)
            WriteLine("CEASED CALCULATING. PRESS ANY KEY.")
            Happy_Result_String = Happy_Result_String & "OUT OF MEMORY EXCEPTION AT LOOP COUNT " & Loop_Count & "." & Chr(13) & Chr(10)
        End Try


Generate_Output:

        Dim Happy_Result_Array = Output.ToArray()

        Array.Sort(Happy_Result_Array)

        For Each i In Happy_Result_Array
            Happy_Result_String = Happy_Result_String & i & Chr(13) & Chr(10)
        Next

        My.Computer.FileSystem.WriteAllText("F:\Partitioner_Output_Temp.txt", Happy_Result_String, True)

        WriteLine()
        WriteLine("Done. Press any key ...")
        Readkey(True)


    End Sub


End Module

I also though of not using arrays at all and using lists exclusively, or perhaps dropping the use of a simple parallel.for and trying a more complex threading thing (it didn't seem appropriate though; I'm not doing a lot of things, I'm doing one thing a couple of billion times), or dusting off my old calculus book for a slightly more efficient means to get my answers, but I don't have it. I read something about manually allocating windows memory which was way over my head and then it said it was for 64 bit systems only anyway. I could just add more memory to my machine, but I can't really apply that as a solution (i.e. some method must be available to just do one thing a whole bunch of times no matter how little memory is available, it's not a complex calculation).

Any suggestions or guidance will be appreciated ...


Where did the flippin smiley face come from? It's like it's mocking me.

This post has been edited by AdamSpeight2008: 27 November 2011 - 06:51 PM
Reason for edit:: Disable emoticons: To remove Simley Face

[AdamSpeight2008]

Smiley Face is from B )(without the space though)
I'd edited your post to disable the emoticons.

[DimitriV]

Well, for one, any way you come at this issue it will take a long time to calculate in theory - it will use many CPU cycles to perform the calculations.
The smiley is this: - just put it into the post box
And here is a tutorial on Parallel.For:
http://www.dreaminco...arallelfor-101/


God, here is how to do the smiley:
Put a colon - :
And then a close brace - )
There is actually a button that looks like a smiley face in the post box, click it and it'll come up with a whole lot of 'em.

[Beach_Coder]

AdamSpeight2008, on 27 November 2011 - 08:53 PM, said:

Smiley Face is from B )(without the space though)
I'd edited your post to disable the emoticons.

Thanks. If I find the solution I'll ask you to turn it back on.

One other thing that seems curious to me. With each loop, the time it takes to do the next one goes up dramatically. I don't know if that would be expected regardless or if it is symptomatic of something that can be effectively tended to.

[AdamSpeight2008]

Beach_Coder
What are attempting to do?

1. Find the all divisors of a specific number?
2. Find of the perfect numbers between two limits?

[dbasnett]

I ahven't checked this

        Dim factorsOf As Long = 4200000000L
        Dim endPT As Long = factorsOf
        Dim listFact As New List(Of Long)

        Dim rmndr As Long = 0L
        Dim rslt As Long = 0L
        Dim nums As Long = 2L
        Dim stpw As New Stopwatch
        stpw.Restart()
        Do
            rslt = Math.DivRem(factorsOf, nums, rmndr)
            If rmndr = 0L Then
                listFact.Add(nums)
                listFact.Add(rslt)
                endPT = rslt
            End If
            nums += 1
        Loop While nums <= endPT
        stpw.Stop()
        Dim foo() As Long = listFact.Distinct.ToArray
        Debug.WriteLine("{0} factors in {1} seconds", foo.Count, stpw.Elapsed.TotalSeconds)
        'on my pc
        '358 factors in 0.0043681 seconds

The number of factors (358) is the same as the brute force.

[Beach_Coder]

AdamSpeight2008, on 28 November 2011 - 02:13 AM, said:

Beach_Coder
What are attempting to do?

1. Find the all divisors of a specific number?
2. Find of the perfect numbers between two limits?

The first thing I need is to figure all of the proper divisors of any given integer.
Future tasks involving that list include determining if the aforementioned given integer is a perfect number.

dbasnett, on 28 November 2011 - 08:19 AM, said:

I ahven't checked this

        Dim factorsOf As Long = 4200000000L
        Dim endPT As Long = factorsOf
        Dim listFact As New List(Of Long)

        Dim rmndr As Long = 0L
        Dim rslt As Long = 0L
        Dim nums As Long = 2L
        Dim stpw As New Stopwatch
        stpw.Restart()
        Do
            rslt = Math.DivRem(factorsOf, nums, rmndr)
            If rmndr = 0L Then
                listFact.Add(nums)
                listFact.Add(rslt)
                endPT = rslt
            End If
            nums += 1
        Loop While nums <= endPT
        stpw.Stop()
        Dim foo() As Long = listFact.Distinct.ToArray
        Debug.WriteLine("{0} factors in {1} seconds", foo.Count, stpw.Elapsed.TotalSeconds)
        'on my pc
        '358 factors in 0.0043681 seconds

The number of factors (358) is the same as the brute force.

Unbelievable. I just did a quick go with this (I'll test it out fully later today) but I think this is spot on!

[AdamSpeight2008]

If you're interested this is now the subject of a challenge.

[Beach_Coder]

dbasnett, on 28 November 2011 - 08:19 AM, said:

I ahven't checked this


The number of factors (358) is the same as the brute force.

I checked it. It works brilliantly. Simple. Fast. Precise.

AdamSpeight2008, on 28 November 2011 - 09:53 PM, said:

If you're interested this is now the subject of a challenge.

I think dbasnet is your man