Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Pi approximation function optimization

Subject: Pi approximation function optimization

From: Jared F

Date: 13 Mar, 2010 01:54:06

Message: 1 of 4

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

Subject: Pi approximation function optimization

From: Sadik

Date: 13 Mar, 2010 13:18:02

Message: 2 of 4

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

Subject: Pi approximation function optimization

From: John D'Errico

Date: 13 Mar, 2010 13:54:02

Message: 3 of 4

"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

Subject: Pi approximation function optimization

From: Mark Shore

Date: 13 Mar, 2010 21:40:26

Message: 4 of 4

"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.

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us