Berry Good...

Bio

Code

Podcasts

Side Projects

Contact Info

Berry Good Code - Prime Squared

Keywords: prime, GPU, Metal, calculation

Abstract

This project started off as a mild curiosity and quickly turned into a learning experince. I wanted to know what percentage of integers have a prime number of distinct prime factors. In other words, 12's distinct prime factors are 2 and 3, there are 2 factors and 2 is a prime number so 12 counts. 16's only distinct prime factor is 2. 1 is not a prime number, so this would not count. I started by writing a program that would sequentially select an integer, find it's prime factors, then figure out if the number of prime factors was itself prime. To speed up the process, I rewrote it to test multiple integers concurrently. To speed it up even more, I rewrote it to use the Metal framework that would allow me to use the GPU for these calculations.

Full Text:

This project has 4 files. main.swift contains the main logic which is broken up into 3 steps. It starts by calculating all the prime numbers between 2 and the max variable. To do this, it generates a list of every integer between 2 and the max divided by 2 (because a factor of N cannot be larger than half of N). It goes through each of those numbers and decides if it's prime by sending them to the GPU. When it's done with that, it factors all the integers between 1 and the max by sending the integer and the prime to the GPU. Lastly, main.swift takes the array of factors that the GPU calculated and figures out if there is a prime number of factors.

The MetalPrimes.swift file prepares the data that is passed to it from main.swift to be processed by the GPU. It must prepare 3 buffers that are stored in memory that is shared between the CPU and GPU. It then interacts with the Metal framework to dispatch the threads to the GPU.

The MetalFactors.swift file is similar to the MetalPrimes.swift file. It has 4 buffers that are shared with the GPU then it interacts with the Metal framework to perform those calculations.

Finally, the FindFactor.metal file is the logic that the GPU should perform. The isPrime function accepts the three buffers that we give it in MetalPrimes and an id that tells us which integer we are testing because the inVector should just be a list of all integers between 1 and the max. The logic is reletively simple, if an integer is divisible by any divisor that is not 1 or itself, it's position in the outVector is marked as 0, otherwise it is prime. This logic would be slow if done in sequence on a CPU, but since the GPU can perform these calculations on each of the items in the buffer at roughly the same time, it is actually reletively efficient. The primeFactors function goes through each number in the divideby buffer and tests whether it divides the integer in the N buffer. If it is, it trys to divide again then starts over with n getting smaller and smaller. The iter buffer captures how many times this happens, giving us the number of distinct prime factors.

This project was really fun because I got to experiment with the Metal framework. It could definitely used some commenting and I'm not entirely sure if the logic is sound, but it was fun to make my laptop's fans spin up.