Yeah, but that's the whole fun of using technology and ridiculously expensive (and quickly obsolete) dedicated processing hardware!

I only started playing video games (recently) just as an excuse to jump on the GPU-craze bandwagon back in 2007.

I never really bothered buying a gaming GPU till I realized just how powerful they are. I still use my first major GPU and it can still max out some of the most demanding applications today.

I just bought my 5870 purely for gpu computing, i don't play computer games. The bitcoin crash has been good for those of us looking for gear on the cheap. For 500 quid you can now get 4x5870s and for a bit more than double you can get 8x the processing power. Will be interesting to see what the next generation brings...

The problem can be greatly simplified by assuming that:

a) the needle always hits in the upper half

b) always is parallel to the x axis

c) always lands to the right

These assumptions ARE valid, as they can be accomplished by rotating or mirroring, which don't change anything in the results.

Now, a little integration, and you're done!

Tom

Hi,
also I didn't have the time. I was only thinking about analytic solution on it one time when driving home. As mentioned many times before we have the coordinates (x, y) of the center of the needle and the angle (alpha for example). Basically try to translate Buffon-Laplace needle (square) to half-circle with one side to be closed (forbidden to be crossed):
- Take half of circle
- Start with Buffon-Laplace needle problem (with all sides closed)
- Change 'left, up and down sides' of the square to be a circle.
- Calculate 'safe region' inside of this object where needle for sure will not touch or cross lines (let's name it region R1, all coordinates that are safe in all angles)
- Calculate the region between outer circle (left) side and inner 'safe' circle 0 beware, Needle problem is not the same - left side of it can not be crossed (needles MUST be inside of circle) so we need to solve P(outer circle) = P(crossing - needle problem with curved lines) - P(crossing only left side).
We have now R2 with probabilities with respect to distance & angle of them.
- Calculate the regione between 'safe space' and inner line - this again could not be straight forward Buffon needle problem because upper and downer regions does not have the same probability as middle one (in the most upper part for example the needle might not be under 90 degrees angle in respect to middle line - it might 'fall out' of the circle.
This is region R3. Maybe this region can again be divided to a square in the middle (R3a), angle-dependent body in the upper and downer part (R3b, R3c).


In the end we would need to divide the full region of half-circle and the sum of the probabilities.

This is just thinking how to 'attack' the problem... I hope I will have some time during the weekend to put it into equations and maybe some nice picture (will I get free beer if I provide nice picture?? ).


Regards,
Jure

Some answers...

The original problem: Take a disk of radius 1 and a needle of length L. Toss the needle until first succes. Here "succes" means the needle is entirely inside the unit circle. When succes happens, what is the chance that the needle (which is now completely inside the unit circle) crosses the vertical diameter (i.e. the line that connects north pole and south pole).

A precise equivalent formulation of the original problem:
(with unit disk and with needle of length L)
1. Choose a point (X,Y) with uniform distribution on the unit disk. Think of that point as the center of the needle.
2. Choose an angle theta with uniform distribution on the interval (-pi/2, +pi/2) and draw the line segment with end points (X-(L/2)cos(theta), Y-(L/2)sin(theta)) and (X+(L/2)cos(theta),Y+(L/2)sin(theta)). This line segment is our needle.

We want the conditionnal probability P[H|I] where
H = "Hit" = the event that the needle crosses the vertical diameter,
I = "Inside" = the event that the needle lies completely inside the unit circle.

Direct approach: P[H |I] = P[I and H]/P[I]

I have computed P[I] and I obtain
P[I] = ( 2 arccos(L/2) - 2L sqrt(1-(L/2)^2) )/pi.
(I am assuming, of course, that 0 < L < 2).

Note that my formula for P[I] satisfies
a) (limit of P[I] as L approaches 2) = 0
b) (limit of P[I] as L approaches 0) = 1
as one would expect.

You have doubts? Fix L and "compute" P[I] via a Monte Carlo simulation.
You will see that my formula is correct.

Now I am hoping to be able to compute P[I and H].

Ciao