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)
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
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.
Reinventing the wheel : write your own fast sine function
Jun/090
A couple of days ago I tried to self study the mathematical explanation of pi (π) and ended up with very interesting results and ideas
First of all lets answer the classic question; What is pi?
Pi or π is a mathematical constant whose value is the ratio of any circle’s circumference to its diameter in Euclidean space… (Wiki)
From its definition it is pretty easy to find it depending on another mathematical function: sinus.
I can hear that two questions rising up in minds rapidly;
1) Why would I need that? -I don’t know the answer, just curiosity
2) How? – Answer is in the rest of the post… continue… cmon, go on!
Since it is hard to write mathematical formulas and drawing shapes on our stupid HCI (human computer interaction; keyboard, mouse, etc.) slavery, I prefered to write them on a notebook and took their shots for the ease of understanding and publishing.
Relation Between Pi and Sinus Function
At first galance it is necessery to know that a circle can be expressed by infinite number of triangles,
so let’s start with the most basic equilateral; square.


The first half of the image above shows how to find the area of the square by using its half-diagonal which is the first step to do inductive reasoning.
And the second half is a generalisation of the formula for an equilateral with ‘n’ sides/corners.
As much as we increase the number of sides of the equilateral as much as it approximates to a circle,
Let’s think that we have an equilateral with infinite sides, then it turns into a circle which means in the result formula if we give a very big value to ‘n’ and 1 to ‘r’, then the result approximates to pi.

instead of depending on the number of sides in the equilateral, we want to be dependent to the angle alpha, to do that we simply replace n with 360/alpha.


the conclusion of this part is awesome; we can find the value of sinus in the degree range of zero and ten, with an acceptable error (+0.001) by only one multiplication.
Some Trigonometry
Althoug it is possible to achieve relatively accurate results with the formula shown above for angles between 0 and 10, as the angle gets wider as it loses its accuricy. Therefore we have to use the magic formula for angles less than 10 but how?!
The answer comes from the trigonometric sine addition formula;
sin(a+b) = sin(a) cos(b) + sin(b) cos(a)
If we can keep the ‘b’ less than 10 then we will be able to use our formula in order to find the sine with a couple of aritchmetic operations.
Let’s say we are asked the sine value for 71.654, then;
a = 70
b = 1.654
and,
sin(71.654) = sin(70 + 1.654) = sin(70) cos(1.654) + sin(1.654) cos (70)
In this formula we are able to use the fast calculation for the sin(1.654) part and for the rest unfortunately we need to have sine and cosine tables. The good thing is we only need the multiply of tens for sine and natural number angles between 0 and 10 for cosine. So lets start writing our own fast sine function.
CODING
-
//precision types
-
-
#ifdef PRECISE
-
#define PRECISION_TYPE double
-
#else
-
#define PRECISION_TYPE float
-
#endif
-
PRECISION_TYPE hollyConstant = 0.017453292519943295769236907684886;
-
//First of all sine and cosine tables
-
-
PRECISION_TYPE sinTable[] = {
-
0.0, //sin(0)
-
0.17364817766693034885171662676931 , //sin(10)
-
0.34202014332566873304409961468226 , //sin(20)
-
0.5 , //sin(30)
-
0.64278760968653932632264340990726 , //sin(40)
-
0.76604444311897803520239265055542 , //sin(50)
-
0.86602540378443864676372317075294 , //sin(60)
-
0.93969262078590838405410927732473 , //sin(70)
-
0.98480775301220805936674302458952 , //sin(80)
-
1.0 //sin(90)
-
};
-
-
PRECISION_TYPE cosTable[] = {
-
1.0 , //cos(0)
-
0.99984769515639123915701155881391 , //cos(1)
-
0.99939082701909573000624344004393 , //cos(2)
-
0.99862953475457387378449205843944 , //cos(3)
-
0.99756405025982424761316268064426 , //cos(4)
-
0.99619469809174553229501040247389 , //cos(5)
-
0.99452189536827333692269194498057 , //cos(6)
-
0.99254615164132203498006158933058 , //cos(7)
-
0.99026806874157031508377486734485 , //cos(8)
-
0.98768834059513772619004024769344 //cos(9)
-
};
-
// sin (a+b) = sin(a)*cos(b) + sin(b)*cos(a)
-
// a = 10*m where m is a natural number and 0<= m <= 90
-
// i.e. lets a+b = 18.22
-
// then a = 10, b = 8.22
-
-
PRECISION_TYPE myFastSin ( PRECISION_TYPE angle )
-
{
-
int a = angle * 0.1f;
-
PRECISION_TYPE b = angle – 10 * a;
-
-
return sinTable[a] * cosTable[int(b)] + b * hollyConstant * sinTable[9-a];
-
}
RESULTS and ERROR rate
The results are really astonishing
I wasn’t really expecting such a result but it just did happen
the first result is the result of our fast sine function and the second one is the result of <cmath> ’s result
0. angle = 0.803589, expected = 0.0140248
OK : FASTER !! time dif. = 4294967233
result = 0.0140253, time spent = 29, error = -4.61005e-007, error % = -0.00328707
result = 0.0140248, time spent = 92, error = 0, error % = 01. angle = 1.50818, expected = 0.0263196
OK : FASTER !! time dif. = 4294967262
result = 0.0263227, time spent = 31, error = -3.03984e-006, error % = -0.0115497
result = 0.0263196, time spent = 65, error = 0, error % = 02. angle = 2.21377, expected = 0.0386279
OK : FASTER !! time dif. = 4294967261
result = 0.0386375, time spent = 31, error = -9.61125e-006, error % = -0.0248816
result = 0.0386279, time spent = 66, error = 0, error % = 03. angle = 2.92035, expected = 0.0509477
OK : FASTER !! time dif. = 4294967259
result = 0.0509698, time spent = 29, error = -2.20649e-005, error % = -0.0433089
result = 0.0509477, time spent = 66, error = 0, error % = 04. angle = 3.62794, expected = 0.0632772
OK : FASTER !! time dif. = 4294967261
result = 0.0633195, time spent = 30, error = -4.23118e-005, error % = -0.0668674
result = 0.0632772, time spent = 65, error = 0, error % = 05. angle = 4.33653, expected = 0.0756145
OK : FASTER !! time dif. = 4294967259
result = 0.0756867, time spent = 30, error = -7.22408e-005, error % = -0.0955383result = 0.0756145, time spent = 67, error = 0, error % = 0
….
94. angle = 71.4059, expected = 0.947801
OK : FASTER !! time dif. = 4294967260
result = 0.947942, time spent = 30, error = -0.000140667, error % = -0.0148414
result = 0.947801, time spent = 66, error = 0, error % = 095. angle = 72.2045, expected = 0.952153
OK : FASTER !! time dif. = 4294967263
result = 0.95228, time spent = 30, error = -0.000126302, error % = -0.0132649
result = 0.952153, time spent = 63, error = 0, error % = 096. angle = 73.0041, expected = 0.956326
OK : FASTER !! time dif. = 4294967262
result = 0.956337, time spent = 29, error = -1.17421e-005, error % = -0.00122784
result = 0.956326, time spent = 63, error = 0, error % = 097. angle = 73.8047, expected = 0.960316
OK : FASTER !! time dif. = 4294967264
result = 0.961116, time spent = 31, error = -0.000799954, error % = -0.0833011
result = 0.960316, time spent = 63, error = 0, error % = 098. angle = 74.6063, expected = 0.964124
OK : FASTER !! time dif. = 4294967261
result = 0.9649, time spent = 29, error = -0.000775695, error % = -0.0804559
result = 0.964124, time spent = 64, error = 0, error % = 099 times faster
0 times more precise
%218.04 faster
total error % = 9.46265, maximum error = 0.00242305, minimum error = 4.47035e-008, average error % =0.0955823
so the average error is %0.1 and its more than 2 times faster. On the other hand the memory used for the sine and cosine tables also should be taken into account but I don’t think its a big deal anyway.
My First DirectX stuff
Jun/090
This is the very first 3D stuff I made on directX.
It involves meshes, animation, stencil shadowing, camera contol, action management and picking.
You can DOWNLOAD the code and documentation from here
Here is the video:
hope you enjoy it ;D







