16 ms·
1.5 is the midpoint between 0 and infinity in Ruby
- hrydgard 6y ago"if x and y are doubles and x > y, then we have shown that double_as_int64(x) > double_as_int64(y)" This only applies for numbers of the same sign though. As soon as the sign changes, the relation breaks since floating point numbers use an independent sign bit while int64 is 2's complement.
- lifthrasiir 6y agodouble_as_int64 as defined in the linked source code does take care of the sign so that double_as_int64(x) == -double_as_int64(-x). This is also important for the negative zero case.
- sriram_malhar 6y agoMaybe it isn't wrong after all. Two uncountable infinities are equal!
- petercooper 6y agoMeta: what is the time between the same URLs being considered unique posts on HN now? I think it was 24 hours back in the old days, but seems to be somewhat less now as the post's author submitted it only 9 hours ago: https://news.ycombinator.com/item?id=25224627 https://news.ycombinator.com/item?id=25224627 :-)
- OJFord 6y agoAs I understand it, it depends on traction. That one got only 9 points; I don't know what the bar is, but I think resubmissions get another shot if it's not met. (And if it's really soon after, submitting a duplicate just redirects you to the extant submission and upvotes it for you.)
- karolkozub 6y agoThe following values were inspected: 1 2 4 8 16 32 64 32 48 40 44 42 43 The most surprising part for me is that in the integer search 32 is inspected twice. From my brief testing it seems to only happen with infinite ranges. Is that a bug in bsearch or am I missing something?
- lifthrasiir 6y agoIt shouldn't be a problem but technically you are right that Ruby does one more comparison than needed. My guess is that it would mean to keep the previous value of mid (as in `bsearch_integer_range(prev_mid, mid, 0)` instead of the current `bsearch_integer_range(beg, mid, 0)`) and that might be annoying to do in C.
- progval 6y agoWith a finite range, you can bisect directly by splitting in the middle of the range. With infinite ranges, you can't do that; so the usual way is to start with a small number and increase exponentially until you find a number that is too large; which is what is done here. When you got that number, it becomes the upper bound of a finite interval. So that's a two step process, which we can see here. The first 32 is in the exponential growth step (so is 64), and the second one is in the bisect step. This will always happen exactly once (unless the expected result is 0) and for only the first pivot in the bisect, so it's not that bad; but indeed, they could get rid of it by bisecting on [1/n; n] instead of [0; n], as they already know that 1/n (and numbers lower than 1/n) isn't a valid candidate from the first step.
- MauranKilom 6y ago> they could get rid of it by bisecting on [1/n; n] instead of [0; n], as they already know that 1/n (and numbers lower than 1/n) isn't a valid candidate from the first step. Did you mean [n/2; n]?
- progval 6y agoOops, yes, I did.
- pmarreck 6y agoEvery time I see a bizarre mathematical output I am reminded that IEEE 754 is gross as hell. I just use bigints wherever it's possible to transform the algorithm to work with bigints, and I "render to decimal" in views
- saagarjha 6y agoI disagree: IEEE 754 is quite elegant. The fact that they are monotonically increasing in correspondence to their bit representation is one of the many nice things about it.
- kazinator 6y agoIEEE 754 specifies some not-a-number values X that are not equal to themselves; i.e. such that X != X. The bit pattern is actually not equal to itself: if we compared X bitwise, like with memcmp in C, it would be equal: memcmp(&X, &X, sizeof X) == 0. That obnoxiously violates the philosophical Law of Identity, as we would like to see it applied in programming languages. https://en.wikipedia.org/wiki/Law_of_identity https://en.wikipedia.org/wiki/Law_of_identity
- pmarreck 6y agoThe lack of precision leads to increasing error over time in many contexts (off the top of my head, multiplication and division). I still think that if an algorithm can be rewritten to work with ints instead of floats, it will be served better the vast majority of the time.
- jacobolus 6y agoMultiplication and division of floats creates rounding errors of <1 ulp each time. In most contexts you never need to worry about them. The operations you need to watch out for are addition/subtraction, in cases where your result has much smaller magnitude than your inputs, causing loss of significance. Sometimes great care must be taken in implementing numerical algorithms to avoid this. But this is an inherent problem in numerical computing, not the fault of the floating point format per se.
- hohenheim 6y agoI wondering why Ruby's binary search uses infinity as the max to kick off the search, instead of max float.
- rm445 6y agoThe programmer wrote 'found_value = (0..Float::INFINITY).bsearch do'...
- sevenoftwelve 6y agoFinally, that settles it: ∞ = 3
- OscarCunningham 6y agoThis fact is also used in quantum chromodynamics: https://en.wikipedia.org/wiki/1/N_expansion https://en.wikipedia.org/wiki/1/N_expansion
- w-m 6y agoAnd we know from the bible that π = 3, so in effect π = ∞. This should simplify many things that people have agonized over!
- ultrarunner 6y agoBetter said, we know from the State of Indiana that π = 3. The biblical thing was observation; the State of Indiana codified it in law.
- rednum 6y agoI vaguely remember learning similar fact years ago, but it was phrased something like "There are as many floats in [0, 1] range as in [1, infty]". Leaving aside where exactly "midpoint" of floats lies (either in Ruby's implementation or other languages'): what would be implications of this for writing code dealing with floats? Can I shoot myself in the foot somehow with low precision if numbers I'm using are "too close" to infinity?
- pantulis 6y agoI guess the fact would be something like: "There are as many floats in [0,1] as integers in [1, infty]". Probably you will have problems mixing operations between numbers too close to infinity with numbers too close to zero. But if you are working with floats you are probably going to shoot yourself in the foot anyway unless you understand IEEE floating point arithmetic, precisions and so on, so better stick to Decimals and BigDecimals if you can.
- TeMPOraL 6y agoYes, you can. A good way to think about it is that a floating point number has a fixed amount of significant digits. A 32-bit float has between 6 to 9 significant digits[0]; a 64-bit float ("a double") can represent just double that - i.e. ~16 significant figures. This means you can represent 12345678 and 0.12345678 as 32-bit floats just fine, but if you try to add the two, you'll just get 12345678. But there's also a more subtle case, in which you try to add 1234.5678 to 0.12345678, and lose half of the significant digits from the smaller number. These types of errors are common in calculations dealing with large differences in orders of magnitude, and a part of the common wisdom to not use floats for anything involving money. Another common occurrence of precision errors happens when modelling large 2D or 3D environments in video games. The simplest approach starts with a global coordinate system, in which calculations take place. Since the number of significant digits remains fixed, the further you are from origin, the less precision you have available for your unit of measure of position - meaning the same calculations happening far away from (0, 0, 0) will have more errors than those happening close. A somewhat well-known example of that was[1] Kerbal Space Program - a game that models realistic spaceflight within a fictional solar system. As you ventured further out and visited the most distant celestial bodies, you'd notice your ships would spontaneously shake apart and/or explode, as if physics stopped working. Affectionately called a "Kraken attack", it was due to floating point precision errors - that far out, in the global coordinate system, the difference between two closest representable positions became comparable with the size of parts from which the ships were built. With that big of a delta, physical calculations would round some forces down to zero, and massively magnify others, as simulated objects could suddenly only move in increments comparable with their own size. -- [0] - The limitation is in binary, which doesn't map cleanly to base 10. [1] - I think they got around to mitigating this eventually. One way you can approach such mitigation is by dividing your space into cells (and possibly subcells), each with its own coordinate system, and do as many calculations as you can within these cells, so that everything is close to the origin of their local coordinate system. Then, for (hopefully few) remaining calculations that involve multiple distant cells, you can use larger-precision representations, which are much more computationally expensive.
- simias 6y ago>And of course, 0 is represented in floating-point with all the bits set to 0. +0 that is, -0 has the MSB set. That's one of the potential annoyances of IEEE floats, unlike two's complement integers there are two zeroes.
- atemerev 6y agoIsn't it -1/12 actually?
- Frost1x 6y agoI was trying to remember the situation where in physics, under certain conditions, a proof that shows infinity can be represented numerically as -1/12 (it was some obscure fraction yet after seeing it, I think this was the value). I couldn't for the life of me remember the set of conditions and proof that shows this but it was interesting when reading through it a few years ago.
- deleted 6y ago[deleted]
- atemerev 6y agoIn physics, it is something related to removing divergences in bosonic string theory, I am not an expert in that. Here, however, is a fantastic article that shows how -1/12 is actually derived: https://medium.com/cantors-paradise/the-ramanujan-summation-1-2-3-1-12-a8cc23dea793 https://medium.com/cantors-paradise/the-ramanujan-summation-... (spoiler: it is really easy and could be done by a high schooler).
- cyphar 6y agoThat proof (and the more general statement) is not correct because it makes assumptions about infinite summation of divergent series that are not true. There is a link between the sum of natural numbers -- namely, the analytic continuation of the Reimann Zeta function has Z(-1) = -1/12. But the Zeta function is only defined to equal the sum of inverse powers for Re(z) > 1. And under a specific definition of summation (Ramanujan summation) you can say that "the sum is equal to -1/12" but that isn't the same as normal summation. Mathologer did a fairly in-depth video[1] into why this proof is wrong and what the actual link is between the infinite series and -1/12. The upshot is that even if you use more complicated definitions of summation, you cannot define sums of the kind 1+2+3+... to equal a finite number. If you assume the infinite sum of 1+2+3+... converges to a finite number you can easily prove a contradictory statement using the same summation properties assumed by that proof. Namely: S = 1 + 2 + 3 + ... = -1/12 S2 = S-S = 0 = 1 + 2 + 3 + ... - 1 - 2 - 3 - ... = 0 = 1 + 2 + 3 + ... - 1 - 2 - ... = 0 S2 = 1 + 1 + 1 + 1 + ... = 0 S3 = S2-S2 = 0 = (1-1) + (1-1) + ... = 1 - 1 + 1 - 1 + ... = 0 But we "derived" in the original proof that S3 is equal to 1/2, which is a contradiction. (You could derive S3 is 1/2 from S but that's what the article does in reverse.) [1]: https://youtu.be/YuIIjLr6vUA https://youtu.be/YuIIjLr6vUA
- prionassembly 6y agoThat's because the well known fact that e^e = inf. Therefore log(inf) = e. Ruby is probably rounding up e/2. Proof: the infinite series 1 + 1/2 +1/3! +... is known to converge to e. Now arrange in binomials: (1+1/2)^e + (1/3!)^e + ... this is known to be larger than (1+1/2)^2 + ... = 1 + 1/2 + 1/4 + 1 + 2/3 + 1/9 + ..... But this infinite series contains the series that sums to 2 (1 + 1/2 + 1/4 +...) and so the series that sums to 3, etc. Then it is equal to the sum of all positive integers which is infinite. (This is a joke.)
- DarkWiiPlayer 6y agobeen looking at `e^e = inf` for a minute now and I just don't get the joke. What am I missing?
- colejohnson66 6y agoThat \sum_{n=1}^inf 1/n is actually -1/12 /s
- jojobas 6y ago3 should be enough for everyone.
- aardvark179 6y agoClearly we'll need to some work in TruffleRuby to be fully compatible. I really hope nobody's code depends on this. Infinity 8.988465674311579e+307 4.4942328371557893e+307 2.2471164185778946e+307 1.1235582092889473e+307 5.6177910464447366e+306 ... 32767.999999999996 16383.999999999998 8191.999999999999 4095.9999999999995 2047.9999999999998 1023.9999999999999 511.99999999999994 255.99999999999997 127.99999999999999 63.99999999999999 31.999999999999996 47.99999999999999 39.99999999999999 43.99999999999999 41.99999999999999 42.99999999999999 42.49999999999999 42.24999999999999 42.12499999999999 42.06249999999999 42.03124999999999 42.01562499999999 42.00781249999999 ... 42.00000000000363 42.00000000000181 42.0000000000009 42.00000000000045 42.00000000000022 42.00000000000011 42.00000000000005 42.00000000000002 42.00000000000001 42.0 42.0
- repsilat 6y agoInteresting -- there are more rows (incl removed rows) in yours, because the first step in TFA halves the exponent. I guess it behaves more like binary searching the list of numbers than binary searching the range of numbers, which should be more efficient when the distribution is so heavily skewed.
- aardvark179 6y agoYes, in fact we have a special version of bsearch to handle all the float corner cases, and part of that deals with the max being infinity [0], we can check that and then just try the largest finite floating point number. [0] (https://github.com/oracle/truffleruby/blob/fde88d4019ab837162e15b65f58b0b3b2fd7f65c/src/main/ruby/truffleruby/core/range.rb#L117 https://github.com/oracle/truffleruby/blob/fde88d4019ab83716...)
- stingraycharles 6y agoJust a shout out that I really appreciate the work you guys are doing on GraalVM, especially the polyglot parts. It’s one of the more exciting parts of Graal that I don’t see too many people talk about, it’s usually all about native image and the JIT.
- tromp 6y agoIn surreal numbers [1], the midpoint between 0 and infinity would be the simplest number greater than 0, which is { 0 | } = 1 [1] https://en.wikipedia.org/wiki/Surreal_number https://en.wikipedia.org/wiki/Surreal_number
- npmisdown 6y agoTIL: apart from infinity (number, larger than any real number in absolute value) there are infinitesimal (number, less than any real number in absolute value and not a zero). Edit: also, those infinitesimals were the subject of political and religious controversies in 17th century Europe, including a ban on infinitesimals issued by clerics in Rome in 1632.
- zests 6y agoThose clerics were ahead of their time. They probably would have banned large cardinals as well (infinites so large we can't prove whether or not they exist.)
- teilo 6y agoYou win the internet, sir.
- user-the-name 6y agoI think a lot of cardinals around then were quite large, actually. https://www.alamy.com/portrait-of-cardinal-flavio-chigii-1631-1693-17th-century-cardinal-flavio-chigi-by-jacob-ferdinand-voet-image184942128.html https://www.alamy.com/portrait-of-cardinal-flavio-chigii-163... https://www.pinterest.com/pin/462252349233672807/ https://www.pinterest.com/pin/462252349233672807/
- colejohnson66 6y agoEven with the shortened URLs, I just knew this was going to be some reference to the Catholic church’s cardinals
- ajarmst 6y agoPaging Dr. Cantor. Dr. Georg Cantor. Paging...
- MaxBarraclough 6y agoThe odds of him picking up are infinitesimal.
- recursive 6y agoThis all makes sense. It seems like there would be some special edge cases around the finite/NaN boundary that would be rarely exercised. I wonder if/how those are handled.
- blm 6y agoFrom Python: >>> import numpy as np >>> 1 + np.Inf inf >>> (0 + np.Inf)/2 inf >>> Infinity is not a number it is a concept[1] My math teacher used to say think of infinity like a impossibly large number. An impossibly large number divided by two is still an impossibly large number [1] http://mathforum.org/dr.math/faq/faq.large.numbers.html http://mathforum.org/dr.math/faq/faq.large.numbers.html
- colejohnson66 6y agoWhile you’re correct, you’re being downvoted probably because you’re taking this seriously. I’m sure most everyone here knows infinity isn’t a number, but a concept, but you never know.
- deleted 6y ago[deleted]
- blm 6y agoI think any conversation that says there is halfway between inf and 0 is treating inf like it is a fixed point and therefore a number and not a concept This is why participating on Hacker News conversations are problematic. I think you are talking about downvoting because a persons misunderstands me. Even in your statement you imply by saying "but you never know" that it is possible people aren't being aware of the point I was making
- recursive 6y agoI'm not talking about math. I'm talking about computer numbers, specifically IEEE-754. NaN is represented by a maximal (all ones) exponent, and at least one non-zero in the mantissa. Infinity has the same exponent but an all-zero mantissa. So with a naive comparison, NaN compares greater than infinity. If you only believe output from programming languages, javascript claims that the type of infinity is "number". >>> typeof Number.POSITIVE_INFINITY "number"
- tedunangst 6y agoThis seems inefficient especially if the answer is close to a power of two? You'll spend a lot of time bouncing between exponents instead of refining the mantissa.
- klodolph 6y agoIt's a binary search in a 64-bit search space. Powers of two are no more inefficient than other answers, on average, if you assume the answers are uniformly distributed. You could do an exponential search, which is a reasonable choice and makes logical sense, but the exponential search won't be any faster on average.
- plx211 6y agoC++ :) #include <iostream> #include <limits> double midpoint(double first, double second) { auto firstAsInt = reinterpret_cast < int64_t & > (first); auto secondAsInt = reinterpret_cast < int64_t & > (second); auto mid = (secondAsInt + firstAsInt) / 2; return reinterpret_cast < double & > (mid); } int main() { std::cout << "1.0 <=> 1.5 = " << midpoint(1.0, 1.5) << "\n" << "0.0 <=> inf = " << midpoint(0.0, std::numeric_limits < double > ::infinity()) << "\n"; return 0; }
- colejohnson66 6y agoRant: Technically, that code invokes undefined behavior as you use `reinterpret_cast` to alias variables. The only standards conforming way (prior to `std::bit_cast`[0] in C++20) was to use `memcpy`.[a] `reinterpret_cast` was added for situations where code you have no control over requires a certain type, but you need to force it to take your variable.[b] [a]: As `memcpy` (in addition to reinterpreting bits) copies the bits (although a compiler will most likely optimize it out), it doesn’t violate aliasing rules. [b]: This also requires that the code you give your kludged variable to not read out those bits as what it thinks it is (because aliasing). Kindof pointless because: what’s the point of passing a variable that’s never read? [0]: https://en.cppreference.com/w/cpp/numeric/bit_cast https://en.cppreference.com/w/cpp/numeric/bit_cast
- kazinator 6y agomemcpy certainly violates aliasing rules. You can access an object as an array of bytes, but you can't memcpy an object to one of a different type and then access it as that type without invoking undefined behavior.
- haberman 6y agomemcpy() by itself cannot violate aliasing rules. By definition, char can alias any object. Whether you can access an object that has been memcpy()'d into is a separate question. I can't find specific language about this, but I strongly suspect that the result is implementation-defined or unspecified (not undefined), unless there is a possibility of a trap representation.
- TheRealPomax 6y agoLike every blog post or article that talks about something weird related to IEEE floats, this absolutely needs to find a way to link to "What Every Computer Scientist Should Know About Floating-Point Arithmetic", over on https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.h..., because that's mandatory reading if you're programming.
- piyh 6y agoShorter and at a level the simple masses of programmers will likely work at - https://docs.python.org/3/tutorial/floatingpoint.html#tut-fp-issues https://docs.python.org/3/tutorial/floatingpoint.html#tut-fp...
- TheRealPomax 6y agoHaving the actual explanation of why floats work the way they do, by explaining how the various kinds of numbers map to the various IEEE defined bit patterns, is crucial in understanding, rather than just having read some text. This python article skips over that entirely, making it yet another tutorial about the fact "that" floats are approximations instead of "why" floats are approximations. Spend the time up from to understand the why, especially if you're the simple masses. If you're programming, it pays to properly learn how something that is integral to programming works and what you can therefore expect when you use it. Which will be all the time.
- piyh 6y agoWhen would knowing that they're an approximation ever be inadequate compared to knowing why they're an approximation in the real world for the simple masses? 99.99% of cases the decision goes "floats are fast and memory efficient, but I need full decimal precision, so I'll use the library"
- guyomes 6y agoAnother short introduction to floating point number with pictures giving a better intuition of their distribution among real numbers: https://blogs.mathworks.com/cleve/2014/07/07/floating-point-numbers/ https://blogs.mathworks.com/cleve/2014/07/07/floating-point-...