## Microsoft Interview Question

**Country:**United States

+1 please give ur algos only, anyone code from an algo.. so its algos what we should discuss not coding

1 correction in the previous action

find the numerator remove the decimal we will get the numerator

here .125 numerator is 125 if 22.36 then 2236

now find the denominator =10^(number of digit after decimal in numerator) here 10^3=1000

now find the HCF of numerator and denominator

here HCF of 125 and 1000 is 125

now divide the numerator and denominator by HCF

we get the answer

just want to make a comment for all approaches which are based on the following loop:

```
double e = 1.123, // number to convert
eps = 1e-17; // mantissa of dp number
int denom = 1;
while(e - (int)e > eps)
{
denom *= 10;
e *= 10;
printf("e: %f; denom: %d\n", e, denominator);
}
```

since 10 is not exactly representable by floating-point,

the above algorithm is supposed to run forever in some cases because with each multiplication by 10 we introduce a small

error to the mantissa.

for example, try the above loop with e = 1.000002

the output is going to be:

```
e: 10.000020; denom: 10
e: 100.000200; denom: 100
e: 1000.002000; denom: 1000
e: 10000.020000; denom: 10000
e: 100000.200000; denom: 100000
e: 1000002.000000; denom: 1000000
e: 10000020.000000; denom: 10000000
e: 100000200.000000; denom: 100000000
e: 1000002000.000000; denom: 1000000000
e: 10000020000.000002; denom: 1410065408
e: 100000200000.000015; denom: 1215752192
e: 1000002000000.000122; denom: -727379968
e: 10000020000000.001953; denom: 1316134912
e: 100000200000000.015625; denom: 276447232
e: 1000002000000000.125000; denom: -1530494976
e: 10000020000000002.000000; denom: 1874919424
e: 100000200000000016.000000; denom: 1569325056
e: 1000002000000000128.000000; denom: -1486618624
e: 10000020000000002048.000000; denom: -1981284352
e: 100000200000000016384.000000; denom: 1661992960
e: 1000002000000000196608.000000; denom: -559939584
e: 10000020000000001966080.000000; denom: -1304428544
e: 100000200000000023855104.000000; denom: -159383552
e: 1000002000000000272105472.000000; denom: -1593835520
e: 10000020000000002721054720.000000; denom: 1241513984
e: 100000200000000027210547200.000000; denom: -469762048
e: 1000002000000000237745733632.000000; denom: -402653184
e: 10000020000000002377457336320.000000; denom: 268435456
e: 100000200000000023774573363200.000000; denom: -1610612736
e: 1000002000000000272930105720832.000000; denom: 1073741824
e: 10000020000000003010776033918976.000000; denom: -2147483648
....
```

and thus never terminates

```
string void ConvertToRational(double n)
{
if (n == 0)
{
return "0";
}
int denominator = 1;
while ((n - (int)n) != 0)
{
n = n * 10;
denominator *= 10;
}
// Use Euclidean theorm to find gcd: en.wikipedia.org/wiki/Euclidean_algorithm
int numerator = (int)n;
if (denominator % numerator == 0)
{
return string.Format("1/{0}", denominator / numerator);
}
int i = numerator;
int j = denominator;
int diff = Math.Abs(i-j);
while ((i % diff != 0) || (j % diff != 0))
{
if (i > j)
{
i = diff;
}
else
{
j = diff;
}
diff = Math.Abs(i-j);
}
return string.Format("{0}/{1}", numerator/diff, denominator/diff);
}
```

"while ((n - (int)n) != 0)"

I think under some circumstances your alg can run

forever because exact comparison of floating-point numbers

is a common source of errors. This is even more true since

you multiply 'n' by 10 which is not a power-of-two

@Anonymous 1

I am not aware of radix implementation in C#. However can you explain how decimals can work with radix?

@Anonymous 2

n - (int) n will eventually reduce to 0 since we are multiplying n by 10. Normally I would have a > 0 condition but in this case it indeed will be equal once all the digits preceed the decimal.

@Ashish Kaila: that's right if we assume to have an fp number with

very large mantissa (e.g., BigFloat).

Remember that, in floating-point format, any number is stored

in scientific format, i.e.:

`sign * mantissa * 2^{exponent + bias}`

each multiplication by 10 introduces some small error and

these errors tend to accumulate. Thus, comparing two fp-numbers

for equality is, in many cases, meaningless. Just try to run your

algorithm for n = 1.000002

<pre lang="" line="1" title="CodeMonkey59447" class="run-this">import java.math.BigDecimal;

import java.util.Arrays;

public class DoubleToFraction

{

public static void main(String[] args)

{

double number = 314159265 / 358979323.0;

toFraction(number);

}

private static void toFraction(double number)

{

BigDecimal numerator = new BigDecimal(number);

int scale = numerator.scale();

numerator = numerator.movePointRight(scale);

BigDecimal denominator = new BigDecimal(10).pow(scale);

BigDecimal gcd = gcd(numerator, denominator);

numerator = numerator.divide(gcd);

denominator = denominator.divide(gcd);

System.out.println(numerator);

System.out.println(createFractionLine(numerator, denominator));

System.out.println(denominator);

}

private static BigDecimal gcd(BigDecimal num1, BigDecimal num2)

{

return (num2.equals(BigDecimal.ZERO)) ? num1 : gcd(num2, num1.remainder(num2));

}

private static String createFractionLine(BigDecimal numerator, BigDecimal denominator)

{

char[] chars = new char[Math.max(numerator.precision(), denominator.precision())];

Arrays.fill(chars, '—');

return new String(chars);

}

}</pre><pre title="CodeMonkey59447" input="yes">

</pre>

int GCD(int a, int b)

{

assert(a > 0);

assert(b > 0);

int m = a > b ? a : b;

int n = a > b ? b : a;

while(n != 0)

{

int temp = m % n;

m = n;

n = temp;

}

return m;

}

void ConvertDouble(double e)

{

const double diff = 1e-32;

bool flag = false;

if(e < 0)

{

e = -e;

flag = ture;

}

int denominator = 1;

while(e - (int)e) > diff)

{

denominator *= 10;

e *= 10;

}

int fraction = (int)e;

int gcd = GCD(denominator, fraction);

denominator /= gcd;

fraction /= gcd;

if(flag)

fraction = -fraction;

printf("%d/%d\n", fraction, denominator);

}

@ all cc users

- kamal November 15, 2011please give ur approach or algo first and then write the code(code is not required the people using the cc have enough potential to code).

my approach

find the numerator remove the decimal we will get the numerator

here .125 numerator is 125

now find the denominator =10^(number of digit in numerator) here 10^3=1000

now find the HCF of numerator and denominator

here HCF of 125 and 1000 is 125

now divide the numerator and denominator by HCF

we get the answer