MATLAB Central Newsreader - Pi approximation function optimization

Pi approximation function optimization

Jared F — Sat, 13 Mar 2010 01:54:06 +0000

I came across the "brain teaser" of finding the best approximation of pi by dividing one 9-digit number by another 9-digit number. Both numbers contain 1 through 9 once.

I found a very close approximation by hand (728691345 / 231948765 = 3.141604763) but I want to know if there are any better ones.

I've tried a couple different methods of writing a program to find a better approximation, but all I can come up with is a massive number of loops that would take way too long for my computer to process.

I'll paste my current program below. If you can think of a better way to write this, let me know. I don't have an extensive background in matlab, so I'm at a loss for how to optimize this. Thanks!

Program Below
____________________________________

for a = 3:9;
for b = 1:9;
for c = 1:9;
for d = 1:9;
for e = 1:9;
for f = 1:9;
for g = 1:9;
for h = 1:9;
for i = 1:9;
for j = 1:9;
for k = 1:9;
for l = 1:9;
for m = 1:9;
for n = 1:9;
for o = 1:9;
for p = 1:9;
for q = 1:9;
for r = 1:9;

x = 100000000.*a+10000000.*b+1000000.*c+100000.*d+10000.*e+1000.*f+100.*g+10.*h+i;
y = 100000000.*j+10000000.*k+1000000.*l+100000.*m+10000.*n+1000.*o+100.*p+10.*q+r;

z = x/y;

if (z - pi < .001)

format short;

printf('x = %i\n', x);
printf('y = %i\n', y);
format long;
printf('z = %i\n', z);
disp('----------');

endif

endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor

Re: Pi approximation function optimization

Sadik — Sat, 13 Mar 2010 13:18:02 +0000

Hi Jared,

Here is my version of it. The operation is limited by the available memory, as well as the maximum number of elements allowed by matlab. Therefore, the following may not be the best solution, but it could hopefully show you another direction of doing it. [It seems that the search for the optimal combination is going to take about 10 hours!]

Best.

% brainTeaser.m

allCombinations = perms(1:9);

allNumbers = zeros(size(allCombinations,1),1);

for k = 1:length(allNumbers)

    for digit = 1:9

        allNumbers(k) = allNumbers(k) + allCombinations(k,digit)*power(10,9-digit);

    end

end

numberOfPartitions = 560; % Form blocks of numbers, each of length 9!/560
partitionLength = length(allNumbers)/numberOfPartitions;

globalMin = 1e6;

for m = 1:numberOfPartitions
    firstPartition = allNumbers((m-1)*numberOfPartitions+(1:partitionLength));
    disp(['Beginning partition ' num2str(m) ' of ' num2str(numberOfPartitions) '...'])
    for n = 1:numberOfPartitions
        secondPartition = allNumbers((n-1)*numberOfPartitions+(1:partitionLength));
        matrixOfDivisions = firstPartition*(1./secondPartition');
        [minValue,minLocation] = min(abs(matrixOfDivisions(:)-pi));
        if minValue < globalMin
            [row,col] = ind2sub(size(matrixOfDivisions),minLocation);
            numerator = firstPartition(row);
            denominator = secondPartition(col);
            globalMin = minValue;
        end

    end

end


disp(['The best approximation is given by ' num2str(numerator) '/' num2str(denominator)])
disp(['The result is equal to ' num2str(numerator/denominator) ', and pi = ' num2str(pi)])

"Jared F" <jfritz408@yahoo.com> wrote in message <hner7u$r8m$1@fred.mathworks.com>...
> I came across the "brain teaser" of finding the best approximation of pi by dividing one 9-digit number by another 9-digit number. Both numbers contain 1 through 9 once.
>
> I found a very close approximation by hand (728691345 / 231948765 = 3.141604763) but I want to know if there are any better ones.
>
> I've tried a couple different methods of writing a program to find a better approximation, but all I can come up with is a massive number of loops that would take way too long for my computer to process.
>
> I'll paste my current program below. If you can think of a better way to write this, let me know. I don't have an extensive background in matlab, so I'm at a loss for how to optimize this. Thanks!
>
> Program Below
> ____________________________________
>
> for a = 3:9;
> for b = 1:9;
> for c = 1:9;
> for d = 1:9;
> for e = 1:9;
> for f = 1:9;
> for g = 1:9;
> for h = 1:9;
> for i = 1:9;
> for j = 1:9;
> for k = 1:9;
> for l = 1:9;
> for m = 1:9;
> for n = 1:9;
> for o = 1:9;
> for p = 1:9;
> for q = 1:9;
> for r = 1:9;
>
> x = 100000000.*a+10000000.*b+1000000.*c+100000.*d+10000.*e+1000.*f+100.*g+10.*h+i;
> y = 100000000.*j+10000000.*k+1000000.*l+100000.*m+10000.*n+1000.*o+100.*p+10.*q+r;
>
> z = x/y;
>
>
> if (z - pi < .001)
>
> format short;
>
> printf('x = %i\n', x);
> printf('y = %i\n', y);
> format long;
> printf('z = %i\n', z);
> disp('----------');
>
> endif
>
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor

Re: Pi approximation function optimization

John D'Errico — Sat, 13 Mar 2010 13:54:02 +0000

"Sadik " <sadik.hava@gmail.com> wrote in message <hng3aa$fr9$1@fred.mathworks.com>...
> Hi Jared,
>
> Here is my version of it. The operation is limited by the available memory, as well as the maximum number of elements allowed by matlab. Therefore, the following may not be the best solution, but it could hopefully show you another direction of doing it. [It seems that the search for the optimal combination is going to take about 10 hours!]
>

But then your solution will take a half day to solve.
Since I don't believe that giving a solution to someone
who is trying to learn actually helps them at all, all I
will do is to suggest that there are far better ways to
approach it.

Be creative. There is at least one solution with error
as low as:

error =
-8.49968984084626e-11

This took 11 lines of code to generate, and 0.23
seconds of cpu time.

John

Re: Pi approximation function optimization

Mark Shore — Sat, 13 Mar 2010 21:40:26 +0000

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <hng5dq$h4b$1@fred.mathworks.com>...
> "Sadik " <sadik.hava@gmail.com> wrote in message <hng3aa$fr9$1@fred.mathworks.com>...
> > Hi Jared,
> >
> > Here is my version of it. The operation is limited by the available memory, as well as the maximum number of elements allowed by matlab. Therefore, the following may not be the best solution, but it could hopefully show you another direction of doing it. [It seems that the search for the optimal combination is going to take about 10 hours!]
> >
>
> But then your solution will take a half day to solve.
> Since I don't believe that giving a solution to someone
> who is trying to learn actually helps them at all, all I
> will do is to suggest that there are far better ways to
> approach it.
>
> Be creative. There is at least one solution with error
> as low as:
>
> error =
> -8.49968984084626e-11
>
> This took 11 lines of code to generate, and 0.23
> seconds of cpu time.
>
> John

Hi John. I managed to do it in 4 lines, also 0.23 seconds on a dual core CPU. Hope the OP puts a working solution up, so we can compare.