ACM competition

I decided to join Brock’s computer science club. One of the reasons was because of the ACM competitions. The Computer Science Club, or CSC, posted a practice problem on their facebook page. The problem was to:

1) For all numbers from one to one million

2) For each number, if even divide by 2, if odd multiply by 3 and add 1

3) Continue step 2 until we get to 1.

4) Find the number between 1 and 1 million that takes the most steps.

The problem seemed trivially easy to code, although I did make a mistake in using ints, and the program hung because integer wrap around turned it to a negative number. I then stupidly used uInt, which actually worked for 1 million but did not work for 10 million. Using long long takes almost exactly twice the processing time, but is necessary to ensure the correct answer. Using uInts was a stupid optimization by me that I quickly corrected.

Anyway, after finding the number, 837 799, for those interested, I wanted to find out how many calculations the computer actually did. Turns out the number is 132 434 424. That’s one hundred and thirty two million calculations. The process took a grand total of 1.171 seconds to complete.

I decided to bump up the amount of numbers from 1 million, to 10 million and then 100 million. 1 billion takes too much memory (3.7 GB’s by my calculations).

At 10 million, the number that takes the most steps to get to 1 is 8 400 511. The total number of calculations are 1 562 724 831. The time is 13.234s.

At 100 million, the number is 63 728 127, and the total calculations are an amazing 18 023 493 583 . The time is 150.444 seconds. Yes, the computer did over 18 billion calculations in 150 seconds. Actually more, since when the computer multiplies by 3 and then adds 1, I only counted that as 1 step. We can safely assume that the computer really performed 18*1.5*10^8, or 27 billion calculations. That means the computer did 179.7 million calculations per second, 179 703 calculations per milli second, 179 calculations per micro second, and 0.179 calculations per nano second.

This just in – computers are really fast.

Although, at the same time, I feel like I’m making some error, since they should be faster. Maybe it’s the if statements that need to be evaluated that are slowing things down. Maybe its the pointer to the memory where the array is stored. I couldn’t store it on the stack, so I might be getting a cache miss every time I exit my NumSteps() function. I’m also slightly suspicious that maybe even my long long got wrapped around, since I would expect that the total calculations would be much more than 10 times higher for a set n = 100 million as compared to n = 10 million.

Taking the total calculations/time for the set of 10 million gives us (after multiplying by 1.5 to correct for the missing step) gives us 0.177 calculations/ns, which rules out wrap around.

Edit: Maybe it’s Time Slicing? As in the operating system taking the core away from me and giving it to some other process.

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s