Mathematics for Computation

HOME

 

We all feel that some rectangles are more pleasing to the eye than others. Many great artists, architects, and designers believe that those, whose length and width satisfy the following proportion, are the most beautiful rectangles:

the greater is to the less as the sum of the two is to the greater.

You may wonder what type of rectangle this is and what the ratio of length to width might be. When starting to search for an answer, you may also find out that the statement in ordinary speech is a bit too long and/or too complicated to follow. However, this verbal statement can be easily written in algebraic form:

Image


in which l represents the length and w represents the width.

To further simplify the algebraic form (remember we want to find out the ratio?), we use a symbol ø (Greek letter phi) to represent the ratio of the length and the width "l / w". Thus, the above proportion will become the following equation:

Image

or

ø = 1 + 1/ø

NUMBER THEORY (HISTORY)

Greatest Common Divisor (GCD)

The best GCD algorithm so far is Euclid's Algorithm

intGCD( int m, int n)
{
if ((m % n) == 0)return n;
return GCD(n, m % n);
}
This algorithm is tail recursive we can make it iterative very easily.
int GCD(int m,int n)
{
while (1)
{
if ((m % n) == 0)return n;
//m<--m%n
m = m % n;
//m<--->n
m ^= n;
n ^= m;
m ^= n;
}
}

LCM (m,n) = (m * n) / GCD (m,n)

Square Root Aproximation

Recursive
float SQRT_r(float n,float guess)
{
if(abs(guess*guess-n)<0.00001)
return guess;
return SQRT_r(n,((n/guess)+guess)/2);
}
Iterative
float SQRT(float n)
{

float guess=1;
while(1)
{
if(abs(guess*guess-n)<0.00001)
return guess;
guess=((n/guess)+guess)/2;
}
}

Caculating m power n

Running Time O( lg(n) )
int exponent(int base,int power)
{
if(power==0)return 1;
if(power==1)return base;
int temp=exponent(base,power/2);
if(power%2==0)
return temp*temp;
return temp*temp*base;
}
Running Time O(n)
int exponent_i(int base,int power)
{
int ret=1;
for(int i=0;i < power;i++)
{
ret*=base;
}
return ret;
}
Fermat primality test
The Fermat primality test is a probabilistic test to determine if a number is 
composite or probably prime.
Fermat’s little theorem states that if p is prime and 1<= a < p
then ( a ^ ( p-1 ) )  %  p = 1(where % is modulo operator)
Here we also use property of modular exponentiation
ULONG CalculateExponentMod(ULONG Exponent,ULONG ModVal)
{
int Base=2;
if(Exponent <= 31)
{
return (exponent(2,Exponent)%ModVal);
}
else
{
ULONG KKK=CalculateExponentMod(31,ModVal);
ULONG LLL=CalculateExponentMod(Exponent-31,ModVal);
return (KKK*LLL)%ModVal;
}
}
ULONG TestPrime(ULONG p)
{
ULONG a=CalculateExponentMod(p-1,p);
if(a==1)
{
return 1;
}
return 0;
}

BASE CONVERSION 

 Here is one good implementation for base conversion Implementation of Base Conversion