1
edit
Changes
→Assignment 3
{{GPU610/DPS915 Index | 20131}}
[[Image:teamname.png|right|frameless|widthpx| ]]
= Project Name TBA Optimus Prime = The following page outlines the three-step progression through a program that counts the number of primes between 1 and N.
== Team Members ==
# [mailto:gtsmyth@learn.senecac.on.ca?subject=gpu610 Graeme Smyth], Some responsibility primary coder# [mailto:rhotin@learn.senecac.on.ca?subject=gpu610 Roman Hotin], Some other responsibility primary coder
[mailto:gtsmyth@learn.senecac.on.ca,rhotin@learn.senecac.on.ca?subject=dps901-gpu610 Email All]
== Progress ==
=== Assignment 3 ===
int check === Assignment 2 ===We chose to work on the program that finds out how many primes are between j+1 and N.;
if(check >= 2 && check <= n)
{
bool flag = true; //Assume prime
if((check % 2 == 0 && check != 2) ||
(check % 3 == 0 && check != 3) ||
(check % 5 == 0 && check != 5) ||
(check % 7 == 0 && check != 7) ||
(check % 11 == 0 && check != 11)) //If divisible by x
flag = false; //Found to not be prime
for(int x = 2; x < check/2 && flag; x++) //Check all numbers 2 to "check"
if(check % x == 0) //If divisible by x
flag = false; //Found to not be prime
if(flag) //If prime
blockSum[i] = 1; //Add one to our numbers
}
if (i === Assignment 1 ===0) answer[blockIdx.x] ====blockSum[[User:Gtsmyth | Graeme Smyth0]]====;=====Topic=====}Making parallel an application which calculates the first n primes.</pre>
The biggest significance was in the numbers we checked. Note the "check/2" in our for loop, which wasn't divided by 2 in A2.
The lowest integer a division can produce that results in a prime is 2.
In other words, the highest number we need check 150 for is 75, as all numbers between 1 and 2 aren't integers, and being 1 (150/150) doesn't make it prime.
Higher values of n were not checked, due to the ridiculously long time A1 would take.
For comparison's sake, A2 and A3 were compared using the max value they could compute (maxThreads * maxBlocks, 512 * 512 = 262,144). Even at such high numbers, A3 is still 2x more efficient than A2.
Data for all assignments, with available graphs, is shown below.
=== Assignment 2 ===
A2 featured a significantly improved prime-counting algorithm, coupled with GPU integration.
Kernel code for A2:
<pre>__global__ void findPrimes(int* answer, int n)
{
int i = threadIdx.x;
int j = blockIdx.x * blockDim.x + threadIdx.x;
__shared__ int blockSum[ntpb];
if(check >= 2 && check <= n) { bool flag = true; //Assume prime for(int len x = strTarget.length2; x < check && flag; x++) //Check all numbers 2 to "check" if(check % x == 0) //If divisible by x flag = false; //Found to not be prime
for (int stride = blockDim.x >> 1; stride > 0; stride >>= 1)
{
if (i < stride)
blockSum[i] += blockSum[i + stride];
__syncthreads();
}
if (i == 0)
answer[blockIdx.x] = blockSum[0];
}</pre>
Sample output from A2, for demonstration:
[[Image:gtsmyth A2.png|widthpx| ]]
Demonstration of how efficient A2 runs for n = 1,000 (for comparison, A1 took 20.78 seconds).
bool isPrime(int x){ for(int a = 0; a < x; a++) //a is any integer [0,x) for(int b = 0; b < x; b++) //b is any integer [0,x) if (a * b > 254== x) { //If a * b = 254x, then x has two integers that multiply to form it, return false; } //hence x is not prime
//Main takes one argument, integer n, and calculates the first n primes.
int main(int argc, char* argv[])
{
time_t timeStart, timeEnd;
//Check argument count
if (argc != 2)
{
cerr << "**invalid number of arguments**" << endl;
return 1;
}
cout << setprecision(3);
cout << "Elapsed time : " << difftime(timeEnd, timeStart) << endl;
}
</pre>
====[[User:Rhotin | Roman Hotin]]====
=====Topic=====
encrypting text
----
<pre>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <string>
#include <cctype>
using namespace std;
void Encrypt(string&);
string Decrypt(string strTarget);
int main(int argc, char* argv[]) { //initialize and get the string from the user string strTarget; cout << "Enter a string to encrypt: "; //getline(cin,strTarget); strTarget = argv[1]; string temp(strTarget); Encrypt(strTarget); cout << "Encrypted: " << strTarget << endl; cout << "Decrypted: " << Decrypt(string strTarget)<< endl; return 0;}
void Encrypt(string &strTarget)
{
int len = strTarget.length();
char a;
string strFinal(strTarget);
for (int i = 0; i <= (len-1); i++)
{
a = strTarget.at(i);
int b = (int)a; //get the ASCII value of 'a'
b += 2; //Mulitply the ASCII value by 2
if (b > 254) { b = 254; }
a = (char)b; //Set the new ASCII value back into the char
strFinal.insert(i , 1, a); //Insert the new Character back into the string
}
string strEncrypted(strFinal, 0, len);
strTarget = strEncrypted;
}
string Decrypt(string strTarget)
{
int len = strTarget.length();
char a;
string strFinal(strTarget);
for (int i = 0; i <= (len-1); i++)
{
a = strTarget.at(i);
int b = (int)a;
b -= 2;
a = (char)b;
strFinal.insert(i, 1, a);
}
string strDecrypted(strFinal, 0, len);
return strDecrypted;
}
</pre>
----