Mathematics Basics for programming
Programming
1. Series
Sum of first n integer:
$$ \sum_{i=1}^{n}{i} = \frac{n(n+1)}{2} $$
Sum of squares of first n integer.
$$ \sum_{i=1}^{n}{i^2} = \frac{n(n+1)(2n+1)}{6} $$
Sum of cubes of first n integer.
$$ \sum_{i=1}^{n}{i^3} = \left(\sum_{i=1}^{n}{i}\right)^2 = \left(\frac{n(n+1)}{2} \right)^2 $$
2. Fast Exponentiation
Recursive copmutation of an :
int power(int a, int n){
if(n==0) return 1;
if(n==1) return a;
int temp = power(a,n/2);
// if odd multiply with a one more time
int temp2 = power(a,n%2);
return temp2 * temp * temp;
}
3. Greatest Common Divisor
gcd(a,b) gives largest integer which divides both a and b.
gcd(a,b) = gcd(a,b-a);
gcd(a,0) = a;
gcd(a,b) is smallest positive number in $$ ax + by | x,y \epsilon \mathbb{Z} $$