this post was submitted on 22 Jan 2024
725 points (99.1% liked)

Science Memes

10348 readers
2100 users here now

Welcome to c/science_memes @ Mander.xyz!

A place for majestic STEMLORD peacocking, as well as memes about the realities of working in a lab.

Rules

  1. Don't throw mud. Behave like an intellectual and remember the human.
  2. Keep it rooted (on topic).
  3. No spam.
  4. Infographics welcome, get schooled.

Research Committee

Other Mander Communities

Science and Research

Biology and Life Sciences

Physical Sciences

Humanities and Social Sciences

Practical and Applied Sciences

Memes

Miscellaneous

founded 2 years ago
MODERATORS
[email protected]
[email protected]
[email protected]
725
Magic π (mander.xyz)
submitted 8 months ago by [email protected] to c/[email protected]
69 comments fedilink hide all child comments
 
you are viewing a single comment's thread
view the rest of the comments
[–] [email protected] 2 points 8 months ago (1 children)

Turns out that's not possible because the complexity of computing pi becomes exponentially harder the more digits you add.

[–] [email protected] 39 points 8 months ago* (last edited 8 months ago) (2 children)

That is definitely not true. Pi has been computed to way more digits than would be feasible if it were exponential. Looks to me like it's O(n log(n)^3) with n=the number of digits, which sounds basically fine for any number of digits any human is going to have the patience to scroll down to.

[–] [email protected] 7 points 8 months ago (1 children)

There was a recent post asking what the self-taught among us feel we are missing from our knowledge base. For me, it's being able to calculate stuff like that for making decisions. I feel like I can spot an equivalence to the travelling salesman problem or to the halting problem a mile away, but anything more subtle is beyond me.

Of course, in this situation, I'd probably just see if I could find a sufficiently large precalculation and just pretend :)

[–] [email protected] 8 points 8 months ago

Just put up a little spinning it’s-loading icon with an increasing delay. Then, when you run out of precalculated data, make it spin forever.

“It’s infinte scrolling man, you just didn’t wait long enough. It’s not my fault you can’t be more patient.”

[–] [email protected] 4 points 8 months ago* (last edited 8 months ago) (1 children)

Okay, maybe exponential is the wrong math term, but my point is, the complexity grows with number of digits. Infinite scrolling is therefore impossible because eventually it will become too slow to keep up with scrolling. You may be right that it may go farther than any human is willing to scroll, but that depends on the human and if they're on a potato phone.

As far as I know, the current fastest algorithm is the Bailey–Borwein–Plouffe formula,, which is O(n log n) to calculate the nth digit (not even the whole number). Infinite scrolling is only possible if we can calculate the nth digit in O(1) time.

[–] [email protected] 8 points 8 months ago

Oh shit! Yeah, it looks like as of 2022 that article I linked to needs to be updated. It should say O(n log n), yes.

That said, scrolling ever-farther on a web page will always get slower the further down you go, and eventually fail, because of memory allocation. If you ignore some of the factors that make all truly-infinite pages impossible, and require an O(1) algorithm to generate numbers within the inherently-more-than-O(1) process of rendering the page in the first place, then sure, it’s impossible. My point is, the asymptotic complexity is low enough that you can make a page that does it and it’ll work in practice.