Posted on by Kalkicode
Code Mathematics

# DFA based division

DFA (Deterministic Finite Automaton) is a concept from automata theory that deals with modeling and analyzing finite state machines. In this context, "DFA-based division" refers to a method of performing division using a finite state machine. This approach is an interesting way to solve the division problem by modeling it as a state transition process.

## Problem Statement

The problem is to implement a division algorithm using a DFA (Deterministic Finite Automaton) approach. Given two positive integers, a dividend and a divisor, the goal is to determine whether the dividend is divisible by the divisor and calculate the remainder if it's not divisible.

## Idea to Solve the Problem

The idea is to treat the division process as a state transition in a deterministic finite automaton. Each state of the automaton corresponds to a partial remainder, and the transitions between states are determined by the bits of the dividend as they are processed one by one.

## Pseudocode

``````function checkState(dividend, remainder, transaction)
if dividend != 0
checkState(dividend >> 1, remainder, transaction)
remainder = transaction[remainder][dividend & 1]

function divide(dividend, divisor)
if divisor <= 0
return

create transaction[divisor][2]
zero = 0
one = 0
remainder = 0

for state from 0 to divisor - 1
zero = state << 1
one = zero + 1
if zero < divisor
transaction[state][0] = zero
else
transaction[state][0] = zero - divisor
if one < divisor
transaction[state][1] = one
else
transaction[state][1] = one - divisor

checkState(dividend, remainder, transaction)

if remainder == 0
print "(", dividend, " / ", divisor, ") Are Divisible \n\n"
else
print "(", dividend, " / ", divisor, ") are not divisible \n"
print "Remainder is: ", remainder, "\n\n"``````

## Algorithm Explanation

1. The `checkState` function is a recursive function that calculates the remainder of the division by traversing the bits of the dividend from the most significant to the least significant. It uses the `transaction` array to determine the next state based on the current bit.

2. The `divide` function takes the dividend and divisor as inputs. It initializes the `transaction` array and sets up the DFA's states and transitions.

3. The nested loop creates transitions for each state. If the transition leads to a state greater than or equal to `divisor`, it adjusts the state to be within the valid range.

4. The `checkState` function is then called to calculate the remainder using the DFA transitions.

5. Based on the remainder calculated, the function prints whether the dividend is divisible by the divisor along with the remainder, if applicable.

## Program Solution

``````// C program for
// DFA based division
#include <stdio.h>

// Recursively, find the remainder of divisor
void checkState(int dividend, int *remainder, int transaction[][2])
{
if (dividend != 0)
{
checkState(dividend >> 1, remainder, transaction);*remainder = transaction[ *remainder][dividend & 1];
}
}
void divide(int dividend, int divisor)
{
if (divisor <= 0)
{
// That is not working when divisor is negative
return;
}
// Use to collect transaction
int transaction[divisor][2];
// Define useful variables
int zero = 0;
int one = 0;
int remainder = 0;
// Execute loop through by given divisor
for (int state = 0; state < divisor; ++state)
{
// Next state for bit zero
zero = state << 1;
// Next state for bit one
one = zero + 1;
if (zero < divisor)
{
transaction[state][0] = zero;
}
else
{
transaction[state][0] = zero - divisor;
}
if (one < divisor)
{
transaction[state][1] = one;
}
else
{
transaction[state][1] = one - divisor;
}
}
// Check remainder
checkState(dividend, & remainder, transaction);
if (remainder == 0)
{
printf(" (%d / %d) Are Divisible \n\n", dividend, divisor);
}
else
{
printf(" (%d / %d) are not divisible \n", dividend, divisor);
printf(" Remainder is : %d\n\n", remainder);
}
}
int main(int argc, char
const *argv[])
{
// Test Case
divide(21, 6);
divide(25, 5);
divide(14, 7);
divide(34, 3);
divide(54, 3);
return 0;
}``````

#### input

`````` (21 / 6) are not divisible
Remainder is : 3

(25 / 5) Are Divisible

(14 / 7) Are Divisible

(34 / 3) are not divisible
Remainder is : 1

(54 / 3) Are Divisible
``````
``````/*
Java Program for
DFA based division
*/
{
int remainder;
{
this.remainder = 0;
}
// Recursively, find the remainder of divisor
public void checkState(int dividend, int[][] transaction)
{
if (dividend != 0)
{
checkState(dividend >> 1, transaction);
this.remainder = transaction[this.remainder][dividend & 1];
}
}
public void divide(int dividend, int divisor)
{
if (divisor <= 0)
{
// That is not working when divisor is negative
return;
}
// Use to collect transaction
int[][] transaction = new int[divisor][2];
// Define useful variables
int zero = 0;
int one = 0;
// Execute loop through by given divisor
for (int state = 0; state < divisor; ++state)
{
// Next state for bit zero
zero = state << 1;
// Next state for bit one
one = zero + 1;
if (zero < divisor)
{
transaction[state][0] = zero;
}
else
{
transaction[state][0] = zero - divisor;
}
if (one < divisor)
{
transaction[state][1] = one;
}
else
{
transaction[state][1] = one - divisor;
}
}
this.remainder = 0;
// Check remainder
checkState(dividend, transaction);
if (this.remainder == 0)
{
System.out.println(" (" + dividend + " / " + divisor + ") Are Divisible \n");
}
else
{
System.out.print(" (" + dividend + " / " + divisor + ") are not divisible \n");
System.out.println(" Remainder is : " + this.remainder + "\n");
}
}
public static void main(String[] args)
{
// Test Case
}
}``````

#### input

`````` (21 / 6) are not divisible
Remainder is : 3

(25 / 5) Are Divisible

(14 / 7) Are Divisible

(34 / 3) are not divisible
Remainder is : 1

(54 / 3) Are Divisible
``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ Program for
DFA based division
*/
{
public: int remainder;
{
this->remainder = 0;
}
// Recursively, find the remainder of divisor
void checkState(int dividend, int transaction[][2])
{
if (dividend != 0)
{
this->checkState(dividend >> 1, transaction);
this->remainder = transaction[this->remainder][dividend &1];
}
}
void divide(int dividend, int divisor)
{
if (divisor <= 0)
{
// That is not working when divisor is negative
return;
}
// Use to collect transaction
int transaction[divisor][2];
// Define useful variables
int zero = 0;
int one = 0;
// Execute loop through by given divisor
for (int state = 0; state < divisor; ++state)
{
// Next state for bit zero
zero = state << 1;
// Next state for bit one
one = zero + 1;
if (zero < divisor)
{
transaction[state][0] = zero;
}
else
{
transaction[state][0] = zero - divisor;
}
if (one < divisor)
{
transaction[state][1] = one;
}
else
{
transaction[state][1] = one - divisor;
}
}
this->remainder = 0;
// Check remainder
this->checkState(dividend, transaction);
if (this->remainder == 0)
{
cout << " (" << dividend << " / " << divisor << ") Are Divisible \n" << endl;
}
else
{
cout << " (" << dividend << " / " << divisor << ") are not divisible \n";
cout << " Remainder is : " << this->remainder << "\n" << endl;
}
}
};
int main()
{
// Test Case
return 0;
}``````

#### input

`````` (21 / 6) are not divisible
Remainder is : 3

(25 / 5) Are Divisible

(14 / 7) Are Divisible

(34 / 3) are not divisible
Remainder is : 1

(54 / 3) Are Divisible
``````
``````// Include namespace system
using System;
/*
Csharp Program for
DFA based division
*/
{
int remainder;
{
this.remainder = 0;
}
// Recursively, find the remainder of divisor
public void checkState(int dividend, int[,] transaction)
{
if (dividend != 0)
{
this.checkState(dividend >> 1, transaction);
this.remainder = transaction[this.remainder,dividend & 1];
}
}
public void divide(int dividend, int divisor)
{
if (divisor <= 0)
{
// That is not working when divisor is negative
return;
}
// Use to collect transaction
int[,] transaction = new int[divisor,2];
// Define useful variables
int zero = 0;
int one = 0;
// Execute loop through by given divisor
for (int state = 0; state < divisor; ++state)
{
// Next state for bit zero
zero = state << 1;
// Next state for bit one
one = zero + 1;
if (zero < divisor)
{
transaction[state,0] = zero;
}
else
{
transaction[state,0] = zero - divisor;
}
if (one < divisor)
{
transaction[state,1] = one;
}
else
{
transaction[state,1] = one - divisor;
}
}
this.remainder = 0;
// Check remainder
this.checkState(dividend, transaction);
if (this.remainder == 0)
{
Console.WriteLine(" (" + dividend + " / " + divisor + ") Are Divisible \n");
}
else
{
Console.Write(" (" + dividend + " / " + divisor + ") are not divisible \n");
Console.WriteLine(" Remainder is : " + this.remainder + "\n");
}
}
public static void Main(String[] args)
{
// Test Case
}
}``````

#### input

`````` (21 / 6) are not divisible
Remainder is : 3

(25 / 5) Are Divisible

(14 / 7) Are Divisible

(34 / 3) are not divisible
Remainder is : 1

(54 / 3) Are Divisible
``````
``````<?php
/*
Php Program for
DFA based division
*/
{
public \$remainder;
public	function __construct()
{
\$this->remainder = 0;
}
// Recursively, find the remainder of divisor
public	function checkState(\$dividend, \$transaction)
{
if (\$dividend != 0)
{
\$this->checkState(\$dividend >> 1, \$transaction);
\$this->remainder = \$transaction[\$this->remainder][\$dividend & 1];
}
}
public	function divide(\$dividend, \$divisor)
{
if (\$divisor <= 0)
{
// That is not working when divisor is negative
return;
}
// Use to collect transaction
\$transaction = array_fill(0, 2, array_fill(0, \$divisor, 0));
// Define useful variables
\$zero = 0;
\$one = 0;
// Execute loop through by given divisor
for (\$state = 0; \$state < \$divisor; ++\$state)
{
// Next state for bit zero
\$zero = \$state << 1;
// Next state for bit one
\$one = \$zero + 1;
if (\$zero < \$divisor)
{
\$transaction[\$state][0] = \$zero;
}
else
{
\$transaction[\$state][0] = \$zero - \$divisor;
}
if (\$one < \$divisor)
{
\$transaction[\$state][1] = \$one;
}
else
{
\$transaction[\$state][1] = \$one - \$divisor;
}
}
\$this->remainder = 0;
// Check remainder
\$this->checkState(\$dividend, \$transaction);
if (\$this->remainder == 0)
{
echo " (".\$dividend." / ".\$divisor.") Are Divisible \n\n";
}
else
{
echo " (".\$dividend." / ".\$divisor.") are not divisible \n";
echo " Remainder is : ".\$this->remainder."\n"."\n";
}
}
}

function main()
{
// Test Case
}
main();``````

#### input

`````` (21 / 6) are not divisible
Remainder is : 3

(25 / 5) Are Divisible

(14 / 7) Are Divisible

(34 / 3) are not divisible
Remainder is : 1

(54 / 3) Are Divisible
``````
``````/*
Node JS Program for
DFA based division
*/
{
constructor()
{
this.remainder = 0;
}
// Recursively, find the remainder of divisor
checkState(dividend, transaction)
{
if (dividend != 0)
{
this.checkState(dividend >> 1, transaction);
this.remainder = transaction[this.remainder][dividend & 1];
}
}
divide(dividend, divisor)
{
if (divisor <= 0)
{
// That is not working when divisor is negative
return;
}
// Use to collect transaction
var transaction = Array(divisor).fill(0).map(() => new Array(2).fill(0));
// Define useful variables
var zero = 0;
var one = 0;
// Execute loop through by given divisor
for (var state = 0; state < divisor; ++state)
{
// Next state for bit zero
zero = state << 1;
// Next state for bit one
one = zero + 1;
if (zero < divisor)
{
transaction[state][0] = zero;
}
else
{
transaction[state][0] = zero - divisor;
}
if (one < divisor)
{
transaction[state][1] = one;
}
else
{
transaction[state][1] = one - divisor;
}
}
this.remainder = 0;
// Check remainder
this.checkState(dividend, transaction);
if (this.remainder == 0)
{
console.log(" (" + dividend + " / " + divisor + ") Are Divisible \n");
}
else
{
process.stdout.write(" (" + dividend + " / " + divisor + ") are not divisible \n");
console.log(" Remainder is : " + this.remainder + "\n");
}
}
}

function main()
{
// Test Case
}
main();``````

#### input

`````` (21 / 6) are not divisible
Remainder is : 3

(25 / 5) Are Divisible

(14 / 7) Are Divisible

(34 / 3) are not divisible
Remainder is : 1

(54 / 3) Are Divisible
``````
``````#  Python 3 Program for
#  DFA based division
def __init__(self) :
self.remainder = 0

#  Recursively, find the remainder of divisor
def checkState(self, dividend, transaction) :
if (dividend != 0) :
self.checkState(dividend >> 1, transaction)
self.remainder = transaction[self.remainder][dividend & 1]

def divide(self, dividend, divisor) :
if (divisor <= 0) :
#  That is not working when divisor is negative
return

transaction = [[0] * (2) for _ in range(divisor) ]
zero = 0
one = 0
#  Execute loop through by given divisor
state = 0
while (state < divisor) :
#  Next state for bit zero
zero = state << 1
#  Next state for bit one
one = zero + 1
if (zero < divisor) :
transaction[state][0] = zero
else :
transaction[state][0] = zero - divisor

if (one < divisor) :
transaction[state][1] = one
else :
transaction[state][1] = one - divisor

state += 1

self.remainder = 0
#  Check remainder
self.checkState(dividend, transaction)
if (self.remainder == 0) :
print(" (", dividend ," / ", divisor ,") Are Divisible \n")
else :
print(" (", dividend ," / ", divisor ,") are not divisible ")
print(" Remainder is : ", self.remainder ,"\n")

def main() :
#  Test Case

if __name__ == "__main__": main()``````

#### input

`````` ( 21  /  6 ) are not divisible
Remainder is :  3

( 25  /  5 ) Are Divisible

( 14  /  7 ) Are Divisible

( 34  /  3 ) are not divisible
Remainder is :  1

( 54  /  3 ) Are Divisible
``````
``````#  Ruby Program for
#  DFA based division
attr_accessor :remainder
def initialize()
self.remainder = 0
end

#  Recursively, find the remainder of divisor
def checkState(dividend, transaction)
if (dividend != 0)
self.checkState(dividend >> 1, transaction)
self.remainder = transaction[self.remainder][dividend & 1]
end

end

def divide(dividend, divisor)
if (divisor <= 0)
#  That is not working when divisor is negative
return
end

#  Use to collect transaction
transaction = Array.new(divisor) {Array.new(2) {0}}
#  Define useful variables
zero = 0
one = 0
#  Execute loop through by given divisor
state = 0
while (state < divisor)
#  Next state for bit zero
zero = state << 1
#  Next state for bit one
one = zero + 1
if (zero < divisor)
transaction[state][0] = zero
else
transaction[state][0] = zero - divisor
end

if (one < divisor)
transaction[state][1] = one
else
transaction[state][1] = one - divisor
end

state += 1
end

self.remainder = 0
#  Check remainder
self.checkState(dividend, transaction)
if (self.remainder == 0)
print(" (", dividend ," / ", divisor ,") Are Divisible \n", "\n")
else
print(" (", dividend ," / ", divisor ,") are not divisible \n")
print(" Remainder is : ", self.remainder ,"\n", "\n")
end

end

end

def main()
#  Test Case
end

main()``````

#### input

`````` (21 / 6) are not divisible
Remainder is : 3

(25 / 5) Are Divisible

(14 / 7) Are Divisible

(34 / 3) are not divisible
Remainder is : 1

(54 / 3) Are Divisible

``````
``````/*
Scala Program for
DFA based division
*/
{
def this()
{
this(0);
}
// Recursively, find the remainder of divisor
def checkState(dividend: Int, transaction: Array[Array[Int]]): Unit = {
if (dividend != 0)
{
checkState(dividend >> 1, transaction);
this.remainder = transaction(this.remainder)(dividend & 1);
}
}
def divide(dividend: Int, divisor: Int): Unit = {
if (divisor <= 0)
{
// That is not working when divisor is negative
return;
}
// Use to collect transaction
var transaction: Array[Array[Int]] = Array.fill[Int](divisor, 2)(0);
// Define useful variables
var zero: Int = 0;
var one: Int = 0;
// Execute loop through by given divisor
var state: Int = 0;
while (state < divisor)
{
// Next state for bit zero
zero = state << 1;
// Next state for bit one
one = zero + 1;
if (zero < divisor)
{
transaction(state)(0) = zero;
}
else
{
transaction(state)(0) = zero - divisor;
}
if (one < divisor)
{
transaction(state)(1) = one;
}
else
{
transaction(state)(1) = one - divisor;
}
state += 1;
}
this.remainder = 0;
// Check remainder
checkState(dividend, transaction);
if (this.remainder == 0)
{
println(" (" + dividend + " / " + divisor + ") Are Divisible \n");
}
else
{
print(" (" + dividend + " / " + divisor + ") are not divisible \n");
println(" Remainder is : " + this.remainder + "\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Test Case
}
}``````

#### input

`````` (21 / 6) are not divisible
Remainder is : 3

(25 / 5) Are Divisible

(14 / 7) Are Divisible

(34 / 3) are not divisible
Remainder is : 1

(54 / 3) Are Divisible
``````
``````/*
Swift 4 Program for
DFA based division
*/
{
var remainder: Int;
init()
{
self.remainder = 0;
}
// Recursively, find the remainder of divisor
func checkState(_ dividend: Int, _ transaction: [
[Int]
])
{
if (dividend  != 0)
{
self.checkState(dividend >> 1, transaction);
self.remainder = transaction[self.remainder][dividend & 1];
}
}
func divide(_ dividend: Int, _ divisor: Int)
{
if (divisor <= 0)
{
// That is not working when divisor is negative
return;
}
// Use to collect transaction
var transaction: [[Int]] =
Array(repeating: Array(repeating: 0, count: 2), count: divisor);
// Define useful variables
var zero: Int = 0;
var one: Int = 0;
// Execute loop through by given divisor
var state: Int = 0;
while (state < divisor)
{
// Next state for bit zero
zero = state << 1;
// Next state for bit one
one = zero + 1;
if (zero < divisor)
{
transaction[state][0] = zero;
}
else
{
transaction[state][0] = zero - divisor;
}
if (one < divisor)
{
transaction[state][1] = one;
}
else
{
transaction[state][1] = one - divisor;
}
state += 1;
}
self.remainder = 0;
// Check remainder
self.checkState(dividend, transaction);
if (self.remainder == 0)
{
print(" (", dividend ," / ", divisor ,") Are Divisible \n");
}
else
{
print(" (", dividend ," / ", divisor ,") are not divisible ");
print(" Remainder is : ", self.remainder ,"\n");
}
}
}
func main()
{
// Test Case
}
main();``````

#### input

`````` ( 21  /  6 ) are not divisible
Remainder is :  3

( 25  /  5 ) Are Divisible

( 14  /  7 ) Are Divisible

( 34  /  3 ) are not divisible
Remainder is :  1

( 54  /  3 ) Are Divisible
``````
``````/*
Kotlin Program for
DFA based division
*/
{
var remainder: Int;
constructor()
{
this.remainder = 0;
}
// Recursively, find the remainder of divisor
fun checkState(dividend: Int, transaction: Array < Array < Int >> ): Unit
{
if (dividend != 0)
{
this.checkState(dividend shr 1, transaction);
this.remainder = transaction[this.remainder][dividend and 1];
}
}
fun divide(dividend: Int, divisor: Int): Unit
{
if (divisor <= 0)
{
// That is not working when divisor is negative
return;
}
// Use to collect transaction
val transaction: Array < Array < Int >> = Array(divisor)
{
Array(2)
{
0
}
};
// Define useful variables
var zero: Int ;
var one: Int;
var state: Int = 0;
while (state < divisor)
{
// Next state for bit zero
zero = state shl 1;
// Next state for bit one
one = zero + 1;
if (zero < divisor)
{
transaction[state][0] = zero;
}
else
{
transaction[state][0] = zero - divisor;
}
if (one < divisor)
{
transaction[state][1] = one;
}
else
{
transaction[state][1] = one - divisor;
}
state += 1;
}
this.remainder = 0;
// Check remainder
this.checkState(dividend, transaction);
if (this.remainder == 0)
{
println(" (" + dividend + " / " + divisor + ") Are Divisible \n");
}
else
{
print(" (" + dividend + " / " + divisor + ") are not divisible \n");
println(" Remainder is : " + this.remainder + "\n");
}
}
}
fun main(args: Array < String > ): Unit
{
// Test Case
}``````

#### input

`````` (21 / 6) are not divisible
Remainder is : 3

(25 / 5) Are Divisible

(14 / 7) Are Divisible

(34 / 3) are not divisible
Remainder is : 1

(54 / 3) Are Divisible
``````

## Resultant Output Explanation

Let's analyze the output of the provided code:

``````(21 / 6) are not divisible
Remainder is: 3

(25 / 5) Are Divisible

(14 / 7) Are Divisible

(34 / 3) are not divisible
Remainder is: 1

(54 / 3) Are Divisible``````

The output consists of two parts: the first part indicates whether the dividend is divisible by the divisor, and the second part shows the remainder if the division is not exact.

For example, when dividing 21 by 6, the output indicates that 21 is not divisible by 6, and the remainder is 3.

## Time Complexity

The time complexity of this algorithm depends on the number of bits in the dividend. Since each bit is processed once, the time complexity is O(log N), where N is the value of the dividend.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post