🚀 go-pugleaf

I heard there is a programmatic way of not just estimating Pi, but PROVING
it to any decimal precision. The problem is that the speed of the algorithm
slows in a logarithmic fashion proportional to the precision... (eg. doubly
long to calculate the next digit and so on)

ch!/\z,
       Kwyxta.

Earl F. Glynn <EarlGlynn@att.net> wrote in message
news:7ks8ls$mgk$1@bgtnsc03.worldnet.att.net...
> An updated "Lab Report" about estimating the value of pi
> by "throwing" needles on a set of parallel lines can be found at:
>
> http://www.efg2.com/lab/Mathematics/Buffon.htm
>
> The example includes complete Delphi source code and a
> complete description of the mathematics and the various
> methods of randomly "throwing" the needles.
>
> Some may be interested in how a procedure variable was
> used by a set of radio buttons to set the procedure that was
> used to do the computations.
>
> _________________________________
> efg's Computer Lab:  http://www.efg2.com/lab
> Delphi Books:  http://www.efg2.com/lab/TechBooks/Delphi.htm
>
> Earl F. Glynn     E-Mail:  EarlGlynn@att.net
> Overland Park, KS  USA
>
>
>

Kwyxta <kwyxta@blaze.net.au> schrieb in im Newsbeitrag: 930210181.490291@diddley.primus.com.au...
> I heard there is a programmatic way of not just estimating Pi, but PROVING
> it to any decimal precision. The problem is that the speed of the algorithm
> slows in a logarithmic fashion proportional to the precision... (eg. doubly
> long to calculate the next digit and so on)

Then "exponentially" would be the right expression, it slows down
exponentially. If this is true, the algorithm ist absolutely useless.

Say, if you need 1/1000 second to calculate 10 digits of PI, you would
need 1.024 seconds to calculate 20 digits and 1048.576 seconds to calculate
30 digits. For only 50 digits you would need over one billion seconds(!).
I could do that myself much quicker.

CU,
  Marco

--
****************************************************
* E-mail:    marco.lange@gmx.de                    *
* Homepage:  http://www.marcolange.de              *
* ICQ:       35807782                              *
****************************************************

JRS:  In article <7ks8ls$mgk$1@bgtnsc03.worldnet.att.net> of Wed, 23 Jun
1999 22:24:59 in news:comp.lang.pascal.delphi.misc, Earl F. Glynn
<EarlGlynn@att.net> wrote:
>An updated "Lab Report" about estimating the value of pi
>by "throwing" needles on a set of parallel lines can be found at:
>
>http://www.efg2.com/lab/Mathematics/Buffon.htm
>
>The example includes complete Delphi source code and a
>complete description of the mathematics and the various
>methods of randomly "throwing" the needles.

The following will do it, in BP7 and D3 DCC32 -cc modes :

  var U, V, W : longint ;
  begin V := 0 ; W := 10000000 ; Randomize ;
  for U := 1 to W do if cos(Random*Pi*0.5)>Random then Inc(V) ;
  Write(2.0/(V/W):0:6) ; Readln ;
  end.

This represents a needle of length 2 thrown on planks spaced by 2, and
tests whether the projected half-length of the needle exceeds the
distance between the centre and the nearest line.

It will be interesting to see whether you've managed to avoid using a
value for Pi, implicitly or explicitly, in the work.

A quick test shows that the result obtained from the above code depends
on, but is not proportional to, the value used for Pi.
 
-- 
 � John Stockton, Surrey, UK.  jrs@merlyn.demon.co.uk   Turnpike v4.00   MIME. �
  Web <URL: http://www.merlyn.demon.co.uk/> - TP/BP/&c. FAQqish topics & links.
  Timo's TurboPascal <A HREF="ftp://garbo.uwasa.fi/pc/link/tsfaqp.zip">FAQ</A>.
  <A HREF="http://www.merlyn.demon.co.uk/clpb-faq.txt">Mini-FAQ</A> of c.l.p.b.

In article <7kss7t$522$1@fu-berlin.de>,
  "Marco Lange" <marco.lange@gmx.de> wrote:
>
> Kwyxta <kwyxta@blaze.net.au> schrieb in im Newsbeitrag:
930210181.490291@diddley.primus.com.au...
> > I heard there is a programmatic way of not just estimating Pi, but
PROVING
> > it to any decimal precision. The problem is that the speed of the
algorithm
> > slows in a logarithmic fashion proportional to the precision... (eg.
doubly
> > long to calculate the next digit and so on)
>
> Then "exponentially" would be the right expression, it slows down
> exponentially. If this is true, the algorithm ist absolutely useless.

    The Buffon needle thing _is_ absolutely useless as a practical
method for calculating Pi. It's not supposed to be a practical
algorithm for finding Pi (plenty of algorithms for that exist),
it's just a mathematical curiosity: hmm, if you do this you get
Pi, isn't that interesting.

> Say, if you need 1/1000 second to calculate 10 digits of PI, you would
> need 1.024 seconds to calculate 20 digits and 1048.576 seconds to
calculate
> 30 digits.

    It's much worse than that (but again, it's not supposed to
be a practical method for doing the calculation). I once made a
little Buffon simulation gizmo - took a _long_ time to get
4 or 5 decimals right, if I recall correctly. (I _never_ got
much farther than that - even ignoring roundoff, you'd need a
very very good random number generator.)

> For only 50 digits you would need over one billion
seconds(!).
> I could do that myself much quicker.
>
> CU,
>   Marco
>
> --
> ****************************************************
> * E-mail:    marco.lange@gmx.de                    *
> * Homepage:  http://www.marcolange.de              *
> * ICQ:       35807782                              *
> ****************************************************
>
>


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

> A quick test shows that the result obtained from the above code depends
> on, but is not proportional to, the value used for Pi.

The probability a needle intersects a line is 1/pi.
A efficient formula to compute pi can be found at
http://www.mathsoft.com/asolve/plouffe/plouffe.html

La probabilite qu'un aiguille intersecte une ligne est 1/pi.
Une formule efficace pour calculer pi se trouve sur
http://www.mathsoft.com/asolve/plouffe/plouffe.html

Emmanuel

JRS:  In article <Im0c0MABmjc3Ew2K@merlyn.demon.co.uk> of Thu, 24 Jun
1999 14:58:25 in news:comp.lang.pascal.delphi.misc, Dr John Stockton
<jrs@merlyn.demon.co.uk> wrote:
>
>It will be interesting to see whether you've managed to avoid using a
>value for Pi, implicitly or explicitly, in the work.

Having now had an opportunity to access the rather nice Web page, I see
that you decided to do so.

As a presentation of the Needles, it looks excellent.

As a means of determining Pi, however, there is a logical difficulty
when the DirectionMethods are considered.

Method 1 is, rightly, both presented and rejected.

Method 2, which AIUI works, considers a semicircle with a circumscribing
semisquare, generates evenly-distributed random points within the
semisquare, and accepts for further use those within the semicircle.
This virtually calculates Pi anyway, as the proportion accepted is Pi/2.
The technique is, BTW, close to that of a good way of generating random
points with a defined but uneven distribution : <URL: http://www.merlyn.
demon.co.uk/pas-rand.htm#RandDist>.

Method 3 uses Sin & Cos of random and adequately large angles,
ostensibly not using Pi.  But these functions require Pi internally,
since practical evaluation will require subtracting multiples of TwoPi
from the argument (assumed in radians; otherwise Pi can be deduced as
below).

Method 4 uses half-angle and angle-addition formulae to generate sines
and cosines of evenly-spaced angles, starting with a "unit" of one
right-angle - these can then be randomly chosen, though it would be
better for the final Buffon value to systematically use all of them (and
to systematically evenly choose the needle-centres).  But, since, for
small x in radians, sin(x)=x, the angle-halving is itself essentially
capable of determining the radian as a fraction of a right angle, which
determines Pi.


I wonder whether there is a method of doing Buffon which does not use Pi
(implicitly or explicitly), does not have a subset-capability of
determining Pi, and does not, as Buffon did, use the Real World?


ISTR that it is established that more rapid convergence is obtained if
you glue the needles together in pairs, at right angles - centrally is
usual but I think not necessary; more rapid even if one counts needles
rather than throws.

It must be better still to glue large numbers, evenly distributed in
angle, together - centrally to get a disc, or endwise to get a ring.
Not too many, though; with an infinite number of needles, unless
carefully treated, there's a risk of getting infinity/infinity as the
result.


I guess that the true intention was to draw attention to the services
you provide at efg's Computer Lab (http://www.efg2.com/lab) - ISTM that
it is working.
 
-- 
 � John Stockton, Surrey, UK.  jrs@merlyn.demon.co.uk   Turnpike v4.00   MIME. �
  Web <URL: http://www.merlyn.demon.co.uk/> - TP/BP/&c. FAQqish topics & links.
  Timo's TurboPascal <A HREF="ftp://garbo.uwasa.fi/pc/link/tsfaqp.zip">FAQ</A>.
  <A HREF="http://www.merlyn.demon.co.uk/clpb-faq.txt">Mini-FAQ</A> of c.l.p.b.

JRS:  In article <37737E88.C3B802D7@research.telcordia.com> of Fri, 25
Jun 1999 09:05:12 in news:comp.lang.pascal.delphi.misc, Emmanuel BRESSON
<ebresson@research.telcordia.com> wrote:
>> A quick test shows that the result obtained from the above code depends
>> on, but is not proportional to, the value used for Pi.
>
>The probability a needle intersects a line is 1/pi.
>A efficient formula to compute pi can be found at
>http://www.mathsoft.com/asolve/plouffe/plouffe.html
>
>La probabilite qu'un aiguille intersecte une ligne est 1/pi.
>Une formule efficace pour calculer pi se trouve sur
>http://www.mathsoft.com/asolve/plouffe/plouffe.html

2.0/Pi, if the needle can just span a board.

Possibly you miss my point; I am referring here not to the ideal Pi, but
to the value actually used in the calculation, which can be changed.  As
the result is not proportional, one might possibly determine Pi as that
value which, when used in the simulation, leads to a result of itself.

The BBP algorithm is certainly interesting; I've put it in my
longcalc.pas, and, if base 16 is set, one can see the digits of 16^n*Pi
settling one by one.  I don't recall any claim that it is particularly
efficient, though.
 
-- 
 � John Stockton, Surrey, UK.  jrs@merlyn.demon.co.uk   Turnpike v4.00   MIME. �
  Web <URL: http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
  Correct 4-line sig. separator is as above, a line precisely "-- " (SoRFC1036)
  Do not Mail News to me.    Before a reply, quote with ">" or "> " (SoRFC1036)

In article <Im0c0MABmjc3Ew2K@merlyn.demon.co.uk>,
  Dr John Stockton <jrs@merlyn.demon.co.uk> wrote:
> JRS:  In article <7ks8ls$mgk$1@bgtnsc03.worldnet.att.net> of Wed, 23
Jun
> 1999 22:24:59 in news:comp.lang.pascal.delphi.misc, Earl F. Glynn
> <EarlGlynn@att.net> wrote:
> >An updated "Lab Report" about estimating the value of pi
> >by "throwing" needles on a set of parallel lines can be found at:
> >
> >http://www.efg2.com/lab/Mathematics/Buffon.htm
> >
> >The example includes complete Delphi source code and a
> >complete description of the mathematics and the various
> >methods of randomly "throwing" the needles.
>
> The following will do it, in BP7 and D3 DCC32 -cc modes :
>
>   var U, V, W : longint ;
>   begin V := 0 ; W := 10000000 ; Randomize ;
>   for U := 1 to W do if cos(Random*Pi*0.5)>Random then Inc(V) ;
>   Write(2.0/(V/W):0:6) ; Readln ;
>   end.
>
> This represents a needle of length 2 thrown on planks spaced by 2, and
> tests whether the projected half-length of the needle exceeds the
> distance between the centre and the nearest line.
>
> It will be interesting to see whether you've managed to avoid using a
> value for Pi, implicitly or explicitly, in the work.
>
> A quick test shows that the result obtained from the above code
depends
> on, but is not proportional to, the value used for Pi.

     I don't know whether there are any Pi's in Earl's code, but
they're not needed for the Buffon thing. You're letting the needle
spin at most one full revolution, stopping at some random spot
during the first revolution. If you instead let the needle spin
"forever" and stop it at a random spot between now and then you
get Pi.

     Ie: if you say cos(Random*L) for some large number L
instead of cos(Random*Pi*0.5) you get an estimate that approaches
Pi as L tends to infinity.

> --
>  � John Stockton, Surrey, UK.  jrs@merlyn.demon.co.uk   Turnpike v4.00
  MIME. �
>   Web <URL: http://www.merlyn.demon.co.uk/> - TP/BP/&c. FAQqish topics
& links.
>   Timo's TurboPascal <A
HREF="ftp://garbo.uwasa.fi/pc/link/tsfaqp.zip">FAQ</A>.
>   <A HREF="http://www.merlyn.demon.co.uk/clpb-faq.txt">Mini-FAQ</A> of
c.l.p.b.
>


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

JRS:  In article <7l165c$gqa$1@bgtnsc02.worldnet.att.net> of Fri, 25 Jun
1999 19:22:15 in news:comp.lang.pascal.delphi.misc, Earl F. Glynn
<EarlGlynn@att.net> wrote:
>Dr John Stockton <jrs@merlyn.demon.co.uk> wrote in message
>news:zZIi7jAzW8c3EwDD@merlyn.demon.co.uk...
>> >It will be interesting to see whether you've managed to avoid using a
>> >value for Pi, implicitly or explicitly, in the work.
>
>> Method 4 uses half-angle and angle-addition formulae to generate sines
>> and cosines of evenly-spaced angles, starting with a "unit" of one
>> right-angle
>
>There was no angle-addition formula used in Method 4.

The rotation matrix is in effect a pair of addition formulae, surely?

>The half-angle recurrence formulas only involves a SQRT, not any
>trig function.  The starting value is 0.0, i.e., cos(90 degrees).
>
>The generated sequences of SIN and COS values from the
>recurrence relationship were just algebraic expressions.
>Is your objection to an "implicit" use of PI because SINs and
>COSs were used in the explanation?  

No; the full paragraph of mine reads "Method 4 uses half-angle and
angle-addition formulae to generate sines and cosines of evenly-spaced
angles, starting with a "unit" of one right-angle - these can then be
randomly chosen, though it would be better for the final Buffon value to
systematically use all of them (and to systematically evenly choose the
needle-centres).  But, since, for small x in radians, sin(x)=x, the
angle-halving is itself essentially capable of determining the radian as
a fraction of a right angle, which determines Pi."

You are using, as part of your emulation of Buffon's random-needle Pi
method, a systematic algorithm which itself essentially determines Pi;
you don't import Pi, you virtually make it!.



I can't imagine that it will make any significant difference to the
final result, as standard computer arithmetic is reasonably precise :
but, in principle, I think that one can improve (with a bit more head-
scratching while programming) on repeatedly bifurcating a right angle
and then continually rotating to get, in linear sequence, an equally-
spaced set of angles filling the right angle.  Starting with the zero-
degree point, rotate it by half the right angle to get a second point,
then repeatedly halve the angle and use rotation of each point by it to
double the set of points - rounding errors will build up even less.


If you have not already done so, it may be possible to make Method 3 a
little quicker by using FSINCOS in the FPU so as to generate both SIN &
COS in one move.


Rather than using two crossed needles on floorboards, one can equally
well, I imagine, use a single needle on a square-tiled floor.
 
-- 
 � John Stockton, Surrey, UK. jrs@merlyn.demon.co.uk / JR.Stockton@physics.org �
  Web <URL: http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
  Correct 4-line sig. separator is as above, a line precisely "-- " (SoRFC1036)
  Do not Mail News to me.    Before a reply, quote with ">" or "> " (SoRFC1036)

In article <zZIi7jAzW8c3EwDD@merlyn.demon.co.uk>,
  Dr John Stockton <jrs@merlyn.demon.co.uk> wrote:
> JRS:  In article <Im0c0MABmjc3Ew2K@merlyn.demon.co.uk> of Thu, 24 Jun
> 1999 14:58:25 in news:comp.lang.pascal.delphi.misc, Dr John Stockton
> <jrs@merlyn.demon.co.uk> wrote:
> >
> >It will be interesting to see whether you've managed to avoid using a
> >value for Pi, implicitly or explicitly, in the work.
>
[...]
> I wonder whether there is a method of doing Buffon which does not use
Pi
> (implicitly or explicitly), does not have a subset-capability of
> determining Pi, and does not, as Buffon did, use the Real World?

       I have no idea what a "subset-capability" is, but modulo
that of course there is. Set one endpoint P1 of the needle to a
random point in a large square. Then set the other endpoint
to another random point. Reject the second endpoint until you
get one with say 0.5 < |P1 - P2| < 2. Then rescale it so
|P1 - P2| = 1. There's your random needle, no trig and hence
no Pi required.

   ("rescale": say P2 := P1 + (P2 - P1)/|P2 - P1| . No
angles, just a square root.)

> ISTR that it is established that more rapid convergence is obtained if
> you glue the needles together in pairs, at right angles - centrally is
> usual but I think not necessary; more rapid even if one counts needles
> rather than throws.
>
> It must be better still to glue large numbers, evenly distributed in
> angle, together - centrally to get a disc, or endwise to get a ring.
> Not too many, though; with an infinite number of needles, unless
> carefully treated, there's a risk of getting infinity/infinity as the
> result.

     Huh? The limit in question _is_ a limit "of the form
infinity/infinity". I don't think there's much danger of
the actual algorithm running infinitely many times.

> I guess that the true intention was to draw attention to the services
> you provide at efg's Computer Lab (http://www.efg2.com/lab) - ISTM
that
> it is working.
>
> --
>  � John Stockton, Surrey, UK.  jrs@merlyn.demon.co.uk   Turnpike v4.00
  MIME. �
>   Web <URL: http://www.merlyn.demon.co.uk/> - TP/BP/&c. FAQqish topics
& links.
>   Timo's TurboPascal <A
HREF="ftp://garbo.uwasa.fi/pc/link/tsfaqp.zip">FAQ</A>.
>   <A HREF="http://www.merlyn.demon.co.uk/clpb-faq.txt">Mini-FAQ</A> of
c.l.p.b.
>


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

On Sat, 26 Jun 1999 18:13:14 GMT, David C. Ullrich
<ullrich@math.okstate.edu> wrote:
>In article <zZIi7jAzW8c3EwDD@merlyn.demon.co.uk>,
>  Dr John Stockton <jrs@merlyn.demon.co.uk> wrote:
>> JRS:  In article <Im0c0MABmjc3Ew2K@merlyn.demon.co.uk> of Thu, 24 Jun
>> 1999 14:58:25 in news:comp.lang.pascal.delphi.misc, Dr John Stockton
>> <jrs@merlyn.demon.co.uk> wrote:
>> >
>> >It will be interesting to see whether you've managed to avoid using a
>> >value for Pi, implicitly or explicitly, in the work.
>>
>[...]
>> I wonder whether there is a method of doing Buffon which does not use
>Pi
>> (implicitly or explicitly), does not have a subset-capability of
>> determining Pi, and does not, as Buffon did, use the Real World?
>
>       I have no idea what a "subset-capability" is, but modulo
>that of course there is. Set one endpoint P1 of the needle to a
>random point in a large square. Then set the other endpoint
>to another random point. Reject the second endpoint until you
>get one with say 0.5 < |P1 - P2| < 2. Then rescale it so
>|P1 - P2| = 1. There's your random needle, no trig and hence
>no Pi required.
>
>   ("rescale": say P2 := P1 + (P2 - P1)/|P2 - P1| . No
>angles, just a square root.)

Will that give an even distribution of angles?  It seems like it ought
to give some sort of bias towards rectangular angles.  (Old joke time:
Is there a STATISTICIAN in the house?)

-- 
"Generally speaking, things have gone about as far as they can possibly
go when things have got about as bad as they reasonably get."

JRS:  In article <7l357k$4m6$1@nnrp1.deja.com> of Sat, 26 Jun 1999
18:13:14 in news:comp.lang.pascal.delphi.misc, David C. Ullrich
<ullrich@math.okstate.edu> wrote:
>In article <zZIi7jAzW8c3EwDD@merlyn.demon.co.uk>,
>  Dr John Stockton <jrs@merlyn.demon.co.uk> wrote:

>       I have no idea what a "subset-capability" is, but modulo
>that of course there is. Set one endpoint P1 of the needle to a
>random point in a large square. Then set the other endpoint
>to another random point. Reject the second endpoint until you
>get one with say 0.5 < |P1 - P2| < 2. Then rescale it so
>|P1 - P2| = 1. There's your random needle, no trig and hence
>no Pi required.
>
>   ("rescale": say P2 := P1 + (P2 - P1)/|P2 - P1| . No
>angles, just a square root.)

ISTM, seemingly confirmed by test, that your method does not give a
uniform distribution of angles.


>> It must be better still to glue large numbers, evenly distributed in
>> angle, together - centrally to get a disc, or endwise to get a ring.
>> Not too many, though; with an infinite number of needles, unless
>> carefully treated, there's a risk of getting infinity/infinity as the
>> result.
>
>     Huh? The limit in question _is_ a limit "of the form
>infinity/infinity". I don't think there's much danger of
>the actual algorithm running infinitely many times.

With an infinite number of needles glued together, the algorithm need
only be run once - though this will take infinite time.
 
-- 
 � John Stockton, Surrey, UK.  jrs@merlyn.demon.co.uk   Turnpike v4.00   MIME. �
  Web <URL: http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
  Correct 4-line sig. separator is as above, a line precisely "-- " (SoRFC1036)
  Do not Mail News to me.    Before a reply, quote with ">" or "> " (SoRFC1036)

On Sat, 26 Jun 1999 20:01:09 GMT, drifkind@acm.deleteme.org (David
Rifkind) wrote:
>On Sat, 26 Jun 1999 18:13:14 GMT, David C. Ullrich
><ullrich@math.okstate.edu> wrote:
>>In article <zZIi7jAzW8c3EwDD@merlyn.demon.co.uk>,
>>  Dr John Stockton <jrs@merlyn.demon.co.uk> wrote:
>>> JRS:  In article <Im0c0MABmjc3Ew2K@merlyn.demon.co.uk> of Thu, 24 Jun
>>> 1999 14:58:25 in news:comp.lang.pascal.delphi.misc, Dr John Stockton
>>> <jrs@merlyn.demon.co.uk> wrote:
>>> >
>>> >It will be interesting to see whether you've managed to avoid using a
>>> >value for Pi, implicitly or explicitly, in the work.
>>>
>>[...]
>>> I wonder whether there is a method of doing Buffon which does not use
>>Pi
>>> (implicitly or explicitly), does not have a subset-capability of
>>> determining Pi, and does not, as Buffon did, use the Real World?
>>
>>       I have no idea what a "subset-capability" is, but modulo
>>that of course there is. Set one endpoint P1 of the needle to a
>>random point in a large square. Then set the other endpoint
>>to another random point. Reject the second endpoint until you
>>get one with say 0.5 < |P1 - P2| < 2. Then rescale it so
>>|P1 - P2| = 1. There's your random needle, no trig and hence
>>no Pi required.
>>
>>   ("rescale": say P2 := P1 + (P2 - P1)/|P2 - P1| . No
>>angles, just a square root.)
>
>Will that give an even distribution of angles?  It seems like it ought
>to give some sort of bias towards rectangular angles.  (Old joke time:
>Is there a STATISTICIAN in the house?)

Ohhh...never mind.

-- 
"Generally speaking, things have gone about as far as they can possibly
go when things have got about as bad as they reasonably get."

In article <3775731b.19624768@netnews.worldnet.att.net>,
  drifkind@acm.deleteme.org (David Rifkind) wrote:
> On Sat, 26 Jun 1999 20:01:09 GMT, drifkind@acm.deleteme.org (David
> Rifkind) wrote:
> >On Sat, 26 Jun 1999 18:13:14 GMT, David C. Ullrich
> ><ullrich@math.okstate.edu> wrote:
> >>In article <zZIi7jAzW8c3EwDD@merlyn.demon.co.uk>,
> >>  Dr John Stockton <jrs@merlyn.demon.co.uk> wrote:
> >>> JRS:  In article <Im0c0MABmjc3Ew2K@merlyn.demon.co.uk> of Thu, 24
Jun
> >>> 1999 14:58:25 in news:comp.lang.pascal.delphi.misc, Dr John
Stockton
> >>> <jrs@merlyn.demon.co.uk> wrote:
> >>> >
> >>> >It will be interesting to see whether you've managed to avoid
using a
> >>> >value for Pi, implicitly or explicitly, in the work.
> >>>
> >>[...]
> >>> I wonder whether there is a method of doing Buffon which does not
use
> >>Pi
> >>> (implicitly or explicitly), does not have a subset-capability of
> >>> determining Pi, and does not, as Buffon did, use the Real World?
> >>
> >>       I have no idea what a "subset-capability" is, but modulo
> >>that of course there is. Set one endpoint P1 of the needle to a
> >>random point in a large square. Then set the other endpoint
> >>to another random point. Reject the second endpoint until you
> >>get one with say 0.5 < |P1 - P2| < 2. Then rescale it so
> >>|P1 - P2| = 1. There's your random needle, no trig and hence
> >>no Pi required.
> >>
> >>   ("rescale": say P2 := P1 + (P2 - P1)/|P2 - P1| . No
> >>angles, just a square root.)
> >
> >Will that give an even distribution of angles?  It seems like it
ought
> >to give some sort of bias towards rectangular angles.  (Old joke
time:
> >Is there a STATISTICIAN in the house?)
>
> Ohhh...never mind.

     Too late. If anyone else is wondering what the problem was,
or is maybe wondering about the same (non-)problem: note the
words "Reject the second endpoint until you get one with say
0.5 < |P1 - P2| < 2."

     (Of course a person wouldn't actually choose a brand-new
P2, a person would choose P2 at random in a small square
centered at P1, trying til he got one in that annullus.)

> "Generally speaking, things have gone about as far as they can
possibly
> go when things have got about as bad as they reasonably get."
>


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

In article <3zADx9AXVWd3EwJU@merlyn.demon.co.uk>,
  Dr John Stockton <jrs@merlyn.demon.co.uk> wrote:
> JRS:  In article <7l357k$4m6$1@nnrp1.deja.com> of Sat, 26 Jun 1999
> 18:13:14 in news:comp.lang.pascal.delphi.misc, David C. Ullrich
> <ullrich@math.okstate.edu> wrote:
> >In article <zZIi7jAzW8c3EwDD@merlyn.demon.co.uk>,
> >  Dr John Stockton <jrs@merlyn.demon.co.uk> wrote:
>
> >       I have no idea what a "subset-capability" is, but modulo
> >that of course there is. Set one endpoint P1 of the needle to a
> >random point in a large square. Then set the other endpoint
> >to another random point. Reject the second endpoint until you
> >get one with say 0.5 < |P1 - P2| < 2. Then rescale it so
> >|P1 - P2| = 1. There's your random needle, no trig and hence
> >no Pi required.
> >
> >   ("rescale": say P2 := P1 + (P2 - P1)/|P2 - P1| . No
> >angles, just a square root.)
>
> ISTM, seemingly confirmed by test, that your method does not give a
> uniform distribution of angles.

    If so then you're trying something other than what I suggested.
Did you read all of it or just a few sentences?

    Psuedocode (note these are all real variables, converting to
integers too soon would be bad):

//"Set [...] P1 [...] to a random
//point in a large square":

    N:= LargeNumber;
    P1.X:= N*random;
    P1.Y:= N*random;

//"Then set the other endpoint
//to another random point. Reject the second endpoint until you
//get one with say 0.5 < |P1 - P2| < 2":

    repeat
       X:= 1 - 2*random;
       Y:= 1 - 2*random;
    until 0.25 < X*X + Y*Y < 4;
//the actual numbers 0.25 and 4 don't matter

//"rescale" as suggested:

    r:= sqrt(X*X + Y*Y);
    P2.X:= P1.X + X/r;
    P2.Y:= P1.Y + Y/r;

     If you don't get a uniform distribution of angles from
lemme know and I'll make an actual compilable version (if the
RNG is worse than I thought it won't work, of course. But I
didn't think the RNG was _that_ bad.)

> >> It must be better still to glue large numbers, evenly distributed
in
> >> angle, together - centrally to get a disc, or endwise to get a
ring.
> >> Not too many, though; with an infinite number of needles, unless
> >> carefully treated, there's a risk of getting infinity/infinity as
the
> >> result.
> >
> >     Huh? The limit in question _is_ a limit "of the form
> >infinity/infinity". I don't think there's much danger of
> >the actual algorithm running infinitely many times.
>
> With an infinite number of needles glued together, the algorithm need
> only be run once - though this will take infinite time.

    Aha.

> --
>  � John Stockton, Surrey, UK.  jrs@merlyn.demon.co.uk   Turnpike v4.00
  MIME. �
>   Web <URL: http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms,
& links.
>   Correct 4-line sig. separator is as above, a line precisely "-- "
(SoRFC1036)
>   Do not Mail News to me.    Before a reply, quote with ">" or "> "
(SoRFC1036)
>


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

JRS:  In article <7l61qb$u9u$1@nnrp1.deja.com> of Sun, 27 Jun 1999
20:33:15 in news:comp.lang.pascal.delphi.misc, David C. Ullrich
<ullrich@math.okstate.edu> wrote:
>In article <3zADx9AXVWd3EwJU@merlyn.demon.co.uk>,
>  Dr John Stockton <jrs@merlyn.demon.co.uk> wrote:
>> JRS:  In article <7l357k$4m6$1@nnrp1.deja.com> of Sat, 26 Jun 1999
>> 18:13:14 in news:comp.lang.pascal.delphi.misc, David C. Ullrich
>> <ullrich@math.okstate.edu> wrote:
>> >       I have no idea what a "subset-capability" is, but modulo
>> >that of course there is. Set one endpoint P1 of the needle to a
>> >random point in a large square. Then set the other endpoint
>> >to another random point. Reject the second endpoint until you
>> >get one with say 0.5 < |P1 - P2| < 2. Then rescale it so
>> >|P1 - P2| = 1. There's your random needle, no trig and hence
>> >no Pi required.
>> >
>> >   ("rescale": say P2 := P1 + (P2 - P1)/|P2 - P1| . No
>> >angles, just a square root.)
>>
>> ISTM, seemingly confirmed by test, that your method does not give a
>> uniform distribution of angles.
>
>    If so then you're trying something other than what I suggested.
>Did you read all of it or just a few sentences?

Yes; but I took |P1 - P2| as the absolute value of the difference in
each (X, Y) direction.

>    Psuedocode (note these are all real variables, converting to
>integers too soon would be bad):
>
>//"Set [...] P1 [...] to a random
>//point in a large square":
>
>    N:= LargeNumber;
>    P1.X:= N*random;
>    P1.Y:= N*random;

This chooses a point at random within a large square - then another.

>//"Then set the other endpoint
>//to another random point. Reject the second endpoint until you
>//get one with say 0.5 < |P1 - P2| < 2":
>
>    repeat
>       X:= 1 - 2*random;
>       Y:= 1 - 2*random;
>    until 0.25 < X*X + Y*Y < 4;
>//the actual numbers 0.25 and 4 don't matter

and select those within a circular relative annulus, so to speak.

>//"rescale" as suggested:
>
>    r:= sqrt(X*X + Y*Y);
>    P2.X:= P1.X + X/r;
>    P2.Y:= P1.Y + Y/r;

No need to rescale just to get angles, of course; that was for getting
needles.

>     If you don't get a uniform distribution of angles from
>lemme know and I'll make an actual compilable version (if the
>RNG is worse than I thought it won't work, of course. But I
>didn't think the RNG was _that_ bad.)


Yes, *that* should work - actually, ISTM that one could make P1 = (0,0),
randomly generate P2 = (X,Y) within a square around that, accept those
P2 within the inscribed circle and not too near the centre, and use
ATAN2(Y, X).

BUT one is then selecting just a fraction Pi/4 of the points as within
the circle, and comment matching my original comment on Method 2 applies
(typo in that : for Pi/2 read Pi/4) to both of our versions -- as a part
of the whole Buffon, one is doing work substantially equivalent to an
evaluation of Pi in relation to needle angle, before adding scatter of
needle centre position.


It's still a good Web page - but one difference between real Buffonian /
Euclidean life and a computer is that real life has a precision-grade
intrinsic absolute standard of angle, the Turn of 2 Pi radians, whereas
the computer must either have a number or an algorithm supplied.
 
-- 
 � John Stockton, Surrey, UK. jrs@merlyn.demon.co.uk / JR.Stockton@physics.org �
  Web <URL: http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.

Hi Guys,


Heeelllooooo

You  crospost all the time!

When do you realize this!

In a german language group the interst of english conversation
is little.

F'up2
comp.lang.pascal.delphi.misc

In article <j+NWi+AgBrd3EwbC@merlyn.demon.co.uk>,
  Dr John Stockton <jrs@merlyn.demon.co.uk> wrote:
> JRS:  In article <7l61qb$u9u$1@nnrp1.deja.com> of Sun, 27 Jun 1999
> 20:33:15 in news:comp.lang.pascal.delphi.misc, David C. Ullrich
> <ullrich@math.okstate.edu> wrote:
> >In article <3zADx9AXVWd3EwJU@merlyn.demon.co.uk>,
> >  Dr John Stockton <jrs@merlyn.demon.co.uk> wrote:
> >> JRS:  In article <7l357k$4m6$1@nnrp1.deja.com> of Sat, 26 Jun 1999
> >> 18:13:14 in news:comp.lang.pascal.delphi.misc, David C. Ullrich
> >> <ullrich@math.okstate.edu> wrote:
> >> >       I have no idea what a "subset-capability" is, but modulo
> >> >that of course there is. Set one endpoint P1 of the needle to a
> >> >random point in a large square. Then set the other endpoint
> >> >to another random point. Reject the second endpoint until you
> >> >get one with say 0.5 < |P1 - P2| < 2. Then rescale it so
> >> >|P1 - P2| = 1. There's your random needle, no trig and hence
> >> >no Pi required.
> >> >
> >> >   ("rescale": say P2 := P1 + (P2 - P1)/|P2 - P1| . No
> >> >angles, just a square root.)
> >>
> >> ISTM, seemingly confirmed by test, that your method does not give a
> >> uniform distribution of angles.
> >
> >    If so then you're trying something other than what I suggested.
> >Did you read all of it or just a few sentences?
>
> Yes; but I took |P1 - P2| as the absolute value of the difference in
> each (X, Y) direction.

   Um, right. I won't ask what you thought the square root I mentioned
was...

    There _was_ an error in what I wrote yesterday, btw. Doesn't
look like you noticed.

> >    Psuedocode (note these are all real variables, converting to
> >integers too soon would be bad):
> >
> >//"Set [...] P1 [...] to a random
> >//point in a large square":
> >
> >    N:= LargeNumber;
> >    P1.X:= N*random;
> >    P1.Y:= N*random;
>
> This chooses a point at random within a large square - then another.

      Huh?

> >//"Then set the other endpoint
> >//to another random point. Reject the second endpoint until you
> >//get one with say 0.5 < |P1 - P2| < 2":
> >
> >    repeat
> >       X:= 1 - 2*random;
> >       Y:= 1 - 2*random;
> >    until 0.25 < X*X + Y*Y < 4;
> >//the actual numbers 0.25 and 4 don't matter

     This is where the typo was. Replace the last two lines with

    until 0.25 < X*X + Y*Y < 1;
//the actual numbers 0.25 and 1 don't matter,
//except that of course the target annulus has to be
//a subset of the square we selected (X,Y) from.

> and select those within a circular relative annulus, so to speak.

    Right.

> >//"rescale" as suggested:
> >
> >    r:= sqrt(X*X + Y*Y);
> >    P2.X:= P1.X + X/r;
> >    P2.Y:= P1.Y + Y/r;
>
> No need to rescale just to get angles, of course; that was for getting
> needles.

     Right, I thought needles was what we wanted.

> >     If you don't get a uniform distribution of angles from
> >lemme know and I'll make an actual compilable version (if the
> >RNG is worse than I thought it won't work, of course. But I
> >didn't think the RNG was _that_ bad.)
>
> Yes, *that* should work - actually, ISTM that one could make P1 =
(0,0),
> randomly generate P2 = (X,Y) within a square around that, accept those
> P2 within the inscribed circle and not too near the centre, and use
> ATAN2(Y, X).
>
> BUT one is then selecting just a fraction Pi/4 of the points as within
> the circle, and comment matching my original comment on Method 2
applies
> (typo in that : for Pi/2 read Pi/4) to both of our versions -- as a
part
> of the whole Buffon, one is doing work substantially equivalent to an
> evaluation of Pi in relation to needle angle, before adding scatter of
> needle centre position.

     What is this obsession with _angles_??? You don't need to
calculate an _angle_ explicitly. You calculate the position of
the needle as above - no angles come into it. (Not explicitly.)

     If you _prefer_ to convert the position of the needle's
emndpoints to an angle, _then_ convert the angle back to needle
endpoints, and then complain about how there was a Pi implicit
in the conversion then that's up to you. But there's no need to
know the value of Pi in the version above - you're just going in
circles. As it were.

> It's still a good Web page - but one difference between real Buffonian
/
> Euclidean life and a computer is that real life has a precision-grade
> intrinsic absolute standard of angle, the Turn of 2 Pi radians,
whereas
> the computer must either have a number or an algorithm supplied.

      Simply not so. (Um, a machine needs to have an algorithm
supplied to do anything. But if you mean that the machine needs
an independent algorithm for the value of Pi, it's simply not so.)

> --
>  � John Stockton, Surrey, UK. jrs@merlyn.demon.co.uk /
JR.Stockton@physics.org �
>   Web <URL: http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms,
& links.
>


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

JRS:  In article <j+NWi+AgBrd3EwbC@merlyn.demon.co.uk> of Mon, 28 Jun
1999 00:14:40 in news:comp.lang.pascal.delphi.misc, Dr John Stockton
<jrs@merlyn.demon.co.uk> wrote:
> ...
>Yes, *that* should work - actually, ISTM that one could make P1 = (0,0),
>randomly generate P2 = (X,Y) within a square around that, accept those
>P2 within the inscribed circle and not too near the centre, and use
>ATAN2(Y, X).
> ...



If one randomly generates TWO points within a square, repeating until
they are neither too near or too distant, then (except in the limit as
"too far" tends to zero, or the square tends to infinite) the slope of
the line joining the first to the second IS NOT as if drawn randomly
from a uniform distribution covering all directions.  In those limits,
the proportion of points accepted tends to zero, which is inefficient.

If one randomly generates ONE point within a square, repeating until the
centre is neither too near or too distant, then the slope of the line
joining the centre to the point IS as if drawn randomly from a uniform
distribution covering all directions - too distant is greater than half
the side of the square.

Test program for square Abs(X)<1, Abs(Y)<1; BP7, ATAN2 from Terje
Mathisen, note "(*..*)" comment :


function atan2(y : extended; x : extended): Extended ; Assembler;
asm  fld [y] ; fld [x] ; fpatan  end ;

var R2, X1, X2, Y1, Y2 : extended ;
A : array [-24..24] of longint ;
J, K, L : longint ;
const JM = 30000000 ;

begin Writeln('---') ; FillChar(A, SizeOf(A), 0) ; J := 0 ;
repeat
  X1 := 2*random-1 ; Y1 := 2*random-1 ;    (* use this line *)
  X1 := 0 ; Y1 := 0 ;                      (* or this one *)
  X2 := 2*random-1 ; Y2 := 2*random-1 ;
  R2 := Sqr(X1-X2) + Sqr(Y1-Y2) ;
  if (R2<1.0) and (R2>0.0001) then begin
    K := Round(7.321 * Atan2(Y1-Y2, X1-X2)) ;
    Inc(A[K]) ; Inc(J) end ;
  until J=JM ;
K := 0 ;
for J := Low(A) to High(A) do if A[J]>K then K := A[J] ;
for J := Low(A) to High(A) do Writeln(J*180/23:0:3,
  '*':Round(A[J]*(60/K))) ;
Write(^G) ; Readln end.


As it also works compiled with D3 "DCC32 -cc", that ATAN2 must do in D3.


Do let us know if an error can be seen in the above program, or if with
two random points it does not test what you intended, on varying the
constant sides of the R2 comparisons.  7.231 and 60 merely scale for
display.
 
-- 
 � John Stockton, Surrey, UK. jrs@merlyn.demon.co.uk / JR.Stockton@physics.org �
  Web <URL: http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.

In article <7+KQSfA9R7d3EwYX@merlyn.demon.co.uk>,
causing a bit of confusion by replying to himself,
  Dr John Stockton <jrs@merlyn.demon.co.uk> wrote:
> JRS:  In article <j+NWi+AgBrd3EwbC@merlyn.demon.co.uk> of Mon, 28 Jun
> 1999 00:14:40 in news:comp.lang.pascal.delphi.misc, Dr John Stockton
> <jrs@merlyn.demon.co.uk> wrote:
> > ...
> >Yes, *that* should work - actually, ISTM that one could make P1 =
(0,0),
> >randomly generate P2 = (X,Y) within a square around that, accept
those
> >P2 within the inscribed circle and not too near the centre, and use
> >ATAN2(Y, X).
> > ...
>
> If one randomly generates TWO points within a square, repeating until
> they are neither too near or too distant, then (except in the limit as
> "too far" tends to zero, or the square tends to infinite) the slope of
> the line joining the first to the second IS NOT as if drawn randomly
> from a uniform distribution covering all directions.  In those limits,
> the proportion of points accepted tends to zero, which is inefficient.

     Of course you don't mean that the _slope_ of the line should
have a uniform distribution (no, that's not quite what you said).
No, this IS NOT as if that - did anyone say it was?

> If one randomly generates ONE point within a square, repeating until
the
> centre is neither too near or too distant, then the slope of the line
> joining the centre to the point IS as if drawn randomly from a uniform
> distribution covering all directions - too distant is greater than
half
> the side of the square.

     That's exactly right - the "too distant is greater than
half the side of the square" is the content of the correction
I posted this morning to yesterday's post.

> Test program for square Abs(X)<1, Abs(Y)<1; BP7, ATAN2 from Terje
> Mathisen, note "(*..*)" comment :
>
> function atan2(y : extended; x : extended): Extended ; Assembler;
> asm  fld [y] ; fld [x] ; fpatan  end ;
>
> var R2, X1, X2, Y1, Y2 : extended ;
> A : array [-24..24] of longint ;
> J, K, L : longint ;
> const JM = 30000000 ;
>
> begin Writeln('---') ; FillChar(A, SizeOf(A), 0) ; J := 0 ;
> repeat
>   X1 := 2*random-1 ; Y1 := 2*random-1 ;    (* use this line *)
>   X1 := 0 ; Y1 := 0 ;                      (* or this one *)
>   X2 := 2*random-1 ; Y2 := 2*random-1 ;
>   R2 := Sqr(X1-X2) + Sqr(Y1-Y2) ;
>   if (R2<1.0) and (R2>0.0001) then begin
>     K := Round(7.321 * Atan2(Y1-Y2, X1-X2)) ;
>     Inc(A[K]) ; Inc(J) end ;
>   until J=JM ;
> K := 0 ;
> for J := Low(A) to High(A) do if A[J]>K then K := A[J] ;
> for J := Low(A) to High(A) do Writeln(J*180/23:0:3,
>   '*':Round(A[J]*(60/K))) ;
> Write(^G) ; Readln end.
>
> As it also works compiled with D3 "DCC32 -cc", that ATAN2 must do in
D3.
>
> Do let us know if an error can be seen in the above program, or if
with
> two random points it does not test what you intended,

    Who _is_ this addressed to? (And whoever it is what _did_
he intend to test? I have a hard time seeing what the "Write(^G)"
does. Also I seem to be missing your point. Unless your point is
that you don't get a uniform distribution of angles with the
line "X1 := 2*random-1 ; Y1 := 2*random-1 ;". In which case I'm
missing your point - nobody said you would.)

    My impression is that through all of this you've been
insisting that a machine needs to already know the value of
Pi, either explicitly or implicitly, to be able to perform
the Buffon thing, making it circular. It's not at all clear
to me whether you're still insisting on this or not.

> on varying the
> constant sides of the R2 comparisons.  7.231 and 60 merely scale for
> display.
>
> --
>  � John Stockton, Surrey, UK. jrs@merlyn.demon.co.uk /
JR.Stockton@physics.org �
>   Web <URL: http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms,
& links.
>


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

David C. Ullrich <ullrich@math.okstate.edu> schrieb in im Newsbeitrag:
7l8lv1$rn9$1@nnrp1.deja.com...

Is it so difficult to understand???

F'up2: comp.lang.pascal.delphi.misc


--
****************************************************
* E-mail:    marco.lange@gmx.de                    *
* Homepage:  http://www.marcolange.de              *
* ICQ:       35807782                              *
****************************************************