In programming we don’t have [real numbers]. We have integers and floating point.
The CPU has floating point and limited precision integers. There is no reason a programming language can’t abstract that away (and IMHO, any high level language really ought to).
For instance, almost all Lisp implementations have exact rational numbers and arbitrary precision integers built in. This frees up the programmer to not have to worry about overflow, floating point precision and other weird behaviour.
Python and Ruby also have arbitrary precision integers built in. There’s a JavaScript proposal to add arbitrary precision integers, but it’s a separate type from regular numbers, so you need to declare in advance that you want to be working on large numbers, which is painful and error-prone.
This industry really has a hard time learning from the past. There’s a lot of research and effort that’s gone into fast calculations which overflow into arbitrary precision integers, for example in the Lisp community (in the early eighties!), but somehow this never really got into the mainstream.
I agree, and rational numbers get really undersold for some reason, but I don’t know of any programming languages that have arbitrary precision reals by default though. (Probably because most of them are infinitely long, upon consideration.) So if you’re dealing with any of the irrational numbers, to multiply by pi or divide by sqrt(2), you still have to care about floating point or some other limited-precision format.
Probably because most of them are infinitely long, upon consideration.
So, that’s not a problem. There is a problem, but it isn’t that. For numbers such pi, which are computable, you can make some representation of the number in memory which contains the “true” number. Perhaps that representation is simply a bit of executable code that calculates pi! If you ask the computer to give you all of it, it will do so, though it will block forever in the effort.
But, the main thrust of this article is that there are numbers (most of the Reals) for which there is no such representation available and indeed it has been proven that there cannot be.
So, let yesterday be remembered as the day that a Wikipedia rabbit hole started by this article lead me to discover Constructivism and decide that I’m a supporter. Tentatively. (Don’t actually know math over here..)
It should be possible, like a sort of stream and making such numbers “primitive” units basically. The more challenging part would be in displaying these numbers. 2pi*sqrt(2) or something should be represented as such when printed, if you don’t want to lose precision.
I know Kawa Scheme has a way of representing numbers with units (like mm and cm) and has some sort of way of reading and writing those. Possibly you could define pi as a unit. You’d have to teach various primitives like the the trigonometric functions about this so they can return the exact value.
Could be an interesting experiment. I’m not a mathematician either, so I’m probably oversimplifying things (as usual).
And second, I guess I was wrong when I described “the main thrust of [qznc’s] article”.. Actually, this “computable real numbers” thing came from wikipedia. I just associated the idea with the first car in my train of links??
FYI, after some more research I have determined that the “non-computable real numbers” aren’t what I thought they were. They are less “important” or “mind blowing” than I thought. I think? I don’t know the math, I think I went down an invalid path.
I like the idea of an “algebraic” numeric type, where values like (* pi (sqrt 2))are represented basically verbatim and can interact with other numeric types as you’d expect (to form bigger algebraic expressions). Then you could have algebraic->inexact and algebraic->exact (which would fail if it was irrational).
You’d probably have to teach each of the trigonometric functions about each other so they can simplify efficiently.
A while back I discovered that Clisp Common Lisp compiler supports arbitrary precision floating point with the long-float type. Most implementations make double-float and long-float equivalent, and that’s the default on Clisp, but it allows the user to setf (long-float-digits):
CL-USER> (long-float-digits)
64
CL-USER> pi
3.1415926535897932385L0
CL-USER> (setf (long-float-digits) 512)
512
CL-USER> pi
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811L0
CL-USER> (sin (* pi 1.25L0))
-0.7071067811865475244008443621048490392848359376884740365883398689953662392310535194251937671638207863675069231154561485124624180279253686063220607485499681L0
I found myself telling people about floating point a lot. Now I try to do it in a more “show, don’t tell” way.
This interactive style feels great. It really makes use of the fact that browsers can contain code to make it interactive. Maybe I should do more of that.
If you have Javascript disabled, the evaluation will not work. Any suggestions how to mitigate that?
If you have JavaScript disabled, the evaluation will not work. Any suggestions how to mitigate that?
For those users, you can do what the excellent free online textbook Introduction to Computer Science using Java does in each chapter. Divide the article into multiple web pages with Back and Next links. At the bottom of each page, write a question, possibly with multiple parts. At the top of the next page, show the question along with the answer(s), and let the user manually compare their mental answer with the written answer.
The textbook’s FAQ calls its style of writing “programmed learning” and describes it in more detail. The questions at the end of each page made the textbook much more interesting to read back in high school. Though your article’s style is slightly different, I found it more fun to read too because of its questions.
The frequent-quizzing approach works better with smaller questions whose answers are easier to memorize. To aid the reader in memorizing their five boolean answers to each of your quizzes, you can put checkboxes next to each question. The checkboxes don’t have to do anything – their state will be saved in browser history, allowing users to go back and see their answers. As an example, chapter 63 of that textbook uses non-functional text fields in some of its short-answer questions.
You could add server-side logic to cause each checkbox form to display different things on the next page, but for this particular article I actually think it would have been better if I could have clicked “show all answers” to see an explanation for every question, rather than clicking “evaluate” to see explanations next to only the questions I got wrong. It makes me more confident in my answers when I see that I got the answer for the same reason as the author. With the current behavior, it could be that I got the right answer for the wrong reason.
That’s a good place to start. If you (like me) find it to be just… too damned ugly (you can’t style it), you can use the checkbox hack to get the same visual behavior from arbitrary HTML elements.
For hiding/unhiding elements without JS, I’ve always used <label>s to <input type="checkbox">. When the user clicks on the label, they toggle the checkbox. The label can be styled any way you want, though I often add cursor: pointer.
The style implication is this. If you place the checkbox before the hidden element, you can hide both the checkbox and any hidden element and use input[type="checkbox"]:checked + #myhiddenelement {display: block} (or similar) to show the hidden element when the preceding checkbox is checked (i.e. when the user clicks the label).
In addition, since most browsers preserve checkbox state across reloads and page navigation, you get to have the state of checkboxes saved, for free!
What I can imagine: The compiler does some interprocedural analysis and figures out the overflow. It decides to optimize the undefined stuff and randomly decides for z == x to be true.
Please fix this ASAP; why does it still tell me I’m wrong when I select it 10h after you published the article? If you’re teaching about tricky parts of C, ignoring UB is a dangerous disservice towards the readers; it reaffirms the oh how popular misconception that UB is something one can just shrug off, or that “compiler will do something sane”.
Please also mention in the article upfront what language the test is about. Maybe it’s not actually C and I am thus misguided.
My understanding is that the primary focus of this article is floating-point numbers, rather than C or its interpretation of integers. UB is out of scope here.
The author already links to an article about UB on Wikipedia, so they claim to be aware of it, and do pull it in scope this way themselves. I’m ok if the language is not C, just “abstract C-like language”, then it would make some sense to claim ignoring UB; but it looks very much like C, and as of now they already mention UB, confirming they do in fact mean C. And they do it incorrectly, by explicitly exempting a case that’s actually possible through UB.
Thanks!!! As for a specific mechanism, I believe the most generic answer can be usually “through inlining”, so not far from your “interprocedural analysis” thesis. The compiler may inline your function, and then do some optimisation based on the surrounding code, and then basically all bets are off. But in general, AFAIU optimisations in compilers are super subtle and tricky, and also a moving target; so asking for a specifics arkund UB is like “but what specifically you claim will I die of if I just book a trip to the South Pole?” For starters, it can be the freezing; but there are so many other possibilities…
The CPU has floating point and limited precision integers. There is no reason a programming language can’t abstract that away (and IMHO, any high level language really ought to).
For instance, almost all Lisp implementations have exact rational numbers and arbitrary precision integers built in. This frees up the programmer to not have to worry about overflow, floating point precision and other weird behaviour.
Python and Ruby also have arbitrary precision integers built in. There’s a JavaScript proposal to add arbitrary precision integers, but it’s a separate type from regular numbers, so you need to declare in advance that you want to be working on large numbers, which is painful and error-prone.
This industry really has a hard time learning from the past. There’s a lot of research and effort that’s gone into fast calculations which overflow into arbitrary precision integers, for example in the Lisp community (in the early eighties!), but somehow this never really got into the mainstream.
The article gives the reason: performance. Working with the CPU representation makes it fast by default.
They can do what you suggested when performance isn’t top priority. That’s most apps.
I agree, and rational numbers get really undersold for some reason, but I don’t know of any programming languages that have arbitrary precision reals by default though. (Probably because most of them are infinitely long, upon consideration.) So if you’re dealing with any of the irrational numbers, to multiply by pi or divide by sqrt(2), you still have to care about floating point or some other limited-precision format.
Now that’s a more fundamental limitation which would be a lot more interesting to discuss :)
So, that’s not a problem. There is a problem, but it isn’t that. For numbers such
pi, which are computable, you can make some representation of the number in memory which contains the “true” number. Perhaps that representation is simply a bit of executable code that calculatespi! If you ask the computer to give you all of it, it will do so, though it will block forever in the effort.But, the main thrust of this article is that there are numbers (most of the Reals) for which there is no such representation available and indeed it has been proven that there cannot be.
So, let yesterday be remembered as the day that a Wikipedia rabbit hole started by this article lead me to discover Constructivism and decide that I’m a supporter. Tentatively. (Don’t actually know math over here..)
It should be possible, like a sort of stream and making such numbers “primitive” units basically. The more challenging part would be in displaying these numbers. 2pi*sqrt(2) or something should be represented as such when printed, if you don’t want to lose precision.
I know Kawa Scheme has a way of representing numbers with units (like mm and cm) and has some sort of way of reading and writing those. Possibly you could define pi as a unit. You’d have to teach various primitives like the the trigonometric functions about this so they can return the exact value.
Could be an interesting experiment. I’m not a mathematician either, so I’m probably oversimplifying things (as usual).
A couple of things. I linked to the wrong wikipedia page. Sorry, sorry.. Here is the one I found yesterday: https://en.wikipedia.org/wiki/Definable_real_number#Computable_real_numbers
And second, I guess I was wrong when I described “the main thrust of [qznc’s] article”.. Actually, this “computable real numbers” thing came from wikipedia. I just associated the idea with the first car in my train of links??
FYI, after some more research I have determined that the “non-computable real numbers” aren’t what I thought they were. They are less “important” or “mind blowing” than I thought. I think? I don’t know the math, I think I went down an invalid path.
I like the idea of an “algebraic” numeric type, where values like
(* pi (sqrt 2))are represented basically verbatim and can interact with other numeric types as you’d expect (to form bigger algebraic expressions). Then you could havealgebraic->inexactandalgebraic->exact(which would fail if it was irrational).You’d probably have to teach each of the trigonometric functions about each other so they can simplify efficiently.
Sympy can sort of do this.
A while back I discovered that Clisp Common Lisp compiler supports arbitrary precision floating point with the long-float type. Most implementations make double-float and long-float equivalent, and that’s the default on Clisp, but it allows the user to setf (long-float-digits):
Cool!
I found myself telling people about floating point a lot. Now I try to do it in a more “show, don’t tell” way.
This interactive style feels great. It really makes use of the fact that browsers can contain code to make it interactive. Maybe I should do more of that.
If you have Javascript disabled, the evaluation will not work. Any suggestions how to mitigate that?
For those users, you can do what the excellent free online textbook Introduction to Computer Science using Java does in each chapter. Divide the article into multiple web pages with Back and Next links. At the bottom of each page, write a question, possibly with multiple parts. At the top of the next page, show the question along with the answer(s), and let the user manually compare their mental answer with the written answer.
The textbook’s FAQ calls its style of writing “programmed learning” and describes it in more detail. The questions at the end of each page made the textbook much more interesting to read back in high school. Though your article’s style is slightly different, I found it more fun to read too because of its questions.
The frequent-quizzing approach works better with smaller questions whose answers are easier to memorize. To aid the reader in memorizing their five boolean answers to each of your quizzes, you can put checkboxes next to each question. The checkboxes don’t have to do anything – their state will be saved in browser history, allowing users to go back and see their answers. As an example, chapter 63 of that textbook uses non-functional text fields in some of its short-answer questions.
You could add server-side logic to cause each checkbox form to display different things on the next page, but for this particular article I actually think it would have been better if I could have clicked “show all answers” to see an explanation for every question, rather than clicking “evaluate” to see explanations next to only the questions I got wrong. It makes me more confident in my answers when I see that I got the answer for the same reason as the author. With the current behavior, it could be that I got the right answer for the wrong reason.
No need to create multiple pages, you can just use the
<details>HTML5 element.That’s a good place to start. If you (like me) find it to be just… too damned ugly (you can’t style it), you can use the checkbox hack to get the same visual behavior from arbitrary HTML elements.
If it is you who wrote that site, you could use plain old cgi to display the correct answer without javascript
For hiding/unhiding elements without JS, I’ve always used
<label>s to<input type="checkbox">. When the user clicks on the label, they toggle the checkbox. The label can be styled any way you want, though I often addcursor: pointer.The style implication is this. If you place the checkbox before the hidden element, you can hide both the checkbox and any hidden element and use
input[type="checkbox"]:checked + #myhiddenelement {display: block}(or similar) to show the hidden element when the preceding checkbox is checked (i.e. when the user clicks the label).In addition, since most browsers preserve checkbox state across reloads and page navigation, you get to have the state of checkboxes saved, for free!
Yep, this is great (though less awesome for screen readers).
The interactive part really adds a lot to the article. Does anyone know whether Wordpress has a plugin to create things like that?
In 1st quiz, with addition when
x + yoverflows anything can happen as this is UB, so nothing preventsz == xin that case.You are correct but can you imagine any way how it might happen?
I considered different signed number representations but that does not work.
What I can imagine: The compiler does some interprocedural analysis and figures out the overflow. It decides to optimize the undefined stuff and randomly decides for z == x to be true.
IIRC MATLAB integers saturate on overflow. So
INT_MAX + 1 == INT_MAX.Please fix this ASAP; why does it still tell me I’m wrong when I select it 10h after you published the article? If you’re teaching about tricky parts of C, ignoring UB is a dangerous disservice towards the readers; it reaffirms the oh how popular misconception that UB is something one can just shrug off, or that “compiler will do something sane”.
Please also mention in the article upfront what language the test is about. Maybe it’s not actually C and I am thus misguided.
edit: Please also make sure that you’ve read the series of articles on UB by John Regehr. They’re very approachable, and you’d do good to advertise them everywhere you can when teaching about C, for the reader’s own sake. Esp. part 2 and part 3 where he mentions real concrete cases found in well known software. Also, “UB-related problems are far from solved [as of 2017]”.
edit 2: Ahh, and I’ve finally found the meta-article I think I liked the most: an up-to-date list of bugs found in FOSS software by PVS-Studio.
My understanding is that the primary focus of this article is floating-point numbers, rather than C or its interpretation of integers. UB is out of scope here.
The author already links to an article about UB on Wikipedia, so they claim to be aware of it, and do pull it in scope this way themselves. I’m ok if the language is not C, just “abstract C-like language”, then it would make some sense to claim ignoring UB; but it looks very much like C, and as of now they already mention UB, confirming they do in fact mean C. And they do it incorrectly, by explicitly exempting a case that’s actually possible through UB.
Fixed. I still would like to see a better explanation.
Thanks!!! As for a specific mechanism, I believe the most generic answer can be usually “through inlining”, so not far from your “interprocedural analysis” thesis. The compiler may inline your function, and then do some optimisation based on the surrounding code, and then basically all bets are off. But in general, AFAIU optimisations in compilers are super subtle and tricky, and also a moving target; so asking for a specifics arkund UB is like “but what specifically you claim will I die of if I just book a trip to the South Pole?” For starters, it can be the freezing; but there are so many other possibilities…
The point is a psychological one. If I tell you a story how Kenny froze to death while sleeping in a tent at the South Pole, it is more convincing.