# Optimising algorithm issue

Page 1 of 1

## 6 Replies - 582 Views - Last Post: 08 May 2013 - 01:10 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=258124&amp;s=31bd823f3b17e8c2d53ce815d8315886&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 ghqwerty

• if(\$spareTime > 0){ \$this->writeCode(); }

Reputation: 43
• Posts: 903
• Joined: 08-August 08

# Optimising algorithm issue

Posted 02 December 2011 - 11:35 AM

I'm trying to optimise a simple algorithm i have for one of the project euler questions.

the question can be found here
Problem 14

using the following code, a brute force attempt, it executes in approx 3.4 seconds
```Function problem14() As String ' Which starting number, under one million, produces the longest chain? (Even, odd => n=n/2, n=3n+1)
Dim startTime As DateTime = DateTime.Now()
Dim longestChain As Integer = 0
Dim longestStart As Integer = 0
Dim maxValue As Integer = 1000000
Dim currNum As Int64
Dim currChain As Integer
For x = 500001 To maxValue
currNum = x
currChain = 0
While currNum <> 1
If currNum Mod 2 = 0 Then
currNum /= 2
Else
currNum = (3 * currNum) + 1
End If
currChain += 1
End While
currChain += 1
If currChain > longestChain Then
longestChain = currChain
longestStart = x
End If
Next

Dim Timespan As TimeSpan = DateTime.Now() - startTime
Return longestStart & vbCrLf & "Execution time: " & Timespan.Seconds() & "s " & Timespan.Milliseconds() & "ms."
End Function ' Which starting number, under one million, produces the longest chain? (Even, odd => n=n/2, n=3n+1)
```

In an attempt to optimise it i wanted to create a table of any values i come across. That way if you follow the pattern and get to a number you have already come across you already know the chain length for that number and can simply add it on the the currChain length and stop looping that number. in theory it should be quicker.
However the following runs in approx 8.5 seconds.

Perhaps i am looking at it the wrong way or simply performing the checks on the hashtable takes longer than iterating the required number of times but could someone please explain the problem?

'optimised' code
```Function problem14() As String ' Which starting number, under one million, produces the longest chain? (Even, odd => n=n/2, n=3n+1)
Dim startTime As DateTime = DateTime.Now()
Dim longestChain As Integer = 0
Dim longestStart As Integer = 0
Dim maxValue As Integer = 1000000
Dim cache As New Hashtable

Dim currNum As int64
Dim currChain As Integer
For x = 500001 To maxValue
currNum = x
currChain = 0
While currNum <> 1
If currNum Mod 2 = 0 Then
currNum /= 2
If cache.ContainsKey(currNum) Then
currChain += cache.Item(currNum) - 1
currNum = 1
End If
Else
currNum = (3 * currNum) + 1
If cache.ContainsKey(currNum) Then
currChain += cache.Item(currNum) - 1
currNum = 1
End If
End If
currChain += 1
End While
currChain += 1
If currChain > longestChain Then
longestChain = currChain
longestStart = x
End If
Next

Dim Timespan As TimeSpan = DateTime.Now() - startTime
Return longestStart & vbCrLf & "Execution time: " & Timespan.Seconds() & "s " & Timespan.Milliseconds() & "ms."
End Function ' Which starting number, under one million, produces the longest chain? (Even, odd => n=n/2, n=3n+1)
```

Thankyou

This post has been edited by ghqwerty: 02 December 2011 - 11:38 AM

Is This A Good Question/Topic? 1

## Replies To: Optimising algorithm issue

### #2 trevster344

• The Peasant

Reputation: 224
• Posts: 1,516
• Joined: 16-March 11

## Re: Optimising algorithm issue

Posted 02 December 2011 - 06:51 PM

You want to store every value that comes up into a table? Why a hash table? I'm sorry if I missed what you meant. Just declare a new variable, and store the value of your expression, and every time your code runs through those expressions add a new value.

### #3 ghqwerty

• if(\$spareTime > 0){ \$this->writeCode(); }

Reputation: 43
• Posts: 903
• Joined: 08-August 08

## Re: Optimising algorithm issue

Posted 03 December 2011 - 03:52 AM

I am sill very new to VB.NET and before that I only knew php, so there are a lot of concepts I don't fully understand. In the forum for this question on ProjectEuler, i noticed people talking about a 'hashtable' to store the values and when googling hashtables for VB.NET I discovered the 'hashtable' datatype/array/function/object (not even 100% sure what it is)and simply assumed they were the same thing, I guess I was wrong for that assumption.

I think i am misunderstanding you, or visa versa, but considering this is looping 500 thousand times surely I don't want to be adding a new variable each time ?

How do you mean?

### #4 trevster344

• The Peasant

Reputation: 224
• Posts: 1,516
• Joined: 16-March 11

## Re: Optimising algorithm issue

Posted 03 December 2011 - 09:48 AM

Well you can put these values in anything, doesn't have to be a hashtable. I was just curious why you were doing that. In your code where you check if the value is odd, or even add the number that is returned for the equation(didn't mean expression sorry to confuse you) and input it into your table, or whatever you want to put the value into. You'll only be putting the value into a single variable.

### #5 ghqwerty

• if(\$spareTime > 0){ \$this->writeCode(); }

Reputation: 43
• Posts: 903
• Joined: 08-August 08

## Re: Optimising algorithm issue

Posted 03 December 2011 - 10:31 AM

Sorry, either i'm just having a complete mental block in understanding what you mean (which is likely given the amount of school work i have been doing recently, leaving me brain-dead in the evenings), or you've interpretted what i want done wrong (both being my fault ).

I can't add it to a single variable there because i need to know 2 values - the number + the chain length after that point.

Both for your benefit and mine i will outline the pseudo process so that you know what i mean, and it is clear what i want to do.

Quote

for example you are given the following chain as an example in the question

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

so to speed things up when i iterate through the values starting from 1 i want to add the chain length each value generated in a table. so by the time we get to 13 in the iteration we will have the chain lengths for each number 1-13

just looking at the example chain we can see

starting value => chain length
1 => 1
2 => 2
3 unknown
4 => 3
5 => 6
6 unknown
7 unknown
8 => 4
9 unknown
10 => 7
11 unknown
12 unknown

now we can use these values to reduce the amount of iterations necesary.
when calculating 13
chain length = 0
is it in the table -> no -> perform operation -> 40 chain length = 1
40 -> is it in the table -> no -> perform operation -> 20 chain length = 2
20 -> is it in the table -> no -> perform operation -> 10 chain length = 3
10 -> is it in the table -> yes -> add the corresponding value to the chain length and stop looping.
add 13 => *the resulted chain length from the previous process* to the table and start 14.

Hopefully this makes more sense ?

### #6 trevster344

• The Peasant

Reputation: 224
• Posts: 1,516
• Joined: 16-March 11

## Re: Optimising algorithm issue

Posted 03 December 2011 - 02:35 PM

I'm sorry today I'm just not able to follow along on what exactly the chain is, maybe someone else can give ya a hand but it's as they say going in one ear, and out the other lol.

### #7 lar3ry

• Coding Geezer

Reputation: 311
• Posts: 1,290
• Joined: 12-September 12

## Re: Optimising algorithm issue

Posted 08 May 2013 - 01:10 PM

First, allow me to thank you for the link to Project Euler. Those are some very interesting problems.

I played around with Problem 14, and used an array to store the chain lengths already figured out. It's a pretty big array, but it sure speeds up the processing. Isn't it always the case? Trade speed for size.

Anyway, I cheated a bit on the array. I made it an array of Int16, because I had foreknowledge of the longest chain, so the array would be even bigger if we increased the maximum number to test.

A few comments on the code...

Since we know that the only way for the sequence to end in a 1, is for it to land on a power of 2, I decided to prefill the array with the chain lengths starting at every power of 2, up to the maximum power of two less than 1000000. I included this prefilling in the time taken, though t's minuscule.

There was no need to check the cache twice (once in the even numbered, and once in the odd numbered currNums).

I added "Iterations Saved" to the label output in order track the number of chain amounts found in the cache(), and thus, the number of times we would have gone through the loop otherwise).

I also changed the For loop to go from 1 to 1,000,000, which better showed the speed differences.

Anyway, here's the code. I had a lot of fun doing it, and I thank you for that, too.

```    Function problem14Cache2() As String ' Which starting number, under one million, produces the longest chain? (Even, odd => n=n/2, n=3n+1)
Dim startTime As DateTime = DateTime.Now()

Dim n As Integer = 1
Dim count As Integer = 1
Dim cache(1000000) As Int16
Do Until n > 1000000
cache(n) = CShort(count)
count += 1
n *= 2
Loop

Dim longestChain As Integer = 0
Dim longestStart As Integer = 0
Dim iterationsSaved As Int64 = 0
Dim maxValue As Integer = 1000000

Dim currNum As Int64
Dim currChain As Integer
'For x = 500001 To maxValue
For x = 1 To maxValue
currNum = x
currChain = 0
While currNum <> 1
If currNum < 1000001 Then
If cache(CInt(currNum)) > 0 Then
iterationsSaved += CInt(cache(CInt(currNum)))
currChain += CInt(cache(CInt(currNum)))
currNum = 1
End If
End If
If currNum > 1 Then
If currNum Mod 2 = 0 Then
currNum = CLng(currNum / 2)
Else
currNum = (3 * currNum) + 1
End If
currChain += 1
End If
End While
cache(x) = CShort(currChain)
If currChain > longestChain Then
longestChain = currChain
longestStart = x
End If
Next

Dim Timespan As TimeSpan = DateTime.Now() - startTime
Return longestStart & vbCrLf & longestChain & vbCrLf & "Iterations Saved: " & iterationsSaved & vbCrLf & "Execution time: " & Timespan.Seconds() & "s " & Timespan.Milliseconds() & "ms."
End Function ' Which starting number, under one million, produces the longest chain? (Even, odd => n=n/2, n=3n+1)

```

Here are my results for the three methods:

#### Attached image(s)

This post has been edited by lar3ry: 08 May 2013 - 01:11 PM