Order of operations and overflow

Let's say you want 50% of 256 million (as in powers of two though like mebibytes, so 2 ^28). Easy, that's 128 million ( 2^27). One could easily write it out as

unsigned int elements = 256 * 1024 * 1024 * 50 * 0.01

You're multiplying 256 by 2^20 and by 0.5, which again equals 128 million. Not so fast! Because the operations happen from left to right, at one point you'll end up with a number that's over 13 billion (13,421,772,800 to be exact). Unsigned ints only go up to around 4 billion, so you'll overflow. The problem is you get an intermediate large number before your final answer. A safer approach is to be multiply the 0.01 before the 50 so you get a smaller intermediate number before your final answer. Yes, even though this is obvious, I still made this mistake.

Project Euler #3: Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

I started off by recycling the code from PE-10. To find the largest prime factor I'm going to find ALL the prime factors. By finding them in increasing order, I'm guaranteed that the last one I find will be the largest prime factor (side note: this also works if the inputted number is a prime number since the factors are 1 and itself).

I begin by setting the limit to the inputted number and starting at 5 and repeating my earlier method to find prime numbers in increasing order (sieving on 2 and 3, then using the idea that the smallest prime factor must be less than or equal to the square root of the number being tested if it's NOT a prime number). For every prime number I test if it's a factor of the inputted number. If it isn't then I store it in my prime number vector and move on. However, if it is then I set the new limit to be the old limit divided by this prime factor. Then I repeat the process. I continue until I reach the limit.

This works only because I'm finding the prime factors in order. Once we find one, we know the next one must be greater or equal to the one we just found. Thus I can continue on in my for-loop, only having to retest the most recent prime number (e.g. 8 is 2x2x2) before moving on. I like this solution because the amount of numbers we test is quite low so it scales really well.

For example, this problem asked for the prime factors of 600851475143. The prime factors are:

1. 71, new limit is 8462696833
2. 839, new limit is 10086647
3. 1471, new limit is 6857
4. 6857, new limit is 6857 (since they're equal)

Once the latest prime factor equals the limit we know we're done! So we only had to test roughly ~1142 numbers (6857 / 6 since we sieved). I'm not sure if the runtime I measured using is accurate, but it's returning 502 microseconds. I didn't bother making a naive version for this one since I was lazy.

The code can be found here.

Project Euler #1: Multiples of 3 and 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

I'm feeling lazy so I'll do a quick post about the first problem since it's pretty straightforward. All I did was  loop through every number from 1 until the limit and test if either 3 or 5 was a divisor. Brute force ftw! Including the printing this takes 0.002 seconds.

Even still, I can think of a few things to speed it up if only trivially.

1. Use something other than mod
2. Instead of incrementing by 1, keep two counters - one for 3 and the other for 5. Increment whichever one is lower and add it to the sum until both counters reach the limit. This way you save on having to test if the number is a multiple of 3 or 5. You do however need to check if your two counters are equal. If they are then you skip that number.

The second solution might deserve to be coded for clarity if there's any interest. Be sure to check out the solution thread as there are some nice ways to get the answer without any coding.

Edit: The code is not formatted properly when embedded here for whatever reason

Empty loop not responding to exit condition (also: how to multi-thread on Windows)

I had the following code

HANDLE * threadHandles
bool exitThreads

void threadEntryPoint(void * data)
{
    while (exitThreads == false){}
    _endthreadex(1);
}

void launchThreads(int nThreads)
{
    exitThreads = false;
    threadHandles = new HANDLE[nThreads];
    for (uint32_t i = 0; i < nThreads; ++i) {
        threadHandles[i] =
            (HANDLE)_beginthreadex(0,
            0,
            (uint32_t(__stdcall *)(void*))threadEntryPoint,
            NULL,
            0,
            0);
    }
}

void killThreads(int nThreads)
{
    exitThreads = true;
    for (uint32_t i = 0; i < nThreads; ++i) {
        WaitForSingleObject(threadHandles[i], INFINITE);
        CloseHandle(threadHandles[i]);
    }
    delete[] threadHandles;
}

This code will launch nThreads threads which will loop pointlessly until you call killThreads(). Ignore why I chose beginthreadex() over beginthread(). This is a good way to max out the cores on your CPU.

Conceptually this should work. And yet it didn't. The program was hanging it seemed as there was none of the expected output. Thankfully I had only launched it with 3 threads on a quadcore machine - I suspect launching it with 4 would've caused the machine to hang. The first thing I tried was debug mode. Multi-threading can get tricky, so might as well start by debugging it. Oddly enough it worked as expected in debug mode. That was weird, maybe the threads aren't printing properly? I then polluted my code with a bunch of cout statements with flushes in release mode, but I found that it would get to WaitForSingleObject() and then stop printing. So for whatever reason the threads were not exiting.

A quick google search turned up this beauty. It seems that the compiler tried to optimize the release version by not loading the value of exitThreads every loop iteration and instead assume it's always false. By adding the the keyword volatile before the bool exitThreads declaration, the compiler is forced to have the loop load the value every iteration - because the value is possibly volatile. I was aware of this concept before, but it's not something I deal with often so it's easy to slip the mind.

Project Euler #10: Summation of primes

This post is copied from another blog I run. I'll be shutting that blog down shortly and all future posts of that kind will go on this blog. These are solutions to various programming brain teasers. Optimizing your solution is the real challenge.

The problem reads as follows:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

Right from the start I can think of two methods:

1. Using a similar solution as for PE-7 but adding the primes instead of storing them
2. Sieve of Eratosthenes

I opted for the first method since I'm lazy. With minimal modifications, I get 173518 microseconds as my runtime. I was curious about the second method, so I copied and modified a solution found in the problem discussion thread. You can find that one under sieve.cpp. It has a runtime of 221631 microseconds. That's still pretty good.

The third way I can think of is to combine the first two methods. As with PE-7, automatically exclude all multiples of 2 and 3 for a 2/3 reduction in numbers considered. Then find all the primes below the square root of 2 million (so anything below and including 1415) and sieve on the remaining 1/3 with those prime numbers. Could result in a nice speedup over the first method. As usual, another thing you could do is to remove the use of the modulus operand - it's expensive.

The code can be found here 

Installing libclc on Ubuntu 14.04 LTS

libclc is needed for using Clang with OpenCL. See here for more details. Unfortunately it requires LLVM to be 3.7 or higher, while Ubuntu 14.04 only has up to 3.6.

Make sure you don't have LLVM installed before proceeding.To get around this you first have to get LLVM 3.7 by adding this line:

deb http://llvm.org/apt/precise/ llvm-toolchain-precise-3.7 main

 to this file:

/etc/apt/sources.list.d/llvm.list

I used nano. The original instructions using output redirection didn't work for me. You can find the address for other versions of Ubuntu or LLVM here. Now install llvm-3.7 and clang-3.7

sudo apt-get install llvm-3.7 clang-3.7

It will complain that it can't verify the source, but we added the source so go ahead and ignore it. Next get libclc if you don't already have it:

git clone http://llvm.org/git/libclc.git

Go through the readme and use llvm-config-3.7 instead of llvm-config. You may get an error like so:

/usr/bin/ld: cannot find -ledit

In this case just install libedit:

 sudo apt-get install libedit-dev

 However I still got many warnings of the following type:

WARNING: Linking two modules of different data layouts: 'amdgcn--/lib/image/write_image_impl.ll.tahiti.bc' is '' whereas 'llvm-link' is 'e-p:32:32-p1:64:64-p2:64:64-p3:32:32-p4:64:64-p5:32:32-p24:64:64-i64:64-v16:16-v24:32-v32:32-v48:64-v96:128-v192:256-v256:256-v512:512-v1024:1024-v2048:2048-n32:64'

A quick google search returned nothing. Because the data layout of the first module is empty I'm going to proceed with the assumption that I can ignore this.

Mixing C and C++

First, use g++ as it can compile C++ AND C - gcc cannot do that. If for whatever reason you need to use gcc, then just make object files to link with using g++ and the cpp files. 

If you're using malloc and get an error like this,

Process.cpp:45:53: error: invalid conversion from void* to char* [-fpermissive]
     char *linkCopy = malloc(strlen(&line[count]) + 1);

 it's because you need to cast the return value in C++ but not C. See this SO Q&A

Linker complains that a function doesn't exist when it does. First verify with nm that the function does indeed exist. You can use it on .o object and .a archive (static library) files. If it does, the your problem is you're trying to include a header for a C file in a C++ file. There's some problems with not enough information being generated from the C file compared to what the C++ file needs. See this SO Q&A for a solution