Fastest and slowest algorithm to compute $\pi$

Slereah

Mar 2, 2018 10:49

you can also calculate pi using the needle trick during the exam

In mathematics, Buffon's needle problem is a question first posed in the 18th century by Georges-Louis Leclerc, Comte de Buffon: Suppose we have a floor made of parallel strips of wood, each the same width, and we drop a needle onto the floor. What is the probability that the needle will lie across a line between two strips? Buffon's needle was the earliest problem in geometric probability to be solved; it can be solved using integral geometry. The solution, in the case where the needle length is not greater than the width of the strips, can be used to design a Monte Carlo method for approximating...

Balarka Sen

tfw you forgot the value of pi while writing an exam so you borrow the teacher's matchbox to do a quick nee--- fucking hell

Slereah

B)

Emilio Pisanty

@BalarkaSen Buffon's needle is sloooooooooooooooooow

Anonymous

If someone forgets the value of pi during a math exam, I doubt they would have any idea about Buffon's needle :P

Slereah

Buffon's noodle

In geometric probability, the problem of Buffon's noodle is a variation on the well-known problem of Buffon's needle, named after Georges-Louis Leclerc, Comte de Buffon who lived in the 18th century. That problem solved by Buffon was the earliest geometric probability problem to be solved. == Buffon's needle == Suppose there exist an infinite number of equally spaced parallel lines, and we were to randomly toss a needle whose length is less than or equal to the distance between adjacent lines. What is the probability that the needle will cross a line? The formula is P ...

even more delicious

Emilio Pisanty

Mar 2, 2018 10:50

you'll be throwing matches all day just to get to three significant figures

Balarka Sen

I did it with 30 matches and some standard ruling and got 3.15 I think

Dawood ibn Kareem

@BalarkaSen You could probably calculate the probability of that happening. Doesn't prove that it doesn't take all day to be sure of three significant figures.

Balarka Sen

Maybe I got ze lucky. I don't know what the standard deviation of that experiment is.

Emilio Pisanty

@Slereah what if you do Buffon's noodle with a Hilbert space-filling curve?

Balarka Sen

@DawoodibnKareem Jesus christ let me finish

Y'all are sniping me hard

rages in the background

Dawood ibn Kareem

Mar 2, 2018 10:53

Sorry, I'll be careful not to talk while you're in the room, and likely to talk yourself.

Balarka Sen

I was being facetious

Dawood ibn Kareem

Snap!

Balarka Sen

lmao

Secret

I wonder what's the quickest way to derive pi to at least 10 d.p. ?

Balarka Sen

You're right, of course. I don't actually know what the standard deviation is.

Dawood ibn Kareem

Mar 2, 2018 10:54

@Secret System.out.println(Math.PI);

Secret

that's cheating!

Anonymous

265

Q: What is the fastest way to get the value of π?

Solutions are welcome in any language. :-) I'm looking for the fastest way to obtain the value of π, as a personal challenge. More specifically I'm using ways that don't involve using #defined constants like M_PI, or hard-coding the number in. The program below tests the various ways I know of. ...

Balarka Sen

Hm, how fast does Wallis product converge?

CooperCape

@Secret Get a polygon with enough sides find the perimeter and do a thing?

Cause I'm basic

Secret

@CooperCape I thought that was too slow...

CooperCape

Mar 2, 2018 10:55

Oh fair enough...

Balarka Sen

Faster than the Riemann sum

Also if you use the wrong Riemann sum you'll converge to 4

Anonymous

The bisection method is still the fastest by hand

Anonymous

I think

John Rennie

@Secret there are series that converge very fast to pi. Offhand I can't remember them, but a quick Google should find the details.

Anonymous

Others are too complicated

Slereah

Mar 2, 2018 10:56

what is the slowest method to get pi, though

Dawood ibn Kareem

@BalarkaSen Yes, that's called squaring the circle.

Anonymous

@Slereah That doesn't converge

Balarka Sen

@JohnRennie There are series acceleration algorithms which accelerate speed of convergence of serieses, IIRC

John Rennie

@Slereah the Euler series converges very slowly as I recall.

Dawood ibn Kareem

@JohnRennie I know one: 1, 2, 3, pi, pi, pi, pi, pi, pi, pi, ...

Secret

Mar 2, 2018 10:57

@Slereah is there even a slowest thing in a linear order set of algorithms? -_-

Balarka Sen

Hah @Dawood

Gotteem

Secret

(To read the above sentence, make "even" higher pitched)

John Rennie

265

Q: What is the fastest way to get the value of π?

Solutions are welcome in any language. :-) I'm looking for the fastest way to obtain the value of π, as a personal challenge. More specifically I'm using ways that don't involve using #defined constants like M_PI, or hard-coding the number in. The program below tests the various ways I know of. ...

performance algorithm language-agnostic unix pi

Anonymous

@Secret Do you think he's being serious :P

Balarka Sen

@Secret Look up Cohen-Villegas-Zagier acceleration

Slereah

Mar 2, 2018 10:57

I remember reading a paper about the slowest sorting algorithm

slower than bogosort

Anonymous

@JohnRennie Ninja'd already :)

Anonymous

^

Secret

Too many snips and ninjas, but thanks guys

John Rennie

@Slereah arrange the elements in a random order. Check if they're sorted. If not rinse and repeat :-)

Slereah

math.northwestern.edu/~mlerma/papers/inefficient_algorithms.pdf

Secret

Mar 2, 2018 10:58

bookmarks conversation

Slereah

very inefficient

Anonymous

I always wanted a ninja costume

Slereah

@JohnRennie that's bogosort :p

This one is even slower

John Rennie

Ah ...

Slereah

statistically, anyway

Bogosort's average sorting time is $O(n!)$, but its worst case is $O(\infty)$

Balarka Sen

Mar 2, 2018 10:59

bogusort

what the fuck does O(\infty) mean

Slereah

well the sorting time can be arbitrarily long

if truly random

Balarka Sen

Is that what you use to denote that? Fucking physicists

Anonymous

Lol. "Quantum Bogosort"

Anonymous

Just google it

Anonymous

122

A: Are there any worse sorting algorithms than Bogosort (a.k.a Monkey Sort)?

Quantum Bogosort A sorting algorithm that assumes that the many-worlds interpretation of quantum mechanics is correct: Check that the list is sorted. If not, destroy the universe. At the conclusion of the algorithm, the list will be sorted in the only universe left standing. This algorithm t...

John Rennie

Mar 2, 2018 11:01

@BalarkaSen that's what Sam uses :-)

Physicists don't believe in infinity anyway

Dawood ibn Kareem

It uses up a lot of universes though. That must piss off the inhabitants somewhat.

Balarka Sen

"This is obviously the best sorting algorithm, not the worst."

John Rennie

Though I'm willing to believe the universe is unbounded. Whether that makes it infinite or not (in mathematician's terms) I neither know nor care :-)

Dawood ibn Kareem

It depends how long it takes to check whether the list is sorted, as many times as there are universes.

Balarka Sen

@JohnRennie It's hella large at the very least :)

Hella large is technically infinite

The adjective "hella" is important

Fastest and slowest algorithm to compute $\pi$

The h Bar

Participants