Mathematical Proof of Cosine Identity (cosine) Theorem
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.
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)
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)
Step-3
Multiply both sides with cos(A+B), get rid of t and organize the equation
step-4, 5, 6, 7, 8
Organizing the equation
step-9
Here we come the the most interesting part, which we have a parabolic equation which means we are close to the solution
Steps 10,11
are the discriminant solution for the parabolic equation
Step 12 is the simplification of inside the root
And finaly step 13,
cos(A+B) = cos(A)*cos(B) + sin(A)*sin(B)
Hacking Captcha with non-artificial intelligence
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
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.
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.
Simulated Annealing
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
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.
-
-
public class State {
-
private List<City> cityList;
-
private double cost;
-
-
public State(List<City> cityList) {
-
setCityList(cityList);
-
}
-
-
public State(State state) {
-
setCityList(new ArrayList<City>(state.getCityList()));
-
}
-
-
public State() {
-
setCityList(new ArrayList<City>());
-
}
-
-
public List<City> getCityList() {
-
return cityList;
-
}
-
-
public void setCityList(List<City> cityList) {
-
this.cityList = cityList;
-
calculateCost();
-
}
-
-
public double getCost() {
-
return cost;
-
}
-
-
public double calculateCost() {
-
double sum = 0;
-
int numOfCities = cityList.size();
-
for (int i = 0; i < numOfCities; i++) {
-
sum += cityList.get(i).getDistace(cityList.get((i + 1) % numOfCities));
-
}
-
cost = sum;
-
return sum;
-
}
-
}
-
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.
-
-
public class TravelingSalesmanProblem implements SimulatedAnnealingProblem {
-
-
State currentState;
-
State nextState;
-
-
final static int numOfCities = 30;
-
-
@Override
-
public void init() {
-
currentState = new State();
-
-
for (int i = 0; i < numOfCities; i++) {
-
City c = new City("c"+i+"", random.nextInt(750),random.nextInt(550));
-
currentState.getCityList().add(c);
-
}
-
currentState.calculateCost();
-
}
-
-
-
@Override
-
public double getCostForCurrentState() {
-
return currentState.getCost();
-
}
-
-
/**
-
* creates a new state and randomly swaps 2 cities in it
-
*/
-
@Override
-
public void createNextState() {
-
nextState = new State(currentState);
-
int i1 = random.nextInt(numOfCities);
-
int i2 = random.nextInt(numOfCities);
-
while (i1 == i2) {
-
i2 = random.nextInt(numOfCities);
-
}
-
-
// randomly swap 2 cities
-
City tmp = nextState.getCityList().get(i1);
-
nextState.getCityList().set(i1, nextState.getCityList().get(i2));
-
nextState.getCityList().set(i2, tmp);
-
nextState.calculateCost();
-
}
-
-
@Override
-
public double getCostForNextState() {
-
return nextState.getCost();
-
}
-
-
@Override
-
public void goToNextState() {
-
currentState = nextState;
-
nextState = null;
-
}
-
-
@Override
-
public boolean isTotalNumberOfStatesReached() {
-
return false; //To change body of implemented methods use File | Settings | File Templates.
-
}
-
-
@Override
-
for (City c : currentState.getCityList()) {
-
result.append(c.getName());
-
if (c != currentState.getCityList().get(numOfCities – 1)) {
-
result.append(" -> ");
-
}
-
}
-
return result.toString();
-
}
-
-
-
@Override
-
public State getCurrentState() {
-
return currentState;
-
}
-
}
-
and finally the main
-
-
public class Main {
-
-
-
-
TravelingSalesmanProblem tsp = new TravelingSalesmanProblem();
-
AnnealingScheduler as = new DefaultSAScheduler();
-
-
SimulatedAnnealingProblemSolver problemSolver = new SimulatedAnnealingProblemSolver(as, tsp);
-
problemSolver.solve();
-
-
}
-
}
-
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
Setting up svn server on Ubuntu 11.04, VPS
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
A tiny ray tracer project…
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)
-
-
#define SCREEN_WIDTH 800
-
#define SCREEN_HEIGHT 600
-
#define AMBIENT_COLOUR COLOUR_BLACK
-
#define NUM_OF_MAX_REFLECTIONS 8
-
#define SQRT_OF_RAYS_PER_PIXEL 1
-
#define NUM_OF_THREADS_PER_CPU 1
-
#define NUM_OF_PIXELS_TO_BE_RENDERED_BY_A_THREAD_AT_A_TIME 100
-
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)
Setting Up a Home Server with Ubuntu 9.10
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…
Speed Test: std::Vector vs Array
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.
-
-
#include <iostream>
-
#include <map>
-
#include <vector>
-
#include <array>
-
#include <stack>
-
#include <windows.h>
-
#include <math.h>
-
typedef DWORD TIME_TYPE;
-
-
-
#define BEGIN_TIMING(repeat) TIME_TYPE dwStartTime = timeGetTime(); for(int __i = 0; __i < repeat; __i++){
-
#define END_TIMING }; TIME_TYPE __ret = (timeGetTime() – dwStartTime); cout<< __FUNCTION__ << "\t\t: elapsed time =\t"<<__ret<<endl; return __ret;;
-
-
-
const unsigned int g_uiStartTestSize = 1000000;
-
const unsigned int g_uiStartRepeatCount = 1;
-
-
unsigned int g_uiTestSize = 0;
-
unsigned int g_uiRepeatCount = 0;
-
unsigned int g_uiNumOfTestSteps = 10;
-
using namespace std;
-
using std::map;
-
using std::vector;
-
-
class ClassA
-
{
-
public:
-
ClassA(){a=b=c=d=0;};
-
~ClassA(){};
-
double a;
-
double b;
-
double c;
-
double d;
-
};
-
-
-
-
vector<ClassA*>* classAVector;
-
ClassA** classAArray;
-
-
TIME_TYPE testFillInArray()
-
{
-
BEGIN_TIMING(1)
-
classAArray = new ClassA*[g_uiTestSize];
-
for(int i =0; i < g_uiTestSize; i++)
-
{
-
classAArray[i] = new ClassA();
-
}
-
END_TIMING
-
}
-
-
TIME_TYPE testFillInVector()
-
{
-
BEGIN_TIMING(1)
-
classAVector = new vector<ClassA*>();
-
for(int i =0; i < g_uiTestSize; i++)
-
{
-
classAVector->push_back(new ClassA());
-
}
-
END_TIMING
-
}
-
-
TIME_TYPE testDestroyArray()
-
{
-
BEGIN_TIMING(1)
-
for (int i = 0; i < g_uiTestSize; i++)
-
{
-
delete classAArray[i];
-
}
-
delete [] classAArray;
-
END_TIMING
-
}
-
-
TIME_TYPE testDestroyVector()
-
{
-
BEGIN_TIMING(1)
-
for (int i = 0; i < g_uiTestSize; i++)
-
{
-
delete (*classAVector)[i];
-
}
-
delete classAVector;
-
-
END_TIMING
-
}
-
-
TIME_TYPE testIterateVector(void)
-
{
-
BEGIN_TIMING(g_uiRepeatCount)
-
ClassA *pClassA;
-
-
/*
-
const int sz = classAVector->size();
-
for (int i = 0; i < sz; i++)
-
{
-
pClassA = (*classAVector)[i];
-
pClassA->a++;
-
pClassA->b++;
-
pClassA->c++;
-
pClassA->d++;
-
}*/
-
-
-
-
vector<ClassA*>::iterator it = classAVector->begin();
-
const vector<ClassA*>::iterator endIt = classAVector->end();
-
while(it != endIt)
-
{
-
pClassA = (*it);
-
pClassA->a++;
-
pClassA->b++;
-
pClassA->c++;
-
pClassA->d++;
-
it++;
-
}
-
-
END_TIMING
-
}
-
-
TIME_TYPE testIterateArray(void)
-
{
-
BEGIN_TIMING(g_uiRepeatCount)
-
ClassA *pClassA;
-
for (int i =0; i < g_uiTestSize; i++)
-
{
-
pClassA = classAArray[i];
-
pClassA->a++;
-
pClassA->b++;
-
pClassA->c++;
-
pClassA->d++;
-
-
}
-
END_TIMING
-
}
-
-
void verify()
-
{
-
cout<<"verifying"<<endl;
-
for (int i=0; i < g_uiTestSize; i++)
-
{
-
if( (*classAArray[i]).a != classAVector->at(i)->a )
-
{
-
cout << "error!:" << i <<endl;
-
}
-
}
-
}
-
-
TIME_TYPE testAll()
-
{
-
BEGIN_TIMING(1)
-
g_uiTestSize = g_uiStartTestSize;
-
for (int i =1; i <= g_uiNumOfTestSteps; i++)
-
{
-
g_uiRepeatCount = g_uiStartRepeatCount * i;
-
cout<< "repeat count =\t\t"<<g_uiRepeatCount<<endl;
-
cout<< "test size =\t\t"<<g_uiTestSize<<endl;
-
testFillInArray();
-
testFillInVector();
-
testIterateArray();
-
testIterateVector();
-
testDestroyArray();
-
testDestroyVector();
-
cout<<"———————————————"<<endl;
-
}
-
g_uiRepeatCount = g_uiStartRepeatCount;
-
for (int i =1; i <= g_uiNumOfTestSteps; i++)
-
{
-
g_uiTestSize = g_uiStartTestSize * i;
-
cout<< "repeat count =\t"<<g_uiRepeatCount<<endl;
-
cout<< "test size =\t"<<g_uiTestSize<<endl;
-
testFillInArray();
-
testFillInVector();
-
testIterateArray();
-
testIterateVector();
-
testDestroyArray();
-
testDestroyVector();
-
cout<<"———————————————"<<endl;
-
}
-
-
END_TIMING
-
-
}
-
-
-
-
-
int main(void)
-
{
-
testAll();
-
return 0;
-
}
-
-
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.
finding prime numbers in a range using python
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.
-
from math import sqrt
-
import time
-
t1 = time.time()
-
primenumbers=[2,3,5]
-
-
for i in range(7,1000000,2):
-
sq = sqrt(i)+1
-
for j in primenumbers:
-
if sq < j:
-
primenumbers.append(i)
-
#print i, len(primenumbers)
-
break
-
-
if i % j == 0:
-
break
-
-
print len(primenumbers)
-
t2 = time.time()
-
print (t2 – t1)
Game Balyoz
Dec/090
svn checkout http://balyoz.googlecode.com/svn/trunk/ balyoz-read-only
http://code.google.com/p/balyoz/
1.XML Based Definition
<?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> |
2.Controller Design


Ray Tracing on Cell by Using KD-Tree Acceleration Structure – PDF
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.








