Programming Geek
Rated 4.7/5 based on 1446 reviews

Calculating Large Factorial

No comments :

Calculating Large Factorial

Factorial of a non-negative number n is denoted by n! and it is the product of all positive integers less than or equal to n. Hence factorial of 5 is:

1*2*3*4*5=120.

 Factorial in a programming language can be calculated using a loop or a recursive procedure. But once the factorial exceeds the largest number supported by standard data type like int or long, it rolls to the negative minimum. Hence sometimes we get weird output.  For an example, factorial of 50 is very large and it overflows the largest number supported by int or long as obvious by the following program:
//Factorial.java
import java.util.Scanner;


/**
 *
 * @author VIK VIKKU VIKASHVVERMA
 */
public class Factorial {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter the number:");
        int num=sc.nextInt();
        int fact=1;
        for (int i = 1; i <=num; i++) {
            fact*=i;
        }
        System.out.println("Factorial of "+num+" is : "+fact);
    }//main(-)
    
}//Factorial





The output of the program is as below:

Enter the number:
50
Factorial of 50 is : 0

When we change the data type of fact to long to increase size and run the same program we get the output as shown below:

Enter the number:
50
Factorial of 50 is : -3258495067890909184

No primitive data type of any language can be used to calculate large factorial. So how can we get the factorial of 50 or other numbers perfectly.?

In JAVA, we have BigInteger class in java.math package which can be used to store very large number and we will be using this class to calculate factorial of such numbers. So here goes a java program to calculate factorial of 50 or 100 or other numbers:
//FactorialDemo.java
import java.math.BigInteger;
import java.util.Scanner;

/**
 *
 * @author VIK VIKKU VIKASHVVERMA
 */
class Factorial {

    int num;
    BigInteger bi = new BigInteger("1");

    public void read() {
        System.out.println("Enter a number:");
        Scanner sc = new Scanner(System.in);
        num = sc.nextInt();
    }//read()

    public void process() {
        if (num < 0) {
            System.out.println("Invalid number!");
            System.exit(1);
        }
        for (int i = 1; i < num; i++) {
            bi = bi.multiply(BigInteger.valueOf(i));
        }
    }//process()

    public void display() {
        System.out.println("Factorial of " + num + " is : " + bi);
    }//display()
}//Factorial

public class FactorialDemo {

    public static void main(String[] args) {
        Factorial f=new Factorial();
        f.read();
        f.process();
        f.display();
    }//main(-)
}//FactorialDemo



The output of this program with 50 as input is as:

Enter a number:
50
Factorial of 50 is : 608281864034267560872252163321295376887552831379210240000000000

Also the factorial of 100 is:

Enter a number:
100
Factorial of 100 is : 933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000


Efficient Algorithm To Test Primality

1 comment :

Efficient Algorithm To Test Primality

A number which is greater than 1 is called prime if its only positive divisors are 1 and the number itself. A number which is not prime is called composite number. Suppose we have following numbers:

1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9

Then the prime numbers are : 2 , 3 , 5 , 7

and composite numbers are:  1 , 4 , 6 , 8 , 9

So to test whether a number is prime or not, the first employed approach is to divide the given number(n) by all numbers from 2 up to n-1 . If the number is divided perfectly then the number is not prime otherwise the number is prime.  Implementing this logic needs n-2 comparison, So the complexity is O(n).

Another approach to test primality is to divide n by all numbers from 2 upto n/2. Also this is not a good approach. It just reduces the number of comparison by half compared to previous approach.

An efficient algorithm to test primality is as follows:

1)      If n is less than 2 then n is invalid number.

2)     If n is equal to 2 then it is a prime number.

3)     If n is divisible by 2 then it is not prime. If n is not divisible by 2 then it won’t be divided by any even number.

4)     If n is prime then there must exist a divisor of n which is less than or equal to square root(n).

So, if n is less than 2 then it is not prime. If n is equal to 2 then it is a prime number.  If it is not divisible by 2 then it will not be divided by any even number. So we need to check only for odd numbers from 3 upto square root(n). Of course if n is prime then a divisor of n must be less than or equal to square root(n). In this approach we need to do (square root(n)/2)-1 comparison. So it is quite fast compared to other two approaches.

Here goes implementation of this efficient primality test algorithm in various languages:

JAVA implementation of primality test:

//PrimeTest.java
import java.util.Scanner;

/**
 *
 * @author VIK VIKKU VIKASH VIKASHVVERMA
 */
public class PrimeTest {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter a number:");
        int num = scanner.nextInt();
        PrimeTest test = new PrimeTest();
        if (test.isPrime(num)) {
            System.out.println(num + " is a prime number!");
        } else {
            System.out.println(num + " is not a prime number!");
        }

    }

    private boolean isPrime(int num) {
        boolean flag = false;
        if (num < 2) {
            return !flag;
        }
        if (num == 2) {
            return true;
        }
        if (num % 2 == 0) {
            return flag;
        }
        int i = 3;
        int rootn = (int) Math.sqrt(num);
        for (; i <= rootn; i += 2) {
            if (num % i == 0) {
                break;
            }

        }
        if (i > rootn) {
            flag = true;
        }
        return flag;
    }
}



C implementation of primality test:

#include<stdio.h>

  #include<math.h>


int isPrime(int num)

  {

  int i=3,rootn=sqrt(num);

  if(num<2)

  {

  return 0;

  }

  if(num==2)

  {

  return 1;

  }

  if(num%2==0)

  {

  return 0;

  }

  for(;i<=rootn;i+=2)

  {

  if(num%i==0)

  return 0;

  }

  return 1;

  }

  int main()

  {

  int num;

  printf("Enter a number:");

  scanf("%d",&num);

  if(isPrime(num))

  {

  printf("%d is a prime number!",num);

  }else

  {

  printf("%d is not a prime number!",num);

  }

  }




C++ implementation of primality test:

#include<iostream.h>

  #include<math.h>


int isPrime(int num)

  {

  int i=3,rootn=sqrt(num);

  if(num<2)

  {

  return 0;

  }

  if(num==2)

  {

  return 1;

  }

  if(num%2==0)

  {

  return 0;

  }

  for(;i<=rootn;i+=2)

  {

  if(num%i==0)

  return 0;

  }

  return 1;

  }

  int main()

  {

  int num;

  cout<<"Enter a number:";

  cin>>num;

  if(isPrime(num))

  {

  cout<<num<<" is a prime number!";

  }else

  {

  cout<<num<<" is not a prime number!";

  }

  }


Codejam 2013

No comments :

Codejam 2013

Codejam is a coding contest organized each year by google. This is an online contest and any one can participate. People across the globe are required to solve the tough algorithmic puzzle.  This year the registration of codejam has been started. Anyone willing to participate can register till April 14, 2013. The contest consists of four online rounds. This year the grand finale will be held at Google’s  office in London in August 2013. This year the winner will grab a prize money of $15000.



The online competition for Veterans 2013 contest just held on March 2nd 2013. Although I did not participate, yet I solved the problems later. After Facebook Hacker Cup 2013, I am willing to participate in Codejam 2013. This is my first time in codejam. So I am going through problems of previous contests. Hope I will do better there. So let’s wait for qualification round first.

Those willing to participate can register at  https://code.google.com/codejam.

Also join facebook and google+ community for latest updates. 


Understanding Importance of Unicode in JAVA

No comments :

Understanding Importance of Unicode in JAVA

Unicode is a character set which allows to represent character of almost all language. Unicode uses 16 bit to represent character of any language. It’s typical representation starts with’\u’. For an example, the Unicode representation of ‘\n’ is ‘\u000A’ .

In JAVA, char takes 2 bytes memory because JAVA supports Unicode and allows character of any language to be used in JAVA program.

Let us first understand the way java program works.

 The source file contains java program. We complie the program and get .class file containing the bytecode. This bytecode is plateform independent and architecture neutral and can be run by any device having  jvm.

 So what happens when we compile a java program?

When we write “javac  ClassName.java” then before compilation all Unicode codes are replaced by their equivalent characters i. e. like C the java program is pre-processed and during this pre-processing all Unicode code is replaced by equivalent character and then compilation phase starts.

The following programs illustrate the concept of Unicode in JAVA:



/**
 *
 * @author VIK 01:48 10 March 2013
 */
public class UnicodeDemo1 {
    public static void main(String[] args) {
    //This line causes problem \u000A because of unicode preprocessing
        System.out.println("This program won't compile!!!");
    }
    
}

The Detailed explanation of above program can be found here.
/**
 *
 * @author VIK VIKKU VIKASHVVERMA
 */
public class UnicodeDemo2 {
    public static void main(String[] args) {
        /*
         * This program also causes compilation error.
         * Becuse this file is saved in c:\units\vikashvverma\stuffs
         * and have improperly formatted unicode code.
         *So While using unicode remeber to format unicode properly
         *          * 
         */
        System.out.println("This is an example java program having improperly formatted unicode !!!");
    }
}

Ok now you are aware of using Unicode in java program.  Can you write a java program without using any keyword and print something e.g.  “Vikash verma” .
Getting problem…? Ok stay updated for next post.