UNIT - II

FACTORING METHODS

FINDING THE SQUARE ROOT OF A NUMBER

Problem Statement: Given a number m devise an algorithm to compute its square root.

FINDING THE SQUARE ROOT OF A NUMBER

Example: Square root of 16 is 4 Square root of 625 is 25 In general, the square root n, of number m must satisfy the equation, n*n=m

FINDING THE SQUARE ROOT OF A NUMBER

Systematic approach to the problem:
1.

2.

3.

Choose a number n less than the number m we want the square root of. Square n and if it is greater than m decrease n by 1 and repeat step 2, else goto step 3. When the square of our guess at the square root is less than m we can start increasing n by 0.1 until we again compute a guess greater than m. At this point, we start decreasing our guess by 0.01 and so on until we have computed the square root we require to the desired accuracy.
4

FINDING THE SQUARE ROOT OF A NUMBER

Algorithm:
1.

2. 3.

4.

Establish m the number whose square root is required and the termination condition error e. Set the initial guess g2 to m/2. Repeatedly, a. Let g1 assume the role of g2, b. Generate a better estimate g2 of the square root using the averaging formula, until the absolute difference between g1 and g2 is less than error e. Return the estimated square root g2.
5

FINDING THE SQUARE ROOT OF A NUMBER

Implementation:

Void sqroot( float m, float error) { float g1,g2; /*Previous and current estimate of square root respectively.*/ {assert: m>0 ^ g1=m/2} g2=m/2; {invariant: |g2 * g2 m|<=|g1*g1-m|^g1>0^g2>0} do { g1=g2; g2=(g1+m/g1)/2; }while(abs(g1-g2)<error); {assert: |g2 * g2 m|<=|g1*g1-m|^|g1-g2|<error} Printf (Square root=%f,g2); }
6

THE SMALLEST DIVISOR OF AN INTEGER

Problem Statement: Given an integer n devise an algorithm that will find its smallest exact divisor other than one.

THE SMALLEST DIVISOR OF AN INTEGER

Example: The smallest divisor of 13 is: 13 The smallest divisor of 12 is: 2

THE SMALLEST DIVISOR OF AN INTEGER

Algorithm:
1.

2.

Establish n the integer whose smallest divisor is required. If n is not odd then return 2 as the smallest divisor. else a. Compute r the square root of n. b. initialize divisor d to 3. c. while not an exact divisor and square root limit not reached do generate next member in odd sequence d. d. If current odd value d is an exact divisor then return it as the exact divisor of n else return 1 as the smallest divisor of n.

THE SMALLEST DIVISOR OF AN INTEGER

Implementation:
int sdivisor(int n) { int d; /* current divisor and member of odd sequence */ int r; /* integer less than or equal to square root of n */ {assert: n>0 } if (n%2==0) return(2); else { r=trunc(sqr(n)) d=3; {invariant: d<=r+1 ^ no odd integer in [3..d-2] exactly divides n} while((n%d<>0) && (d<r)) d=d+2; {assert: d is smallest exact divisor of n ^ d<=r V (d<=r+1) ^ n is prime} if n%d==0 then return(d); else return (1); } }

10

THE GREATEST COMMON DIVISOR OF TWO INTEGERS

Problem Statement: Given two positive non-zero integers n and m design an algorithm for finding their greatest common divisor (GCD).

11

THE GREATEST COMMON DIVISOR OF TWO INTEGERS

GCD of two integers is the largest integer that divides the two integers exactly with no remainder.

12

THE GREATEST COMMON DIVISOR OF TWO INTEGERS

Example: GCD of 12 and 18 is 6.

13

THE GREATEST COMMON DIVISOR OF TWO INTEGERS

Algorithm: 1. Establish the two positive non-zero integers smaller and larger whose gcd is being sought. 2. Repeatedly, a. Get the remainder from dividing the larger integer by the smaller integer. b. Let the smaller integer assume the role of the larger integer. c. Let the remainder assume the role of the divisor. until a zero remainder is obtained. 3. Return the gcd of the original pair of integers.
14

THE GREATEST COMMON DIVISOR OF TWO INTEGERS

Implementation:

int gcd( int n, int m) { int r; /*Remainder after division of n by m*/ {assert: n>0 and m>0} do { {compute next gcd candidate and associated remainder} r=n mod m; n=m; m=r; }while(r==0); {assert: n=gcd of original pair n and m} return n; }
Applications: Reducing a fraction to its lowest terms.

15

GENERATING PRIME NUMBERS

Problem Statement: Design an algorithm to establish all the primes in the first n positive integers.

16

GENERATING PRIME NUMBERS

Example: If n=5, then the first 5 prime numbers generated are 2, 3, 5, 7, 11

17

GENERATING PRIME NUMBERS Algorithm:

1. 2. 3.

Initialize and write out the first 3 primes. Also initialize the square of the 3rd prime. Initialize x to 5. While x less than n do a. Get next x value excluding multiples of 2 and 3. b. If not past end of multiples list then
a.

If x>=square of largest prime then

a.

4.

5.

Include next prime multiple as its square b. Update square by squaring next prime. While have not established x is non-prime with valid prime multiples do a. While current prime multiple is less than x, increment by current prime value doubled. b. Do prime test by comparing x with current multiple. If current x prime then a. Print x and if it is less square root of n store it.

18

GENERATING PRIME NUMBERS

Implementation:
Void prime( int n) { int multiple[100]; /* multiples of primes */ int p[100] ; /* Primes upto sqrt(n) */ int i /*Index for primes saved*/ int j /*index of primes and multiple array*/ int limit /*Upper index for primes less than sqrt(x)*/ int plimsq /*Square of largest prime included so far*/ int rootn /*truncated sqrt(n)*/ int dx /*increment either 2 or 4 to avoid multiples of 3*/ int x /*current candidate for prime test*/ int prime; P[1]=2;p[2]=3; p[3]=5;i=3; if ( n<5 ) { for (j=1;j<=(n+1)/2;j++) printf(%d,p[j]); }

19

GENERATING PRIME NUMBERS

else { for (j=1;j<=3;j++) printf (%d, p[j]); x=5; sqlim=25; limit=3; dx=2; rootn=trunc(sqrt(n)); while(x<n) { x=x+dx; dx=abs(dx-6); if (limit<=i) { if (x>=sqlim) { mult[limit]=sqlim; limit++; if (limit<=i) sqlim=sqr(p[limit]); } prime=1; j=3;

20

GENERATING PRIME NUMBERS

While(prime && (J<limit)) { while (mult[j]<x) { mult[j]=mult[j]+p[j]*2; prime=x!=mult[j]; j++; } } If (prime) { printf(%d,x); if (x<=rootn) { i++; p[i]=x; } } } } }

21

GENERATING PRIME NUMBERS

There are approximately n/logen primes in the first n positive integers.

22

COMPUTING THE PRIME FACTORS OF AN INTEGER

Problem Statement: Every integer can be expressed as a product of prime numbers. Design an algorithm to compute all the prime factors of an integer n.
23

COMPUTING THE PRIME FACTORS OF AN INTEGER

Prime factors of a integer are the prime numbers that divide the integer exactly without leaving a remainder. Example: Prime factors of 6 are 2,3. Prime factor of 5 is 5. 1 has no Prime factor.
24

COMPUTING THE PRIME FACTORS OF AN INTEGER Algorithm:

1. 2.

3.

Establish n the number whose prime factors are sough t. Compute the remainder r and quotient q for the first prime nxtprime=2. While it is not established that n is prime do a. If nxtprime is an exact divisor of n then a. Save nxtprime as a factor f b. Reduce n by nxtprime
Else

4. 5.

get next biggest prime from sieve of Eratosthenes b. Compute next quotient q and remainder r for current value of n and current prime divisor nxtprime. If n is greater than 1 then add n to list as a prime factor f Return the prime factors f of the original number n.
a.

25

COMPUTING THE PRIME FACTORS OF AN INTEGER

Implementation:
Void primefactors( int f[], int i, int n) { int q; /* n/nxtprime */ int r; /* n%nxtprime */ int nxtprime; /*next prime divisor to be tested*/ int d[100] /* multiples array for sieve */ nxtprime=2; q=n/nxtprime ; r=n%nxtprime ; i=0 while (r==0) || (q>nxtprime) do { if (r==0) { i++; f[i]=nxt; n=q; } else nxt=eratosthenses(d,nxtprime0;

26

COMPUTING THE PRIME FACTORS OF AN INTEGER

q=n/nxtprime ; r=n%nxtprime; } } if n>1 then { i=i+1; f[i]=n; } }

Applications: Factoring numbers with upto six digits.

27

GENERATION OF PSEUDO-RANDOM NUMBERS

Problem Statement: Use the congruential method to generate a uniform set of pseudo-random numbers.

28

GENERATION OF PSEUDO-RANDOM NUMBERS

A sequence of random numbers should exhibit the following behavior.
1.

2.

The sequence should appear as though each number had occurred by chance. Each number should have a specified probability of falling within a given range.

29

GENERATION OF PSEUDO-RANDOM NUMBERS

Linear congruential method: Successive members of the sequence {x} are generated using the expression, Xn+1=(axn+b) mod m for n>=0 Where, Parameters a, b, m are referred to as the multiplier, increment and modulus respectively.

All parameters should be integers greater than or equal to zero and m should be greater than x0, a, b. Parameter x0 in the range <=0 and <m. Parameter m should be greater than or equal to the length of the random sequence required. Parameter a depends on parameter m. if m is a power of 2 then a should satisfy, a mod 8=5 if m is a power of 10 then a should satisfy, a mod 200=21 Parameter b should be odd and not a multiple of 5.
30

GENERATION OF PSEUDO-RANDOM NUMBERS Implementation: void random(int x) { /* Generates m pseudo-random numbers in the range 0 to m1*/ int a,b,m; /* multiplier, increment and modulus respectively */ m=4096; {assert: 0<=x<=m-1} b=853; a=109; x=(a * x + b) % m; printf(%d,x); }
31

Applications: Analysis of algorithms, simulation problems and games.

RAISING A NUMBER TO A LARGE POWER

Problem statement: Given some integer x, compute the value of xn where n is a positive integer considerably greater than 1.

32

RAISING A NUMBER TO A LARGE POWER

Example: If x=2 and n=4 then, xn=24=16

33

RAISING A NUMBER TO A LARGE POWER

Algorithm:

1. Establish n, the integer power, and x the integer to be raised to the power n. 2. Initialize the power sequence and product variable for the zero power case. 3. While the power n is greater than zero do, a. if next most significant binary digit of power n is one then a. multiply accumulated product by current power sequence value. b. reduce power n by a factor of two using integer division. c. get next power sequence member by multiplying current value by itself. 4. Return x raised to the power n.
34

RAISING A NUMBER TO A LARGE POWER

Implementation:

int power(int x, int n) { int product; /* current accumulated product */ int psequence; /* current power sequence value*/ {assert: x>0 ^ n>=0 ^ n0=n} product=1; psequence=x; {invariant: product * (psequence)^n = x^n0 ^ n>=0} while (n>0) { if (n%2==1) product =product*psequence; n=n/2; psequence=psequence*psequence; } {assert: product = x^n0} return(product) }

35

RAISING A NUMBER TO A LARGE POWER

Multiplications of order of log2n are needed to raise x to the power n. Applications: Encryption and testing for non-primality of numbers.

36

COMPUTING THE NTH FIBONACCI NUMBER

Problem Statement: Given a number n generate the nth member of the Fibonacci sequence.

37

COMPUTING THE NTH FIBONACCI NUMBER

The nth member of the Fibonacci sequence is defined as follows: f0=0 f1=1 fn=fn-1+fn-2 for n>2

38

COMPUTING THE NTH FIBONACCI NUMBER

Algorithm:
1. 2. 3. 4.

5.

Establish n, indicating the nth fibonacci number is required. Derive the binary representation of n by repeated division by 2 and store representation in array d[1i-1] Initialize the first two members of the sequence. Stepping down from the (i-1)th most significant digit in the binary representation of n to 1 do a. Use current pair of Fibonacci numbers fn and fn+1 to generate the pair f2n and f2n+1. b. If current binary digit d[k] is zero then make the reassignments to fn and fn+1 else extend sequence by 1 number and then make the reassignments to fn and fn+1 Return the nth Fibonacci number fn.
39

COMPUTING THE NTH FIBONACCI NUMBER

Implementation:

int nfib(int n) { int d[100] ; /* array containing binary digits*/ int fn; /* nth fibonacci number */ int f2n ; /* 2nth fibonacci number */ int fnpl; /* (n+1)th fibonacci number */ int f2npl; /* (2n+1)th fibonacci number */ int i ; /* binary digit count less 1 of n */ int k ; /* index for array of binary digits */ int sqfnpl; /* square of the (n+1)th fibonacci number */ { assert: n>0 ^ n has <=100 digits in its binary representation} i=0; {invariant: after the ith iteration the least significant bits of binary representation of original n stored in d[i..1]} while(n>1) { i++; if (n%2!=0) d[i]=1; else 40 d[i]=0; n=n/2; }

COMPUTING THE NTH FIBONACCI NUMBER

Fn=0; fnpl=1

for(k=I;k>=1;k--) { sqfnpl=fnpl * fnpl; f2n=fn*fn+fnpl; f2npl=2*fn*fnpl+sqfnpl; if (d[k]==0) { fn=f2n; fnpl=f2npl; } else { fn=f2npl; fnpl=f2npl * f2n; } } return(fn); }

41

COMPUTING THE NTH FIBONACCI NUMBER

The algorithm requires of the order of log2n steps to compute the nth Fibonacci number.

42