News for hackers. Stuff that matters.

A comment on 0.30000000000000004. Parent comment

Re:0.30000000000000004 by dnautics on Monday December 02, 2019 @05:50PM (#21687935)
it's not just that they are expensive, it's that there is a nondetermistic compute time.

Let's say we need to do a comparison. Set

    a = 34241432415/344425151233
and

    b = 45034983295/453218433828
Which is greater?

Or even more feindish, Set

    a = 14488683657616/14488641242046
and

    b = 10733594563328/10733563140768
which is greater?

By what algorithm would you do the computation, and could you guarantee me the same compute time as comparing 2/3 and 4/5?

[ Parent | on HN ]
Re:0.30000000000000004 by WaldoDude on Monday December 02, 2019 @06:32PM (#21688292)
I’m not sure I follow. Isn’t it just two integer multiplications followed by a comparison.

a/b > x/y is the same as ay > xb

Assuming you don’t overflow your integer type.

[ Parent | on HN ]
Re:0.30000000000000004 by atq2119 on Monday December 02, 2019 @06:57PM (#21688451)
> Assuming you don’t overflow your integer type.

There's your answer :)

It's far too easy to overflow your integer type by simply adding a bunch of rationals whose denominators happen to be coprime, or just by multiplying rationals. For this reason, the vast majority of rational implementations use arbitrary precision integers, and of course arithmetic on those isn't constant time.

[ Parent | on HN ]
Re:0.30000000000000004 by _bxg1 on Monday December 02, 2019 @09:47PM (#21689465)
One approach would be to hold on to rationals for as long as possible, to eliminate drift, and then dump them out to the nearest floating-point at the very last moment
[ Parent | on HN ]