Division by Different way

When dividing two numbers, there are several algorithms and techniques beyond the direct use of the division operator (/). These techniques are useful in scenarios where direct division might not be feasible, such as in low-level programming or specialized hardware implementations. Let’s explore multiple division processes, each with a different approach to dividing integers:

1. Direct Division (Using / Operator)

Ø  Process: This is the simplest and most common method for dividing two numbers. It directly uses the division operator (/).

Ø  Pros: Efficient, built-in, and quick.

Ø  Cons: Not always available in all systems (e.g., some hardware implementations or environments may lack division instructions).

Example:

java

public static final long directDivision(int a, int b) {     return a / b; }

 

2. Division by Subtraction (Loop-based Division)

Ø  Process: This method repeatedly subtracts the divisor from the dividend until the dividend becomes less than the divisor. The number of subtractions is the quotient.

Ø  Pros: Simple and intuitive; works without needing the division operator.

Ø  Cons: Can be slow for large numbers due to the number of subtractions.

Steps:

Ø  Start with the dividend (a) and the divisor (b).

Ø  Subtract b from a repeatedly.

Ø  Count how many subtractions can be made before the dividend becomes negative or less than the divisor.

Example:

java

public static final long divisionBySubtraction(int a, int b) {     int absoluteA = Math.abs(a);     int absoluteB = Math.abs(b);     int result = 0;       while (absoluteA >= absoluteB) {         absoluteA -= absoluteB;         result++;     }     return (a < 0 && b < 0 || a > 0 && b > 0) ? result : -result; }

 

3. Division by Recursion

Ø  Process: This is a recursive version of the subtraction method. Instead of looping, it calls itself until the dividend is smaller than the divisor.

Ø  Pros: Recursive, so it’s conceptually elegant.

Ø  Cons: Can lead to stack overflow for large inputs, as it involves deep recursion.

Steps:

Ø  Check if the dividend is smaller than the divisor. If so, return 0.

Ø  Subtract the divisor from the dividend and call the function recursively.

Example:

java

public static final long divisionByRecursion(int a, int b) {     int absoluteA = Math.abs(a);     int absoluteB = Math.abs(b);       if (absoluteA < absoluteB) return 0;       return 1 + divisionByRecursion(absoluteA - absoluteB, absoluteB); }

 

4. Bitwise Division (Shift-based Division)

Ø  Process: Uses bitwise operations (shifting) to divide numbers efficiently. The idea is to find how many times the divisor can be doubled (via left shift) before it becomes larger than the dividend. Then, subtract the divisor and repeat for the remainder.

Ø  Pros: Efficient in environments with limited arithmetic operations; faster than subtraction for large numbers.

Ø  Cons: More complex to implement and understand.

Steps:

Ø  Left shift the divisor until it is greater than or equal to the dividend.

Ø  Subtract the largest shifted divisor from the dividend.

Ø  Repeat the process for the remainder until it is smaller than the divisor.

Example:

java

public static final long divisionByBitwiseShift(int a, int b) {     int absoluteA = Math.abs(a);     int absoluteB = Math.abs(b);     long result = 0;       while (absoluteA >= absoluteB) {         int tempB = absoluteB;         int multiple = 1;           while (absoluteA >= (tempB << 1)) {             tempB <<= 1;             multiple <<= 1;         }           absoluteA -= tempB;         result += multiple;     }       return (a > 0 && b > 0 || a < 0 && b < 0) ? result : -result; }

 

5. Division Using Multiplication and Shifting

Ø  Process: This approach uses bit shifts and multiplication to simulate division. By shifting the divisor and calculating powers of 2, you simulate how many times the divisor can fit into the dividend.

Ø  Pros: Efficient for large numbers as it reduces the number of steps by using powers of 2.

Ø  Cons: Complex implementation.

Steps:

Ø  Shift the divisor left (multiplied by powers of 2) until it is larger than the dividend.

Ø  Subtract the largest shifted divisor and continue the process.

Example:

java

public static final long divisionByMultiplication(int a, int b) {     int absoluteA = Math.abs(a);     int absoluteB = Math.abs(b);     long result = 0;       while (absoluteA >= absoluteB) {         int shiftCount = 0;         while (absoluteA >= (absoluteB << shiftCount)) {             shiftCount++;         }         result += (1L << (shiftCount - 1));         absoluteA -= (absoluteB << (shiftCount - 1));     }       return (a > 0 && b > 0 || a < 0 && b < 0) ? result : -result; }

 

6. Division Using Logarithms

Ø  Process: Leverages the logarithmic properties of numbers. The logarithm of the quotient of two numbers is equal to the difference between their logarithms. This method uses base-10 logarithms and exponentiation to compute division.

Ø  Pros: A novel way of dividing numbers using logarithmic math.

Ø  Cons: Relies on floating-point math, which may lose precision for very large or small numbers.

Steps:

Ø  Take the logarithm of both the dividend and divisor.

Ø  Subtract the logarithms and exponentiate the result.

Example:

java

public static final long divisionByLogarithms(int a, int b) {     double logA = Math.log10(Math.abs(a));     double logB = Math.log10(Math.abs(b));     long result = (long) Math.pow(10, logA - logB);     return (a > 0 && b > 0 || a < 0 && b < 0) ? result : -result; }

 

7. Booth's Algorithm for Division

Ø  Process: This is a hardware-based algorithm primarily used for multiplication and division in computers. It efficiently handles signed division and is often implemented at the CPU level.

Ø  Pros: Optimized for hardware; handles signed numbers well.

Ø  Cons: More complex to implement in software.

Steps for Booth's Division:

1. Initialize: Start with the dividend and divisor in binary form.
2. Shift: Left shift the divisor based on the position of the most significant 1 in the dividend.
3. Subtract: Try to subtract the shifted divisor from the dividend.
4. Iterate: Shift and subtract repeatedly, adjusting the quotient bit by bit.
5. Handle Signed Numbers: Handle both positive and negative numbers.

 

Booth-Inspired Division Algorithm in Java:

Here is a Booth-inspired binary division approach implemented in Java. It works by shifting and subtracting, while adjusting for signed numbers.

java

package com.kartik;   public class BoothDivision {       // Method to perform Booth-inspired binary division     public static long boothDivision(int dividend, int divisor) {         // Determine sign of the result         boolean negativeResult = (dividend < 0) ^ (divisor < 0);                 // Work with positive absolute values of dividend and divisor         int absDividend = Math.abs(dividend);         int absDivisor = Math.abs(divisor);           // Initialize quotient and remainder         long quotient = 0;         long remainder = 0;           // Number of bits to represent the dividend         int numberOfBits = Integer.SIZE;           // Iterate for each bit of the dividend         for (int i = numberOfBits - 1; i >= 0; i--) {             // Left shift remainder and bring down the next bit of the dividend             remainder = (remainder << 1) | ((absDividend >> i) & 1);               // Subtract divisor from remainder             if (remainder >= absDivisor) {                 remainder -= absDivisor;                 quotient |= (1L << i);  // Set the corresponding quotient bit             }         }           // Adjust sign of the quotient based on the original signs of dividend and divisor         return negativeResult ? -quotient : quotient;     }       // Test the Booth-inspired division method     public static void main(String[] args) {         int dividend = -43;         int divisor = 5;           long result = boothDivision(dividend, divisor);         System.out.println("Result of division: " + result);     } }

 

Summary of Techniques:

1. Direct Division (/): The simplest and fastest but not always available in low-level environments.
2. Subtraction-based Division: Useful for simulating division in environments that lack division operators.
3. Recursive Division: Elegant and straightforward but may lead to deep recursion for large numbers.
4. Bitwise Division: Efficient and used in systems with limited arithmetic capabilities.
5. Multiplication and Shifting: Optimizes the process by reducing the number of steps through powers of 2.
6. Logarithmic Division: Uses logarithms to compute division but is not precise for all cases.
7. Booth's Algorithm: A low-level, hardware-focused approach.

Each method has its strengths and weaknesses, and the appropriate choice depends on the specific context and requirements.

 

Example 1 divisionUsingShift:

Division by Shift

Example 2 divisionUsingMultiplication with recursion:

Division by recursion