14 Mar 2003 11:31:54 -0500

Related articles |
---|

rational to floating point thant@acm.org (Thant Tessman) (2003-03-09) |

Re: rational to floating point chase@theworld.com (David Chase) (2003-03-14) |

Re: rational to floating point nmm1@cus.cam.ac.uk (2003-03-14) |

Re: rational to floating point thant@acm.org (Thant Tessman) (2003-03-14) |

Re: rational to floating point joachim_d@gmx.de (Joachim Durchholz) (2003-03-14) |

Re: rational to floating point ajo@andrew.cmu.edu (Arthur J. O'Dwyer) (2003-03-14) |

Re: rational to floating point gah@ugcs.caltech.edu (Glen Herrmannsfeldt) (2003-03-14) |

Re: rational to floating point tmk@netvision.net.il (2003-03-14) |

Re: rational to floating point Peter-Lawrence.Montgomery@cwi.nl (2003-03-14) |

Re: rational to floating point francis@thibault.org (John Stracke) (2003-03-14) |

From: | "Arthur J. O'Dwyer" <ajo@andrew.cmu.edu> |

Newsgroups: | comp.programming,comp.compilers |

Date: | 14 Mar 2003 11:31:54 -0500 |

Organization: | Carnegie Mellon, Pittsburgh, PA |

References: | 03-03-035 |

Keywords: | arithmetic |

Posted-Date: | 14 Mar 2003 11:31:54 EST |

On Sun, 9 Mar 2003, Thant Tessman wrote:

*>*

*> This is a math question, but one I hope is relevant to this newsgroup.*

Possibly also comp.programming. Cross-posted.

*> I've been writing an interpreter for a functional programming language*

*> in C++. One of the datatypes it supports is an arbitrary-precision*

*> rational number type. Currently the interpreter displays rational*

*> numbers as the ratio of two integers. I'd like it to display rational*

*> numbers as floating-point numbers whenever the conversion to floating*

*> point won't produce an infinite (repeating) stream of digits.*

*>*

*> The question is: Under what conditions will a rational number produce*

*> an infinite stream of digits for a given base? What I've come up with*

*> is this:*

*>*

*> Converting a rational number to a floating point value is equivalent*

*> to multiplying the numerator and denominator by some number that*

*> converts the denominator to a whole-number power of the base. That is:*

*> b^n = c * d where 'b' is the base, 'd' is the denominator, and 'n' and*

*> 'c' are some whole numbers that satisfy the equation.*

This is absolutely correct. But for interfacing to real computer

languages like C++, you also have the constraint that 'b' is 2 (or

FLT_RADIX) and 'n' is no larger than some fixed value (the number of bits

in the mantissa of a floating-point number; I forget what C++ calls it

exactly).

But I see from your website that you probably want to implement your

own floating-point class also, and you don't care about sizeof(double).

So that constraint isn't as relevant as it might be.

*> I think there is no solution to the above equation if the denominator*

*> of the original rational number and the base contain no prime factors*

*> in common.*

More generally, there is a solution c to (b^n = c*d) *if and only

if* d has no prime factors which are not prime factors of b. (For

example, 1/12 is not terminating in base 4, because 3 does not divide

4. But 1/4 is terminating in base 12, because 2 divides 12.)

*> And I think that this in turn implies that if and only if*

*> gcd(d,b) is 1 and 'd' is not 1, then the original rational number can*

*> only be represented by an infinite stream of digits.*

I don't think that's quite equivalent to what I said above, but you

were on the right track.

*> Is my reasoning sound? Is there a simpler test?*

See above.

*> For the curious, a description and source for my interpreter can be*

*> found at:*

*>*

*> http://www.standarddeviance.com*

*>*

*> My gratitude goes to folks in this newsgroup who have helped improve my*

*> understanding of concepts I put to use building this.*

*>*

*> -thant*

Hope this helps.

-Arthur

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.