3

In my situation I am attempting to divide one float p by another q. The top is a multiple of the bottom and both have these properties:

  1. Exactly representable in decimal
  2. Have at most 3 or 4 significant figures
  3. Are between 1 and 1e-8.

(think, e.g., p=.0014 and q=.00002)

In a perfect world the division would come out to a perfect integer (here 70). But floating point arithmetic is often imperfect.

I would like the simplest, safest, and most efficient method to avoid an error of returning p/q - 1 when I cast the quotient to int.

My best solution right now is to do something like this:

int(p/q + 1e-10)

but that feels unclean and potentially less efficient that what may be possible.

Also, I am aware I can round, but that seems misleading in the code and potentially less efficient than a straight cast of some sort.

Community
  • 1
  • 1
watsonic
  • 3,155
  • 1
  • 27
  • 31
  • 3
    If you need precise floating point math, use the built in `decimal` module. – Peter DeGlopper May 31 '14 at 01:38
  • 2
    Using `decimal` helps if, and only if, you need exact representation of terminating decimal fractions. It does no better than binary floating point at representing one third, or worse still sqrt(2). – Patricia Shanahan May 31 '14 at 02:54
  • hmm.. how is rounding less of a "strait cast" than truncation? – SingleNegationElimination May 31 '14 at 03:18
  • `round()` generates a float which then must be cast to `int` – watsonic May 31 '14 at 03:21
  • @PeterDeGlopper: I implemented your suggestion below. It's not super pretty but perhaps its the safest in the circumstances I outline? How does this compare with the Fraction ansewr Aaron gave? – watsonic May 31 '14 at 03:59
  • Some context could be useful: where is the information that `p` is an exact integer multiple of `q` coming from? Are these financial data? – Mark Dickinson May 31 '14 at 12:36
  • Mark: these are model parameters which I iterate over. – watsonic May 31 '14 at 17:45
  • @PatriciaShanahan's comment is correct - `decimal` is right for terminating decimals, `fraction` can handle rationals. So it depends on what your numbers are. Irrationals are always going to be imprecise. – Peter DeGlopper May 31 '14 at 17:47

4 Answers4

3

Working from an idea in the comment to the question, here is a solution through decimal:

from decimal import Decimal

p = .0014
q = .00002

quotient = int(Decimal(str(p)) / Decimal(str(q)))

which of course results in 70.

Note that the conversion through string appears necessary because of this:

>>>print decimal.Decimal(8.4)
8.4000000000000003552713678800500929355621337890625

whereas

>>>print decimal.Decimal(str(8.4))
8.4
watsonic
  • 3,155
  • 1
  • 27
  • 31
  • 1
    Note that `str` does some rounding on it's own, I think it's about 12 decimal places vs. the 15 that are inherent to floats. – Mark Ransom May 31 '14 at 03:45
  • 3
    This won't help you in cases where `p` and `q` don't originate from numbers with a short, exact decimal representation. For an example, try `p = 4.0 / 3` and `q = 2.0 / 3`. On Python 2, you'll get `1` using this method. Really, if you know the numerator is close to an integer multiple of the denominator, and that that integer isn't huge, `int(round(p / q))` is by far the simplest solution. – Mark Dickinson May 31 '14 at 12:00
  • @MarkDickinson: I will clarify in my question that these are numbers constrained to have certain properties (including exact decimal representation) that correspond to my example. – watsonic May 31 '14 at 18:16
  • @MarkDickinson I am tempted to think you are correct from what I've seen. It seems too heavy handed to resort to either Decimal or Fraction modules to arrive at something I know should be a perfect integer (since p is a multiple of q). – watsonic May 31 '14 at 18:54
2

How you handle these up the point you are doing the division is up to you. Perhaps you should be using Decimal or Fraction objects up to that point, but at the point of evaluating division, Python provides a module for that:

>>> import fractions
>>> fractions.Fraction(.0014/.00002)
Fraction(70, 1)
>>> int(fractions.Fraction(2.3))
2
>>> int(fractions.Fraction(8.35))
8

But after a careful reading of your question, I think your worries are not warranted. If you try to think of a fraction where, due to a rounding error, you would be below an integer that, if you could calculate with higher precision, you would be above, you can't.

For example, there's no way the fraction of numbers given below will ever round below 1:

>>> fractions.Fraction(1.000000000000001)
Fraction(4503599627370501, 4503599627370496)

In a comment, someone suggested arriving at a dividend that is no where near the 1.64. How he arrived at that, he doesn't say, but as I said in my introduction, how you calculate up to the point of division is up to you.

Russia Must Remove Putin
  • 374,368
  • 89
  • 403
  • 331
  • I am thinking of this example: http://stackoverflow.com/a/10011589/695804 so by analogy imagine that `p = .0014` was represented as slightly below .0014 and `q = .00002` was slightly greater than that number. The quotient would be slightly less than 70 and hence when cast would wind up as 69 – watsonic May 31 '14 at 03:22
  • It's easy to find examples where the numerator rounds slightly less than the actual value and the denominator rounds slightly more. I don't think the division is guaranteed to round up in that case. For example `0.0164` becomes `0.01619999999999999912292381054612633306533098220825195` and `0.0054` becomes `0.00540000000000000028588242884097780915908515453338623`; try dividing those and see what you get. – Mark Ransom May 31 '14 at 03:25
  • @MarkRansom please show us the process that leads to that rounding error. – Russia Must Remove Putin May 31 '14 at 13:26
  • Aaron: just try `int(fractions.Fraction(0.0162 / 0.0054))` at the prompt. (I think there's a typo in @MarkRansom's comment: I suspect he meant `0.0162` rather than `0.0164`.) – Mark Dickinson May 31 '14 at 14:27
  • @MarkDickinson yes that's a typo, thanks. And my method is even easier, it's just `'%0.53f' % 0.0162` although in hindsight I needed to print a few more digits. As for how I found number combinations that would be a problem I just used a simple for loop. – Mark Ransom May 31 '14 at 15:14
2

Floating-point division will give an exact answer if the numerator is a multiple of the denominator and the quotient is exactly representable. So dividing the top by the bottom is safe if that's what you're trying to do.

Often, however, you're working with numbers that have been converted from decimal or are the results of some computation. In these cases, you need to figure out how much error can occur in the computation (relative error of 1.11e-16 is a safe bet for conversion from decimal unless the numbers are really tiny) and scale the result up by that before converting to integer.

That is, int((top / bot) * (1 + 2.22e-16)) ought to do what you want when top and bot are in a reasonable range.

tmyklebu
  • 13,915
  • 3
  • 28
  • 57
  • do you have a reference for your first assertion concerning an exact answer? i'd like to see something which states this is true in all cases... – watsonic May 31 '14 at 03:25
  • @watsonic: The IEEE spec specifies that division is correctly rounded. This implies the first sentence of my answer. – tmyklebu May 31 '14 at 03:27
  • if you can provide a reference to a paragraph / section of a spec confirming this i'd be happy to accept your answer – watsonic May 31 '14 at 03:28
  • 2
    I think your first statement is false, or at the very least misleading. The easiest example I can use to refute it is to divide `0.3` by `0.1`. Your recommendation at the end is reasonable though. – Mark Ransom May 31 '14 at 03:31
  • @watsonic: The first paragraph of section 5 of IEEE 754-1985 explicitly states that addition, subtraction, multiplication, division, and square root are correctly-rounded. – tmyklebu May 31 '14 at 03:33
  • @MarkRansom: And how are you representing `0.3` and `0.1` in floating-point? – tmyklebu May 31 '14 at 03:33
  • confirming Mark's statement: in Python 2.7 I see: `>>>int(.3/.1)` producing `2` – watsonic May 31 '14 at 03:35
  • @watsonic: You're not confirming his statement. You're doing arithmetic on rounded values. – tmyklebu May 31 '14 at 03:36
  • @tmyklebu `0.3` evaluates to `0.2999999999999999888977697537484345957636833190917968750` exactly, and `0.1` evaluates to `0.1000000000000000055511151231257827021181583404541015625` exactly. – Mark Ransom May 31 '14 at 03:36
  • I haven't rounded anything. Whatever it is you think I just did, the fact stands that what I want is a solution which returns `3` when employing those numbers to produce an integer representation of the quotient. – watsonic May 31 '14 at 03:39
  • @MarkRansom: Yeah. You're not dividing `0.3` by `0.1`. You're dividing the closest `double` to `0.3` by the closest `double` to `0.1`. And you're getting what you asked for. – tmyklebu May 31 '14 at 14:10
  • @watsonic: You should either round-to-int the quotient or use the thing at the end of my answer. But you're living dangerously here; it's not hard to break either one of these solutions, or any other solution anyone might propose. – tmyklebu May 31 '14 at 14:12
  • @tmyklebu I just realized I misunderstood your top statement. I think it would help if you clarified to say "and the quotient is exactly representable **in binary**". But realistically, how often does it come up that people work with data where they know their quotients are exactly representable in binary? Thats not the case here (in my example for instance). So that statement might be best left out or put at the end of your answer. The second part (mult by a number slightly greater than 1) seems more on point. – watsonic May 31 '14 at 18:42
1

It appears that by far the most straightforward solution is to round to int:

int(round(p/q))

perhaps accompanied on the line by a short comment noting that p is a multiple of q to avoid the wayward implication that p/q is something with potentially significant distance from an integer.

Note that this solution is guaranteed to be perfectly safe since the cast via int() in this circumstance acts on a float which will be an exact representation of an integer, as returned by round(). This exactness is guaranteed up to 253 according to the IEEE floating point standard for double precision which Python float complies with.

It may be microscopically less efficient than what could be cooked up otherwise (a la the suggestion in the question), but certainly more efficient than processing through decimal or fractions modules. And probably on par with other solution that employed an extra multiplication and addition.

Community
  • 1
  • 1
watsonic
  • 3,155
  • 1
  • 27
  • 31