Issue24546

Created on **2015-07-01 16:06** by **Serge Anuchin**, last changed **2018-06-27 06:56** by **rhettinger**. This issue is now **closed**.

Files | ||||
---|---|---|---|---|

File name | Uploaded | Description | Edit | |

additional_specs.txt | Serge Anuchin, 2015-07-05 10:16 |

Messages (29) | |||
---|---|---|---|

msg246038 - (view) | Author: Serge Anuchin (Serge Anuchin) | Date: 2015-07-01 16:06 | |

It seems there is minor bug in random.choice. I've got traceback from my server with IndexError from random.choice, but sequence wasn't empty (seq value was: u'\u0411\u0413\u0414\u0416\u0418\u041b\u0426\u042b\u042d\ u042e\u042f\u0410\u0412\u0415\u041a\u041c\u0420\u0422\ u042312456789') Maybe I mistaken, but only explanation that I have for this exception is rounding by int() of random value that was very close to 1. TL;RD: >>> int(0.99999999999999995) 1 >>> seq = 'test' >>> seq[int(0.99999999999999995 * len(seq))] # logic from random.choice IndexError: string index out of range Is it plausible explanation of exception or I'am wrong? |
|||

msg246057 - (view) | Author: Steven D'Aprano (steven.daprano) * | Date: 2015-07-02 03:54 | |

Your example of int(0.99999999999999995) returning 1 is misleading, because 0.999...95 is already 1.0. (1.0 - 1/2**53) = 0.9999999999999999 is the nearest float distinguishable from 1.0. It seems to me that either random() may return 1.0 exactly (although I've never seen it) or that 0.9999999999999999*len(s) rounds up to len(s), which I guess is more likely. Sure enough, that first happens with a string of length 2049: py> x = 0.9999999999999999 py> for i in range(1, 1000000): ... if int(i*x) == i: ... print i ... break ... 2049 However your string has length 35, and it certainly doesn't happen there: py> int(x*len(s)) 34 |
|||

msg246059 - (view) | Author: Tim Peters (tim.peters) * | Date: 2015-07-02 04:05 | |

> random() may return 1.0 exactly That shouldn't be possible. Although the code does assume C doubles have at least 53 bits of mantissa precision (in which case it does arithmetic that's exact in at least 53 bits - cannot round up to 1.0; but _could_ round up if the platform C double has less than 53 bits of precision). > py> x = 0.9999999999999999 > py> for i in range(1, 1000000): > ... if int(i*x) == i: > ... print i > ... break > ... > 2049 Very surprising! Which platform & Python is that? The loop runs to completion on my box: Python 2.7.9 (default, Dec 10 2014, 12:28:03) [MSC v.1500 64 bit (AMD64)] on win32 |
|||

msg246062 - (view) | Author: Tim Peters (tim.peters) * | Date: 2015-07-02 05:19 | |

FYI, where x = 1.0 - 2.**-53, I believe it's easy to show this under IEEE double precision arithmetic: For every finite, normal, double y > 0.0, IEEE_multiply(x, y) < y under the default (nearest/even) rounding mode. That implies int(x*i) < i for every int i > 0 representable as an IEEE double (including monstrous ints like 123456789 << 300). Which makes your output _extremely_ surprising, Steven ;-) |
|||

msg246064 - (view) | Author: Serge Anuchin (Serge Anuchin) | Date: 2015-07-02 07:01 | |

> Which platform & Python is that? Python 2.6.6 (r266:84292, Dec 26 2010, 22:31:48) [GCC 4.4.5] on linux2 Linux li307-195 2.6.39.1-x86_64-linode19 #1 SMP Tue Jun 21 10:04:20 EDT 2011 x86_64 GNU/Linux |
|||

msg246078 - (view) | Author: Steven D'Aprano (steven.daprano) * | Date: 2015-07-02 14:28 | |

On Thu, Jul 02, 2015 at 04:05:45AM +0000, Tim Peters wrote: > Very surprising! Which platform & Python is that? Python 2.7.2 (default, May 18 2012, 18:25:10) [GCC 4.1.2 20080704 (Red Hat 4.1.2-52)] on linux2 I get the same result on Python 2.6 and 3.3, but *not* using Jython or IronPython. Both of those run to completion. Don't you love floating point mysteries? I cannot imagine how confusing it was back in the dark ages pre-IEEE 754. |
|||

msg246080 - (view) | Author: Stefan Krah (skrah) * | Date: 2015-07-02 14:39 | |

> Very surprising! Which platform & Python is that? I'm unable to reproduce this using Linux-amd64, Python 2.7.6, gcc 4.8.2. |
|||

msg246081 - (view) | Author: STINNER Victor (vstinner) * | Date: 2015-07-02 14:44 | |

> Your example of int(0.99999999999999995) returning 1 is misleading On my setup, this number is rounded 1.0: >>> float('0.99999999999999995').hex() '0x1.0000000000000p+0' CPU: Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz OS: Fedora release 22 Python 2.7.10 or 3.4.2 (same result for both versions) |
|||

msg246089 - (view) | Author: Tim Peters (tim.peters) * | Date: 2015-07-02 17:35 | |

Steven, there's something wrong with the arithmetic on your machine, but I can't guess what from here (perhaps you have a non-standard rounding mode enabled, perhaps your CPU is broken, ...). In binary, (2**53-1)/2**53 * 2049 is: 0.11111111111111111111111111111111111111111111111111111 times 100000000001.0 which is exactly: 100000000000.11111111111111111111111111111111111111111 011111111111 I inserted a blank after the 53rd bit. Because the tail (011111111111) is "less than half", under any rounding mode _except_ "to +inf" that should be rounded to the 53-bit result: 100000000000.11111111111111111111111111111111111111111 That's strictly less than 2049, so int() of that should deliver 2048. For a start, is it the multiplication that's broken on your machine, or the int() part? These are the expected hex values (same as the binary values shown above, but easier to get Python to show - and these should be identical across all 754-conforming boxes using the default rounding mode): >>> x = 1.-2.**-53 >>> y = 2049.0 >>> x.hex() '0x1.fffffffffffffp-1' >>> y.hex() '0x1.0020000000000p+11' >>> (x*y).hex() '0x1.001ffffffffffp+11' |
|||

msg246093 - (view) | Author: R. David Murray (r.david.murray) * | Date: 2015-07-02 18:28 | |

"perhaps you have a non-standard rounding mode enabled" I think Mark added code to python3 at least to handle non-standard rounding modes being set, but I'm not sure. |
|||

msg246106 - (view) | Author: Steven D'Aprano (steven.daprano) * | Date: 2015-07-02 23:58 | |

On Thu, Jul 02, 2015 at 05:35:53PM +0000, Tim Peters wrote: > Steven, there's something wrong with the arithmetic on your machine, > but I can't guess what from here (perhaps you have a non-standard > rounding mode enabled, perhaps your CPU is broken, ...). It's not just me. Others have confirmed the same behaviour, but only on 32-bit Linux: https://mail.python.org/pipermail/python-list/2015-July/693481.html Thread begins here: https://mail.python.org/pipermail/python-list/2015-July/693457.html > For a start, is it the multiplication that's broken on your machine, or the int() part? Looks like multiplication: >>> x = 1.-2.**-53 >>> assert x.hex() == '0x1.fffffffffffffp-1' >>> assert (2049.0).hex() == '0x1.0020000000000p+11' >>> (x*2049.0).hex() # Should be '0x1.001ffffffffffp+11' '0x1.0020000000000p+11' I'd like to see what result the OP gets if he runs this. Serge is using Linux, but if I'm reading it right, it looks like a 64-bit Linux. |
|||

msg246109 - (view) | Author: Tim Peters (tim.peters) * | Date: 2015-07-03 00:37 | |

Thanks for the legwork, Steven! So far it looks like a gcc bug when using -m32 (whether ints, longs and/or pointers are 4 or 8 bytes _should_ make no difference to anything in Jason Swails's C example). But it may be a red herring anyway: there's only one chance in 2**53 of getting a random.random() result equal to 1.-2.**-53 to begin with. |
|||

msg246119 - (view) | Author: Tim Peters (tim.peters) * | Date: 2015-07-03 01:41 | |

I'm guessing this is a "double rounding" problem due to gcc not restricting an Intel FPU to using 53 bits of precison: > In binary, (2**53-1)/2**53 * 2049 is: > > 0.11111111111111111111111111111111111111111111111111111 > times > 100000000001.0 > > which is exactly: > > 100000000000.11111111111111111111111111111111111111111 011111111111 The internal Intel "extended precision" format has 64 bits in the mantissa. The last line there has 65 bits in all (53 to the left of the blank, and 12 to the right). Rounding _that_ to fit in 64 bits throws away the rightmost "1" bit, which is "exactly half", and so nearest/even rounding bumps what's left up by 1, leaving the 64-bit: 100000000000.11111111111111111111111111111111111111111 10000000000 in the extended-precision register. Rounding that _again_ to fit in 53 bits then yields the observed 100000000001.0 result. No int i with 0 < i < 2049 produces the same kind of double-rounding surprise. And with that I have to bow out - people have spent many years arguing with gcc developers about their floating-point decisions, and they rarely budge. Why does -m32 have something to do with it? "Just because" and "tough luck" are typically the only responses you'll get ;-) |
|||

msg246132 - (view) | Author: Tim Peters (tim.peters) * | Date: 2015-07-03 05:07 | |

Should also note that double rounding cannot account for the _original_ symptom here. Double rounding surprises on Intel chips require an exact product at least 65 bits wide, but the OP's sequence is far too short to create such a product. (Steven's 2049 just barely requires 12 bits, which when multiplied by a 53-bit value can require 12+53 = 65 bits to hold the full product.) |
|||

msg246164 - (view) | Author: Stefan Krah (skrah) * | Date: 2015-07-03 11:00 | |

Just to defend gcc. :) I still cannot reproduce Steven's problem even with the C example and -m32. Steven's gcc [GCC 4.1.2 20080704 (Red Hat 4.1.2-52)] is very old and probably has quite a lot of distro patches. I'd try a modern vanilla version. |
|||

msg246178 - (view) | Author: R. David Murray (r.david.murray) * | Date: 2015-07-03 14:19 | |

OK, so we don't know what caused the OPs original problem, and at the moment we don't have enough info to figure it out. Serge, you'll have to find some way to get more information on exactly what is failing in order for this issue to make progress. |
|||

msg246252 - (view) | Author: Stefan Krah (skrah) * | Date: 2015-07-04 12:17 | |

People have posted the asm now: https://mail.python.org/pipermail/python-list/2015-July/693509.html The fmull result appears to be the same. The good gcc versions set the control word to "truncate" and then use fistpl (single rounding with the correct mode): fmull -0x10(%ebp) fnstcw -0x1a(%ebp) movzwl -0x1a(%ebp),%eax mov $0xc,%ah mov %ax,-0x1c(%ebp) fldcw -0x1c(%ebp) fistpl -0x20(%ebp) The bad versions dump the result of fmull to memory, using "round-to-nearest" and *then* attempt to truncate with cvttsd2si, which is too late. fmull 0x18(%esp) fstpl 0x8(%esp) cvttsd2si 0x8(%esp),%eax I suspect that there are passages in various standards that allow both behaviors. ;) |
|||

msg246259 - (view) | Author: Mark Dickinson (mark.dickinson) * | Date: 2015-07-04 14:32 | |

Agreed with Tim Peters about this not being possible with fully compliant IEEE 754 arithmetic (see http://stackoverflow.com/a/3041071/270986 for a sketch of a proof), but it's certainly a possibility with double rounding, as Steven's result demonstrates. And 32-bit Linux is currently the worst offender for double rounding: IIRC OS X uses the SSE2 instructions exclusively for floating-point arithmetic, and 64-bit Linux tends to do the same. Windows uses the x87 FPU, but sets the FPU precision to 53-bits, so you don't see double rounding within the normal range (though it's still possible with computations having subnormal results). So I'd say that yes, this *is* a bug in random.choice, though it's one that should show up very rarely indeed. |
|||

msg246264 - (view) | Author: Tim Peters (tim.peters) * | Date: 2015-07-04 15:58 | |

Mark, note that the sequence in the OP's original report only contains 35 elements. That, alas, makes "double rounding" irrelevant to this bug report. That is, while random.choice() can suffer double-rounding surprises in _some_ cases, it cannot in the case actually reported here: in the 64-bit extended-precision format, there are at least 64 - (53 + (35).bit_length()) = 5 trailing zeroes in any possible random.random() * 35 result. IOW, all such results are exact in 64-bit arithmetic, so the first "cut back to 64 bits" rounding is a no-op. |
|||

msg246265 - (view) | Author: Mark Dickinson (mark.dickinson) * | Date: 2015-07-04 16:08 | |

Tim: yes, I agree that this shouldn't happen for the string posted. |
|||

msg246283 - (view) | Author: Raymond Hettinger (rhettinger) * | Date: 2015-07-05 01:19 | |

I would like to close this as "won't fix". Add given the infinitesimal probability of occurrence (and long standing code), I don't think there needs to be a change to the documentation either. |
|||

msg246288 - (view) | Author: Steven D'Aprano (steven.daprano) * | Date: 2015-07-05 02:10 | |

I've been running this snippet for almost 72 hours now: s = u"БГДЖИЛЦЫЭu042eЯАВЕКМРТu042312456789" while True: state = random.getstate() try: a = random.choice(s) except IndexError: break with no results yet. I cannot replicate the original error. |
|||

msg246289 - (view) | Author: Tim Peters (tim.peters) * | Date: 2015-07-05 02:38 | |

Raymond, there are (at least) two bugs here: 1. The original bug report. Nobody yet has any plausible theory for what went wrong there. So "won't fix" wouldn't be appropriate. If the OP can't provide more information, neither a reproducible test case, then after a while closing this report as "works for me" would be appropriate. 2. The "double rounding" bug. That cannot be the cause of the OP's problem, so doesn't really belong in this report. Nobody knows how rare it is. I suspect, but have not proved, that 1. - 2.**-53 is the only random.random() result for which it's possible that double-rounding can cause int(i * random.random()) == i. Given that unlikely - but possible - value, there are at least half a million ints 0 < i < 1000000000 for which equality holds (but only on platforms where the double rounding bug is possible, which doesn't include any platform I use ;-) ). That probably should get a report of its own. It's unintended and unanticipated behavior, causing simple code to raise a wholly unexpected & unpredictable exception. That's "a bug" to me. |
|||

msg246292 - (view) | Author: Steven D'Aprano (steven.daprano) * | Date: 2015-07-05 03:06 | |

I've created a new issue 24567 for the double-rounding bug. I have taken the liberty of copying the nosy list from this issue to the new one, apologies if that is inappropriate. |
|||

msg246296 - (view) | Author: Mark Dickinson (mark.dickinson) * | Date: 2015-07-05 07:18 | |

[Tim] > I suspect, but have not proved, that 1. - 2.**-53 is the only > random.random() result for which it's possible that double-rounding > can cause int(i * random.random()) == i. I'm sure this is true. Any other random value is at most 1 - 2**-52, and we're always going to have (1 - 2**-52) * i <= next_below(i), (where * represents multiplication in the rationals, with unrounded result), and since next_below(i) is representable both in the extended 64-bit precision and the target 53-bit precision, neither of the roundings will change that inequality. |
|||

msg246300 - (view) | Author: Serge Anuchin (Serge Anuchin) | Date: 2015-07-05 10:16 | |

> Serge, you'll have to find some way to get more information on exactly what is failing in order for this issue to make progress. This exception occurred only once and I can't reproduce it. Additional system specs in attachment. |
|||

msg246301 - (view) | Author: Stefan Krah (skrah) * | Date: 2015-07-05 10:31 | |

Any chance that another program (C-extension) had set the FPU control word to an unusual value (24bit prec?). |
|||

msg246335 - (view) | Author: Tim Peters (tim.peters) * | Date: 2015-07-05 19:17 | |

Thanks, Mark! That's convincing. Just as a sanity check, I tried all ints in 1 through 4 billion (inclusive) against 1. - 2.**-52, with no failures. Although that was with ad hoc Python code simulating various rounding methods using scaled integers, so may have its own bugs. |
|||

msg320547 - (view) | Author: Raymond Hettinger (rhettinger) * | Date: 2018-06-27 06:56 | |

Marking this as closed -- the original bug doesn't seem to be reproducible. See additional reasons and discussion in Issue #24567. |

History | |||
---|---|---|---|

Date | User | Action | Args |

2018-06-27 06:56:24 | rhettinger | set | status: open -> closed resolution: works for me messages: + msg320547 stage: resolved |

2015-07-05 20:16:49 | rhettinger | set | assignee: rhettinger -> |

2015-07-05 19:17:33 | tim.peters | set | messages: + msg246335 |

2015-07-05 10:31:26 | skrah | set | messages: + msg246301 |

2015-07-05 10:16:51 | Serge Anuchin | set | files:
+ additional_specs.txt messages: + msg246300 |

2015-07-05 07:18:12 | mark.dickinson | set | messages: + msg246296 |

2015-07-05 03:06:56 | steven.daprano | set | assignee: rhettinger messages: + msg246292 |

2015-07-05 02:38:16 | tim.peters | set | messages: + msg246289 |

2015-07-05 02:10:39 | steven.daprano | set | messages: + msg246288 |

2015-07-05 01:19:02 | rhettinger | set | messages: + msg246283 |

2015-07-04 16:08:49 | mark.dickinson | set | messages: + msg246265 |

2015-07-04 15:58:35 | tim.peters | set | messages: + msg246264 |

2015-07-04 14:32:07 | mark.dickinson | set | messages: + msg246259 |

2015-07-04 12:17:41 | skrah | set | messages: + msg246252 |

2015-07-03 14:19:55 | r.david.murray | set | messages: + msg246178 |

2015-07-03 11:00:35 | skrah | set | messages: + msg246164 |

2015-07-03 05:07:59 | tim.peters | set | messages: + msg246132 |

2015-07-03 01:41:03 | tim.peters | set | messages: + msg246119 |

2015-07-03 00:37:20 | tim.peters | set | messages: + msg246109 |

2015-07-02 23:58:55 | steven.daprano | set | messages: + msg246106 |

2015-07-02 18:28:23 | r.david.murray | set | nosy:
+ r.david.murray messages: + msg246093 |

2015-07-02 17:35:53 | tim.peters | set | messages: + msg246089 |

2015-07-02 14:44:49 | vstinner | set | nosy:
+ vstinner messages: + msg246081 |

2015-07-02 14:39:22 | skrah | set | nosy:
+ skrah messages: + msg246080 |

2015-07-02 14:28:08 | steven.daprano | set | messages: + msg246078 |

2015-07-02 10:54:10 | serhiy.storchaka | set | nosy:
+ serhiy.storchaka |

2015-07-02 07:01:36 | Serge Anuchin | set | messages: + msg246064 |

2015-07-02 06:01:48 | rhettinger | set | assignee: rhettinger -> (no value) |

2015-07-02 05:19:01 | tim.peters | set | messages: + msg246062 |

2015-07-02 04:05:45 | tim.peters | set | nosy:
+ tim.peters messages: + msg246059 |

2015-07-02 03:54:01 | steven.daprano | set | nosy:
+ steven.daprano messages: + msg246057 |

2015-07-01 16:29:13 | rhettinger | set | assignee: rhettinger |

2015-07-01 16:06:30 | Serge Anuchin | create |