Shriram Krishnamurthi

Oh good! Someone from the @racketlang community can weigh in on the benefits.

Oh wait…

Anyway, sooner or later the time for computable reals will come. I'm still HODLing stock in continued fractions (and teaching them every year to my first-year students).

Nov 6 at 7:32pmWeb
Show thread(Vita)soy BoyNov 6
@shriramk @racketlang did anyone ask the numbers if they wanted to be computed
Show threadShriram KrishnamurthiNov 6
@secretasianman Ay, there's the rub. @racketlang
Show threadAshton WiersdorfNov 8

@secretasianman @shriramk

According to a recent Numberphile video I watched, the *vast* majority of numbers definitely do *not* want to be computed.

Show threadShriram KrishnamurthiNov 8
@wiersdorf
Unhinged attitude on their part. Are you sure they're rational?
@secretasianman
Show threadAshton WiersdorfNov 8

@shriramk @secretasianman

There is neither time nor space enough in our universe for me to enumerate their normal, irrational behaviors

Show threadcurcheNov 6

@shriramk
Have you previously written or know any blog posts related to computable reals? Always looking to learn more.

Sidenote: a while back there was a hit twitter thread about android's calculator app. Its also available verbatim in a website but felt easier to read the thread. Is this relevant in some way 🤔
https://chadnauseam.com/coding/random/calculator-app

calculator-app - Chad Nauseam Home

"A calculator app? Anyone could make that." (this was originally a https://x.com/ChadNauseam/status/1890889465322786878, and has since been turned into an asterisk article) "A calculator app? Anyone …

Chad Nauseam Home
Show threadcurcheNov 6
Also my only (indirect) experience with gnu multi precision was it as a dependency to another c++ library and me failing spectacularly to get it working on both MacOS/clang & RHEL/gcc 😔
Show threadShriram KrishnamurthiNov 6
@curche Ha, no, but I'm probably one of the very few people who ran the *original* Böhm arbitrary precision calculator — Hans had left Rice but an old binary of his Russell programming language was still around on the SPARC machines, and I used to use it to play with its wacky types…and as a calculator. (-: This is what I wanted to do a PhD in, but the time for it had passed. )-:
Show threadcurcheNov 6
@shriramk
Holy shit, that's amazing.
Show threadShriram KrishnamurthiNov 6
@curche That blog post is the best thing in that genre tha I know on this topic and its history.
Show threadcurcheNov 6
@shriramk
Oh shit lol!! That's great to know, I keep coming back to it to re-read it and am happy that its now available as a blog post.
Show threadDavid BremnerNov 6
@shriramk @racketlang I think we can all agree that samth is a programming languages researcher, so the summary is already doing better than average.
Show threadPlaidNov 6
@shriramk @racketlang Oh good, I can finally work out the numerical solution to e/pi. For reasons.
Show threadTim MakariosNov 6
@shriramk @racketlang
Continued fractions are fun, but do your favourite algorithms actually terminate if you try to use them to calculate, say, floor(sqrt(2) * sqrt(2))?
Show threadShriram KrishnamurthiNov 7
@TMakarios @racketlang Yeah, depends on your implementation of all those operations! Nothing beats Mathematica. (-:
Show threadTim MakariosNov 7
@shriramk @racketlang
I guess my point was: If you're relying only on continued fractions, and you have two numbers that begin like [1;2,2,2,…], and you don't know that they're both sqrt(2), and you try to multiply them, you can't even output the integer part of the result at all, unless and until one of them gives you something other than 2 as one of its later terms.
Show threadShriram KrishnamurthiNov 7
@TMakarios Yep, I understood that. I don't know all the different ways people have figured out arithmetic on them, and it's conceivable there's some representation that manages to collapse this. After all, [1;2,...] has a *representation* that makes clear it's a quadratic irrational, and you could imagine * operating in a way that exploits when you're computing sqrt(n) * sqrt(m) (and especially sqrt(n) * sqrt(n)).
@racketlang
Show threadTim MakariosNov 7

@shriramk @racketlang
Oh, if you're not already familiar with it, you might enjoy reading https://www.tweedledum.com/rwg/cfup.htm . (While I was trying to find it again, I came across https://hsinhaoyu.github.io/cont_frac/ which I haven't read, but which may or may not help to explain the former link.)

But yes, using non–continued fraction representations (possibly as well as using continued fractions in some way) may help, but there's enough undecidability about the reals, and the operations people want to perform on them (see https://en.wikipedia.org/wiki/Richardson%27s_theorem ), that I think there'd still be some cases where we'd have to say something like "either floor(x) = 2 or 2 - ε < x < 2; how small do you want me to make ε before I give up trying to totally rule out floor(x) = 1?".

SAILDART filename CFUP[1,RWG] date 1975.12.01 time 08:08

Show threadShriram KrishnamurthiNov 7
@TMakarios
Oh, that's really neat — they reconstructed the Gosper notation! Expressing it as tensors is quite a flex (-:. I'll have to read that code a bit more slowly.
@racketlang
Show threadKonrad HinsenNov 7

@shriramk In which context do you introduce continued fractions to first-year students?

As for computable reals, I'd love to see them become more widely (and easily) available. For testing numerical methods, and for exploring their properties.

Show threadShriram KrishnamurthiNov 7

@khinsen See for yourself!

https://cs.brown.edu/courses/csci0190/2025/contfrac.html

Contfracs

Show threadShriram KrishnamurthiNov 7
@curche , FYA, I link that Android blog post to my assignment [search for "Android" in the assignment link in the previous post].
@khinsen
Show threadKonrad HinsenNov 7
@shriramk That's a nice assignment! Including the presentation (sidenotes!) and in particular the section on "socially responsible computing".
Show threadShriram KrishnamurthiNov 7
@khinsen Thanks! We actually have some of those spread through the course and also spread throughout the entire CS curriculum.
https://responsible.cs.brown.edu/
SRC@Brown

Show threadAndres MorenoNov 7

@shriramk @khinsen

What a lovely assignment! Congrats!

Show threadMartin EscardoNov 7

@shriramk @racketlang

I am glad some big company, in this case Google, implemented in practice a phone calculator for exact real number computation.

My PhD thesis was, in fact, about this subject.

But I was more interested in theoretical questions, e.g. whether you could come up with a theoretical higher-order programming language including real numbers such that reals, functions, and functionals are definable in this language if and only if they are computable.

This I achieved. I called the language Real PCF. This is a Turing-universal higher-order programming language for exact real number computation.

And also, one of the papers I read regarding this was Boehm's 1987 one, on which the Android calculator is based on.

In any case, although my interests are mainly theoretical, by my nature, I also flirt with practical things, in particular regarding this subject.

Here is a 2011 Haskell file that computes exactly with real numbers:

https://martinescardo.github.io/papers/fun2011.lhs

In addition to all that Boehm computes, we compute integrals.

Also this literate file contains a lot of discussion of the history of the subject (although it doesn't aim to be comprehensive).

This was for Fun in the Afternoon (does this UK meeting series still exist)?

Show threadShriram KrishnamurthiNov 7
@MartinEscardo
Oh wow, that is an absolutely lovely question! I hadn't thought of it in those terms before. Like Scott-Strachey domains taken to the extreme!
@racketlang
Show threadMartin EscardoNov 7

@shriramk

In any case, I love that Boehm managed to make his 1987 ideas, which go way back to the early 20th century, including Brouwer, into a practical tool, the Android calculator.

He was hired by Google due to different achievements, and then, eventually, he managed to convince his employer to make an old academic paper into reality.

I wish all programming language libraries incorporated these ideas.

The benefits and the trade-offs are lucidly discussed in his 2020 paper

https://dl.acm.org/doi/abs/10.1145/3385412.3386037

This is a lovely paper, both practically and theoretically. I highly recommend it.

Show threadShriram KrishnamurthiNov 7
@MartinEscardo It is indeed. I link to the blog post version from my course homework page!
Show threadsoaprootNov 9
@MartinEscardo @shriramk I recently switched to a @murena phone running the /e/OS variant of Android and I was curious whether it had this calculator. I put in √2 and scrolled to the right a few hundred digits and it kept giving digits to me so I think it does. (Via AOSP - Android Open Source Project - presumably).
Show threadConor Titania Mc BrideNov 7
@MartinEscardo @shriramk @racketlang Re Fun in the Afternoon, it guttered and spat for a bit, but ultimately did not survive my move back to Scotland.
Show threadJeremy GibbonsNov 7
@pigworker @MartinEscardo @shriramk @racketlang SPLS is perhaps the new FitA.
Show threadConor Titania Mc BrideNov 7
@jer_gib @MartinEscardo @shriramk @racketlang SPLS was the old FitA!
Show threadShriram KrishnamurthiNov 7
@pigworker
I feel like I've gotten stuck in a Monty Python skit.
@jer_gib @MartinEscardo @racketlang
Show threadCounting Is HardNov 7

@shriramk @racketlang

I remember mark weaver (not sure if he is on mastodon) had some work doing gosper style continued fractions for guile, but I think it never got publicly released. shame really.

Show threadWorikNov 7

@shriramk @racketlang Only integers exist. All else is an abomination....

Seriously I wonder about the counter history where we never invented floating point hardware and used integer algorithms for all our calculations.

Life is too short, but integer algorithms are very interesting

E.g. I do a lot with digital audio from Jack that is f32. I wonder about translating it to u32 or u64 and how that would effect my algorithms

Life is too short...

Show threadWorikNov 7

@shriramk @racketlang of course we do computing with finite bit fields.

So the only concrete numbers we have are integers and their products

Reals are always simulated and lossy

Show threadLindsey KuperNov 8
@shriramk @racketlang I think @samth could argue either side of that one and win.
Show threadShriram KrishnamurthiNov 8
@lindsey @racketlang @samth You can probably remove "of that".
Show threadSam Tobin-HochstadtNov 11
@lindsey @shriramk @racketlang No, exact rationals don't work as a real solution (except in education-like settings) -- the other side is wrong.
Show threadLindsey KuperNov 11
@samth @shriramk @racketlang Dang it. You didn't take the bait
Show thread0xPsiDec 1
i'm hodling continued fractions too, but only because every time i try to cash out the price turns into 1 + 1/(1 + 1/(1 + …)) and the broker says it's still “converging” and to please come back after ω trades