Base Number Conversion:

Decimal is our most recognizable base number, while computers are very recognizable with binary numbers (that is, octal and hexa too). The ability to transform between bases is significant.

Big Mod:

Modulo (or remainder) is significant arithmetic operation and nearly each and every programming language give this basic operation. Though, basic modulo operation is not enough if we are interested in finding the modulo of a very big integer, which will be hard and has tendency for overflow. Luckily, we encompass a good formula here:

(A*B*C) mod N == ((A mod N) * (B mod N) * (C mod N)) mod N.

To convince you that this works, the example is as shown below:

(7*11*23) mod 5 is 1; let's see the calculations step by step:
((7 mod 5) * (11 mod 5) * (23 mod 5)) Mod 5 =
((2 * 1 * 3) Mod 5) =
(6 Mod 5) = 1

This formula is employed in several algorithms like in Fermat Little Test for primality testing:

R = B^P mod M (B^P is a very big number). By utilizing the formula, we can get the right answer devoid of being afraid of overflow.

This is how to compute R quickly (employing Divide & Conquer approach):

long bigmod(long b,long p,long m) {
  if (p == 0)
    return 1;
  else if (p%2 == 0)
    return square(bigmod(b,p/2,m)) % m; // square(x) = x * x
  else
    return ((b % m) * bigmod(b,p-1,m)) % m;
}

Big Integer:

In previous time, 16-bit integer is adequate: [-215 to 215-1] ~ [-32,768 to 32,767].

Whenever 32-bit machines are getting admired, 32-bit integers become essential. This data type can hold range from [-231 to 231-1] ~ [2,147,483,648 to 2,147,483,647]. Any integer with 9 or less digits can be safely evaluated by using this data type. If you in some way should use the 10th digit, be careful of the overflow.

But man is very much greedy, 64-bit integers are formed, referred to as programmers as long as long data type or Int64 data type. It consists of an awesome range of which can covers 18 digits integers completely, plus the 19th digit partially [-263-1 to 263-1] ~ [9,223,372,036,854,775,808 to 9,223,372,036,854,775,807]. Practically this data type is safe to calculate most of the standard arithmetic problems, except few problems.

Now, RSA cryptography requires 256 bits of number or more. This is essential, human always wish for more security right? Though, some problem setters in programming contests as well follow this trend. Simple problem like finding n'th factorial will become very hard once the values surpass 64-bit integer data type. Yes, long double can store much high numbers, however it actually only stores first few digits and an exponent, long double is not accurate.

Implement your own random precision arithmetic algorithm Standard pen and pencil algorithm taught in an elementary school will be your tool to implement fundamental arithmetic operations: subtraction, addition, multiplication and division. More sophisticated algorithm is accessible to improve the speed of division and multiplication. Things are getting very complex now.

Carmichael Number:

The Carmichael number is a number which is not prime however has >= 3 prime factors. You can calculate them by using prime number generator and prime factoring algorithm.

The initial 15 Carmichael numbers are as follows:

561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973

Catalan Formula:

The number of different binary trees can be generalized as Catalan formula, symbolized as C(n).

C(n) = 2n C n / (n+1)

When you are asked the values of several C(n), it might be a good choice to calculate the values bottom up.

As C(n+1) can be expressed in C(n), as:

Catalan(n) =  2n!/ n! * n! * (n+1)

Catalan(n+1) = 2*(n+1)/ (n+1)! * (n+1)! * ((n+1)+1)

(2n+2) * (2n+1) * 2n!/ (n+1) * n! * (n+1) * n! * (n+2)
 
(2n+2) * (2n+1) * 2n!/ (n+1) * (n+2) * n! * n! * (n+1)

[(2n+2) * (2n+1)/ (n+1) * (n+2)] * Catalan(n)

Counting Combinations - C(N, K):

C(N,K) signifies how many ways that N things can be taken K at a time. This can be a great challenge whenever N and/or K become very big.

The combination of (N, K) is defined as:

N!/(N-K)!*K!

Thus, how to compute the values of C(N, K) whenever N and/or K is big however the result is guaranteed to fit in the 32-bit integer?

=> Divide by the GCD before multiply (sample code in C)

long gcd(long a,long b) {
  if (a%b==0) return b; else return gcd(b,a%b);
}
void Divbygcd(long& a,long& b) {
  long g=gcd(a,b);
  a/=g;
  b/=g;
}
long C(int n,int k){
  long numerator=1,denominator=1,toMul,toDiv,i;
  if (k>n/2) k=n-k; /* use smaller k */
  for (i=k;i;i--) {
    toMul=n-k+i;
    toDiv=i;
    Divbygcd(toMul,toDiv);       /* always divide before multiply */
   Divbygcd(numerator,toDiv);    
Divbygcd(toMul,denominator);
    numerator*=toMul;
    denominator*=toDiv;
  }
  return numerator/denominator;
}

Divisors and Divisibility:

If d is a divisor of n, then therefore is n/d, however d & n/d can’t both be bigger than sqrt(n).

2 is a divisor of 6, therefore 6/2 = 3 is as well a divisor of 6

Let N = 25, so no divisor will be bigger than sqrt (25) = 5. (The divisors of 25 is 1 & 5 only)

If you maintain that rule in your mind, you can design an algorithm to determine a divisor better, that's it, and no divisor of a number can be bigger than the square root of that specific number.

If a number N == a^i * b^j * ... * c^k then N has (i+1)*(j+1)*...*(k+1) divisors.

Exponentiation:

(Suppose pow() function in <math.h> doesn't exist...). At times we want to do exponentiation or take a number to power n. There are numerous ways to do that. The standard technique is standard multiplication.

Standard multiplication:

long exponent(long base,long power) {
  long i,result = 1;
  for (i=0; i<power; i++) result *= base;
  return result;}

This is quite 'slow', especially whenever power is big - O(n) time. It is better to employ divide & conquer.

Divide & Conquer exponentiation:

long square(long n) { return n*n; }
long fastexp(long base,long power) {
  if (power == 0)
    return 1;
  else if (power%2 == 0)
    return square(fastexp(base,power/2));
  else
    return base * (fastexp(base,power-1));
}
Using built in formula, a^n = exp(log(a)*n) or pow(a,n)
#include <stdio.h>
#include <math.h>
 
void main() {
  printf("%lf\n",exp(log(8.0)*1/3.0));
  printf("%lf\n",pow(8.0,1/3.0));
}

Factorial:

Factorial is naturally stated as Fac(n) = n * Fac(n-1).

Illustration:

Fac(3) = 3 * Fac(2)
Fac(3) = 3 * 2 * Fac(1)
Fac(3) = 3 * 2 * 1 * Fac(0)
Fac(3) = 3 * 2 * 1 * 1
Fac(3) = 6

Iterative version of factorial:

long FacIter(int n) {
  int i,result = 1;
  for (i=0; i<n; i++) result *= i;
  return result;
}

This is the most excellent algorithm to calculate factorial O(n).

Fibonacci:

Fibonacci numbers was introduced by Leonardo of Pisa (Fibonacci). He stated fibonacci numbers as a growing population of the immortal rabbits. Sequence of Fibonacci numbers are:

1,1,2,3,5,8,13,21,...

Recurrence relation for Fib(n):

Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n-1) + Fib(n-2)

Greatest Common Divisor (GCD):

As the name suggest, Greatest Common Divisor (or GCD) algorithm determines the greatest common divisor between two number a and b. GCD is a very helpful method, for instance to decrease rational numbers into its smallest version (3/6 = 1/2). The best GCD algorithm so far is the Euclid's Algorithm. Euclid found this fascinating mathematical equality. GCD(a,b) = GCD (b,(a mod b)).

Here is the fastest implementation of the GCD algorithm.

int GCD(int a,int b) {
  while (b > 0) {
    a = a % b;
    a ^= b;    b ^= a;    a ^= b;  }  return a;
}

Lowest Common Multiple (LCM):

Lowest Common Multiple (or LCM) and Greatest Common Divisor (or GCD) are two significant number properties, and they are inter-related. Even although GCD is more frequently employed than LCM, it is very useful to learn LCM too.

LCM (m,n) = (m * n) / GCD (m,n)
LCM (3,2) = (3 * 2) / GCD (3,2)
LCM (3,2) = 6 / 1
LCM (3,2) = 6

Application of LCM -> to find a synchronization time among two traffic light, if traffic light A display green color in every 3 minutes and traffic light B display green color in every 2 minutes, then every 6 minutes, both traffic light will display green color at similar time.

Mathematical Expressions:

There are three kinds of mathematical or algebraic expressions. They are Infix, Prefix & Postfix expressions.

Infix expression grammar:

<infix> = <identifier> | <infix><operator><infix>
<operator> = + | - | * | /  <identifier> = a | b | .... | z

Infix expression illustration: (1 + 2) => 3; the operator is in the middle of two operands. Infix expression is a normal manner human compute numbers.

Prefix expression grammar:

<prefix> = <identifier> | <operator><prefix><prefix>
<operator> = + | - | * | / <identifier> = a | b | .... | z

Prefix expression illustration: (+ 1 2) => (1 + 2) = 3, the operator is the first item. One programming language which uses this expression is Scheme language.

The advantage of prefix expression is it permits you write: (1 + 2 + 3 + 4) similar to this (+ 1 2 3 4), this is simpler.

Postfix expression grammar:

<postfix> = <identifier> | <postfix><postfix><operator>
<operator> = + | - | * | / <identifier> = a | b | .... | z

Postfix expression illustration: (1 2 +) => (1 + 2) = 3, the operator is the final item.

Postfix Calculator:

Computers do postfix computation better than infix computation. Thus whenever you compile your program, the compiler will transform your infix expressions (most programming language employ infix) into the postfix, the computer-friendly version.

Why do computer like Postfix better than the Infix?

It is because computer employ stack data structure, and postfix computation can be done simply by using stack.

Infix to postfix conversion:

To utilize this very efficient Postfix computation, we require converting our Infix expression into Postfix. The procedure is as shown below:

Illustration:

Infix statement: ( ( 4 - ( 1 + 2 * ( 6 / 3 ) - 5 ) ) ). This is what the algorithm will do, appear carefully at the steps:

Prime Factors:

Each and every integer can be expressed as a product of primes and such primes are termed as prime factors of that number. 

Exceptions:

For the negative integers, multiply by -1 to form it positive again. For -1,0, and 1, no prime factor. (By definition...)

Standard way:

Produce a prime list again, and then check how many of such prime can divide n. This is extremely slow. Perhaps you can write a very proficient code by using this algorithm, however there is another algorithm which is much more efficient than this.

Creative way, using Number Theory:

A) Do not make prime, or even checking for the primality.

B) Always employ stop-at-sqrt method.

C) Keep in mind to check the repetitive prime factors, illustration = 20->2*2*5, do not count 2 twice. We wish for distinct primes (though, some problems really need you to count such multiples)

D) Make your program utilize constant memory space, no array required.

E) Utilize the definition of prime factors wisely, this is the main idea. A number can always be splitted into a prime factor and the other prime factor or another number. This is termed as the factorization tree.

Prime Numbers:

Prime numbers are significant in Computer Science (For illustration: Cryptography) and finding prime numbers in a specified interval is a "tedious" task. Generally, we are looking for big (or very big) prime numbers thus searching for a better prime numbers algorithms will never stop.

1) Standard prime testing:

int is_prime(int n) {
  for (int i=2; i<=(int) sqrt(n); i++) if (n%i == 0) return 0;
  return 1;
}void main() {
  int i,count=0;
  for (i=1; i<10000; i++) count += is_prime(i);
  printf("Total of %d primes\n",count);
}

2) Pull out the sqrt call:

The primary optimization was to pull the sqrt call out of the limit test, just in situation the compiler was not optimizing that appropriately, this one is faster:

int is_prime(int n) {
  long lim = (int) sqrt(n);
  for (int i=2; i<=lim; i++) if (n%i == 0) return 0; return 1;}

3) Restatement of sqrt.

int is_prime(int n) {
  for (int i=2; i*i<=n; i++) if (n%i == 0) return 0;
  return 1;
}

4) We do not require checking even numbers:

int is_prime(int n) {
  if (n == 1) return 0;         // 1 is NOT a prime
  if (n == 2) return 1;         // 2 is a prime
  if (n%2 == 0) return 0;       // NO prime is EVEN, apart from 2
  for (int i=3; i*i<=n; i+=2)   // begin from 3, jump 2 numbers
    if (n%i == 0)               //  no requirement to check even numbers
      return 0;
  return 1;
}

5) Other prime properties:

A very little bit of thought must tell you that no prime can end in 0,2,4,5,6, or 8, leaving just 1,3,7, and 9. It is fast & easy. Memorize this method. It will be very obliging for your programming assignments dealing with comparatively small prime numbers (16-bit integer 1-32767). This divisibility check (step 1 - 5) will not be appropriate for bigger numbers. First prime and the just even prime: 2. largest prime in 32-bit integer range:

2^31 - 1 = 2,147,483,647

6) Divisibility check employing smaller primes beneath sqrt(N):

In reality, we can enhance divisibility check for the bigger numbers. Further investigation concludes that a number N is a prime if and only when no primes beneath sqrt(N) can divide N.

Fermat Little Test:

This is the probabilistic algorithm so you can’t guarantee the possibility of getting accurate answer. In range as big as 1-1000000, Fermat Little Test can be fooled by (merely) 255 Carmichael numbers (numbers which can fool Fermat Little Test). Though, you can do multiple random checks to raise this probability.

Fermat Algorithm:

If 2^N modulo N = 2 then N consists of a high probability to be a prime number.

Sieve of Eratosthenes:

Sieve is the most excellent prime generator algorithm. This will produce a list of primes very quickly; however it will require a very big memory. You can employ Boolean flags to do this (that is, Boolean is only 1 byte).

Algorithm for Sieve of Eratosthenes to determine the prime numbers in a range L, U (inclusive), where should be L<=U.

void sieve(int L,int U) {
  int i,j,d;
  d=U-L+1; /* from range L to U, we have d=U-L+1 numbers. */
  /* use flag[i] to mark whether (L+i) is a prime number or not. */
  bool *flag=new bool[d];
  for (i=0;i<d;i++) flag[i]=true; /* default: mark all to be true */
   for (i=(L%2!=0);i<d;i+=2) flag[i]=false; 
  /* sieve by prime factors staring from 3 till sqrt(U) */
  for (i=3;i<=sqrt(U);i+=2) {
    if (i>L && !flag[i-L]) continue;
    /* choose the first number to be sieved -- >=L,
       divisible by i, and not i itself! */
    j=L/i*i;    if (j<L) j+=i;
    if (j==i) j+=i; /* if j is a prime number, have to start form next
one */
    j-=L; /* change j to the index representing j */
    for (;j<d;j+=i) flag[j]=false;
  }
  if (L<=1) flag[1-L]=false;
  if (L<=2) flag[2-L]=true;
  for (i=0;i<d;i++) if (flag[i]) cout << (L+i) << " ";
  cout << endl;
}

Latest technology based Programming Languages Online Tutoring Assistance

Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Programming Languages help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Programming Languages, project ideas and tutorials. We provide email based Programming Languages help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Programming Languages. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Programming Languages Homework help and assignment help services. They use their experience, as they have solved thousands of the Programming Languages assignments, which may help you to solve your complex issues of Programming Languages. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.