programming question! Options

[pebkac]

Ok, so I'm taking Desrosiers (yeah, he sucks) for CS 1412 and I'm working on a programming assignment right now (in C#).

What I basically have to do is create a class that stores a fraction. One of the things it's supposed to do is take a floating point number and convert that to a fraction. What my class basically does is round the floating point number to 5 decimal places, then multiplies it by 100,000. It then uses the resulting integer as the numerator and 100,000 as the denominator and simplifies that.

That works fine for the most part, but what I would also like to be able to do is have it recognize .33333 as 1/3, .66667 as 2/3, 1.33333 as 4/3, etc.

I can take the modulus of the floating point number and see if the remainder is zero, but I think that way would be really prone to rounding errors.

I don't necessarily have to implement that (he said that the method can have limitations as long as we document them), but it would be nice if I could do that. Does anyone have any advice?

[Spectatrix]

If it's got a repeating digit (e.g. 1/3 = 0.333, 2/3 = 0.666, 1/6 = 0.1666), etc:

Call the floating point number x.
Multiply it by 10 to shift the decimal point over one. Call this y.

y-x will get rid of the repeating part of the floating point number. Thus you'll have 9x = some rational fraction. Then you can plug this into your remaining stuff. Rational fraction * 100000 as your numerator, 900000 as your denominator. Simplify.

Got that general algorithm from here: http://www.webmath.com/dec2fract.html Plug in a decimal number to see a sample work-through.

Edit: This is ONLY for irrational numbers with a single repeating digit. If it's a repeating sequence (e.g. 1/11 = 0.090909...) then you'd need to multiply by a power of 10 equal to the number of digits that are repeated. 100x for two digits (like 1/11), 1000x for three digits, etc. Might be more complicated than you want to implement.

This post has been edited by Spectatrix: Feb 1 2008, 03:06 PM

[Jim]

If it's got a repeating digit (e.g. 1/3 = 0.333, 2/3 = 0.666, 1/6 = 0.1666), etc:

Call the floating point number x.
Multiply it by 10 to shift the decimal point over one. Call this y.

y-x will get rid of the repeating part of the floating point number. Thus you'll have 9x = some rational fraction. Then you can plug this into your remaining stuff. Rational fraction * 10000 as your numerator, 90000 as your denominator. Simplify.

Got that general algorithm from here: http://www.webmath.com/dec2fract.html Plug in a decimal number to see a sample work-through.

That program is borked. Put in an irrational number and see what happens. My example was .4657101685

It appears that there is a certain threshold the program can take (which is understandable). However, the programmers should have seen this and then had the output be something different saying that the limit has been reached instead of giving me -(2/-4) as the answer.

[2wolUTT]

That program is borked. Put in an irrational number and see what happens. My example was .4657101685

It appears that there is a certain threshold the program can take (which is understandable). However, the programmers should have seen this and then had the output be something different saying that the limit has been reached instead of giving me -(2/-4) as the answer.

That's what I said.

[Spectatrix]

Oh here we go, better example (scroll to the bottom): http://math2.org/math/general/arithmetic/fradec.htm

Need to convert a repeating decimal to a fraction? Follow these examples:
Note the following pattern for repeating decimals:
0.22222222... = 2/9
0.54545454... = 54/99
0.298298298... = 298/999
Division by 9's causes the repeating pattern.

Note the pattern if zeros preceed the repeating decimal:
0.022222222... = 2/90
0.00054545454... = 54/99000
0.00298298298... = 298/99900
Adding zero's to the denominator adds zero's before the repeating decimal.

To convert a decimal that begins with a non-repeating part, such as 0.21456456456456456..., to a fraction, write it as the sum of the non-repeating part and the repeating part.
0.21 + 0.00456456456456456...
Next, convert each of these decimals to fractions. The first decimal has a divisor of power ten. The second decimal (which repeats) is convirted according to the pattern given above.
21/100 + 456/99900
Now add these fraction by expressing both with a common divisor
20979/99900 + 456/99900
and add.
21435/99900
Finally simplify it to lowest terms
1429/6660
and check on your calculator or with long division.
= 0.2145645645...

This post has been edited by Spectatrix: Feb 1 2008, 03:14 PM

[Mommy]

Im posting in this thread so I feel smart

[theIncredibleEdi...]

My advice...pick a new major.

[impala454]

interesting project... now I must do it.. ass.

[pebkac]

Oh here we go, better example (scroll to the bottom): http://math2.org/math/general/arithmetic/fradec.htm

This is all well and good, but first I have to get the program to recognize that the number is repeating. I could probably analyze the number digit by digit, but as this isn't the primary focus of the project, I don't want to go into that much depth. I could also see if the remainder is 0 if I divide by a set group of integers, but that may not be of much help as there will probably be a significant number of rounding errors.

[zetec]

Derosiers does suck. He was supposed to be my advisor, but he was NEVER in his office, EVER. Even during his hours. Every time i've had to talk to Sherri instead. (Sherri rocks.)

[Jim]

Derosiers does suck. He was supposed to be my advisor, but he was NEVER in his office, EVER. Even during his hours. Every time i've had to talk to Sherri instead. (Sherri rocks.)

This is truth. Super truth.

Also, regarding the repeating number bit, you should make it an array, then, and do some fancy array manipulation.

[blaarg]

This is all well and good, but first I have to get the program to recognize that the number is repeating.

That's easy to do with a loop depending on how you handle the number.
shrug*

Also, regarding the repeating number bit, you should make it an array, then, and do some fancy array manipulation.

this is what I mean when I say "depending on how you handle the number"

[pebkac]

Meh, I sent Derosiers an email and he basically told me not to worry about it. Oh well, one less thing I have to worry about.

[impala454]

I haven't gotten around to doing this yet (reformatted back to xp from vista, super bowl, etc etc), but if you want to recognize a pattern, use the Regex class.

[zetec]

[impala454]

Finally got around to this in some bored time at work. Works pretty damn good so far. Feel free to break it and let me know what did it.

CODE

using System;
using System.Collections.Generic;
using System.Text;
//-------------------------
using System.Text.RegularExpressions;
using System.Collections;

namespace FractionConvert
{
    class Program
    {
        static void Main(string[] args)
        {
            Fraction f = new Fraction();
            double d = 0;
            Double.TryParse(args[0], out d);
            Fraction.TryParse(d, out f);
            Console.WriteLine(f.ToString());
        }
    }

    class Fraction
    {
        int m_nNumerator;
        int m_nDenominator;
        bool m_bNegative;
        double m_dDecimal;

        public Fraction()
        {
            m_nNumerator = 0;
            m_nDenominator = 0;
            m_dDecimal = 0;
            m_bNegative = false;
        }

        public Fraction(double DecimalToConvert)
        {
            m_nNumerator = 0;
            m_nDenominator = 0;
            m_dDecimal = DecimalToConvert;
            m_bNegative = false;

            ParseFraction();
        }

        public static bool TryParse(double DecimalInput, out Fraction FractionOutput)
        {
            try
            {
                FractionOutput = new Fraction(DecimalInput);
            }
            catch (Exception)
            {
                FractionOutput = new Fraction(0);
                return false;
            }

            return true;
        }

        public override string ToString()
        {
            if(m_bNegative)
                return string.Format("-{0}/{1}", m_nNumerator, m_nDenominator);
            else
                return string.Format("{0}/{1}", m_nNumerator, m_nDenominator);
        }

        private void ParseFraction()
        {
            if (m_dDecimal == 0)
            {
                m_nNumerator = 0;
                m_nDenominator = 1; // this could be any number really
                return;
            }

            string Whole = "";
            string Decimal = m_dDecimal.ToString();

            // strip off the minus sign if there is one
            if (Decimal[0] == '-')
            {
                m_bNegative = true;
                Decimal = Decimal.Substring(1, Decimal.Length - 1);
            }

            // split out the whole number, no need to parse that
            if (Decimal.Contains("."))
            {
                Whole = Decimal.Split('.')[0];
                Decimal = Decimal.Split('.')[1];
            }

            string Pattern = GetPattern(Decimal);

            int ParseInt = 0;
            int Divisor = 1;
            ArrayList Divisors = new ArrayList();

            if (!Int32.TryParse(Pattern, out ParseInt))
            {
                throw new Exception("Not a valid decimal number");
                return;
            }

            while (ParseInt > Divisor)
            {
                if (ParseInt % Divisor == 0)
                    Divisors.Insert(0, Divisor);

                Divisor++;
            }

            int WholeNumber = 0;
            Int32.TryParse(Whole, out WholeNumber);

            // if we only have one divisor, obviously it's 1
            if (Divisors.Count == 1)
            {
                m_nNumerator = 1;
                m_nDenominator = ParseInt;
                return;
            }

            foreach (int n in Divisors)
            {
                if (10 % n == 0)
                {
                    if(Pattern.Length <= 1)
                        m_nDenominator = 10 * n / ParseInt;
                    else
                        m_nDenominator = (Pattern.Length - 1) * (int)Math.Pow(10, (double)n+1) / ParseInt;

                    if (WholeNumber > 0)
                        m_nNumerator = m_nDenominator * WholeNumber + n;
                    else
                        m_nNumerator = n;
                    break;
                }
            }
        }

        private string GetPattern(string Decimal)
        {
            // the accuracy can't be any better than half the number of digits!
            //if (m_nAccuracy > Decimal.Length / 2)
            int Accuracy = Decimal.Length / 2;

            string Pattern = "";
            int NumRepeats = 0;
            int MeasuredAccuracy = 0;
            int MaxRepeats = 0;

            for (int i = 1; i <= Accuracy; i++)
            {
                NumRepeats = 0;

                Pattern = Decimal.Substring(0, i);
                for (int j = 0; j <= Decimal.Length - Accuracy; j += Pattern.Length)
                {
                    if (Decimal.Substring(j, Pattern.Length) == Pattern)
                        NumRepeats++;
                    else
                        break;
                }
                if (NumRepeats >= MaxRepeats)
                {
                    MaxRepeats = NumRepeats;
                    MeasuredAccuracy = Pattern.Length;
                }
            }

            // if we didn't find the pattern more than once, there is no pattern
            if (MaxRepeats <= 1)
                return Decimal;
            else
                return Decimal.Substring(0, MeasuredAccuracy);
        }
    }
}

[Spectatrix]

Too long. Cliff notes?

(I kid)

[pebkac]

Interesting. I can see why Desrosiers told me not to worry about it now. When he showed us his version of this program, he didn't even implement the function at all because it was too "ambiguous."

At any rate, it's pretty helpful to know how to actually do that.

[impala454]

Too long. Cliff notes?

(I kid)

DO IT WITH LESS CODE THEN BITCH



oh and actually didn't use regexes, so that "Using Regexes" line at the top can be removed.

[Spectatrix]

DO IT WITH LESS CODE THEN BITCH



oh and actually, didn't use regexes, so that "Using Regexes" line at the top can be removed.

OK MAYBE I WILL!

[zetec]

I was right about to say, why aren't you using regular expressions again?