rationalize returns curious/incorrect values

[rickhg12hs]

$ ./julia 
               _
   _       _ _(_)_     |  A fresh approach to technical computing
  (_)     | (_) (_)    |  Documentation: http://docs.julialang.org
   _ _   _| |_  __ _   |  Type "help()" to list help topics
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 0.3.0-prerelease+1713 (2014-02-24 06:46 UTC)
 _/ |\__'_|_|_|\__'_|  |  Commit 0f55c2f* (0 days old master)
|__/                   |  i686-redhat-linux

julia> versioninfo()
Julia Version 0.3.0-prerelease+1713
Commit 0f55c2f* (2014-02-24 06:46 UTC)
Platform Info:
  System: Linux (i686-redhat-linux)
  CPU: Genuine Intel(R) CPU           T2250  @ 1.73GHz
  WORD_SIZE: 32
  BLAS: libopenblas (DYNAMIC_ARCH NO_AFFINITY)
  LAPACK: libopenblas
  LIBM: libopenlibm

julia> nextfloat(0.1)
0.10000000000000002

julia> rationalize(Int128,nextfloat(0.1))
1//10

julia> nextfloat(0.1) - rationalize(Int128,nextfloat(0.1))
1.3877787807814457e-17

Seems like a much better pair of Int128's exists.

Here's what Sage returns where both numerator and denominator fit in Int64's.

sage: QQ(RDF("0.1")+RDF("0.1").ulp())
379250494936463/3792504949364629

Here's another rationalize issue:

julia> rationalize(Int128,nextfloat(BigFloat("0.1")))
0//1

julia> BigFloat("0.1")
1.000000000000000000000000000000000000000000000000000000000000000000000000000002e-01 with 256 bits of precision

julia> nextfloat(BigFloat("0.1"))
1.000000000000000000000000000000000000000000000000000000000000000000000000000013e-01 with 256 bits of precision

julia> 

[vtjnash]

related to #2960

how odd -- I was contemplating ways of improving Rational on my drive to work this morning.

[rickhg12hs]

There seem to be several Type issues within the rationalize function that can cause errors and limit the achievable tolerance tol.

[StefanKarpinski]

The rationalize function is kind of a disaster. It needs a lot of work. I'll take a crack at it soon if no one else gets there first.

[vtjnash]

Since you'll probably get to it first, I'll add my thought here on how to improve Rational.

---

First, make Rational take any Number type as a type parameter (instead of Integer). Rational{Float64} would be the new default output type for rationalize (and most other implicit ctors)

Rational{F<:FloatingPoint} would use a pair of floating point numbers for storage and be defined as follows. The point of this is to give much better support for avoiding overflow of most operations without much effort by taking full advantage of the FPU, while maintaining the ability to divide numbers without approximation (but gracefully dropping digits as necessary). Before and after each operation, the mantissa bits would be redistributed to make optimal use of the storage -- for BitsTypes, this would involve direct bit manipulations for higher precisions; for other types, it would only be able to perform simple operations.

Rational{I<:Integer} would then be free to take the existing behavior, but rigorously defining the overflow behavior to be useful, sane, and predictable.

Rational{C<:Complex} would also be valid, although I cannot immediately describe how it would work

---

Alternatively, we could represent

type Rational{I<:Integer}
  top::I
  bot::I
  mantissa::Int8
end

And do much the same operations, but then we need to handle all of the overflow in the CPU / Julia. And we aren't able to make use of the difference between Float64/Int64 to alter the behavior of the overflow characteristics of the type and it has alignment issues which will often waste space. (If you can't tell, I like the first option)

[jiahao]

I think Complex{Rational} would generally be preferred over Rational{Complex}, since we already have Complex{Real} and Rational <: Real, and the latter can always be rationalized into a Complex//Real form which can be easily expressed as Complex{Rational}.