Skip to main content

DFA based division

Here given code implementation process.

// 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
Last updated on by Kalkicode




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.

New Comment