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
-
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 thetransaction
array to determine the next state based on the current bit. -
The
divide
function takes the dividend and divisor as inputs. It initializes thetransaction
array and sets up the DFA's states and transitions. -
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. -
The
checkState
function is then called to calculate the remainder using the DFA transitions. -
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
*/
public class DFAdivision
{
int remainder;
public DFAdivision()
{
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)
{
DFAdivision task = new DFAdivision();
// Test Case
task.divide(21, 6);
task.divide(25, 5);
task.divide(14, 7);
task.divide(34, 3);
task.divide(54, 3);
}
}
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
*/
class DFAdivision
{
public: int remainder;
DFAdivision()
{
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()
{
DFAdivision *task = new DFAdivision();
// Test Case
task->divide(21, 6);
task->divide(25, 5);
task->divide(14, 7);
task->divide(34, 3);
task->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
// Include namespace system
using System;
/*
Csharp Program for
DFA based division
*/
public class DFAdivision
{
int remainder;
public DFAdivision()
{
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)
{
DFAdivision task = new DFAdivision();
// Test Case
task.divide(21, 6);
task.divide(25, 5);
task.divide(14, 7);
task.divide(34, 3);
task.divide(54, 3);
}
}
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
*/
class DFAdivision
{
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()
{
$task = new DFAdivision();
// Test Case
$task->divide(21, 6);
$task->divide(25, 5);
$task->divide(14, 7);
$task->divide(34, 3);
$task->divide(54, 3);
}
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
*/
class DFAdivision
{
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()
{
var task = new DFAdivision();
// Test Case
task.divide(21, 6);
task.divide(25, 5);
task.divide(14, 7);
task.divide(34, 3);
task.divide(54, 3);
}
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
class DFAdivision :
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() :
task = DFAdivision()
# Test Case
task.divide(21, 6)
task.divide(25, 5)
task.divide(14, 7)
task.divide(34, 3)
task.divide(54, 3)
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
class DFAdivision
# Define the accessor and reader of class DFAdivision
attr_reader :remainder
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()
task = DFAdivision.new()
# Test Case
task.divide(21, 6)
task.divide(25, 5)
task.divide(14, 7)
task.divide(34, 3)
task.divide(54, 3)
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
*/
class DFAdivision(var remainder: Int)
{
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 = {
var task: DFAdivision = new DFAdivision();
// Test Case
task.divide(21, 6);
task.divide(25, 5);
task.divide(14, 7);
task.divide(34, 3);
task.divide(54, 3);
}
}
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
*/
class DFAdivision
{
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()
{
let task: DFAdivision = DFAdivision();
// Test Case
task.divide(21, 6);
task.divide(25, 5);
task.divide(14, 7);
task.divide(34, 3);
task.divide(54, 3);
}
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
*/
class DFAdivision
{
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
{
val task: DFAdivision = DFAdivision();
// Test Case
task.divide(21, 6);
task.divide(25, 5);
task.divide(14, 7);
task.divide(34, 3);
task.divide(54, 3);
}
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.
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.
New Comment