# 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)
{
// Test Cases
}
}``````

#### 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()
{
// Test Cases
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)
{
// Test Cases
}
}``````

#### 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()
{
// Test Cases
}
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()
{
// Test Cases
}
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() :
#  Test Cases

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()
#  Test Cases
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
}
}``````

#### 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
{
// Test Cases
}``````

#### 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()
{
// Test Cases
}
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.

## 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.