0

I need to compute a ratio of two number that are computed in a cycle. The problem is that b becomes too big and it is equal to numpy.inf at some point. However, the ratio a/b should exist and not be zero.

for i in range(num_iter):
    a += x[i]
    b += y[i]
return a/b

What are tricks to compute this type of limits?

Please let me know if it is a wrong stackexchange site for the question.

Update:

The loop is finite, I have two arrays x and y that can be analysed in advance on big number or something.

I guess dividing x and y by some large number (rescaling) might work?

ashim
  • 24,380
  • 29
  • 72
  • 96
  • 2
    What does the mathematical series look like? – C.B. Oct 21 '14 at 18:37
  • I do not know, it is a part of an algorithm and values can be arbitrary, the only thing is known that the limit exists – ashim Oct 21 '14 at 18:38
  • What kind of values can go in the "..." spots? Just numbers? arithmetic expressions containing the `a` and `b` variables? `random.randint(0, 1000000)?` If it can be literally anything, then there's simply no generic way to calculate the ratio ahead of time. – Kevin Oct 21 '14 at 18:42
  • 2
    Do you know *anything* about the series? Is it at least well-behaved? – Borodin Oct 21 '14 at 18:42
  • I know that the limit should exist – ashim Oct 21 '14 at 18:44
  • @msh: There are many series that have a limit but aren't computable. Please enlarge the background to this. Is it homework that you have, or is it a physics experiment? – Borodin Oct 21 '14 at 18:48
  • @msh: Okay, so please expand on that. Do you have something that can return arbitrarily-large integers? – Borodin Oct 21 '14 at 18:53
  • Have you looked at the intermediate values of the ratio, before your numbers reach `numpy.inf`? I would be extremely surprised if you didn't already have a very good estimate of `a/b` well before you encounter an error. – cloudfeet Oct 21 '14 at 18:59
  • `a = sum(x[:num_iter]); b = sum(y[:num_iter])` – gboffi Oct 21 '14 at 19:21
  • You have two summations, `a_n = sum(x_i, i=1,...,n)` and similarly `b_n = ...`. If you could devise two analytical functions of the variable `s`, `a(s)` and `b(s)` to which the summations converge for large values of `n`, then you could apply http://en.wikipedia.org/wiki/L'H%C3%B4pital's_rule. – gboffi Oct 21 '14 at 19:34

3 Answers3

0

You don't say what you are adding to a and b each time through the loop, but presumably both values get so large that any error introduced by truncating the increments to integers will be negligible in the limit. This way, you use arbitrary integers rather than floating-point values, which have both an upper bound on their magnitude and limited precision.

for i in range(num_iter):
    a += int(...)
    b += int(...)
return a/b
chepner
  • 497,756
  • 71
  • 530
  • 681
  • You could do something like a += int(10 * ...) and b += int(10*...) to add an additional digit of precision to the summation. Then do 100* for 2 digits, 1000 for 3 and so on. – BKay Oct 21 '14 at 18:52
  • This is a very bad idea. It can produce a systematic rounding error, e.g. `a += int(1)` and `b += int(1.4)` - you'd end up with an `a`:`b` ratio of `1` instead of `1.4`. In fact, for *most* inputs this will give you an inaccurate answer. – cloudfeet Oct 21 '14 at 18:52
  • The only way to avoid such a rounding error would be "dithering", e.g `a += int(... + random.uniform(-0.5, 0.5))`. Without that, this solution is not mathematically sound - however, that still feels incredibly hacky. – cloudfeet Oct 21 '14 at 18:56
0

Building on Chepner's idea, how about tracking the float and the int part separately, then bringing the int part back when it it is larger than 1. Something like this:

for i in range(num_iter):
    afloat += ... - int(...)
    bfloat += ... - int(...)
    a += int(...) + int(afloat)
    b += int(...) + int(bfloat)
    afloat += int(afloat)
    bfloat += int(bfloat)
return a/b
BKay
  • 1,397
  • 1
  • 15
  • 26
0

If a and b have the same length, you know that the ratio of the means is equal to the ratio of the sum. If it isn't, you can use the ratio of the number of items to correct you ratio. 

for i in xrange(num_iter):
    numpy.append(a, ...)
    numpy.append(b, ...)

return (mean(a)/mean(b)) * (float(len(b))/len(a))

It could be slow and it will use more memory, but I think it should work.

If you don't want to save everything, you can calculate the mean for every N elements, and do a weighted mean when you need to calculate it.

asimoneau
  • 695
  • 7
  • 18