Re: Pi day
- To: mathgroup at smc.vnet.net
- Subject: [mg108450] Re: Pi day
- From: dh <dh at metrohm.com>
- Date: Thu, 18 Mar 2010 04:32:44 -0500 (EST)
- References: <hnqa11$s88$1@smc.vnet.net>
Hi,
I did not take the trouble to go through all proposed solutions, so it
could be that somebody else already got the same idea.
a) Consider a sorted list of all permutations of 0..9, call it: per.
b )consider a function quot[x1_,x2_]:=per[[x1]]/per[[x2]]
c) consider a 2 dim grid of indices (1..Length[per]) X (1..Length[per])
d) consider the surface defined by f evaluated on this grid. Note that
this surface is monotonically ascending from the upper right to the
lower left (low raw-high column to high row-low column index)We are
looking for the contour line f==Pi. As this line may lay between grid
points, we are looking for a line on the grid with maximal f and the
condition f<=Pi. Note that along this line the column indeces are
increasing (not necessarily strict) with row indeces. This makes it
simple to calculate.
e) Next we check which grid point on this "contour line" is closest to
Pi from below.
On my machine the code to create and sort the possible numbers takes:
13 sec.
The code for the search takes 67 sec. If Pi is not rationalized the time
is: 77 sec
The result is: {9735046128 / 3098761425} what is 2.4 10^-12 below Pi.
The approximation from above should be obvious.
Here is the code:
===========================
per = Sort[FromDigits /@ Permutations[{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}]];
p = Rationalize[Pi, 10^-20];
len = Length[per]; Print["len=", len];
ind[x_] := Module[{i1 = 1, i2 = Length[per], i},
While[i2 - i1 > 1,
i = Floor[(i1 + i2)/2];
If[x < per[[i]], i2 = i, i1 = i]; Print[{i1, i2, x < per[[i]]}];
];
i1
];
quot[i1_, i2_] := per[[i1]]/per[[i2]];
col = row = 1;
max = 0; row0 = 1; col0 = 1;
While [quot[row + 1, col] < p, ++row]; Print["row0=", row];
While[row < len && col < len,
If[quot[row + 1, col] < p, ++row, ++col];
If[(t = quot[row, col]) > max, max = t; row0 = row; col0 = col;];
];
Print["Error,num,denum=", {max - Pi // N, per[[row0]], per[[col0]]}]
================================================
Daniel
On 17.03.2010 11:13, Daniel Lichtblau wrote:
> Ray Koopman wrote:
>> The code I gave can certainly be speeded up, but right now I'm more
>> concerned about the algorithm. 'hi' is meant to be the smallest value
>> of the form s[[i]]/s[[j]] that is greater than Pi, and 'lo' is meant
>> to be the largest value of the form s[[i]]/s[[j]] that is less than
>> Pi. 'hi' is OK, but I wonder about 'lo'.
>
> I have not looked carefully at the code. The basic idea is smarter than
> I thought (more correctly, my understanding was stupider than necessary).
>
> A variant would do an iteration over valid denominators. For each, find
> the integer numerator that gives the closest approximation to pi. Then
> walk in both directions (that is, increment and decrement) until you
> find a valid numerator, and see if either gives a result better than teh
> best found thus far.
>
> Or only look at valid numerators (that is, those formed by permutations
> of the available digits), and do a binary search to get to the one
> giving a value closest to pi. For this one would need to sort the
> available values. not to onerous when there are only 9! or so.
>
> Daniel
>
--
Daniel Huber
Metrohm Ltd.
Oberdorfstr. 68
CH-9100 Herisau
Tel. +41 71 353 8585, Fax +41 71 353 8907
E-Mail:<mailto:dh at metrohm.com>
Internet:<http://www.metrohm.com>