1.5 is the midpoint between 0 and infinity in Ruby
blog.peterzhu.ca
blog.peterzhu.ca
https://docs.python.org/3/tutorial/floatingpoint.html#tut-fp...
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.
https://blogs.mathworks.com/cleve/2014/07/07/floating-point-...
• tan maps (0, π/2) onto (0, ∞), and tan(π/4) = 1.
• f(x) = x/(1 - x) maps (0, 1) onto (0, ∞), and f(1/2) = 1.
• exp is an isomorphism from the reals under addition to the positive reals under multiplication. 0 is the natural "midpoint" of the reals under addition, and exp(0) = 1.
(Closely related to that last one: when dealing only with positive numbers (and their limits 0 and ∞), it's natural to think of their group operation, multiplication, for which 1 is the identity, creating a symmetry between the numbers smaller than 1 and the numbers larger than 1 under reciprocation.)
If this was true:
tan maps (0, π/2) onto (0, ∞), and tan(π/4) = 1
Wouldnt it imply that
tan(π/8) would be halfway between 0 and 1 ie .5?
By my calculations it is 0.414 or √2 - 1
ALso with:
• f(x) = x/(1 - x) maps (0, 1) onto (0, ∞), and f(1/2) = 1.
wouldnt this mean that f(0.25) is supposed to be half way between 0 and 1 or .5. However f(0.25) = 0.25/0.75 = 1/3
It implies that tan(π/8) would be "halfway" between 0 and 1 in this sense of what "halfway" means. In this sense, 0.5 is not halfway between 0 and 1, 0.414 is.
It's easier to visualize it. You're standing on the roof of a 1-meter-tall building on a flat earth with a perfectly clear atmosphere. If you look straight out (90°) you can see to infinity (tan 90°). If you look down (0°) you can see where you are (tan 0°). If you look halfway between those (45°), you can see 1 (tan 45°) meter straight in front of you. But if you look halfway down again, you won't see exactly 0.5 meters, will you?
The original issue at hand is to talk sensibly about “half way” between 0 and infinity. But in the standard way we think about distance between numbers, there’s obviously no way to do that — you can’t add and subtract real numbers to infinity!
So, implicitly what’s happening here is that by talking about a map between a finite interval and (0,inf), we are equipping (0,inf) with a new, special definition of distance between numbers. This is called a metric.
Usually, when we talk about the distance between x and y, we mean `d(x,y) = |x-y|` — this is called the Euclidean metric (in 1 dimension).
Here, we’ve introduced a new metric on (0,inf): `d2(x,y) = |tan^-1(x) - tan^-1(y)|/(pi/8)`
The half way point between 0 and 1 under the Euclidean metric is 0.5. The half way point between 0 and 1 under our fancy new metric d2 is ~0.414.
TL;DR: You can generalize the notion of “distance between two numbers”, using distance functions called metrics. Under the typical metric, the half way point between 0 and 1 is 0.5. Under our cool new infinite-tan metric, the half way point between 0 and 1 is ~0.414.
tan(π/8) = √2 - 1, not 1/2, but the value is indeed halfway between 0 and 1 if you take the distance function to be
d(a, b) = |b - a| / (√(1 + a²)√(1 + b²)) or
d(a, b) = |b - a| / |1 + ab|
(These are chordal distance or stereographic distance, respectively, when the real number line is used to represent points on a circle under stereographic projection.)
The halfway point is 0.5 when you use the distance function d(a, b) = |b - a|.
Traditionally one distinguishes between rational, algebraic, and transcendental numbers; e is transcendental. This tree is related to continued fraction expansions. Any number is a limit of a path in this tree, and one can talk about the pattern in the path from a CS automata theory point of view. Now e comes out one of the easier limits.
> In surreal numbers [1], the midpoint between 0 and infinity would be the simplest number greater than 0, which is { 0 | } = 1
But { 0 | ω } = 1, right?
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.
https://www.alamy.com/portrait-of-cardinal-flavio-chigii-163... https://www.pinterest.com/pin/462252349233672807/
tiny = infinitesimal
huge = infinity
N = number to be bucketed
tiny <= N < 10 --> bucket 1
10 <= N < 20 --> bucket 2
...
X <= N < huge --> last bucket
As for how common they are, we learn about them in any introductory calculus course when defining derivatives. You come across the idea whenever discussing limits, if somewhat obliquely.
If I learned about it in high school math, and again in "real" math courses at my university, I'd say it's pretty standard.
Also, you seem to be conflating "common" with "standard". "standard" is a mathematical term. Infinitesimal are handwavy in standard analysis (epsilon-delta are the rigorous alternative), but exist rigorously in nonstandard analysis.
There are other instances where I've had a need for such a smallest positive number, where logic is simplified as opposed to checking for 0 in a special way. Whether there's an agreed upon term for that, I know where I've found value in programming tasks.
When I need such a thing, it is almost invariably in comparisons, so I am not doing arithmetic with multiple instances of that smallest representable positive number.
Philosophical problems surrounding the perplexing concept of infinity were already hotly debated by the ancient Greeks. Aristotle made an ontological distinction between actual and potential infinities, and argued that actual infinity cannot exist but potential infinity can. This was also the consensus position of later scholars, and became a sticking point in the acceptance of calculus because infinitesimals (and infinite sums of them) were an example of the ontologically questionable actual infinities.
As I mentioned before, standard modern analysis is based on limits, not infinitesimals, and requires no extension of real numbers. Indeed the limit definition of calculus only requires the concept of potential infinities, so philosophers should be able to rest easy! But infinitesimals still occur in our notation which is largely inherited from Leibniz, however. We say that the derivative of y(x) is dy/dx, or the antiderivative of y(x) is ∫ y(x) dx, and while acknowledging that dy and dx are not actual mathematical objects, just syntax, we still do arithmetic on them whenever it's convenient to do so! For example, when we make a change of variables in an integral, we can substitute x = f(t) for some f, and then say dx/dt = f'(t) and "multiply by dt" to get dx = f'(t) dt to figure out what we should put in the place of the "dx" in the integral.
Actual infinitesimal numbers are not dead, either, they're used in a branch of analysis called nonstandard analysis which formalizes them in the logically rigorous manner that is now expected from mathematics.
________
¹ Not that they had a rigorous theory of real numbers, either, that came in the 19th and early 20th century. In fact what we now understand as formal, axiomatized math didn't really exist before the 19th century at all!
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[0] (https://github.com/oracle/truffleruby/blob/fde88d4019ab83716...)
Both solutions make sense... the blog post refers to a ieee<->integer representation hack that likely finds answers faster, because it more quickly finds the values that tend to be in realistic numbers. It works by doing a binary search of all possible values representable in floating point (of which there are more for smaller numbers, due to the design tradeoff of IEEE floating point).
The TruffleRuby binary search solution is also "correct" in its own way, in that it's binary searching using the actual floating point values themselves.
EDIT: It will also be probing to the ULP level, which the print could be rounding to 42.0. That could explain why there are at least two checks of "42.0".
The following values were inspected:
1
2
4
8
16
32
64
32
48
40
44
42
43
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.
Did you mean [n/2; n]?
In fact, if you're checking N, it's guaranteed that N/2 has already been checked, and the next best step should be (3/4)N; in this case 48.
(And if it's really soon after, submitting a duplicate just redirects you to the extant submission and upvotes it for you.)
+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.
See a random video showcasing the issue here: https://youtu.be/D2XX2ZnRk8M?t=197
You can see all the moving elements jerking around as they "snap" to the next available float value.
A common fix for this issue is to use two sets of coordinates: you can for instance represent your world as a grid with fixed-size cells, then you translate all your models into the local cell before computing anything, this way you always have good enough precision since you effectively limit the amplitude of your floats. Of course I handwave many complications here, such as what happens when you're at the edge of a cell for instance, but it's workable.
There's a lot of interesting problems that arise when making a 3d game vs a 2d one.
Isn't this in practise creating a double-precision float by adding a second "significant figure" in a "base float" system?
It's somewhat reminiscent of segmented memory in a way.
> creating a double precision float ... ?
This added top-level is uniformly distributed - so yes, it's a more precise float, but no, it's not a direct analogue.
You can't represent infinite precision with finite bits so you must run into an issue eventually.
The visible universe (according to Wikipedia) is 8.8 * 10^26 meters or about 5.4 * 10^61 Plank lengths. That gives us a log2 of 205.1
In other words if my maths is correct if you want to represent the entire visible universe down to the scale of the Planck length you need 206bits of resolution, or 4 64 bit integers with a lot of room to spare.
And if you don't actually aim to simulate subatomic particles you can get down to millimeter resolution with "only" 100bits.
And that's not even taking into account that, our universe being so empty, you can probably fudge super large distances a bit (having a lower resolution at scales where the universe is mostly empty). Nobody is going to notice if Andromeda if a few parsecs closer than it should be.
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.
Yes, as far as I know nowadays KSP works by inversing the point of reference, that is, your spaceship does not move and sits at (0,0,0) at all times, it's the whole solar system that moves around you.
Of course, functionnally it does not make a difference, and it solves the problem ;)
EDIT: ah, interesting that you have another theory, now I wonder :)
I can imagine KSP going with what you described, because in that game, things you aren't actively controlling and that aren't in "physics range" (2.5 kilometers IIRC) are either treated as stationary or on-rails (i.e. they're in orbit, and their positions are computed with a closed-form equation); anything that's neither stationary nor in orbit will be deleted once it leaves the physics range. This way, there is no physics simulation to be done on things you don't control or aren't withing few kilometers of, so centering the coordinate system at your active vessel would be a very good approach.
The "number of sig figs" precision will be the same for large values far away from zero, as for values close to zero. E.g. IEEE 64 bit reliably gives you about 15 decimal digits of precision. Any decimal number with 15 digits of precision that is in the range of the IEEE 64 bit double can be converted to that type, and then back to decimal, such that all those digits of precision are recovered.
You can shoot yourself in the foot if you rely on floating-point values being able to exactly represent integers, but the values go beyond the range where that is possible. Beyond a certain range, all consecutive integers are no longer representable; some integers get approximated by nearby integers.
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.
This should simplify many things that people have agonized over!
#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;
}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?
> Where strict aliasing prohibits examining the same memory as values of two different types, std::memcpy may be used to convert the values.
I don't see any such a claim about memcpy having magic powers in the N4659 C++ draft.
All it says is that the underlying bytes of an object can be copied to an array of char, unsigned char, or std::byte. Then if that array is copied back into the object, the object subsequently holds its original value.
Anything more about memcpy comes from C by reference, and that would be about the last document on Earth to grant definedness and portability to something like this.
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.
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.)
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.
>>> import numpy as np
>>> 1 + np.Inf
inf
>>> (0 + np.Inf)/2
inf
>>>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"I was fully away of that stuff you say about how NaN is represented and was also aware of how Inf is represented. My statement and link to the concept of Infinity on mathforum was an effort to support the idea of why most math done with code involving Inf will also result in an answer of Inf.
The article that this whole discussion is about seems to think it is OK (ie not a bug) to convert a float like Inf to a integer do some math and convert back to a float and get 1.5 and that is OK. It seems like a bug to me.
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
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.
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.
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
I just use bigints wherever it's possible to transform the algorithm to work with bigints, and I "render to decimal" in views
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.
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.