Velocity Reviews > what this program do

# what this program do

Morris Dovey
Guest
Posts: n/a

 03-27-2008
Richard Tobin wrote:

> See http://www.mathpropress.com/stan/bib...phy/spigot.pdf

I got to thinking about how one might go about using the pi and e
digit strings to build a random number generator. Seemed like a
good idea at the time.

Then I wrote a tiny program to give me the digit frequencies and
decided that the idea might not be as good as I'd thought it
might be. With a initialized to 10000 and the printf() format
changed to "%.3ld" to produce the digits, I ran my little counter
program to get:

0 56
1 92
2 83
3 80
4 80
5 73
6 77
7 75
8 76
9 90

Which surprised me because I'd expected a much more even
distribution.

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto/

Dik T. Winter
Guest
Posts: n/a

 03-27-2008
In article <fsg4bp\$24pj\$(E-Mail Removed)> http://www.velocityreviews.com/forums/(E-Mail Removed) (Richard Tobin) writes:
> In article <(E-Mail Removed)>,
> CBFalconer <(E-Mail Removed)> wrote:
> >I haven't the vaguest idea of the algorithm.

>
> See http://www.mathpropress.com/stan/bib...phy/spigot.pdf

....
> A similar algorithm for calculating the digits of e - also given in
> the same paper - is much easier to understand.

Right. When I wrote the program originally with a cow-orker the idea
was to see how the algorithm we knew for a long time for 'e' work out
for 'pi'. However, the algorithm for 'pi' is much shakier than that
for 'e'. In order to let it work correctly you should ensure that the
"digits" are always within certain bounds. For 'e' that is simple, it
is assured by the series development for 'e'. For 'pi' that is not the
case. And indeed, if you increase the arrays and the loop length etc.
you will find that at a certain point the program will start to give
wrong results. Once we had the program working I thought to decrease
its size and obfuscate the program as much as possible (although the
decrease in size was the most important for me). It had gone to a point
where even the C-beautifier of that time did not know what to do with it.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

Dik T. Winter
Guest
Posts: n/a

 03-27-2008
In article <(E-Mail Removed)> Morris Dovey <(E-Mail Removed)> writes:
....
> I got to thinking about how one might go about using the pi and e
> digit strings to build a random number generator. Seemed like a
> good idea at the time.
>
> Then I wrote a tiny program to give me the digit frequencies and
> decided that the idea might not be as good as I'd thought it
> might be. With a initialized to 10000 and the printf() format
> changed to "%.3ld" to produce the digits, I ran my little counter
> program to get:

....
> Which surprised me because I'd expected a much more even
> distribution.

You would have gotten that with the format string "%.4d". On the other
hand, using pi and e for random digits only works when they are normal
to base 10 (and there must be some additional randomness in the digits).
It is unknown whether they are.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

Morris Dovey
Guest
Posts: n/a

 03-27-2008
"Dik T. Winter" wrote:
>
> In article <(E-Mail Removed)> Morris Dovey <(E-Mail Removed)> writes:

> > Which surprised me because I'd expected a much more even
> > distribution.

>
> You would have gotten that with the format string "%.4d". On the other
> hand, using pi and e for random digits only works when they are normal
> to base 10 (and there must be some additional randomness in the digits).
> It is unknown whether they are.

I tried that, with this result:

0 74
1 92
2 83
3 80
4 80
5 73
6 77
7 75
8 76
9 90

which is more uniform, but less so than I'd expected.

The "digit spigot" is very interesting!

Thanks

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto/

Richard Tobin
Guest
Posts: n/a

 03-27-2008
In article <(E-Mail Removed)>,
Morris Dovey <(E-Mail Removed)> wrote:
>which is more uniform, but less so than I'd expected.

See http://mathworld.wolfram.com/PiDigits.html, which includes a table
of the distribution of digits in the first 10^n places for n up to 12,
and says it "shows no statistically significant departure from a
uniform distribution".

-- Richard
--
:wq

Richard Bos
Guest
Posts: n/a

 03-27-2008
(E-Mail Removed) (Richard Tobin) wrote:

> In article <(E-Mail Removed)>,
> CBFalconer <(E-Mail Removed)> wrote:
> >I haven't the vaguest idea of the algorithm.

>
> See http://www.mathpropress.com/stan/bib...phy/spigot.pdf
>
> In short: if you represent pi in the "mixed-radix" base where the
> values for each digit overflow at
>
> . 1/3 2/5 3/7 4/9 ...
>
> (that is, the first digit after the point represents thirds, the
> second multiples of 1/3 * 2/5, and so on),
>
> then the representation of pi is
>
> 2 . 2 2 2 2 ...
>
> and the program works by converting that to base 10 (actually, 10000).

Very clever.

Richard

Richard
Guest
Posts: n/a

 03-27-2008
Morris Dovey <(E-Mail Removed)> writes:

> Richard Tobin wrote:
>
>> See http://www.mathpropress.com/stan/bib...phy/spigot.pdf

>
>
> I got to thinking about how one might go about using the pi and e
> digit strings to build a random number generator. Seemed like a
> good idea at the time.
>
> Then I wrote a tiny program to give me the digit frequencies and
> decided that the idea might not be as good as I'd thought it
> might be. With a initialized to 10000 and the printf() format
> changed to "%.3ld" to produce the digits, I ran my little counter
> program to get:
>
> 0 56
> 1 92
> 2 83
> 3 80
> 4 80
> 5 73
> 6 77
> 7 75
> 8 76
> 9 90
>
> Which surprised me because I'd expected a much more even
> distribution.

Looks even enough to me considering the numbers involved.