Out of Memory Exception / Parallel.For Loop / Large Numbers

Page 1 of 1

8 Replies - 1738 Views - Last Post: 29 November 2011 - 02:15 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=257412&amp;s=c43e480c9833fc5ccbcfac01c7c6af2b&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 Beach_Coder

Reputation: 16
• Posts: 123
• Joined: 10-November 11

Out of Memory Exception / Parallel.For Loop / Large Numbers

Posted 27 November 2011 - 06:34 PM

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.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
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 ...")

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

Is This A Good Question/Topic? 0

Replies To: Out of Memory Exception / Parallel.For Loop / Large Numbers

• MrCupOfT

Reputation: 1948
• Posts: 8,666
• Joined: 29-May 08

Re: Out of Memory Exception / Parallel.For Loop / Large Numbers

Posted 27 November 2011 - 06:53 PM

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

#3 DimitriV

• Don't try to save yourself… the circle is complete

Reputation: 544
• Posts: 2,632
• Joined: 24-July 11

Re: Out of Memory Exception / Parallel.For Loop / Large Numbers

Posted 27 November 2011 - 06:56 PM

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.

#4 Beach_Coder

Reputation: 16
• Posts: 123
• Joined: 10-November 11

Re: Out of Memory Exception / Parallel.For Loop / Large Numbers

Posted 27 November 2011 - 07:04 PM

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.

• MrCupOfT

Reputation: 1948
• Posts: 8,666
• Joined: 29-May 08

Re: Out of Memory Exception / Parallel.For Loop / Large Numbers

Posted 28 November 2011 - 12:13 AM

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?

#6 dbasnett

• D.I.C Regular

Reputation: 86
• Posts: 487
• Joined: 01-October 08

Re: Out of Memory Exception / Parallel.For Loop / Large Numbers

Posted 28 November 2011 - 06:19 AM

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

#7 Beach_Coder

Reputation: 16
• Posts: 123
• Joined: 10-November 11

Re: Out of Memory Exception / Parallel.For Loop / Large Numbers

Posted 28 November 2011 - 06:52 AM

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
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!

• MrCupOfT

Reputation: 1948
• Posts: 8,666
• Joined: 29-May 08

Re: Out of Memory Exception / Parallel.For Loop / Large Numbers

Posted 28 November 2011 - 07:53 PM

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

#9 Beach_Coder

Reputation: 16
• Posts: 123
• Joined: 10-November 11

Re: Out of Memory Exception / Parallel.For Loop / Large Numbers

Posted 29 November 2011 - 02:15 PM

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