Distinct Numbers in a N by N multiplication matrix

Category:

Academia

Languages:

C

Technologies:

C MPI (Message Passing Interface), distributed computing, parallel computing

Description:

This was the final exam/assessment to my parallel computer course. It does not sound like a challenging task, but once the size of N becomes large, you start to run into issues. Depending on your implementation, you will run out of memory very quickly. If you try and store 500,0002 32 bit integers in an array, you will need about 256 GB of memory. As space complexity is the limiting factor for this problem, my algorithm was designed to optimize for a reduced memory footprint. Resulting in an algorithm that allowed for larger matrices to be used. Considering the memory limits of a 32-bit operating system, the largest value of N that the naïve solution could calculate is N = 65,535, my solution allows for a maximum of around N = 4,000,000,000.