The question is not extremely Nim-specific, although it could be more than I can think of...
So... I'm trying to figure out whether a number, represented as a rational (with a numerator and a denominator, both 64-bit integers) can be accuretely represented as a floating-point number.
My code:
func canBeCoerced(x: VRational): bool =
let quotient = float(x.num) / float(x.den)
let roundTrip = quotient * float(x.den)
return float(x.num) == roundTrip
And let's say that's how VRational is defined (nothing too fancy):
type
VRational = object
num: int
den: int
Now, the problem is that when I pass e.g. 5401/1800 to the canBeCoerced function above, it returns true. However, the result is: 3.000555555555556 (which is exactly what should return false)
Also see: https://www.wolframalpha.com/input?i=5401%2F1800
What am I missing here?
Thanks for the suggestion!
I just tried one of the proposed solution, since it seemed rather straightforward:
func oddPart(x: int): float =
result = frexp(float(x))[0]
while result mod 1.0 != 0.0:
result *= 2.0
func canBeCoerced(x: VRational): bool =
oddPart(x.num) mod oddPart(x.den) == 0.0
Unfortunately, with that, I'm now having the opposite problem: e.g 5929/1250 returns true (while it can be accurately represented simply as 4.7432).
Hmm... seems like the issue is far more complicated than I initially expected!
To be more specific and exact, a bit of number theory:
The denominator of a fractional number can only be properly represented by a numbering system if that denominator's primes fall with in the base of the numbering system.
So for Base-10, decimal, you can represent any number that is a multiple of 2 or 5. So, the following works:
But the following does NOT work in Base-10:
For example, 1/3 becomes 0.33333.... That is because 3 is a prime not found in 10 (2, 5).
The same thing is true for binary floats, which is Base-2. So, these store just fine:
But these do not:
Those also become repeating numbers. Due to "fancy rounding" measures put in the float library, you will not always notice this. That is why:
var a = 0.1 * 10000
echo $a
var b = 0.0
for _ in 0 ..< 10000:
b += 0.1
echo $b
should display the same number twice. But it won't. You instead get:
1000.0
1000.000000000159
That is because Base-2 cannot support 0.1 (aka 1 / ( 2 * 5) ) because the prime number 5 is in the denominator. A single step of math is "handled" by the rounding function. But after 10000 rounds, the errors of failure-to-store accumulate. It's not a bug. It should be off by 0.000000000159 after 10000 rounds when using an IEEE float64.
OT: When using ancient Babylonian sexagesimal, which is Base-60, one divided by 3 (1/3) is an even number.
OT OT: if "absolute precision" is every really needed, the ideal numbering system uses proper fractions, not points. So, 5401/1800 would be stored as (5401 / 1800).
I don't know of a Nim library that does this, but I've seen it in other languages. It would be the equivalent of:
type
PerfectFloat = object
numerator: BigInt
denominator: BigInt
Multiplication and division would be fast. But addition (and subtraction) would be crazy slow.
Nim's standard library has std/rationals where you can use any integer type you want.