Talk:Convert decimal number to rational

Name change?

To possibly: "Convert decimal number to rational". To make it more descriptive. --Paddy3118 05:59, 12 June 2011 (UTC)

Or "Convert from decimal into a fraction" --Markhobley 08:34, 12 June 2011 (UTC)

What are the plans for results greater than one? Do we want a "top heavy" fraction or whole number and fractional component? What should 3.5 and 7 look like? Presumably we want "7/2" and "7/1" or do we want "3 1/2" and "7"?

Well, since it is not specified, I would think that it is left to the individual, but giving a fraction that is still reducible, such as 5/10 would not feel right. --Paddy3118 11:42, 12 June 2011 (UTC)

Yeah. We definitely need lowest terms.--Markhobley 12:14, 12 June 2011 (UTC)

Yes - please rename this, something like "Convert Decimal to Fractional type" or even "Convert to Fraction" works. My first reaction to the name was that this was some kind of duplicate task. --Dgamey 11:05, 17 June 2011 (UTC)

Decimal?

Are we talking about only rationals? What about 3.14159265...? --Ledrug 06:36, 12 June 2011 (UTC)

Well if you can express it as a finite decimal expansion ... :-)
--Paddy3118 11:44, 12 June 2011 (UTC)

Presumably we are only working to the precision (or double precision) of the system registers, (or to the number of digits originally provided in numerical string based implementations), so the values would all be rational. --Markhobley 12:28, 12 June 2011 (UTC)

System registers? Double precision? I ain't knowing nuttin' 'bout registers or doubles nohow, noway. The REXX language (for instance) doesn't use floating point, nor registers. It uses whatever precision is in effect, and that may be increased to almost anything pratical (eight million digits is about the useful limit). -- Gerard Schildberger 19:23, 13 August 2012 (UTC)

Definitions: Rationals - the real numbers constructible as ratio of A/B, where A and B are both integers. Irrationals - the real numbers that cannot be expressed as such a ratio.

The set of rationals exactly matches the set of numbers with decimal expansions that either terminate (i.e. fixed length), or become periodic (i.e. written it with a bar over the last N digits).

The set of irrationals exactly matches the set of numbers with decimal expansions that neither terminate nor become periodic.

Therefore, there is no way to put an irrational number into your code as a decimal number, even if you can also indicate number of repeating digits. You *can* say PI or sqrt(2) in most languages, but what you get from those is just the largest (truncated) decimal version that fits into your floating point representation.

To summarize, IMHO, *yes*, only rationals make sense for this task. --Util 14:49, 12 June 2011 (UTC)

Good, I just wanted to clarify whether the task was talking about machine precision floats or any conceptual real numbers, because specifying a "best approximation" for irrationals would make it a lot more complicated. --Ledrug 22:01, 12 June 2011 (UTC)

Bah, I implemented the best approximation method anyway, 10 digit integer fractions are just so useless. The task author really needs to clarify what he had in mind. --Ledrug 01:22, 13 June 2011 (UTC)

Repetitive digit chains and rounding

What do we want to do with chains of repeating sequences such as 0.333333333333? Do we want 111111111111/333333333333 or 333333333333/1000000000000 or do we need to round out the repetitions before evaluation (producing 3/10? or possibly even 1/3). --Markhobley 12:52, 12 June 2011 (UTC)

I recommend allowing a second optional parameter to indicate number of repeating digits. dec2frac(0.1234,2) would mean 0.123434343434... (written as 0.1234 with a bar over the "34), and should convert to 611/4950, while dec2frac(0.1234) or dec2frac(0.1234, 0) would mean *exactly* 0.1234 (1234/10000), which should convert to 617/5000. --Util 13:48, 12 June 2011 (UTC)

For an algorithm to handle such indicated repeating digits, see [1] --Util 15:15, 12 June 2011 (UTC)

It is certainly interesting, but I think it goes well beyond what is in the task description and given in the first, (canonical?), example in BASIC. I read it as needing a routine that can take the given decimal numbers and generate their rational approximations with no need to introduce repeating digit handling. --Paddy3118 15:25, 12 June 2011 (UTC)

Yeah, you are probably right Paddy. The repeating sequence scenario only applies if it occurs across the full width of input. Handling of repetitive digits could be dealt with by a separate handler before this routine is called. A separate task could be to create such a handler. For this task (not the handler task) we could deal just with the conversion, and the output is taken as it is. --Markhobley 16:09, 12 June 2011 (UTC)

Whoops! I posted my Perl 6 solution (that handles rep-digits) before checking here. If the task comes out of Draft status with this decision (no rep-digits) intact, then I will reduce the Perl 6 solution to fit the simpler problem. I think that the Python solution will need similar attention. --Util 16:39, 12 June 2011 (UTC)

It probably won't need trimming. We can probably just add a note that the repetitive sequences are sanitized by this version of the program. --Markhobley 17:25, 12 June 2011 (UTC)

J and best fit

This is a curiosity rather than critism, because I know nothing about J to begin with. My question: how is a floating point stored in J, and how does it determine what a "best fit" is? In the first example 0.518518 turned into a "866492568306r1671094481399" ("r" means "/" I assume?). Why? What about 518518/1000000? --Ledrug 17:57, 14 June 2011 (UTC)

I believe J floats are bog standard ieee floats which means just under 16 decimal digits of precision. And, yes, r means ratio -- it's the first integer divided by the second integer. As for 866492568306 divided by 1671094481399, when you divide that out and compare 866492568306 with 866492568305 and 866492568307, you have to drop down to 11 digits of precision to before the +1 and -1 versions look identical. That means that 866492568306 is roughly accurate to 12 digits of precision. In other words, we might be ignoring up to 16 trailing binary digits with that answer (and apparently the algorithm being used in that version of J apparently requires that we keep over 10 digits of precision).

I have not studied this matter very closely, but this seems like it is related to the way J checks for equality on floating point numbers:

J uses an epsilon which is scaled by the value with the largest magnitude when checking for equality . The idea is that floating point numbers that are meant to be equal are usually quite close. In other words, when the difference between the two floating point values is less than (in the default case) 2^-44 times the larger magnitude value they are "equal". This does not always do the right thing (floating point subtraction can get awful), and can be turned off when the programmer is prepared to deal with proper numerical analysis, but it's usually the right thing to do when using an algorithm that cares about equality in the context of floating point numbers. --Rdm 20:30, 14 June 2011 (UTC)

I see. 2^-44 epsilon makes it sound like J's doulbe is the typical 8 byte IEEE float, so if J were just taking the bits out of the float, the denominator would be a power of 2 or power of 10. It probably did something similar to the continued fraction, but with a rather large denominator limit. For the record, for .518518 my perl code also gives goofy numbers like 30117673588/58084142861 from 10¹¹ on, so it's just a matter of different rounding then. --Ledrug 21:15, 14 June 2011 (UTC)

inaccuracies

The first two examples (and fifth) aren't correctly presented. The left side doesn't (exactly) equal the right side --- close ... but no cigar. Unless, however, the equal sign is replaced with an approximately equal (≈) or similar symbol, or the right side number is represented/indicated with some sort of a repeating fraction symbol(s), or an appended plus sign (or somesuch symbol) is used, or some statement to the effect, n/m = .dddddd to x places. Could it be assumed that the task is asking the program examples to use approximation methods? Then, what precision could/would be used? When using high precision arithmetic, crossing that "line" is really a far, far way down the pike. I was referring the high precision. -- Gerard Schildberger 20:07, 13 August 2012 (UTC)

Given that floating point representation can only exactly represent fractions whose denominators are powers of 2, I think that we have to assume that an approximation is demanded here (and, frankly, this should hold -- that we are dealing with approximations -- in any context where floating point is used to represent fractions [unless all denominators are explicitly declared to be powers of 2], and also where floating point is used to represent integers which are larger than the floating point mantissa [unless, of course, the mantissa times power-of-two multiplier is explicitly declared to have sufficient precision for complete accuracy]). --Rdm 20:26, 13 August 2012 (UTC)