C++ for beginners, part 6

These posts tend to be longer than I expect, so without further a-

-do, here’s the 3rd and final R function to convert:

Pic1It is by far the easiest thing we’ve had to write in C++. Indeed:

Pic2

This is the point where I was gonna compare the speeds of the three functions (brute force, pre-allocate vectors, pure math) between R and C++, but I hit a wall with every function, except for the pure math function in R.

Speed and Sleuthing

Brute force has a problem because it keeps adding values to something preexisting, so you just have to pray there’s enough space in memory for it. This happens in both C++ and R.

So we pre-allocated vectors. In R, running the function up to 100,000,000 says the vector of size 203.5Mb is too big to allocate. Let’s work out why.

  • The vectors contain all multiples of 3 and 5, up to 100,000,000. Maybe the actual values are too large? Well, the highest number has to be less than 100 million, but a 32-bit number (which R uses) can hold signed values up to 2.15 billion. Yowza.  So that can’t be the problem (also, uhm, it already told us it’s a memory problem. But this kind of Columbo thinking is good practice for debugging).
  • The lengths of these vectors are ~33.3 million and ~19.9 million. Adding them together, the length of the vector we try to apply the ‘unique’ function to is 54 million. Is that too big to store in memory?
  • 54 million numbers. Each number is 32 bits. So: 32*54 million = about 1.7 billion bits. There are 8 bits in a byte, so we divide this by 8, giving: 216 million bytes. A Mb or Megabyte is a million bytes. So our vector is about 216Mb, which is pretty damn close to the 203.5Mb that we got in the error message! It always seems so obvious in hindsight, doesn’t it?

problem

  • Oddly enough, you can assign this ridiculously sized vector in R, but you don’t get the error until you try to apply ‘unique’ to it. The help guides for R are a lot less detailed than those for C++, so I don’t know why this is happening. Oh well.

In C++, this function breaks down at the 100,000 range:

  • Pic6Checking R for what the answer should be, we get 2,333,316,668. Oh right! ‘Int’ can only hold up to 2.15 billion, but our value is 2.33 billion. So it overshoots the mark and goes into negative numbers. Because:
  • Of the 2,333,316,668 we want, it can represent up to and including 2,147,483,647 without problem. There’s still 185,833,021 left to represent. So starting from the lowest negative number, we add this amount (minus 1 to account for the fact that we already ‘added’ the first value by starting on the lowest negative number). So: -2,147,483,648 + 185,833,020 = -1961650628. Aha. Integer overflow. To help visualize this, check out this image on this page.

As for the pure math function, in R it works up to and including: 1 followed by 154 0s.

  • 1000000000000000000000000000000000000000000000000000
  • 0000000000000000000000000000000000000000000000000000
  • 000000000000000000000000000000000000000000000000000
  • I feel it worth pointing out that there are:

Pic7fry davies

Gosh.

Optimizing the R functions

Moral of the story: some numbers are ridiculously big. Also: vectors get out of hand really easily. Let’s deal with this vector problem. A good programming discipline is to never use something unless it is absolutely necessary. Are vectors appropriate for this function? Turns out, for even modestly large numbers, they’re not. Ultimately, we’re just adding numbers together. Once a number is added, we never need it again. And why create a number before it’s needed? Why don’t we just sum up as we go along, and deal with one number at a time? This solves the vector problem. We just have a cumulative sum:

Pic8

That goes further than the original function, because there’s no unnecessary vectors. Well, almost none. In the for-loop, it has 1:(thresh-1). It’s not a figure of speech, it actually creates that vector. This can be a problem:

Pic9So, we’ll take a page out of C++’s book (hmm, that possessive apostrophe looks like I’m self-censoring. I would never do that. Cuntflaps. See?) and try a C++ style of for-loop, using ‘while’:Pic10

Swish! Until 5 minutes ago, I’d never encountered that problem with a for-loop in R (never gave it that large a vector before), nor used the C++ style of loop in R. I’m learning too, see? Now the function isn’t constrained by any internal memory or representation, only your patience (I ran it about 5 minutes ago, and that function is still running on the range up to 1000000000000000, but it is running).

Tidying up the second function similarly:

Pic12

Again, it has no vectors, and will run as long as you have the patience for. Also, it’s worth linking to this, which compares the merits of different indentation styles. It does actually make a big difference in reading and keeping track of larger (more realistic sized) programs.

Optimizing the C++ functions

For the brute force function, use cumulative sum instead of vector:Pic13

  • Note: I removed the cin part that requests user input, because when timing the code, that includes the time it takes to type the input.  By declaring the values inside the code each time I run it, I can get a more reliable idea of timing performance between functions and languges.
  • Anyway, this still has an integer overflow when thresh is 100,000.
  • So, replace all instances of ‘int’ with ‘unsigned long long’ (except for int main(), which is just the way things are). Unsigned uses the extra bit to double the range. While long long doubles the number of bits. (‘long’ is either larger or equal to ‘int’ on different platforms/compilers etc, so ‘long long’ guarantees a size larger than ‘int’). See this page here for more types and their ranges. Oh, and unsigned long long can take anywhere from 0 to 18,446,744,073,709,551,615. Cor blimey. Anyhoo:

Pic14

For the second function (using known multiples), it’s the same process. Replace int with unsigned long long, and get rid of vectors, by using loops. Again, instead of using unique to find unique multiples of 3 and 5, we just subtract the sum of multiples of 15. Easy:

Pic15

For the final function, there’s no vectors to get rid of, we’re just changing int to unsigned long long:

Pic16

That’s it. That’s as far as we can optimize based on what I know so far. And it leaves us in a position to time each function so we can compare between functions and languages. But since I’ve hit the 1000 words mark, I’ll leave that for the next post.

Advertisements
This entry was posted in C++, Problem 1 and tagged , . Bookmark the permalink.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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