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 ===
Please note the preliminary check for division by 2, 3, 5, 7 and 11. By checking these common primes first, we could eliminate most possibilities without even entering a loop. It is very insignificant, but helps in most cases.
<pre>
__global__ void findPrimes(int* answer, int n)
{
int i = threadIdx.x;
int j = blockIdx.x * blockDim.x + threadIdx.x;
__shared__ int blockSum[ntpb];
int check = j+1;
if((check % 2 ==0 && check != Assignment 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 }
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>
150 / 150 = 1
This created a speedup of roughly 2x, as compared to A2.
Compared to A1, the results were more than 125,000x for n=1000.
This means that the simple algorithm improvements made appear to be the only optimizations possible.
[[Image:Gtsmyth a3.png|widthpx| ]]
[[Image:Gtsmyth a3 2.png|widthpx| ]]
Going from A1 to A2, our code experienced a speed-up of 6,015,300% (or 60,154x faster (literally - A1 was <u>'''''that'''''</u> inefficient)).
<pre>__global__ void findPrimes(int* answer, int n)
{
int i = threadIdx.x;
int j = blockIdx.x * blockDim.x + threadIdx.x;
__shared__ int blockSum[ntpb];
int len check = strTarget.lengthj+1; blockSum[i] = 0; __syncthreads(); if(check >= 2 && check <= n) { bool flag = true; //Assume prime for(int x = 2; 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(strTarget) << endl;
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>
----