Mathematical Proof of Cosine Identity (cosine) Theorem

21
Nov/110

Last summer I was randomly surfing on internet at home and saw cosine theory on wiki and wanted to proof the identities by myself. However, despite having a good trigonimetry and geometry background, I couldn’t remember the proof. Honestly I got a bit sad as I realized that it is being more than ten years since high school. I searched for its proof and I found a nice geometric proof. This time I got angry as I wasn’t able to find this geometric proof. It was time to get my hands dirty.

Here is a perpendicular triangle.

Mathematical proof of cosinus idendity cosinus theoremMathematical proof of cosinus idendity theorem – step 1 putting the known parts together

Step-1
Let’s say A is divided by a line segment
|AD| = t,
then |AB| = t*cos(A), BD = t*sin(A)

Now let’s draw a hight from D to |AC| named H so we have similarity between the big triangle and the small one; (ABC) ~ (DHC)
|HD| = t * sin(B),
|DC| = t * sin(B) / cos(A+B),
|HC| = t * sin(B) * sin(A+B) / cos(A+B)
|HA| = t * cos(B)

Mathematical proof of cosinus idendity cosinus theorem

Mathematical proof of cosinus idendity theorem - step 2

Step-2
Looking at the big triangle (ABC), its hypotenus is equal to |AH| + |HC| which also is also equal to |AB| / cos(A+B)

Mathematical proof of cosinus idendity cosinus theorem

Mathematical proof of cosinus idendity theorem - step 3

Step-3
Multiply both sides with cos(A+B), get rid of t and organize the equation

Mathematical proof of cosinus idendity cosinus theorem

Mathematical proof of cosinus idendity theorem - step 4

Mathematical proof of cosinus idendity cosinus theorem

Mathematical proof of cosinus idendity theorem - step 5

Mathematical proof of cosinus idendity cosinus theorem

Mathematical proof of cosinus idendity theorem - step 6

Mathematical proof of cosinus idendity cosinus theorem

Mathematical proof of cosinus idendity theorem - step 7

Mathematical proof of cosinus idendity cosinus theorem

Mathematical proof of cosinus idendity cosinus theorem - step 8

step-4, 5, 6, 7, 8
Organizing the equation

Mathematical proof of cosinus idendity cosinus theorem

Mathematical proof of cosinus idendity cosinus theorem - step 9

step-9
Here we come the the most interesting part, which we have a parabolic equation which means we are close to the solution

Mathematical proof of cosinus idendity cosinus theorem

Mathematical proof of cosinus idendity cosinus theorem - step 10

Mathematical proof of cosinus idendity cosinus theorem

Mathematical proof of cosinus idendity cosinus theorem - step 11

Steps 10,11
are the discriminant solution for the parabolic equation

Mathematical proof of cosinus idendity cosinus theorem

Mathematical proof of cosinus idendity cosinus theorem - step 12

Step 12 is the simplification of inside the root

Mathematical proof of cosinus idendity cosinus theorem

Mathematical proof of cosinus idendity cosinus theorem - step 13

And finaly step 13,
cos(A+B) = cos(A)*cos(B) + sin(A)*sin(B)

Tagged as: , , , , , , ,
No Comments

Hacking Captcha with non-artificial intelligence

15
Nov/110

Nowadays I am looking through twitter api (twitter4j) and trying to learn twitter services as I want to find out how many times status containing the words ’steve jobs died’ or ‘want buy mazda 3′ tweeted. As you just noticed using tweets as a source of information, it is possible to find out which car is popular nowadays… examples can be extended far different points …

however as the company i am working is restricting access to twitter, I couldn’t use twitter api. but hold on I can also do that by using google searches. if you type site:twitter.com inurl:”/status” steve jobs died in the google search box you will get lots of tweets apprising death of steve jobs to people. What’s more is if you have a programming background you can get search result in you program to analyse. By doing that, for instance, you may find out peoples’ impression; if they are happy or unhappy… I know it was a silly example but you can deal with it :)

At this point another problem emerges. After a few sequence of requests, google get suspicious if you are a robot and asks you a captch question. for those who doesn’t know captch may just skip reading this post :P or check wiki.

Ok now we know that captcha is a common problem for robots trying to hack web sites or collecting data but how to deal with it? up to now many methods has emerged mostly using artificial intelligence (specifically anns) but I have another idea (well I have no idea if people has already tought or are presently using), solving this problem not with ai but with non-artificial intelligences called human beings :) . why don’t we ask captchas to other people and give rewards to those answering correctly? Assume we have an online game and if a user answers a captch correctly, give him/her additional chips/resources or whatever.

Here is the diagram of the entities represented with capical letter prefixes and actions represented with number prefixes.

hacking captch

hacking captch

At the first step our robot sends a search request to google, google either sends the result or asks for a captcha. if it is a captcha our robot sends the request to our web site and asks to real users. if any of the users answers, our site sends the request to the robot back and redirects it to the google with the answer. if the answer is true, system gives a present to the user.

that’s all for now. if you have any questions or ideas please don’t hesitate to give me feedbacks and at least leave a comment.

Tagged as: , , ,
No Comments

Simulated Annealing

19
Oct/110

Definition:Simulated Annealing (SA) is a random search technique which exploits an analogy between the way in which metal cools and freezes into a minimum energy crystalline (Busetti, F.)
I am too lazy to get into details but you can check presentations if you want to have more information!
Simulated annealing presentation in pdf format
Simulated annealing presentation in pptx (office 2010) format

Download Simulated Annealing Java Library including source codes

I also created a java library which you can use as you want. Library compounds of two interfaces and one concrete class.

Interfaces;
AnnealingScheduler provides information about the cooling schedule and termination conditions depending on the temperature
SimulatedAnnealingProblem represents the actual problem interface. You can easily integrate your problem using  SimulatedAnnealingProblem interface

Classes;
SimulatedAnnealingProblemSolver is class which solves a given  SimulatedAnnealingProblem using a given  AnnealingScheduler.

Here is an example:
Lets try to solve Travelling Salesman Problem using our library

After downloading the simulated annealing library first lets create POJOS which will be used in problem class

  1.  
  2. public class City {
  3.  
  4.         private String name;
  5.         private Point point;
  6.  
  7.         public City() {
  8.         }
  9.  
  10.         public City(String name, int latitude, int longitude) {
  11.             this.name = name;
  12.             point = new Point((int) latitude, (int) longitude);
  13.         }
  14.  
  15.         public String getName() {
  16.             return name;
  17.         }
  18.  
  19.         public void setName(String name) {
  20.             this.name = name;
  21.         }
  22.  
  23.         public Point getPoint() {
  24.             return point;
  25.         }
  26.  
  27.         public void setPoint(Point point) {
  28.             this.point = point;
  29.         }
  30.  
  31.         public double getDistace(City c) {
  32.             return point.distance(c.getPoint());
  33.         }
  34.  
  35. }
  36.  

Now lets create the State class. Our library is not dependent to any state classes however as the Simulated Annealing is Markov Chain type of method, having the state class makes more sense. State has two elements; cost and cityList. cost is the sum of the distances starting from the first city towards the last city in the cityList. cityList is in order as the cost depends on it.

  1.  
  2. public class State {
  3.     private List<City> cityList;
  4.     private double cost;
  5.  
  6.     public State(List<City> cityList) {
  7.         setCityList(cityList);
  8.     }
  9.  
  10.     public State(State state) {
  11.         setCityList(new ArrayList<City>(state.getCityList()));
  12.     }
  13.  
  14.     public State() {
  15.         setCityList(new ArrayList<City>());
  16.     }
  17.  
  18.     public List<City> getCityList() {
  19.         return cityList;
  20.     }
  21.  
  22.     public void setCityList(List<City> cityList) {
  23.         this.cityList = cityList;
  24.         calculateCost();
  25.     }
  26.  
  27.     public double getCost() {
  28.         return cost;
  29.     }
  30.  
  31.     public double calculateCost() {
  32.         double sum = 0;
  33.         int numOfCities = cityList.size();
  34.         for (int i = 0; i < numOfCities; i++) {
  35.             sum += cityList.get(i).getDistace(cityList.get((i + 1) % numOfCities));
  36.         }
  37.         cost = sum;
  38.         return sum;
  39.     }
  40. }
  41.  

Here is the class impelements SimulatedAnnealingProblem from our library. There are two important functions createNextState and goToNextState. in create next state, it creates a new state from the current state but swaps two cities locations.

  1.  
  2. public class TravelingSalesmanProblem implements SimulatedAnnealingProblem {
  3.  
  4.     Random random = new Random();
  5.     State currentState;
  6.     State nextState;
  7.  
  8.     final static int numOfCities = 30;
  9.  
  10.     @Override
  11.     public void init() {
  12.         currentState = new State();
  13.  
  14.         for (int i = 0; i < numOfCities; i++) {
  15.             City c = new City("c"+i+"", random.nextInt(750),random.nextInt(550));
  16.             currentState.getCityList().add(c);
  17.         }
  18.         currentState.calculateCost();
  19.     }
  20.  
  21.  
  22.     @Override
  23.     public double getCostForCurrentState() {
  24.         return currentState.getCost();
  25.     }
  26.  
  27.     /**
  28.      * creates a new state and randomly swaps 2 cities in it
  29.      */
  30.     @Override
  31.     public void createNextState() {
  32.         nextState = new State(currentState);
  33.         int i1 = random.nextInt(numOfCities);
  34.         int i2 = random.nextInt(numOfCities);
  35.         while (i1 == i2) {
  36.             i2 = random.nextInt(numOfCities);
  37.         }
  38.  
  39.         // randomly swap 2 cities
  40.         City tmp = nextState.getCityList().get(i1);
  41.         nextState.getCityList().set(i1, nextState.getCityList().get(i2));
  42.         nextState.getCityList().set(i2, tmp);
  43.         nextState.calculateCost();
  44.     }
  45.  
  46.     @Override
  47.     public double getCostForNextState() {
  48.         return nextState.getCost();
  49.     }
  50.  
  51.     @Override
  52.     public void goToNextState() {
  53.         currentState = nextState;
  54.         nextState = null;
  55.     }
  56.  
  57.     @Override
  58.     public boolean isTotalNumberOfStatesReached() {
  59.         return false;  //To change body of implemented methods use File | Settings | File Templates.
  60.     }
  61.  
  62.     @Override
  63.     public String getSolutionString() {
  64.         StringBuffer result = new StringBuffer();
  65.         for (City c : currentState.getCityList()) {
  66.             result.append(c.getName());
  67.             if (c != currentState.getCityList().get(numOfCities – 1)) {
  68.                 result.append(" -> ");
  69.             }
  70.         }
  71.         return result.toString();
  72.     }
  73.  
  74.  
  75.     @Override
  76.     public State getCurrentState() {
  77.         return currentState;
  78.     }
  79. }
  80.  

and finally the main

  1.  
  2. public class Main {
  3.    
  4.  
  5.     public static void main(String[] args) {
  6.  
  7.         TravelingSalesmanProblem tsp = new TravelingSalesmanProblem();
  8.         AnnealingScheduler as = new DefaultSAScheduler();
  9.  
  10.         SimulatedAnnealingProblemSolver problemSolver = new SimulatedAnnealingProblemSolver(as, tsp);
  11.         problemSolver.solve();
  12.  
  13.         System.out.println(tsp.getSolutionString());
  14.         System.out.println(tsp.getCostForCurrentState());
  15.     }
  16. }
  17.  

For fine tuning you can use setters in AnnealingScheduler class.

Outcome should be something like :
c13 -> c6 -> c11 -> c4 -> c9 -> c17 -> c16 -> c22 -> c15 -> c1 -> c8 -> c10 -> c20 -> c0 -> c28 -> c12 -> c27 -> c24 -> c5 -> c2 -> c14 -> c7 -> c3 -> c21 -> c18 -> c25 -> c29 -> c19 -> c23 -> c26
3164.855706704416

Download Simulated Annealing Java Library including source codes

Tagged as: , ,
No Comments

Setting up svn server on Ubuntu 11.04, VPS

21
Sep/111

Hi again after a long long long time I decided to send a new post! surprise surprise…

recently i again started playing with vps an needed to install svn server. as my clumsy friend huseyin massed up with permissions i wanted this post to stay in my blog so he can open and remember how to install svn server whenever he wants! (as far as he is online :) )

first of all it should be noted that ubuntu is installed on a VPS and I connect it via a ssh client as ‘root’, but still I’ll use sudo for the sake of the post. My name is UMUT so I will create UMUT for the username and HUSEYIN for my clumsy friens, besides I will create the repository in /home/svn and only users with permissions can access to the repo.

here are the shell commands:

sudo apt-get update
sudo apt-get install nano apache2 subversion libapache2-svn

  • at this point it may ask you if you really want to install the packages, asnwer yes by pressing ‘Y’

htpasswd -cm /etc/apache2/dav_svn.passwd UMUT

  • we created the file, it will ask you the password here, type the password

htpasswd -m /etc/apache2/dav_svn.passwd HUSEYIN

  • as the file is created we dont put -cm but -c instead, it will ask for the pass of HUSEYIN, again type the pass,

nano /etc/apache2/dav_svn.authz

  • copy and past the following 2 lines in order to give the read/write permission to everyone logged in the svn, and then ctrl+o to save and ctrl+x to exit

[/]

* = rw

svnadmin create /home/svn

nano /etc/apache2/mods-enabled/dav_svn.conf

  • a long file will show up, we need to uncomment (delete # ’s) the following lines

<Location /svn>

DAV svn

SVNPath /home/svn

AuthType Basic

AuthName “Subversion Repository”

AuthUserFile /etc/apache2/dav_svn.passwd

AuthzSVNAccessFile  /etc/apache2/dav_svn.authz

Require valid-user

#  SVNAutoversioning on

#  Satisfy Any

</Location>

cd /home/svn

mkdir dav

chmod -R 770 ./*

chown -R www-data:www-data ./*

/etc/init.d/apache2 restart

keep in mind that you need to enter http://ip_or_site_name/svn as we defined in/etc/apache2/mods-enabled/dav_svn.conf

that’s all hope it works

ref: http://blog.ortimo.com/svn-serveron-ubuntu-11-04/257/

Filed under: Ubuntu, svn
1 Comment

A tiny ray tracer project…

6
May/100


You can download the .zip file including the sourcecode and executable file for windows.

Project page :
http://code.google.com/p/tinyraytracer/



Here is one of the latest personal project I’ve been workin on… Actually I spent about 3 days to finish it up.

It is objective is to create a customizable ray tracer using as much processing power as possible. For now it is multithtreaded but uses only the CPUs, not GPUs.

you can customize the ray tracer parameters from Main.cpp file (hardcoded for now)

  1.  
  2. #define SCREEN_WIDTH    800
  3. #define SCREEN_HEIGHT   600
  4. #define AMBIENT_COLOUR  COLOUR_BLACK
  5. #define NUM_OF_MAX_REFLECTIONS  8
  6. #define SQRT_OF_RAYS_PER_PIXEL  1
  7. #define NUM_OF_THREADS_PER_CPU  1
  8. #define NUM_OF_PIXELS_TO_BE_RENDERED_BY_A_THREAD_AT_A_TIME      100
  9.  

here is the objective which you can also find at http://code.google.com/p/tinyraytracer/

a primitive ray tracer which for the beginning renders only spheres no texturing only reflection only point light sources static super sampling (but hard shadows) multithreaded static scene

in the future renders triangles 2d texturing might be kd-tree (not sure of it) reflection and refraction point and plane light sources dynamic super sampling CUDA or OpenCL dynamic scene (moving objects and camera)

Tagged as: , ,
No Comments

Setting Up a Home Server with Ubuntu 9.10

16
Apr/100

It’s being a long time since my last post in my blog but this time I wanted to come across with something different which I think might be quite useful for whom wants to assess their old PCs or laptops.

If ten years ago someone had told me that one day I will have three computers at home in my service, I only would have laughed. But today it is real :) I actually have 2 laptops (one is my mother’s which would have made me laugh even more) and one desktop.

The desktop is an AMD athlon 2500 1GB RAM and NVidia 6600GT, one of the laptops is a 512MB RAM (384MB after sharing ) intel 1.6 GHz and other laptop is a intel dualcore 1.8GHz with 2GB RAM. After buying my laptop I gave up using my PC for more than one year. It was resting in peace :)

Recently I decided to assess it and wanted to set it up as a server for downloading stuff and for experimental uses. However in my first try I couldn’t manage to install Ubuntu 9.10 as I was using my two 120GB disks with Raid0. Unfortunately Ubuntu 9.10 (yes it is the desktop version not the server one) having some problems with Raid 0 on my hardware. I removed the strip and also one of the hdds, started installation… Booom!!! my cdrom wasn’t working properly. There was only one way; to install Ubuntu via a usb drive.

Typing ‘install ubuntu from usb’ on google, I found https://help.ubuntu.com/community/Installation/FromUSBStick and https://help.ubuntu.com/community/USB%20Installation%20Media . Using UNBootin (http://unetbootin.sourceforge.net/) as advised and setting the usb drive as the boot media from my pc’s setup, installation started at last! It should be noted that if the usb drive is an external harddrive then UNbootin doesn’t seem to work, instead use an usb pendrive. Installing ubuntu from a pendrive works pretty fast and flawles.

Anyway

TO BE CONTINUED…

Tagged as: , , , , , ,
No Comments

Speed Test: std::Vector vs Array

12
Mar/100

Most recently I have been working on a multithreaded ray tracer in order to port it to CUDA so I am not using any recursion. The first step is implementing the ray tracer without using any acceleration structure. So I simply test a ray with all the objects in a scene thus I needed to decide using whether an array or a vector.
As the current code strongly relies on the data structure I am using, I wanted to test the iteration speed of std::vector versus array.

Here is the code I used for testing.

  1.  
  2. #include <iostream>
  3. #include <map>
  4. #include <vector>
  5. #include <array>
  6. #include <stack>
  7. #include <windows.h>
  8. #include <math.h>
  9. typedef DWORD TIME_TYPE;
  10.  
  11.  
  12. #define BEGIN_TIMING(repeat)     TIME_TYPE dwStartTime = timeGetTime();         for(int __i = 0; __i < repeat; __i++){
  13. #define END_TIMING              }; TIME_TYPE __ret = (timeGetTime() – dwStartTime); cout<< __FUNCTION__ << "\t\t: elapsed time =\t"<<__ret<<endl; return __ret;;
  14.  
  15.  
  16. const unsigned int g_uiStartTestSize    = 1000000;
  17. const unsigned int g_uiStartRepeatCount = 1;
  18.  
  19. unsigned int g_uiTestSize       = 0;
  20. unsigned int g_uiRepeatCount = 0;
  21. unsigned int g_uiNumOfTestSteps = 10;
  22. using namespace std;
  23. using std::map;
  24. using std::vector;
  25.  
  26. class ClassA
  27. {
  28. public:
  29.         ClassA(){a=b=c=d=0;};
  30.         ~ClassA(){};
  31.         double a;
  32.         double b;
  33.         double c;
  34.         double d;
  35. };
  36.  
  37.  
  38.  
  39. vector<ClassA*>* classAVector;
  40. ClassA** classAArray;
  41.  
  42. TIME_TYPE testFillInArray()
  43. {
  44.         BEGIN_TIMING(1)
  45.                 classAArray = new ClassA*[g_uiTestSize];
  46.                 for(int i =0; i < g_uiTestSize; i++)
  47.                 {
  48.                         classAArray[i] = new ClassA();
  49.                 }
  50.         END_TIMING
  51. }
  52.  
  53. TIME_TYPE testFillInVector()
  54. {
  55.         BEGIN_TIMING(1)
  56.                 classAVector = new vector<ClassA*>();
  57.                 for(int i =0; i < g_uiTestSize; i++)
  58.                 {
  59.                         classAVector->push_back(new ClassA());
  60.                 }
  61.         END_TIMING
  62. }
  63.  
  64. TIME_TYPE testDestroyArray()
  65. {
  66.         BEGIN_TIMING(1)
  67.                 for (int i = 0; i < g_uiTestSize; i++)
  68.                 {
  69.                         delete classAArray[i];
  70.                 }
  71.                 delete [] classAArray;
  72.         END_TIMING
  73. }
  74.  
  75. TIME_TYPE testDestroyVector()
  76. {
  77.         BEGIN_TIMING(1)
  78.                 for  (int i = 0; i < g_uiTestSize; i++)
  79.                 {
  80.                         delete (*classAVector)[i];
  81.                 }
  82.                 delete classAVector;
  83.  
  84.         END_TIMING
  85. }
  86.  
  87. TIME_TYPE testIterateVector(void)
  88. {
  89.         BEGIN_TIMING(g_uiRepeatCount)
  90.         ClassA *pClassA;
  91.  
  92. /*
  93.         const int sz = classAVector->size();
  94.         for (int i = 0; i < sz; i++)
  95.         {
  96.                 pClassA = (*classAVector)[i];          
  97.                 pClassA->a++;
  98.                 pClassA->b++;
  99.                 pClassA->c++;
  100.                 pClassA->d++;
  101.         }*/
  102.  
  103.  
  104.  
  105.         vector<ClassA*>::iterator it = classAVector->begin();
  106.                 const vector<ClassA*>::iterator endIt = classAVector->end();
  107.                 while(it != endIt)
  108.                 {
  109.                         pClassA = (*it);
  110.                         pClassA->a++;
  111.                         pClassA->b++;
  112.                         pClassA->c++;
  113.                         pClassA->d++;
  114.                         it++;
  115.                 }
  116.  
  117.         END_TIMING
  118. }
  119.  
  120. TIME_TYPE testIterateArray(void)
  121. {
  122.         BEGIN_TIMING(g_uiRepeatCount)
  123.         ClassA *pClassA;
  124.         for (int i =0; i < g_uiTestSize; i++)
  125.         {
  126.                 pClassA = classAArray[i];
  127.                 pClassA->a++;
  128.                 pClassA->b++;
  129.                 pClassA->c++;
  130.                 pClassA->d++;
  131.  
  132.         }
  133.         END_TIMING
  134. }
  135.  
  136. void verify()
  137. {
  138.         cout<<"verifying"<<endl;
  139.         for (int i=0; i < g_uiTestSize; i++)
  140.         {
  141.                 if( (*classAArray[i]).a != classAVector->at(i)->a )
  142.                 {
  143.                         cout << "error!:" << i <<endl;
  144.                 }
  145.         }
  146. }
  147.  
  148. TIME_TYPE testAll()
  149. {
  150.         BEGIN_TIMING(1)
  151.                 g_uiTestSize = g_uiStartTestSize;
  152.                 for (int i =1; i <= g_uiNumOfTestSteps; i++)
  153.                 {
  154.                         g_uiRepeatCount = g_uiStartRepeatCount * i;
  155.                         cout<< "repeat count =\t\t"<<g_uiRepeatCount<<endl;
  156.                         cout<< "test size    =\t\t"<<g_uiTestSize<<endl;
  157.                         testFillInArray();
  158.                         testFillInVector();
  159.                         testIterateArray();
  160.                         testIterateVector();
  161.                         testDestroyArray();
  162.                         testDestroyVector();
  163.                         cout<<"———————————————"<<endl;
  164.                 }
  165.                 g_uiRepeatCount = g_uiStartRepeatCount;
  166.                 for (int i =1; i <= g_uiNumOfTestSteps; i++)
  167.                 {
  168.                         g_uiTestSize = g_uiStartTestSize * i;
  169.                         cout<< "repeat count =\t"<<g_uiRepeatCount<<endl;
  170.                         cout<< "test size    =\t"<<g_uiTestSize<<endl;
  171.                         testFillInArray();
  172.                         testFillInVector();
  173.                         testIterateArray();
  174.                         testIterateVector();
  175.                         testDestroyArray();
  176.                         testDestroyVector();
  177.                         cout<<"———————————————"<<endl;
  178.                 }
  179.  
  180.         END_TIMING
  181.  
  182. }
  183.  
  184.  
  185.  
  186.  
  187. int main(void)
  188. {
  189.         testAll();
  190.         return 0;
  191. }
  192.  
  193.  

Here is the code to download

Results
Results are striking indeed. If you compiling the code in Release mode without any run-time error checking and disabled exection support iterating a Vector by using std::vector<>::iterator is almost as fast as using array.

However testing them on debug mode shows the difference, iteration time is terribly slow on std::vector ; about 60 times slower.

Conclusion
std::vector is almost as fast as using a static array on release mode (using Visual Studio 2008) but terribly slow on debug mode. So if your code is running slow on the debug mode, don’t give up std::vector and give a go on the release mode.

Tagged as:
No Comments

finding prime numbers in a range using python

15
Dec/090

the dictionary definition of prime numbers gives us a clear idea about prime number finding algorithm; ‘–noun Mathematics.
a positive integer that is not divisible without remainder by any integer except itself and 1, with 1 often excluded: The integers 2, 3, 5, and 7 are prime numbers. ‘ according to http://dictionary.reference.com/browse/prime+number.

hence the most primitive algorithm is dividing the number by all the positive numbers between 2 and the number-1 and waiting for non-zero reminders from all.

however it is not really the most practical way.

first of all it is obvious that any numbers except for 2 cannot be divided without reminder by its decrement. this way of thinking leads us to question the range of the numbers to be used as divider. logically the limit should be between 2 and square root of the number. the explanation is simple; lets assume that the number is not prime and we divide it with a number bigger than its square root, in that case the result will be a number between 2 and the number’s square root, which we should have already tested (since we start the division test in order starting from two).
secondly the test should be done only with prime numbers, not all. the reason is quite simple, if X divides Y then all the multipliers of X also divides Y. think about dividing 600 by 30; 600 can also be divided by 2, 3 and 5 which are the multipliers of 30.

lastly there is no point of testing even numbers as they already can be divided by 2. by doing that, for finding prime number in a range, we also prevent the division by 2 tests.

here is the python code for finding prime numbers in the range of 2 to 1′000′000, takes aroun 5.4 seconds on my laptop.

  1. from math import sqrt
  2. import time
  3. t1 = time.time()
  4. primenumbers=[2,3,5]
  5.  
  6. for i in range(7,1000000,2):
  7.         sq = sqrt(i)+1
  8.         for j in primenumbers:
  9.                 if sq < j:
  10.                         primenumbers.append(i)
  11.                         #print i, len(primenumbers)
  12.                         break
  13.  
  14.                 if i % j == 0:
  15.                         break
  16.  
  17. print len(primenumbers)
  18. t2 = time.time()
  19. print (t2 – t1)
Tagged as: , ,
No Comments

Game Balyoz

10
Dec/090

svn checkout http://balyoz.googlecode.com/svn/trunk/ balyoz-read-only

http://code.google.com/p/balyoz/


Balyoz is a 3D shooter game having been written using OGRE engine.The aim is to provide a interesting
and enjoyable game play experience for the player and still in development.In order to achieve this purpose,
we have been using PyhsicX physic engine to provide a more realistic and unique game experience.Although
Balyoz is a classic 3D shooting game,it has also some different features then classic shooting games
offer and full of challenge even its underlying structure.The war plane will be flying over a terrain and be
capable of moving both X and Z direction.Besides, there will be different weapon options which makes
the game play more enjoyable.In Balyoz, other then enemy air units, there will be navy and ground units
which will be shooting to out plane as well.To destroy ground units, player have to use bombs with
the correct timing and position combination.I would like to give some information about the underlying
structure of the Balyoz game.

1.XML Based Definition

In order to achieve flexibility, unit definitions, weapons, levels, maps etc.. are defined XML files.
They are loaded either on game initialization stage or level lodging stage.It provides us a great
flexibility to alter the attributes, for example weapon attributes like speed, range or controller
type, or level attributes like the unit types in level and their positions, without changing even
one line code.It also prevents us to recompile the code for each time we change a attribute.
Let us have a look a example xml used in game.
<?xml version="1.0" ?>
<weapons>
<weapon>
<name>bazooka</name>
<mesh>cube.mesh</mesh>
<reloadtime>500</reloadtime>
<numofbullets>
<capacity>1000</capacity>
<initial>1</initial>
<maximum>9</maximum>
<minimum>1</minimum>
<anglebetweenbullets>18</anglebetweenbullets>
</numofbullets>
<bullet>
<initialspeed>10</initialspeed>
<maximumspeed>-100</maximumspeed>
<power>100</power>
<radius>10</radius>
<effect>linear</effect>
<lifetime>4.5</lifetime>
<particles>Examples/Smoke</particles>
<explosion>explosion</explosion>
<controller>dummy</controller>
</bullet>
</weapon>
</weapons>
XML structure in terms of game is shown below,
Game.xml
|
Levels.xml ____
|                             |
Map.xml Terrain.xml
|
Units.xml
|
Weapons.xml
|
BulletController.xml
So,if it is needed to load a unit into the game, first units.xml file will be read and unit attribute
will be figured out from units.xml file.Then, weapon names related to that unit will be read from
units.xml file and with that reference, weapon attributes will be taken from weapon.xml file.
After that, the information about by which weapon controller it will be controlled will be read
from BulletController.xml file since for example guided missiles should be controlled in a
different way.As you can see, even controller types are defined in xml files and for sure, this
system provides a great flexibility when we want to add a new weapon to a unit, or a new
unit to a level.It is one of the most powerful feature of Balyoz in terms of design.

2.Controller Design

As a design decision, a main controller is implemented which is responsible to process
and update all the game events. Main game controller process the events via a event
queue it contains. Besides, there are some sub-controllers like Unit Controller or
Collision Controller which are responsible for creating related game events and adding
the main controller`s queue.So, before each frame is rendered, first all the controllers
are executed, produced related event and added to main controller`s event queue. Then
before rendering the frame (or after) this queue is processed by main controller and game
word is updated. Separating controlling behaviors to different controllers is also provides a
flexibility to implement control behavior and maintaining the code.Moreover, game core
talks to just main controller and does not need to know about sub-controllers.These design
decisions are shown by images below,
controllers-sequence
controllers-class
Balyoz is still in its early stage of development.I will be adding news about the progress of game.Beside, screenshots and videos will be added soon as well.
al
ates
Tagged as: , , ,
No Comments

Ray Tracing on Cell by Using KD-Tree Acceleration Structure – PDF

30
Nov/090

It’s being a long time since promising to publish my dissertation thesis with the title of Ray Tracing on Cell by Using KD-Tree Acceleration Structure

At last I found it and decided to publish! Unfortunately html version is a bit crappy and it’s a pain in the neck to make it tidy and nice. You can also check the PDF version of my MSc thesis out.

Tagged as: , , , , , , , , , , ,
No Comments
Older Entries »

Pages

Categories

My Own Sites

Other sites you may interested

Calendar

February 2012
M T W T F S S
« Nov    
 12345
6789101112
13141516171819
20212223242526
272829  

Most Popular Tags

action game AI artificial intelligence Artificial intelligence in real-time strategy games BVH tree c++ cell processor cmath computer graphics cuda decision making direct input direct sound directX Distributed Neural Networks fast math fast sine function fast sin function fast sinus function fuzzy logic game game programming google Group Work interview KD tree long term decision making in strategy games master thesis MSc Dissertation MSc Project neural networks NVidia Ogre3D optimisation particle system play station 3 pooling ps3 python questions raytracing ray tracing ray tracing on cell real time ray tracing RTS Games shooting game short term decision making in strategy games Smart Attack University of Abertay Dundee using xml in games