13 ms·
Python rounds float values by converting them to string and then back
- bishala 7y agoRelated thread on Twitter https://twitter.com/whitequark/status/1164395585056604160 https://twitter.com/whitequark/status/1164395585056604160
- Jenz 7y agoI dunno, how efficient is this?
- coldtea 7y agoSo efficient that nobody really cared about or mentioned it all those decades, so there's that...
- zsrxx 7y agoIt's Python, it's not like anybody is going to complain about performance, because nobody expects any.
- mkl 7y agoMany people complain about performance, and enormous amounts of effort have been spent on improving it, successfully. People do expect good performance, and can achieve it in many useful cases.
- fernandotakai 7y agoi mean, if you are worried about python's rounding number performance, you are probably using numpy already (which has a different implementation that is faster).
- Shorel 7y agoI used to complain about performance, as I remember the abysmally bad performance of Zope (Python web framework) back in 2003 -2004. It made me write off that language for about a decade. Benchmarking Python3 code reveals that there have been some quite noticeable improvements.
- coldtea 7y agoIf this implementation was a bottleneck in anything, people would have complained, as they have in other areas in Python. There are performance improvements in places people complain about all the time. Besides you missed the part where this is used in other speed-critical places, like protobuf, the K&P implementation, etc.
- ThePadawan 7y agoI agree - my takeaway is "float-to-string and string-to-float conversion is probably faster than I thought"
- ben509 7y agoCompared to base=10^places, multiply, truncate, divide? Horriby inefficient.
- dagw 7y agoSure, but their approach is on the other hand more correct. All numerical code reaches a point where you have to balance performance vs. correctness, and here cpython has chosen correctness over speed.
- ben509 7y agoThey're creating a sequence of digits and then truncating. If you want to replicate that precisely, you could use an accumulator and a loop to do the same thing. At least then you could break early.
- ben509 7y agoIt's slower than native python. %timeit round(12335423552.33, -6) %timeit int(12335423552.33 / 1_000_000.0) * 1_000_000.0 500 ns ± 3.88 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 219 ns ± 1.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
- dagw 7y agoWell obviously the approach round() takes is slower than the naive approach. The whole point of doing it the way round() does it is that it gives the correct answer in cases where the naive approach fails.
- latchkey 7y agohttps://0.30000000000000004.com/ https://0.30000000000000004.com/
- TekMol 7y agoComputers can only natively store integers, so they need some way of representing decimal numbers. Really? How do computers "natively" store integers?
- tyingq 7y agoIt seems to just be layman shorthand for storing (not huge) integers as binary isn't lossy.
- Dylan16807 7y agoStoring integers as decimal (which computers can do easily) isn't lossy either.
- viraptor 7y agoI believe that's where "natively" comes in. If you store it in binary, you can operate on the values as numbers. If you do some decimal conversion, it's a blob of data. (Yes, there are BCD instructions but they're massively limited)
- SmellyGeekBoy 7y agoDecimal numbers are still "stored as binary" at the silicon level.
- mondoshawan 7y agoUnless you're on an IBM 1401... :D
- Merrill 7y ago
- ChrisSD 7y agoMaybe I'm missing something but what's wrong with rounding floats this way?
- f00zz 7y agoThat's what round(3) is for
- masklinn 7y agoround(3) can only round to an integer. Python's round works to an arbitrary decimal position. It would previously scale up, round (ceil/floor really) then scale down. That turned out to induce severe precision issues: https://bugs.python.org/issue1869 https://bugs.python.org/issue1869
- f00zz 7y agoThat's the first thing I'd try, multiply by 10^digits, round, divide by 10^digits. Thanks for the link.
- bottled_poe 7y agoThe two concerns I have are performance and correctness. I don’t know enough about the implementation of round(3) to know... perhaps someone else does?
- dagw 7y agoThis approach is used specifically because of correctness. Doing things the 'obvious' way with round(3) or truncation introduces precision problems in corner cases.
- emsy 7y agoPython already doesn't have the best performance. If you need to round a lot of floats in a loop you better bring some time.
- 7y ago
- fs111 7y agoApples libc used to shell-out to perl in a function: https://github.com/Apple-FOSS-Mirror/Libc/blob/2ca2ae74647714acfc18674c3114b1a5d3325d7d/gen/wordexp.c#L192 https://github.com/Apple-FOSS-Mirror/Libc/blob/2ca2ae7464771...
- f00zz 7y ago/* XXX this is _not_ designed to be fast */
- vectorEQ 7y agoit is hard to do without a subshell). It is probbably just plan a Bad Idea to call in anything setuid, or executing remotely. */ laughing so hard :')
- imglorp 7y agoO_o
- tus88 7y agoThat's hilarious. You're not supposed to go the other direction libc!
- stefan_ 7y agoI thought this is what the Unix philosophy is supposed to be all about. (Realistically, calling wordexp should just abort the program. Now I actually want to make a hacked up musl that aborts in all the various "libc functions no one should ever use" and see how far I get into a Ubuntu boot..)
- f00zz 7y agoWould be pretty awesome if Perl called wordexp(3) somewhere along this code path
- microtherion 7y agoI seem to recall that perl used to shell out to /bin/sh for some related task...
- coldtea 7y agoSeems to be one of the best ways to go about it. From the comment in protobuf source (which does the same thing as Python), mentioned in the Twitter thread: (...) An arguably better strategy would be to use the algorithm described in "How to Print Floating-Point Numbers Accurately" by Steele & White, e.g. as implemented by David M. Gay's dtoa(). It turns out, however, that the following implementation is about as fast as DMG's code. Furthermore, DMG's code locks mutexes, which means it will not scale well on multi-core machines. DMG's code is slightly more accurate (in that it will never use more digits than necessary), but this is probably irrelevant for most users. Rob Pike and Ken Thompson also have an implementation of dtoa() in third_party/fmt/fltfmt.cc. Their implementation is similar to this one in that it makes guesses and then uses strtod() to check them. (...) https://github.com/protocolbuffers/protobuf/blob/ed4321d1cb33199984118d801956822842771e7e/src/google/protobuf/stubs/strutil.cc#L1174-L1213 https://github.com/protocolbuffers/protobuf/blob/ed4321d1cb3...
- ChrisLomont 7y ago>Seems to be one of the best ways to go about it. The C/C++ standards do not require formatting to round correctly or even be portable. I recently had an issue where a developer used this method to round floats for display, and there were differences on PC and on Mac. It literally rounded something like 18.25 to 18.2 on one platform and 18.3 on the other. This led to all sorts of other bugs as some parts of the program used text to transmit data, which ended up in weird states. The culprit was this terrible method. If you want anything approaching consistency or predictability, do not use formatting to round floating point numbers. Pick a numerically stable method, which will be much faster of done correctly. Coincidentally, C/C++ do not require any of their formatting and parsing routines to round-trip floating point values correctly (except the newly added hex formatted floats which are a direct binary representation, and some newly added function allowing an obscure trick I do not recall at the moment... )
- eesmith 7y ago> The C/C++ standards do not require formatting to round correctly or even be portable. The linked-to method uses PyOS_snprintf(). Its documentation at https://docs.python.org/3/c-api/conversion.html https://docs.python.org/3/c-api/conversion.html says: """PyOS_snprintf() and PyOS_vsnprintf() wrap the Standard C library functions snprintf() and vsnprintf(). Their purpose is to guarantee consistent behavior in corner cases, which the Standard C functions do not."""
- shellac 7y agoOpenJDK BigDecimal::doubleValue() goes via a string in certain situations https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/math/BigDecimal.java#L3667 https://github.com/openjdk/jdk/blob/master/src/java.base/sha...
- SloopJon 7y agoI just ran into a similar booby trap the other day: whereas BigDecimal::BigDecimal(double) does the full decimal expansion, BigDecimal::valueOf(double) goes through Double::toString(double), which is generally a lot fewer digits.
- Noe2097 7y agoWell, the problem is precisely that rounding as it is generally conceived, is expressed in base 10 - as we generally conceive numbers including floating point ones in base 10. Yet at the lowest level, the representation of numbers is in base 2, including floating point ones. It is imaginable, would be more correct and efficient to perform rounding (or flooring or ceiling, for that matter) in base 2, but it would be that more difficult to comprehend when dealing with non integers in code. Rounding in base 10 needs some form of conversion anyway, going for the string is one way that is, at least, readable (pun intended).
- bhouston 7y agoIn my experience there are few things slower that float to string and string to float. And it seems so unnecessary. I always implemented round to a specific digit based on the built-in roundss/roundsd functions which are native x86-64 assembler instructions (i.e. https://www.felixcloutier.com/x86/roundsd https://www.felixcloutier.com/x86/roundsd). I do not understand why this would not be preferable to the string method. float round( float x, int digits, int base) { float factor = pow( base, digits ); return roundss( x * factor ) / factor; } I guess this has the effect of not working for numbers near the edge of it's range. One could check this and fall back to the string method. Or alternatively use higher precision doubles internally: float round( float x, int digits, int base ) { double factor = pow( base, digits ); return (float)( roundsd( x * factor ) / factor ); } But then what do you do if you have a double rounded and want to maintain all precision? I think there is likely some way to do that by somehow unpacking the double into a manual mantissa and exponent each of which are doubles and doing this manually - or maybe using some type of float128 library (https://www.boost.org/doc/libs/1_63_0/libs/multiprecision/doc/html/boost_multiprecision/tut/floats/float128.html https://www.boost.org/doc/libs/1_63_0/libs/multiprecision/do...)... But changing this implementation now could cause slight differences and if someone was rounding then hashing this type of changes could be horrible if not behind some type of opt-in.
- messe 7y agoUsing native x86_64 instructions isn't portable.
- jharger 7y agoWhy not have optimized versions that use native instructions when available, and then fall back to the portable version when they are not?
- messe 7y agoI'm unsure as to why they don't do that, I suspect it's because nobody using Python has found floating-point rounding to be a bottleneck yet.
- zelly 7y agoThis is what we are promised will make trucks drive themselves and usher in the 4th industrial revolution.
- StreamBright 7y agoI am not sure if people understand what kind of hellhole is IT in general.
- Scarblac 7y agoThere is an XKCD for that: https://www.xkcd.com/2030/ https://www.xkcd.com/2030/
- olooney 7y agoPython?
- d--b 7y agoNote that there is a fallback version that doesn't use strings. This is definitely something that's been thought through.
- analog31 7y agoMy quick impression is that the choice of a rounding algorithm is relative to the purpose that it serves. For instance, floor(x + 0.5) is good enough in many applications. In some cases, rounding is performed for the primary purpose of displaying a number as a string, in which case it can't be any less complicated than the string conversion function itself.
- raphlinus 7y agoFun fact: floor(x + 0.5) rounds 0.49999997 to 1.0 (this is 32 bit floats, the same principle applies to 64). Most libraries have slower than ideal round conversion because of historical dross; modern chips have a very fast SIMD round instruction but its behavior doesn't exactly match libc round. See https://github.com/rust-lang/rust/issues/55107 https://github.com/rust-lang/rust/issues/55107 for a deeper discussion.
- dwheeler 7y agoI just tried this on Python3 on a 64-bit x86 system: import math x = 0.49999999999999994 print(x-0.5) print(math.floor(x+0.5)) I got these printouts: -5.551115123125783e-17 1 So yes, something less than 1/2, with 1/2 added to it, has a floor of 1 in floating point math. Yet another reminder that floating point calculations are approximations, and not exact.
- deleted 7y ago[deleted]
- e12e 7y agoIn Julia it's easy to see the difference between promoting to full number tower and sticking to 64 floats (ed: note difference in result 0 vs 1): julia> using Benchmarktools julia> @btime floor(0.49999999999999997+0.5) 0.027 ns (0 allocations: 0 bytes) 1.0 julia> @btime floor(0.49999999999999997+BigFloat(0.5)) 280.594 ns (6 allocations: 336 bytes) 0.0 julia> @code_native floor(0.49999999999999997+BigFloat(0.5)) .text ; ┌ @ floatfuncs.jl:152 within `floor' subq $24, %rsp movq %rsi, 16(%rsp) movq (%rsi), %rax ; │┌ @ floatfuncs.jl:152 within `#floor#543' movq %rax, (%rsp) movabsq $jl_system_image_data, %rax movq %rax, 8(%rsp) movabsq $japi1_round_16005, %rax movabsq $jl_system_image_data, %rdi movq %rsp, %rsi movl $2, %edx callq *%rax ; │└ addq $24, %rsp retq nopw %cs:(%rax,%rax) ; └ julia> @code_native floor(0.49999999999999997+0.5) .text ; ┌ @ floatfuncs.jl:152 within `floor' ; │┌ @ floatfuncs.jl:152 within `#floor#543' ; ││┌ @ floatfuncs.jl:152 within `round' vroundsd $9, %xmm0, %xmm0, %xmm0 ; │└└ retq nopw (%rax,%rax) ; └
- deckar01 7y ago`blob/master` isn't a suitable permalink. Use the first few letters of the commit hash so the line numbers and code are still relevant when this file inevitably gets modified.
- ericfrederich 7y agoI was looking once at Python and Redis and how numbers get stored. I remember Python would in the end send Redis some strings. I dove pretty deep and found that Python floats when turned into a string and then back are exactly the same float. I remember even writing a program that tested every possible floating point number (must have only been 32 bit). I think I used ctypes and interpreted every binary combination of 32 bits as a float, turned it into a string, then back and checked equality. A lot of them were NaN.
- dagw 7y agoA lot of them were NaN. I seem to recall that ~0.5% of the IEEE 32 bit float space is NaN.
- ekimekim 7y agoA NaN is any value where the 7-bit (for 32-bit floats) exponent is all 1s, except for +/-inf. So a quick approximation is that 1/128 ~= 0.78% of the space is NaN. That means there's 25 bits that we can change while still being either a NaN or an inf. But two of those values are infs, so we need to remove them. Divide that by the entire range and we have (2^25 - 2) / 2^32 = 16777215/2147483648, or about 0.78124995%.
- mark-r 7y agoChecking equality on NaN doesn't work the way it does for other numbers. Your test might have had a fatal flaw.
- science404 7y agoMisleading title is misleading... CPython rounds float values by converting them to string and then back
- duckerude 7y agoPyPy does it too: https://bitbucket.org/pypy/pypy/src/2fc0a29748362f2a4b99ab57aa551fc906878a6b/rpython/rlib/rfloat.py#lines-113 https://bitbucket.org/pypy/pypy/src/2fc0a29748362f2a4b99ab57... Jython instead uses BigDecimal::doubleValue: https://github.com/jythontools/jython/blob/b9ff520f4f65231209d5200c22724516a72e75f2/src/org/python/core/util/ExtraMath.java#L39 https://github.com/jythontools/jython/blob/b9ff520f4f6523120... But as another comment noted, BigDecimal::doubleValue can pull a similar trick: https://news.ycombinator.com/item?id=20818586 https://news.ycombinator.com/item?id=20818586
- jancsika 7y agoA bit on topic... Is there a phrase for the ratio between the frequency of an apparent archetype of a bug/feature and the real-world occurrences of said bug/feature? If not then perhaps the "Fudderson-Hypeman ratio" in honor of its namesakes. For example, I'm sure every C programmer on here has their favored way to quickly demo what bugs may come from C's null-delimited strings. But even though C programmers are quick to cite that deficiency, I'd bet there's a greater occurrence of C string bugs in the wild. Thus we get a relatively low Fudderson-Hypeman ratio. On the other hand: "0.1 + 0.2 != 0.3"? I'm just thinking back through the mailing list and issue tracker for a realtime DSP environment that uses single-precision floats exclusively as the numeric data type. My first approximation is that there are significantly more didactic quotes of that example than reports of problems due to the class of bugs that archetype represents. Does anyone have some real-world data to trump my rank speculation? (Keep in mind that simply replying with more didactic examples will raise the Fudderson-Hypeman ratio.)
- pvg 7y agoWhat's the 'class' of the second thing? Numerics/fp bugs of all stripes are super common. Just often less crashy or noticeable.
- acoye 7y agoAnother pragmatic aspect of Python as I see it.
- seamyb88 7y agoAm I the only one grimacing at the lack of curlies around if/else scope? Just good practice!
- dahart 7y agoNot entirely unlike how one of the better ways to deep-copy a JSON object in Javascript is json.parse(json.stringify(obj))
- kstenerud 7y agoThis is where decimal floating point really shines. Since the exponential portion is base 10, it's trivially easy to round the mantissa. The only silly part of ieee754 2008 is the fact that they specified two representations (DPD, championed by IBM, and BID, championed by Intel) with no way to tell them apart.
- deleted 7y ago[deleted]