Skip to main content

Convert given decimal number into an irreducible fraction

Converting a decimal number into an irreducible fraction is a mathematical operation that involves representing a decimal value as a fraction in its simplest form, where the numerator and denominator have no common factors other than 1. This process is important for accurately representing decimal numbers as fractions, especially when precise fractions are needed for calculations, comparisons, or other purposes.

Problem Statement and Description

The problem is to convert a given decimal number into an irreducible fraction. An irreducible fraction is a fraction where the numerator and denominator have no common factors other than 1. The algorithm should take a decimal number as input and output its equivalent irreducible fraction.

Example

Let's consider an example to understand the problem. Suppose we have a decimal number 0.625 that we want to convert into an irreducible fraction. The algorithm should produce the fraction 5/8, as 0.625 is equivalent to 5/8 in its simplest form.

Idea to Solve the Problem

To solve this problem, we need to develop an algorithm that converts a given decimal number into an irreducible fraction. We'll use the greatest common divisor (GCD) to simplify the fraction. The algorithm will involve the following steps:

  1. Convert the decimal number into its integral and fractional parts.
  2. Calculate the GCD of the fractional part numerator and the desired precision (to avoid floating-point imprecision).
  3. Divide the fractional part numerator and the precision by their GCD to simplify the fraction.
  4. Display the irreducible fraction by combining the integral part with the simplified fractional part.

Pseudocode

Here's the pseudocode for the algorithm:

function gcd(a, b):
    if a == b:
        return a
    else if a == 0:
        return b
    else if b == 0:
        return a
    else if a < b:
        return gcd(a, b % a)
    return gcd(b, a % b)

function fraction(decimal):
    precision = 1000000000
    integral = floor(decimal)
    fractional = decimal - integral
    auxiliary = gcd(round(fractional * precision), precision)
    first = round(fractional * precision) / auxiliary
    second = precision / auxiliary
    display integral * second + first / second

main:
    fraction(15.20)
    fraction(3.9)
    fraction(0.77)
    fraction(9.3)
    fraction(6.5)

Algorithm Explanation

  1. Define the gcd function to calculate the greatest common divisor.
  2. Define the fraction function that takes a decimal as input.
  3. Convert the decimal into integral and fractional parts.
  4. Calculate the GCD of the fractional part numerator and the precision.
  5. Divide the numerator and precision by the GCD to simplify the fraction.
  6. Display the irreducible fraction by combining the integral part with the simplified fractional part.
  7. In the main program, call the fraction function for different test cases.

Program Solution

// Java program for
// Convert given decimal number into an irreducible fraction
public class FractionValue
{
	// Recursive function to return gcd of a and b
	long gcd(long a, long b)
	{
		if (a == b)
		{
			// When both number are same
			return a;
		}
		else if (a == 0)
		{
			// When a is zero then b will be resultant value
			return b;
		}
		else if (b == 0)
		{
			// When b is zero then a will be resultant value
			return a;
		}
		else if (a < b)
		{
			// Recursively find gcd by change parameter value
			return gcd(a, b % a);
		}
		// Recursively find gcd
		return gcd(b, a % b);
	}
	// Convert given decimal into its fraction value
	public void fraction(double number)
	{
		long precision = 1000000000;
		// Get integral part 
		double integral = Math.floor(number);
		// Get fractional part
		double fractional = number - integral;
		// calculate GCD
		long auxiliary = gcd(Math.round(fractional * precision), precision);
		// First resultant part
		long first = Math.round(fractional * precision) / auxiliary;
		// Second resultant part
		long second = precision / auxiliary;
      	System.out.print("\n Given Number : "+number);
		// Display calculated result
		System.out.print("\n Fraction Value : " + ((long)(integral * second) + first) + " / " + second);
	}
	public static void main(String[] args)
	{
		FractionValue task = new FractionValue();
		// Test Cases
		task.fraction(15.20);
		task.fraction(3.9);
		task.fraction(0.77);
		task.fraction(9.3);
		task.fraction(6.5);
	}
}

input

 Given Number : 15.2
 Fraction Value : 76 / 5
 Given Number : 3.9
 Fraction Value : 39 / 10
 Given Number : 0.77
 Fraction Value : 77 / 100
 Given Number : 9.3
 Fraction Value : 93 / 10
 Given Number : 6.5
 Fraction Value : 13 / 2
// Include header file
#include <iostream>
#include <math.h>
using namespace std;

// C++ program for
// Convert given decimal number into an irreducible fraction
class FractionValue
{
	public:
		// Recursive function to return gcd of a and b
		long gcd(long a, long b)
		{
			if (a == b)
			{
				// When both number are same
				return a;
			}
			else if (a == 0)
			{
				// When a is zero then b will be resultant value
				return b;
			}
			else if (b == 0)
			{
				// When b is zero then a will be resultant value
				return a;
			}
			else if (a < b)
			{
				// Recursively find gcd by change parameter value
				return this->gcd(a, b % a);
			}
			// Recursively find gcd
			return this->gcd(b, a % b);
		}
	// Convert given decimal into its fraction value
	void fraction(double number)
	{
		long precision = 1000000000;
		// Get integral part 
		double integral = floor(number);
		// Get fractional part
		double fractional = number - integral;
		// calculate GCD
		long auxiliary = this->gcd(round(fractional *precision), precision);
		// First resultant part
		long first = round(fractional *precision) / auxiliary;
		// Second resultant part
		long second = precision / auxiliary;
		cout << "\n Given Number : " << number;
		// Display calculated result
		cout << "\n Fraction Value : " << ((long)(integral *second) + first) << " / " << second;
	}
};
int main()
{
	FractionValue *task = new FractionValue();
	// Test Cases
	task->fraction(15.2);
	task->fraction(3.9);
	task->fraction(0.77);
	task->fraction(9.3);
	task->fraction(6.5);
	return 0;
}

input

 Given Number : 15.2
 Fraction Value : 76 / 5
 Given Number : 3.9
 Fraction Value : 39 / 10
 Given Number : 0.77
 Fraction Value : 77 / 100
 Given Number : 9.3
 Fraction Value : 93 / 10
 Given Number : 6.5
 Fraction Value : 13 / 2
// Include namespace system
using System;
// Csharp program for
// Convert given decimal number into an irreducible fraction
public class FractionValue
{
	// Recursive function to return gcd of a and b
	long gcd(long a, long b)
	{
		if (a == b)
		{
			// When both number are same
			return a;
		}
		else if (a == 0)
		{
			// When a is zero then b will be resultant value
			return b;
		}
		else if (b == 0)
		{
			// When b is zero then a will be resultant value
			return a;
		}
		else if (a < b)
		{
			// Recursively find gcd by change parameter value
			return this.gcd(a, b % a);
		}
		// Recursively find gcd
		return this.gcd(b, a % b);
	}
	// Convert given decimal into its fraction value
	public void fraction(double number)
	{
		long precision = 1000000000;
		// Get integral part 
		double integral = Math.Floor(number);
		// Get fractional part
		double fractional = number - integral;
		// calculate GCD
		long auxiliary = this.gcd((long)(Math.Round(fractional * precision)), precision);
		// First resultant part
		long first = (long)(Math.Round(fractional * precision) / auxiliary);
		// Second resultant part
		long second = precision / auxiliary;
		Console.Write("\n Given Number : " + number);
		// Display calculated result
		Console.Write("\n Fraction Value : " + ((long)(integral * second) + first) + " / " + second);
	}
	public static void Main(String[] args)
	{
		FractionValue task = new FractionValue();
		// Test Cases
		task.fraction(15.2);
		task.fraction(3.9);
		task.fraction(0.77);
		task.fraction(9.3);
		task.fraction(6.5);
	}
}

input

 Given Number : 15.2
 Fraction Value : 76 / 5
 Given Number : 3.9
 Fraction Value : 39 / 10
 Given Number : 0.77
 Fraction Value : 77 / 100
 Given Number : 9.3
 Fraction Value : 93 / 10
 Given Number : 6.5
 Fraction Value : 13 / 2
<?php
// Php program for
// Convert given decimal number into an irreducible fraction
class FractionValue
{
	// Recursive function to return gcd of a and b
	function gcd($a, $b)
	{
		if ($a == $b)
		{
			// When both number are same
			return $a;
		}
		else if ($a == 0)
		{
			// When a is zero then b will be resultant value
			return $b;
		}
		else if ($b == 0)
		{
			// When b is zero then a will be resultant value
			return $a;
		}
		else if ($a < $b)
		{
			// Recursively find gcd by change parameter value
			return $this->gcd($a, $b % $a);
		}
		// Recursively find gcd
		return $this->gcd($b, $a % $b);
	}
	// Convert given decimal into its fraction value
	public	function fraction($number)
	{
		$precision = 1000000000;
		// Get integral part 
		$integral = floor($number);
		// Get fractional part
		$fractional = $number - $integral;
		// calculate GCD
		$auxiliary = $this->gcd(round($fractional * $precision), $precision);
		// First resultant part
		$first = round($fractional * $precision) / $auxiliary;
		// Second resultant part
		$second = $precision / $auxiliary;
		echo("\n Given Number : ".$number);
		// Display calculated result
		echo("\n Fraction Value : ".(($integral * $second) + $first).
			" / ".$second);
	}
}

function main()
{
	$task = new FractionValue();
	// Test Cases
	$task->fraction(15.2);
	$task->fraction(3.9);
	$task->fraction(0.77);
	$task->fraction(9.3);
	$task->fraction(6.5);
}
main();

input

 Given Number : 15.2
 Fraction Value : 76 / 5
 Given Number : 3.9
 Fraction Value : 39 / 10
 Given Number : 0.77
 Fraction Value : 77 / 100
 Given Number : 9.3
 Fraction Value : 93 / 10
 Given Number : 6.5
 Fraction Value : 13 / 2
// Node JS program for
// Convert given decimal number into an irreducible fraction
class FractionValue
{
	// Recursive function to return gcd of a and b
	gcd(a, b)
	{
		if (a == b)
		{
			// When both number are same
			return a;
		}
		else if (a == 0)
		{
			// When a is zero then b will be resultant value
			return b;
		}
		else if (b == 0)
		{
			// When b is zero then a will be resultant value
			return a;
		}
		else if (a < b)
		{
			// Recursively find gcd by change parameter value
			return this.gcd(a, b % a);
		}
		// Recursively find gcd
		return this.gcd(b, a % b);
	}
	// Convert given decimal into its fraction value
	fraction(number)
	{
		var precision = 1000000000;
		// Get integral part 
		var integral = Math.floor(number);
		// Get fractional part
		var fractional = number - integral;
		// calculate GCD
		var auxiliary = this.gcd(Math.round(fractional * precision), precision);
		// First resultant part
		var first = Math.round(fractional * precision) / auxiliary;
		// Second resultant part
		var second = precision / auxiliary;
		process.stdout.write("\n Given Number : " + number);
		// Display calculated result
		process.stdout.write("\n Fraction Value : " + ((integral * second) + first) + " / " + second);
	}
}

function main()
{
	var task = new FractionValue();
	// Test Cases
	task.fraction(15.2);
	task.fraction(3.9);
	task.fraction(0.77);
	task.fraction(9.3);
	task.fraction(6.5);
}
main();

input

 Given Number : 15.2
 Fraction Value : 76 / 5
 Given Number : 3.9
 Fraction Value : 39 / 10
 Given Number : 0.77
 Fraction Value : 77 / 100
 Given Number : 9.3
 Fraction Value : 93 / 10
 Given Number : 6.5
 Fraction Value : 13 / 2
import math
#  Python 3 program for
#  Convert given decimal number into an irreducible fraction
class FractionValue :
	#  Recursive function to return gcd of a and b
	def gcd(self, a, b) :
		if (a == b) :
			#  When both number are same
			return a
		elif (a == 0) :
			#  When a is zero then b will be resultant value
			return b
		elif (b == 0) :
			#  When b is zero then a will be resultant value
			return a
		elif (a < b) :
			#  Recursively find gcd by change parameter value
			return self.gcd(a, b % a)
		
		#  Recursively find gcd
		return self.gcd(b, a % b)
	
	#  Convert given decimal into its fraction value
	def fraction(self, number) :
		precision = 1000000000
		#  Get integral part 
		integral = math.floor(number)
		#  Get fractional part
		fractional = number - integral
		#  calculate GCD
		auxiliary = self.gcd(round(fractional * precision), precision)
		#  First resultant part
		first = round(fractional * precision) / auxiliary
		#  Second resultant part
		second = precision / auxiliary
		print("\n Given Number : ", number, end = "")
		#  Display calculated result
		print("\n Fraction Value : ", 
              (int)((integral * second) + first) ,
              " / ", (int)(second), end = "")
	

def main() :
	task = FractionValue()
	#  Test Cases
	task.fraction(15.2)
	task.fraction(3.9)
	task.fraction(0.77)
	task.fraction(9.3)
	task.fraction(6.5)

if __name__ == "__main__": main()

input

 Given Number :  15.2
 Fraction Value :  76  /  5
 Given Number :  3.9
 Fraction Value :  39  /  10
 Given Number :  0.77
 Fraction Value :  77  /  100
 Given Number :  9.3
 Fraction Value :  93  /  10
 Given Number :  6.5
 Fraction Value :  13  /  2
#  Ruby program for
#  Convert given decimal number into an irreducible fraction
class FractionValue 
	#  Recursive function to return gcd of a and b
	def gcd(a, b) 
		if (a == b) 
			#  When both number are same
			return a
		elsif (a == 0) 
			#  When a is zero then b will be resultant value
			return b
		elsif (b == 0) 
			#  When b is zero then a will be resultant value
			return a
		elsif (a < b) 
			#  Recursively find gcd by change parameter value
			return self.gcd(a, b % a)
		end

		#  Recursively find gcd
		return self.gcd(b, a % b)
	end

	#  Convert given decimal into its fraction value
	def fraction(number) 
		precision = 1000000000
		#  Get integral part 
		integral = number.floor()
		#  Get fractional part
		fractional = number - integral
		#  calculate GCD
		auxiliary = self.gcd((fractional * precision).round(), precision)
		#  First resultant part
		first = (fractional * precision).round() / auxiliary
		#  Second resultant part
		second = precision / auxiliary
		print("\n Given Number : ", number)
		#  Display calculated result
		print("\n Fraction Value : ", ((integral * second) + first) ," / ", second)
	end

end

def main() 
	task = FractionValue.new()
	#  Test Cases
	task.fraction(15.2)
	task.fraction(3.9)
	task.fraction(0.77)
	task.fraction(9.3)
	task.fraction(6.5)
end

main()

input

 Given Number : 15.2
 Fraction Value : 76 / 5
 Given Number : 3.9
 Fraction Value : 39 / 10
 Given Number : 0.77
 Fraction Value : 77 / 100
 Given Number : 9.3
 Fraction Value : 93 / 10
 Given Number : 6.5
 Fraction Value : 13 / 2
// Scala program for
// Convert given decimal number into an irreducible fraction
class FractionValue()
{
	// Recursive function to return gcd of a and b
	def gcd(a: Long, b: Long): Long = {
		if (a == b)
		{
			// When both number are same
			return a;
		}
		else if (a == 0)
		{
			// When a is zero then b will be resultant value
			return b;
		}
		else if (b == 0)
		{
			// When b is zero then a will be resultant value
			return a;
		}
		else if (a < b)
		{
			// Recursively find gcd by change parameter value
			return gcd(a, b % a);
		}
		// Recursively find gcd
		return gcd(b, a % b);
	}
	// Convert given decimal into its fraction value
	def fraction(number: Double): Unit = {
		var precision: Long = 1000000000;
		// Get integral part 
		var integral: Double = Math.floor(number);
		// Get fractional part
		var fractional: Double = number - integral;
		// calculate GCD
		var auxiliary: Long = gcd(Math.round(fractional * precision), precision);
		// First resultant part
		var first: Long = Math.round(fractional * precision) / auxiliary;
		// Second resultant part
		var second: Long = precision / auxiliary;
		print("\n Given Number : " + number);
		// Display calculated result
		print("\n Fraction Value : " + ((integral * second).toLong + first) + " / " + second);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: FractionValue = new FractionValue();
		// Test Cases
		task.fraction(15.2);
		task.fraction(3.9);
		task.fraction(0.77);
		task.fraction(9.3);
		task.fraction(6.5);
	}
}

input

 Given Number : 15.2
 Fraction Value : 76 / 5
 Given Number : 3.9
 Fraction Value : 39 / 10
 Given Number : 0.77
 Fraction Value : 77 / 100
 Given Number : 9.3
 Fraction Value : 93 / 10
 Given Number : 6.5
 Fraction Value : 13 / 2
// Kotlin program for
// Convert given decimal number into an irreducible fraction
class FractionValue
{
	// Recursive function to return gcd of a and b
	fun gcd(a: Long, b: Long): Long
	{
		if (a == b)
		{
			// When both number are same
			return a;
		}
		else if (a == 0L)
		{
			// When a is zero then b will be resultant value
			return b;
		}
		else if (b == 0L)
		{
			// When b is zero then a will be resultant value
			return a;
		}
		else if (a < b)
		{
			// Recursively find gcd by change parameter value
			return this.gcd(a, b % a);
		}
		// Recursively find gcd
		return this.gcd(b, a % b);
	}
	// Convert given decimal into its fraction value
	fun fraction(number: Double): Unit
	{
		val precision: Long = 1000000000;
		// Get integral part 
		val integral: Double = Math.floor(number);
		// Get fractional part
		val fractional: Double = number - integral;
		// calculate GCD
		val auxiliary: Long = this.gcd(Math.round(fractional * precision), precision);
		// First resultant part
		val first: Long = Math.round(fractional * precision) / auxiliary;
		// Second resultant part
		val second: Long = precision / auxiliary;
		print("\n Given Number : " + number);
		// Display calculated result
		print("\n Fraction Value : " + ((integral * second).toLong() + first) + " / " + second);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: FractionValue = FractionValue();
	// Test Cases
	task.fraction(15.2);
	task.fraction(3.9);
	task.fraction(0.77);
	task.fraction(9.3);
	task.fraction(6.5);
}

input

 Given Number : 15.2
 Fraction Value : 76 / 5
 Given Number : 3.9
 Fraction Value : 39 / 10
 Given Number : 0.77
 Fraction Value : 77 / 100
 Given Number : 9.3
 Fraction Value : 93 / 10
 Given Number : 6.5
 Fraction Value : 13 / 2
import Foundation;
// Swift 4 program for
// Convert given decimal number into an irreducible fraction
class FractionValue
{
	// Recursive function to return gcd of a and b
	func gcd(_ a: Int, _ b: Int) -> Int
	{
		if (a == b)
		{
			// When both number are same
			return a;
		}
		else if (a == 0)
		{
			// When a is zero then b will be resultant value
			return b;
		}
		else if (b == 0)
		{
			// When b is zero then a will be resultant value
			return a;
		}
		else if (a < b)
		{
			// Recursively find gcd by change parameter value
			return self.gcd(a, b % a);
		}
		// Recursively find gcd
		return self.gcd(b, a % b);
	}
	// Convert given decimal into its fraction value
	func fraction(_ number: Double)
	{
		let precision = 1000000000;
		// Get integral part 
		let integral = floor(number);
		// Get fractional part
		let fractional = number - integral;
		// calculate GCD
		let auxiliary = self.gcd(
          Int(round( Double(fractional * Double(precision)))), precision);
		// First resultant part
		let first = Int(round(
          Double(fractional * Double(precision)))) / auxiliary;
		// Second resultant part
		let second = precision / auxiliary;
		print("\n Given Number : ", number, terminator: "");
		// Display calculated result
		print("\n Fraction Value : ", 
              (Int((integral * Double(second))) + first) ,
              " / ", second, terminator: "");
	}
}
func main()
{
	let task = FractionValue();
	// Test Cases
	task.fraction(15.2);
	task.fraction(3.9);
	task.fraction(0.77);
	task.fraction(9.3);
	task.fraction(6.5);
}
main();

input

 Given Number :  15.2
 Fraction Value :  76  /  5
 Given Number :  3.9
 Fraction Value :  39  /  10
 Given Number :  0.77
 Fraction Value :  77  /  100
 Given Number :  9.3
 Fraction Value :  93  /  10
 Given Number :  6.5
 Fraction Value :  13  /  2

Time Complexity

The time complexity of this algorithm primarily depends on the GCD calculation, which has a time complexity of O(log(min(a, b))), where a and b are the two numbers being compared. The rest of the operations in the algorithm involve basic arithmetic and comparisons, which have constant time complexity. Therefore, the overall time complexity of the algorithm is still dominated by the GCD calculation.

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