10 ms·
Toward an API for the Real Numbers
- kevincox 6y agoTangentially related, the stock Android calculator app is fantastic. It has good accuracy as mentioned in the article and an easy to explore and use history. It is one of the few things that will make me hunt around for my phone when I am working on my desktop.
- anonymfus 6y agoAs a refugee from Windows Phone I actually use Uno Calculator on Android, which is a port of Windows Calculator. It also has good accuracy and easy to explore history, and also sane interface without Android's idiosyncrasies. And you can install it on your presumably non-Windows desktop too.
- unnouinceput 6y agoWhy? Your operating system of choice lacks a proper calculator on your desktop PC?
- kevincox 6y agoYes. I use gnome personally and macOS at work and both default calculators are not nearly as nice to use.
- unnouinceput 6y agoThen it's probably a good time to write one yourself. Or use wine to run the one from Windows.
- qppo 6y agoWhat about NaN values? Are the runtime errors or do they propagate down the chain of execution? Are they comparable?
- skulk 6y agoFor a high-level API, shouldn't this be expressed with types such as a `Result<T,E>` at the library level? edit: now that I think about it, that would require some really nice optional chaining syntax to be even slightly usable.
- fouronnes3 6y agoOh now I'm curious if IEEE 754 NaN rules are isomorphic to a number optional type with monadic chaining syntax
- SAI_Peregrinus 6y agoBasically. And you can stick error codes in the value too, so you can know down the line what caused the NaN.
- neolog 6y agoThere are no NaN values in the real numbers.
- fanf2 6y agoYou need some way to cope with operations that don’t have real results for some values, such as log and sqrt of negative numbers
- molyss 6y agoyou can just represent those as a pair of real numbers, one for the real part, and one for the imaginary part. As long as you only (recursively) apply exponential and trig functions on those numbers, I believe you'll stay within the realm of complex numbers.
- flubert 6y ago0/0, tan(pi/2), log(0)
- modeless 6y agoLooks like a cool library. I'm curious why the Android calculator app needs reliable exact equality tests. It doesn't appear to have an equality test function. Edit: the paper claims that you need exact equality tests to avoid printing unnecessary zeros at the end of decimal expansions, among other things. Interesting that this work was done by Hans-J. Boehm, better known for the widely used Boehm garbage collector.
- _ouml_ 6y agoThe equality test is equivalent to deciding if something is 0. You can probably ask the app to calculate sqrt(2) * sqrt(2). If that doesn't show a 2 as answer, you've lost. Same goes for sin(arcsin(1/2)). You want the exact answer.
- H8crilA 6y agoEquality is also needed if you want to know whether "x<y". Proof: 1) suppose you can decide whether "x<y" for all x,y. 2) Then, for all x,y you can decide whether x==y because that's just "!(x<y) && !(y<x)"
- teslalang 6y agoRepresenting reals as fractions (rationals) goes a long way toward achieving this goal.
- fanf2 6y agoThe point of the paper is that is nowhere near enough for common calculator operations like trigonometry or exponentials
- MauranKilom 6y agoThe real numbers are notoriously non-equivalent to the rational numbers.
- masukomi 6y agosure, but supporting rational numbers solves for 2/3 of the types of "real" numbers in a dramatically better way than just making less crappy decimal representations.
- SloopJon 6y agoI haven't read the paper yet, but if I understand the post correctly, this interface represents numbers as the product of a rational and a recursive real, where the latter may be 1.
- slx26 6y agoIn "safe" languages we often talk about how you can't ignore errors in return values. Your program "leaks" if that happens. But with integer overflows and floating point precision, we just ignore the leaks as something that programmers already know about and have to consider while coding. Of course, it's not an easy problem to deal with, as computers don't have infinite memory and they need to be performant, but we really need to spend more time thinking about and supporting improvements like this. If it only takes 6k lines to provide an API for more precise real numbers, then almost every programming language should have it. The ideas of allowing programmers to get information about the real and potential precision errors in operations are also interesting. Well, in general the ability to define the kind of numbers you want to be working with and their precision is fairly poor in computer science as a whole, there's still a long road ahead.
- qsort 6y ago> the ability to define the kind of numbers you want to be working with and their precision is fairly poor in computer science... It's poor because it's undecidable. We would ideally want to work with the real numbers, but no computational model can represent all real numbers (by a trivial cardinality argument). Obviously, we can make useful progress in practice and evolve beyond the floating point representation (at least for general tasks), similar to what we did for other theoretically undecidable problems (like garbage collectors), but let's not pretend it's something that's easy to fix. The paper is interesting and talks about very real problems, but it's still a far cry from something that can be used in production.
- millstone 6y agoSurely working with computable reals is sufficient? There's no point in writing a computer program that attempts to work with non-computable reals, for obvious reasons. And computable reals are countable.
- alentist 6y agoEquality of computable reals is undecidable. https://mathoverflow.net/questions/40618/uncomputability-of-the-identity-relation-on-computable-real-numbers https://mathoverflow.net/questions/40618/uncomputability-of-...
- fdej 6y agoThe API itself is perhaps less interesting than the implementation strategy. I'm presently developing a C library for exact real and complex numbers (http://fredrikj.net/calcium/ http://fredrikj.net/calcium/) that goes much further to make equality decidable even in complicated cases while also enabling efficient computations. Still working on implementing functionality and writing up a formal paper.
- taeric 6y agoI am surprised not to see any mention of the numerical tower, used by some lisps. Did I just miss it?
- fanf2 6y agoCommon Lisp and Scheme don’t have built-in support for exact real arithmetic
- taeric 6y agoDoesn't the nature of the tower mean you could add it in and it would just slow down computations that required it? I'm guessing the dynamic nature of the languages is the factor in leaning on? That is, both have the surprise for most people that (/ 1 3) doesn't get rounded or truncated by default, due to the default of supporting rationals. You have to coerce into a floating point, right? Couldn't you do the same with exact reals? Put them at the top of the tower and maintain existing projections through the tower? Edit:. Note that I don't think this precludes the algorithms here. Just that a type system that could use the tower could be augmented to get here. If that makes sense. Hence why I would think it would be mentioned. It is the expectations that things project in one direction that folks want? Right?
- unnouinceput 6y agoQuote: "Operations complete in under a millisecond, not GFLOPS performance, but certainly good enough for many applications". Then you have a scientist reading this, wants it for research and then wonders why a simple 3 lines in Python code takes 3 days to complete. True story!
- TeMPOraL 6y agoIf these 3 lines of Python give you correct results... I keep wondering and never have this answered to my satisfaction: if so many people are just using floating point numbers in scientific calculations, and arguably even most scientists don't understand FP math any way better than the users of Android's Calculator app, then how many bad results are out there, that could be attributed to FP errors? Related: I don't understand why the default in scientific computing isn't some kind of scheme with error band propagation. What I mean is, when dealing with measurements, the result of 2.1 * 2.12345 isn't 4.459245, because the result exceeds the precision of the first factor. I'd like a common API that handles this, whether implicitly (through notation) or explicitly (through requiring you to state the precision of every number you use).
- swiley 6y agoIt seems strange that they don't use a rational type, those are much easier for "normal" people to reason about. What you want would maybe be better as probability distributions (maybe parameterized with rational numbers)
- TeMPOraL 6y agoProbability distributions are a related concepts, and I'd love to work with them as first-class objects. But just carrying the confidence intervals around would be a huge win; even ignoring the underlying distribution, it matters whether your result is 1.23 ± 0.0001, or 1.23 ± 20.
- jepler 6y ago(sin⁻¹(cos⁻¹(tan⁻¹(tan(cos(sin(9))))))−9)^−1 produces "Timeout. Undefined?". That's the closest I could get to baffling or tricking it. (it's division by zero)
- TheDong 6y agoIs there a typo in that? Where's the division by zero? Wolfram alpha has that as exactly equal to 1/(3pi - 18) https://www.wolframalpha.com/input/?i=%28sin%E2%81%BB%C2%B9%28cos%E2%81%BB%C2%B9%28tan%E2%81%BB%C2%B9%28tan%28cos%28sin%289%29%29%29%29%29%29%E2%88%929%29%E2%81%BB%C2%B9 https://www.wolframalpha.com/input/?i=%28sin%E2%81%BB%C2%B9%...
- wiml 6y agoIt's multi-valued, I suppose. tan^-1 (tan (x)) is equal to x plus any integer multiple of pi (or of 180°). Same for the other pairs of functions. But one of the values results in a division by zero.
- taeric 6y agoYou did it in radians. Try degrees. Edit: (Or use 0.15708 instead of 9 in your link.)
- deleted 6y ago[deleted]
- agravier 6y agocos is not the inverse of sin, cos(sin(9)) is not 9
- molyss 6y agoI think the intended simplification is : (sin⁻¹(cos⁻¹(tan⁻¹(tan(cos(sin(9))))))−9)⁻¹ -> (sin⁻¹(cos⁻¹(cos(sin(9))))−9)⁻¹ -> (sin⁻¹(sin(9))−9)⁻¹ -> (9−9)⁻¹ -> 0⁻¹ -> 1/0
- 6y ago
- MarkSweep 6y agoAnother example of how to solve this problem is the rational number library used in the Microsoft Calculator. It is called “RatPak” and it is open source: https://github.com/microsoft/calculator/blob/master/src/CalcManager/Ratpack/ratpak.h https://github.com/microsoft/calculator/blob/master/src/Calc...
- yarg 6y agoRationals are a strict subset of the reals. There are also the irrationals, and most of those cannot even be expressed (fortunately, since they cannot be expressed, there's no chance of you bumping into them by accident - so it's somewhat of a moot point). The subset that you want to aim for is not the rationals, but the definable reals: https://en.wikipedia.org/wiki/Definable_real_number https://en.wikipedia.org/wiki/Definable_real_number.
- taylodl 6y agoIEEE 754. If you're going to do any serious computation in floating point, serious meaning people's lives are going to depend on the outcome or a lot of money is on the line, then you MUST know what you're doing. We have standards in place so people can learn it, people creating math libraries can adhere to it, and those creating these kinds of applications can have confidence that things are going to work. I'm sorry addition isn't commutative, there are known ways for dealing with it. I took two courses in Numerical Computing in college. Trust me, the people working in this space are serious, and really, there's a few basic rules of the road you need to learn and you're on your way.
- dchapp 6y ago> I'm sorry addition isn't commutative... My understanding is that in IEEE 754 compliant implementations of floating-point arithmetic, commutativity over "+" holds but not associativity. (With the possible exception to commutativity for the NaNs, though I don't remember offhand whether this caveat is necessary).
- taylodl 6y agoYou are correct. It's associativity that doesn't hold, not commutativity. It really throws people off.
- lmm 6y agoIt's a lot more than "a few basic rules of the road". Why squander your attention budget on a numeric type with so many caveats and edge cases? What do you gain from it? If you actually need the performance of IEEE 754, then sure, use it, and have fun debugging all of the problems it has. But it's an extremely poor default for general-purpose programming.
- otabdeveloper4 6y agoI disagree. IEEE 754 is a fantastic solution if you want a no-brainer plug-and-play approximation of the real numbers. Most people who complain really just want a rational number type.
- philzook 6y agoFun fact: The Boehm of this paper is the same Boehm as the garbage collector Exact Reals are an interesting topic. They go beyond fractions and and algebraic numbers by representing numbers as some kind of object that supports querying an arbitrary number of digits. This object may be a stream, generator, or function. There is some similarity between its implementation techniques and those of automatic differentiation. The theory behind exact reals goes quite deep. Some other interesting things to look at: - https://hackage.haskell.org/package/exact-real https://hackage.haskell.org/package/exact-real - https://www.youtube.com/watch?v=h7g4SxKIE7U https://www.youtube.com/watch?v=h7g4SxKIE7U - https://github.com/dpsanders/ExactReals.jl https://github.com/dpsanders/ExactReals.jl
- moonchild 6y ago> Boehm Also the creator of the rope data structure for storing and efficiently mutating large strings (used by many text editors); as well as the c memory model.
- fanf2 6y agoSimon Tatham has an exact real calculator called “spigot” https://www.chiark.greenend.org.uk/~sgtatham/spigot/ https://www.chiark.greenend.org.uk/~sgtatham/spigot/
- acrophiliac 6y agoAren't there many applications where Java's BigDecimal is a simple and suitable implementation to avoid many of Float's problems?
- deleted 6y ago[deleted]
- zulu-inuoe 6y agoThe comments on that article are frustrating because they clearly didn't read it, by proposing that a rational type is sufficient. "We solved this 40 years ago in SmallTalk!"