Intriguing...
searches seem to refer to this as a Spigot algorithm, but I find no
references to droplet.
---david
On Monday, March 9, 2015 at 11:46:52 AM UTC+1, Hans W Borchers wrote:
>
> The following function is an implementation of the famous "droplet"
> algorithm of Rabinowitz and Wagon for calculating \pi to n (internal)
> decimal places (no analytic functions, no arbitrary precision, some digits
> could even be calculated by hand):
>
> function droplet_pi(n)
> Pi = p = ""
> no_nines = 0
> d = n + 2
> N = ifloor(10*d/3.0 + 1)
> a = fill(2, N+1)
> for l in 1:d
> a = 10 * a
> for i in (N+1):-1:2
> j = 2*i - 1
> q, r = divrem(a[i], j)
> a[i] = r
> a[i-1] += q * (i-1)
> end
> q, r = divrem(a[1], 10)
> a[1] = r
> if q < 9
> Pi *= string(p) * ("9"^no_nines)
> p = q
> no_nines = 0
> elseif q == 9
> no_nines += 1
> elseif q == 10
> p += 1
> Pi *= string(p) * ("0"^no_nines)
> p = 0
> no_nines = 0
> else
> error("droplet_pi: algorithm error!")
> end
> end
> Pi[1:1] * "." * Pi[2:end]
> end
>
>
> julia> @time droplet_pi(1000)
> elapsed time: 0.166306075 seconds (27629136 bytes allocated)
>
> "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348
>
> 2534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555
>
> 9644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610
>
> 4543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600
>
> 1133053054882046652138414695194151160943305727036575959195309218611738193261179310511854807
>
> 4462379962749567351885752724891227938183011949129833673362440656643086021394946395224737190
>
> 7021798609437027705392171762931767523846748184676694051320005681271452635608277857713427577
>
> 8960917363717872146844090122495343014654958537105079227968925892354201995611212902196086403
>
> 4418159813629774771309960518707211349999998372978049951059731732816096318595024459455346908
>
> 3026425223082533446850352619311881710100031378387528865875332083814206171776691473035982534
>
> 9042875546873115956286388235378759375195778185778053217122680661300192787661119590921642019
> 89"
>
> This implementation continuously appends digits to a string. It will
> probably be faster to preallocate a vector of (integer) digits and to
> combine these into a string in one step at the end of the procedure. Maybe
> I didn't know how to do this when I wrote this code.
>
>
