Can programmers do math? What is a real number, really?
Vložit
- čas přidán 5. 06. 2024
- Sure, integer arithmetic on a computer may lead to overflows, but this behaviour is manageable and easy to predict... why do programmers settle for the wacky artefacts of floating-point arithmetic?
__________
Timestamps:
00:00 - Introduction
00:36 - What is a real number?
02:02 - Why bother with infinite precision?
02:51 - Implementing real numbers
03:37 - Technical interview
04:04 - Naïve implementation
04:53 - Less naïve implementation
05:19 - Working with real numbers
05:47 - Continuous extension of sqrt
06:33 - Discontinuity
06:54 - Positivity check (impossible)
07:54 - PSA
08:09 - "Impossibility" of discontinuity
08:49 - Apology (if you skip to this chapter, I'll be sad)
09:36 - Thx 4 watching - Věda a technologie
Currently getting started on my math undergrad, guess i'll have to watch this video to know the ways of abstract tomfoolery.
Don't get me started on abstract nonsense!
@@SheafificationOfGBe you a fellow abstract nonsense enjoyer?
A function is just a morphism in the category of topological spaces, so all functions are actually continuous
Wanted to talk about discountinuous functions anyway for a laugh? The forgetful functor Top --> Set has a left adjoint, you're welcome
Very discrete, but Top is categorically unpleasant, and I prefer localising at the homotopy equivalences so that the space of real numbers is *really* easy to work with.
@@SheafificationOfG I'm very profinite-pilled, so I place my faith in Scholze and Clausen to deliver us from this evil 🙏
I see you have mastered select, copy and paste. You might want to work on your math skills now!
@@JakubWaniek CZcams feels oddly small when my Facebook internet friends show up in CZcams comments. How is your PhD going anyway?
It gets worse than this: it's not possible for any real number representation to represent non computable numbers, so any "real number type" necessarily will have gaps you just cannot represent. That's why if I want rigour I will use an integer, rational or other algebraic type and otherwise... "floats are fiiiiine 😅"
you can also try your hand at an epsilon approximation of computable Real numbers. Which in most cases, you can just call "Reals" and be done with it. Alternatively, for day to day use, you can just use a 1024 bits fixed precision (512 bits of integer, and 512 bits of fraction). With that you can write a Kerbal space simulation that will span several time the observable universe at under the plank constant granularity.
My freshman year of college, I presented on p-adic numbers, and at the start I asked if anyone knew how real numbers are defined, which no one did. Literally everyone was operating on the "real numbers are the numbers in between the rational numbers" level instead of thinking of them as sums of smaller and smaller rational numbers. So I totally believe you that other disciplines never learn this 😂
Meanwhile programmers are out there working with 2-adics without even realising.
p adics are basically little endian numbers in base p right
@@hellishbrogaming3643 this is my first time hearing the term, so I'm a little out of my depth here, but if you're asking if there's anything more going on than a reordering of the digits, yes, very much so. I'll just explain what I know lol. the distance between two numbers x and y is defined as |x-y|, which is then part of defining convergence for infinite series (each finite step has to get closer and closer to the goal value) and the real numbers are then defined as the numbers you can reach with these convergent sums. But there's another family of absolute value functions that do what an absolute value function needs to (besides the one you know and some degenerate case): |x|=p^-a where x= p^a * r/s (r and s don't divide p). For example the 3-adic norm of 18/5 = 3^-2. Anyway you can use these to flesh out p-adic numbers in the same way the reals are fleshed out, and you get a coherent mathematical system, but there's a bunch of weird stuff going on. I'm talkin fractal number lines, positive expressions for negative values, open balls and closed balls are the same thing, crazy stuff. One of those things is that digits can extend infinitely to the left, but ...111111 does genuinely mean 1+10+100+... It just doesn't diverge.
Anyway, I can only hope this was useful at all. Literally everything I know about "endians" is a five minute wiki skim I just did.
@@SheafificationOfG I actually did realize this when I first learned about p-adics and related it to integer overflow.
In ZF, with the Axiom of Infinity and the Power Set Axiom...
Natural numbers can be defined as the set of all natural numbers that came before.
Integers can be defined as infinite sets of pairs of natural numbers who are related by a-b=c-d or a+d=b+c.
Rationals can be defined as infinite sets of pairs of integers who are related by p/q = r/s or ps=rq, notably, q and s cannot be 0 unless you wanna go down the unsigned infinity + the nullity rabbit hole.
Real numbers can be defined as a pair of infinite sets of rational numbers either less than (set A) or greater than or equal to (set B) the given number.
Taking it a step further, complex numbers can be defined as a pair of real numbers.
The details of implementing the operations, particularly for the real numbers, are a little more nuanced and my teenage programmer mind cannot understand those yet.
I can understand implementing addition, multiplication, and subtraction for the natural numbers and integers, but where does the decimal place representation come into play, particularly when doing elementary operations on rational numbers?
Even though we don't know whether or not pi contains every possible string, I'd expect us to have checked relatively small strings longer than phone numbers and social security numbers, so the clip shown might be technically correct even though misleading.
I was thinking about that, too (but only after I uploaded the video). The clip I yanked from (from an episode of Person of Interest) went on for much longer than talking about security numbers and locker combinations: the guy went on to talk about how, if converted from decimal to "letters" (idk, maybe he meant base 36 or some other mapping to strings), then pi contained Shakespeare, your life story, everything you'd ever say, etc.
But you're right, if limited to some small finite sequence length, it's likely from the number of digits of pi that we've computed that we can confirm the existence of each such sequence.
As a meandering philosopher, Ultrafinitism is infinitely fun to drop in a math department with whilst armed with delicious controversy popcorn. I like to quip that a good lower bound is the value of the Ackerman function for the number of particles in the observable universe.
Great video, thanks for making and sharing it.
Ah, the meandering philosopher, a mathematician's worst nightmare
can you make a video on the law of the excluded middle? It's really entertaining to see your jokes about it so please throw us more of it
Maybe I will, maybe I won't 🙃
@@SheafificationOfG bold of you to assume there’s not a middle 🤔
One of the best video I've seen on youtube in my life
The recording noise somehow carries subtle meaning and helps convey the flow of the video, well done!
And the content is great too! I have wanted to talk about this for a long time, now I can just point to this video
Thank you! Finally, someone recognising the purpose of my audio, and that it's definitely and absolutely not a reflection of how I can't afford a good mic...
@@SheafificationOfG You can remedy that with some free/pirated noise reduction, but do keep a small amount because I genuinely like that (except it maybe being a bit too loud).
oh no. the level of nuanced shade was an immediate subscribe. Wow, this is brilliantly hilairous.
Nice video!
Thanks!
I have never met a programer who new anything about math let alone passed a math class. I understand that some degrees required a basic math background to graduate. But not the basement coders and self served programers and hackers. Known as geeks! I say let them wait..
Wow! This video is amazing! I've been thinking about this sort of issue for a while. Thank you!
Have you seen any of Norman J. Wildberger (Mathematician) videos?
Thanks!
I feel like I need to be in a very particular frame of mind to watch Wildberger's stuff (and I've never been in that frame of mind).
Wildberger is on the fine line between mathematics and crankery.
congrats on 315 subscribers
Thanks!
I wonder if I could implement the unsigned integers in the same way that mathematicians do it: 0 = the empty array [], 1 = [0], 2 = [0,1], 3 = [0,1,2], for some n, n+1 = [all the elements of n, n], and we can keep going to implement integers, rationals, reals, and complex numbers.
You can definitely encode von Neumann naturals as lists, if you like, and work your way up. All arithmetic operations and comparisons can be implemented all the way until real numbers. Once you're at reals, then you run into the issues mentioned in the video: discontinuous operations may spell trouble (e.g. equality of real numbers), no matter your choice of implementation.
I have a degree in applied physics, and I am a software developer with 6 years of experience and it's true, I have no idea how to do math
This is the dual of the last video
I wonder what video co/evaluation would mean for this pair of videos 🤔
As someone taking their second semester real analysis class i never considered this application but its straight out of the textbook in theory lol
As a computer programmer: most of us can't do math. I would point you to the Linux tool bc, though. It stores numbers in a manner such that .1+.2=.3 correctly, exactly, and with no magic. It is just slow (the version on Android is faster that the GNU version). As for me: if I say arbitrary precision, I mean an a priori precision, so that I can compute the working precision necessary for the final result to have that precision. And then the program would run at a fixed precision.
While fixed precision is essentially unavoidable, one caveat is that it's impossible to maintain a fixed precision: approximation errors will grow as you keep operating on the numbers (this is somewhat reflected by my definitely non-contrived example in 2:38).
@@SheafificationOfG The theory behind the Table-Maker's Dilemma is frequently not a practical limitation.
The answer to the interview question is just the naive solution as long as they don't need trigonometry or exponential functions (with reasonable assumptions about the model that has infinite memory). This is why functional containers are used (like streams or channels) in HPC for even the most mundane operations. The main misconception this video leverages is that math and computer science deal with numbers in the same way, they do not. Computer science deals with already extant data held within some model and the way that data is stored or retrieved will determine the type of that data, not some intrinsic property. Thus, to say that there is some real number that is "impossible to represent" is just to say that a given algorithm to store and/or retrieve that data has an issue. Whether that issue is one of computability or complexity depends more on the operations accepted by the algorithm.
As a side note, if "runtime isn't an issue" then an infinite amount of time to run isn't an issue. That's what runtime means
Wow you guys are smart I just like this because it makes me feel like a genius
Short answer: no.
Давай!!! ДАВАААЙ УРАА ДАВААЙ ДАВААААЙ
I believe your representation of real numbers by Cauchy successions falls off when considering the distance between x and xn is less than 1/2^n. Mathematically of course it holds since the interval of a_n and b_n halves in distance each iteration; yet the algorithm implementation of such proof (5:31) loses precision when computing *rational mid*, since by dividing by 2 a binary number you are subsequently adding another bit.
Now, I don't know how you implemented the *rational* class and if you've overloaded the / operator, but as long as it has finite bit representation, we've got a contradiction. The only silver lining is if *rational* would have size arbitrarily large depending on n, which would indeed be a crazy mad idea: Since you have perfect bit representation for any element in the set A made of 1,2, and the property (x+y)/2€A, with the fact that A is dense in R, we get the assurance that any real number on (1,2) can be the point of convergence of some succession of A (finally proving |x-xn|
Rationals are _not_ represented using sequences of decimals, since that would just introduce the same problem. They are represented using a sign bit and a pair of two (arbitrarily sized) natural numbers. Then the implementation of / is straightforward.
Moneybags forgot to mention that the programmer before you already implemented arbitrary precision rational numbers. As @vekyll says, this isn't nearly as challenging as implementing real numbers.
Arbitrary-precision integers are okay: you can encode any integer as a (not uniformly bounded) finite sequence of bits (e.g., std::vector, if you like). As long as memory is no issue, you can hold any integer you desire. You can then overload the arithmetic operations and whatnot. (Python already does this sort of thing; memory is allocated according to the number of bits needed to encode the integer.)
You can then implement rational numbers as mentioned at the end of the video, as a pair of integers (numerator and denominator). Then, overloading the arithmetic operators for rational numbers will be just like we did it back in grade school. In particular, every rational number is constructible (in finite time and memory).
Although rational numbers are (definitionally?) dense in the reals, and every real number can be encoded as a Cauchy sequence of rationals (or whatever other model of real numbers you want to work with), an arbitrary real number cannot be necessarily encoded in finite memory. Some can (even pi, as mentioned in the video), but the set of all "finitely representable / constructible" real numbers will always be countable, and therefore cannot account for all real numbers.
I feel like I went on a bit of a tangent, so I hope this addresses your comment.
"why do programmers settle for the wacky artefacts of floating-point arithmetic?"
I mean you could try asking them.
And, hey, just because you're unable to explain a Monad to anyone that isn't a mathematician. It's ok. I still choose to believe that it's *not* just something math people made up to sound impressive.
To answer this question: computing floating point numbers requires multiplying and dividing by powers of your working base. When your working base is your representation base, then this is just shuffling digits around. It's a performance hack that people smarter than most programmers agreed on.
Can you elaborate on how it's impossible to construct a discontinuous function ℝ→ℝ? Maybe I'm misunderstanding, but wouldn't something like f(x) = { 0 if x < 0, 1 if x ≥ 0 } be ℝ→ℝ and have a discontinuity?
So, by "construct f(x)", I mean "determine a finite-time procedure for computing f(x) if given x."
While your function f(x) certainly has a discontinuity (in fact, your function is exactly `is_pos`), the hard part is to actually implement it constructively.
How do you check if f(x) = 0 given your f? You can't know if x < 0 using a Turning machine.
I'm currently studying abroad in math. I can confirm that mathematicians are in fact this insane.
I'm a computer scientist, doing math and physics and math pedantry is just not as fun as CS pedantry but we are at least lazy where it matters. When it feels good physics is not LAZY, it's GAMBLING
Ironically doing precise math is harder on high level languages then on low level ones.
Probably doesn't fit with the video, but it's ok, i have still to watch it ;-)
Curious what you mean when you say higher-level languages have a harder time doing precise math? I was originally going to "implement" reals with Python instead of C++, but I quickly realised there wasn't enough gatekeeping this way.
At least Python's negative integer division isn't broken by design like C and C++'s are.
You aren't saying that programmers can't do math. You are saying that computers can't do math.
And that is clearly false given WolframAlpha exists
Shh, don't give programmers another reason to blame the computer instead of looking inward and realise the deficiency is in their code all along!
As for your second comment: although WolframAlpha is a remarkable tool for symbolic mathematics, it's still constrained to constructible real numbers (or constructible approximations of real numbers) when the going gets tough. By definition, it's really difficult for us to hit it with non-constructive real numbers, so this kind of distinction is not important for what happens "irl", for the most part.
Computers can't do math! They perform algorithms on bits that are consistent with math.
this channel is clearly very good but i did not ever really learn math so i have no way of knowing what youre actually saying half the time. is this different from bigint libraries in some way?
BigInt libraries, as the name suggests, is concerned with arbitrary-precision integers. Although arbitrary integers have no bound on size, any one integer can be encoded using *finite* memory, which is why BigInt is possible to fully implement. Using BigInt, you can also define arbitrary-precision *rational* numbers as a ratio of BigInts. However, the jump from rational to *real* is what this video is concerned with: no matter what you try, it's impossible to fully implement (arbitrary precision) real number logic and operations, no matter how you approach it.
@@SheafificationOfG thank you for the explanation! i somehow forgot the distinction between rational and real while writing that comment but this makes perfect sense
Does this mean that you can't check if a value is equal to 0? Or am I misunderstanding.
Yeah you can't check equality for any pair, just precision within a level of tolerance, at least for this data structure. Notably, the approximations are not unique!!
@@tsawy6 So is it possible to construct a program where you enter an expression (Eg: Trig functions, Integrals, normal stuff, Factorials etc) and an error margin which returns the answer that is guaranteed to be within that error?
@siddanthvenkatesh2744 yeah! For any constructive continuous function! Integrals im not 100% on, and factorials will always be a bit weird cuz yer using reals so youdd have to use the gamma function which id always freaky, but trig would be totally fine
Just to follow up on @tsawy6, once you unwind the definitions of integrals / factorials (another integral) / etc as limits of finite constructions, you'll be able to tease out programs for approximating them to whatever precision you want (though the implementation will depend on the integrand if you're particular about the error bounds).
JapanEat's alt channel
3:10 you forgot to assume a flat earth! 😱
The information you're sharing is too important to have audio this bad. Where do I sign up to help fund better audio?
Hahaha yes my poor mic is begging to retire
I'm on the fence about panhandling the viewers until I figure out my life schedule
@@SheafificationOfG I mean, if you wanna co-shill, I could start making tuts for folks just starting to dig into maths and send ‘em your way. Anything to hear what you have to say w/o my ears bleeding lol.
Alternatively, there are post-process processes that could clean up the audio quite well
This has no connectin to real numbers
A real number is any value that does not contain i
In the forms,xi, x+yi, and its negatives
Thanks for your comment!
You're defining real numbers as the subset of complex numbers that have no imaginary component (no "i", as you say), but this begs the question: how do you define *complex* numbers (without referencing real numbers)?
Usually, people define real numbers first (by "filling the gaps" between rational numbers), and _then_ define complex numbers as numbers of the form x + yi, where x and y are real numbers.
@@SheafificationOfG oh. Ok
A complex number is i^x +i^(x+1)
Where x is equal to a non imaginary number that can be represented by a fraction, and the numbers after its decimal points are zero, the first exponent must not result in a imaginary number, and the second results in a non imaginary number.
@mihaleben6051 If you look closely, your definition still relies on real numbers ("non-imaginary"). How do you define non-imaginary numbers without referencing complex numbers and real numbers?
The deeper you go with these things, the more you find subtleties if you're trying to avoid being circular.
@@SheafificationOfG ...
You
Cant...
Wait
A number is a constant. A variable is not a constant, and can be a number, but not considered a number itself
So
a+bi
But i know its impossible.
Does this mean that 0x...AAAB is a ℝeal number? I thought that numbers with infinitely many digits to the left of the radix point weren't considered ℝeal even if they don't contain an "i".
P.S. The number I gave is specifically 1/3 in hexadecimal.
Programming has nothing to do with implementing mathematical abstraction. Never. The most it comes in the vicinity of that goal is to implement real world applications of those abstract concepts. And in this, programmer can become really good and useful. Most abstract concepts of mathematicians are completely decoupled from real world applications. Without those programmers, they would seldomly become useful for real life, and mathematicians would barely be as respected and useful as they are nowadays. As a mathematician, avoid going into disrespect against the most useful group of professionals that are out there to make your work into actually useful tools!
😔 what's the point of being both a mathematician and a programmer if I can't dunk on both groups
Juste pour être bien sûr, t'es québécois ???????
Nahh, le dernier message c'est en hommage à la loi sur les langues officielles 🙃
Sorry, but I gotta say it for the meme: Have you considered rewriting this video in Rust?
I'm surprised I managed to go as long as I have without encountering the rustaceans.
🦀
i don’t know how to do math :)
Forget the logic, we have breaks and continue
Who cares about speed of algorithms
Breaks and continues will ensure the algorithm terminates, at the cost of a bit of "undefined behaviour" at very low orders of magnitude. Of course, that's perfectly fine in real life (otherwise we probably would've already ditched IEEE754).
My eyes grow dim waiting for the Lord the number of my enemies is greater than the hairs on my head people speak against me in the gate Lord i call upon thee in my time of trouble psalm sixty nine the Lord said to moses bring joshua to elisha the priest and in the sight of elisha commision joshua so moses found joshua and commisioned him Numbers you are of the flesh so i feed you milk because you are an infant not ready for solid food that is why you are jealous because you are of the flesh one corinthians
LEM bad
LEM not good*
LEM some affirmative definition of bad that implies not good
nerd
You've just proven that real numbers aren't real. They are an idea that is only formed by looking at rational numbers in decimal notation and saying "Wow, this notation is great, but let's make the amount of digits we can put after the dot unbounded". The moment you make any idea unbounded it ceases to exist in reality.
Also, certain kinds of mathematical questions don't have actual answers. They only have rational approximations for answers that don't really answer the question. Like the question: "How many radi of a circle fit into it's circumference?".
Your point on the ability to represent pi in a finite way using an integral over the root of 1 - x^2 is wrong. An integral isn't a finite process. It deals with adding infinitesimals together, which is yet another unbounded process. You can only calculate a Riemann approximatiom for it. Or, if you're lucky, you can get an antiderivative, which, when evaluated, can only be evaluated to a rational approximation. The second formula you mention requires you to select a finite number of terms to calculate an answer, which results in another rational approximation of pi.
The number pi doesn't exist. All that exists are a bounded (not unbounded) number of approximations that we could feasibly reproduce for different use cases.
Now, this doesn't mean that real numbers don't have any utility. They absolutely do in the conceptual/unevaluated domain (in question form). We can work in this conceptual domain until we've come to some representation which represents our question in the simplest way possible and the pull that into the real world by getting a rational approximation to it's answer at the very end.
For the astute amongst you, you might realise that even rational numbers don't truly exist given that a ratio is just a question asking "What is the answer of 'a' divided by 'b'?", where we only have answers if the result was a product of a or b with an actual integer.
How about negative integers? Show me a negative number. You can't, yet it has utility for when someone finally pays off their debt to know they're square.
In fact, show me the number one. You can't, because the difinition of the number one, like beauty, is in the eye of the beholder. A spoon is one as a spoon, but multiple as molecules, even more so as atoms, etc.
The only thing you can show me is the number zero because it implies a lack of something to show.
you lack imagination if your notion of reality only includes aspects of the physical world, especially if it's only your arbitrary perception of what is possible.
The only honest answer to "is the universe finite or infinite?", for example, is "i don't know".
@@Errenium My imagination is definitely not limited to the physical world. That should be obvious of any individual. Anyone can think of things that don't exist.
The point of mathematics is to be of utility in the real world. Or do you regard it as a form of imaginary entertainment?
Were you even listening? As long as you aren't bringing in discontinuous functions, the space of real numbers works just fine!
Well, *constructive* real numbers, but that's a technicality. The point is, this space includes Pi and other weird transcendental constants defined by arbitrarily complex formulas.
@@user-qm4ev6jb7d I didn't say that real numbers don't work, in fact I said they have utiliy. What I did say is that they cannot be represented in reality.
In the video he has to rely on programming that only has rational approximations with the numbers he's solving for. Maybe you weren't watching.
@@gustavstreicher4867 A computational device (like a C++ function) that generates digits on demand *is* a representation in reality. The function itself *is* the number. If that's not a representation, I don't know what is.
congrats on 314 subscribers
Thanks!
@@SheafificationOfG holy shit you're growing quickly
Ikr?? I can't say I expected this