http://www.mathworks.com/matlabcentral/newsreader/view_thread/276324
MATLAB Central Newsreader  Pi approximation function optimization
Feed for thread: Pi approximation function optimization
enus
©19942015 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://www.mathworks.com/images/membrane_icon.gif

Sat, 13 Mar 2010 01:54:06 +0000
Pi approximation function optimization
http://www.mathworks.com/matlabcentral/newsreader/view_thread/276324#725980
Jared F
I came across the "brain teaser" of finding the best approximation of pi by dividing one 9digit number by another 9digit number. Both numbers contain 1 through 9 once.<br>
<br>
I found a very close approximation by hand (728691345 / 231948765 = 3.141604763) but I want to know if there are any better ones.<br>
<br>
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.<br>
<br>
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!<br>
<br>
Program Below<br>
____________________________________<br>
<br>
for a = 3:9;<br>
for b = 1:9;<br>
for c = 1:9;<br>
for d = 1:9;<br>
for e = 1:9;<br>
for f = 1:9;<br>
for g = 1:9;<br>
for h = 1:9;<br>
for i = 1:9;<br>
for j = 1:9;<br>
for k = 1:9;<br>
for l = 1:9;<br>
for m = 1:9;<br>
for n = 1:9;<br>
for o = 1:9;<br>
for p = 1:9;<br>
for q = 1:9;<br>
for r = 1:9;<br>
<br>
x = 100000000.*a+10000000.*b+1000000.*c+100000.*d+10000.*e+1000.*f+100.*g+10.*h+i;<br>
y = 100000000.*j+10000000.*k+1000000.*l+100000.*m+10000.*n+1000.*o+100.*p+10.*q+r;<br>
<br>
z = x/y;<br>
<br>
<br>
if (z  pi < .001)<br>
<br>
format short;<br>
<br>
printf('x = %i\n', x);<br>
printf('y = %i\n', y);<br>
format long;<br>
printf('z = %i\n', z);<br>
disp('');<br>
<br>
endif<br>
<br>
endfor<br>
endfor<br>
endfor<br>
endfor<br>
endfor<br>
endfor<br>
endfor<br>
endfor<br>
endfor<br>
endfor<br>
endfor<br>
endfor<br>
endfor<br>
endfor<br>
endfor<br>
endfor<br>
endfor<br>
endfor

Sat, 13 Mar 2010 13:18:02 +0000
Re: Pi approximation function optimization
http://www.mathworks.com/matlabcentral/newsreader/view_thread/276324#726062
Sadik
Hi Jared,<br>
<br>
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!]<br>
<br>
Best.<br>
<br>
% brainTeaser.m<br>
<br>
allCombinations = perms(1:9);<br>
<br>
allNumbers = zeros(size(allCombinations,1),1);<br>
<br>
for k = 1:length(allNumbers)<br>
<br>
for digit = 1:9<br>
<br>
allNumbers(k) = allNumbers(k) + allCombinations(k,digit)*power(10,9digit);<br>
<br>
end<br>
<br>
end<br>
<br>
numberOfPartitions = 560; % Form blocks of numbers, each of length 9!/560<br>
partitionLength = length(allNumbers)/numberOfPartitions;<br>
<br>
globalMin = 1e6;<br>
<br>
for m = 1:numberOfPartitions<br>
firstPartition = allNumbers((m1)*numberOfPartitions+(1:partitionLength)); <br>
disp(['Beginning partition ' num2str(m) ' of ' num2str(numberOfPartitions) '...'])<br>
for n = 1:numberOfPartitions<br>
secondPartition = allNumbers((n1)*numberOfPartitions+(1:partitionLength));<br>
matrixOfDivisions = firstPartition*(1./secondPartition');<br>
[minValue,minLocation] = min(abs(matrixOfDivisions(:)pi));<br>
if minValue < globalMin<br>
[row,col] = ind2sub(size(matrixOfDivisions),minLocation);<br>
numerator = firstPartition(row);<br>
denominator = secondPartition(col);<br>
globalMin = minValue;<br>
end<br>
<br>
end<br>
<br>
end<br>
<br>
<br>
disp(['The best approximation is given by ' num2str(numerator) '/' num2str(denominator)])<br>
disp(['The result is equal to ' num2str(numerator/denominator) ', and pi = ' num2str(pi)])<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
"Jared F" <jfritz408@yahoo.com> wrote in message <hner7u$r8m$1@fred.mathworks.com>...<br>
> I came across the "brain teaser" of finding the best approximation of pi by dividing one 9digit number by another 9digit number. Both numbers contain 1 through 9 once.<br>
> <br>
> I found a very close approximation by hand (728691345 / 231948765 = 3.141604763) but I want to know if there are any better ones.<br>
> <br>
> 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.<br>
> <br>
> 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!<br>
> <br>
> Program Below<br>
> ____________________________________<br>
> <br>
> for a = 3:9;<br>
> for b = 1:9;<br>
> for c = 1:9;<br>
> for d = 1:9;<br>
> for e = 1:9;<br>
> for f = 1:9;<br>
> for g = 1:9;<br>
> for h = 1:9;<br>
> for i = 1:9;<br>
> for j = 1:9;<br>
> for k = 1:9;<br>
> for l = 1:9;<br>
> for m = 1:9;<br>
> for n = 1:9;<br>
> for o = 1:9;<br>
> for p = 1:9;<br>
> for q = 1:9;<br>
> for r = 1:9;<br>
> <br>
> x = 100000000.*a+10000000.*b+1000000.*c+100000.*d+10000.*e+1000.*f+100.*g+10.*h+i;<br>
> y = 100000000.*j+10000000.*k+1000000.*l+100000.*m+10000.*n+1000.*o+100.*p+10.*q+r;<br>
> <br>
> z = x/y;<br>
> <br>
> <br>
> if (z  pi < .001)<br>
> <br>
> format short;<br>
> <br>
> printf('x = %i\n', x);<br>
> printf('y = %i\n', y);<br>
> format long;<br>
> printf('z = %i\n', z);<br>
> disp('');<br>
> <br>
> endif<br>
> <br>
> endfor<br>
> endfor<br>
> endfor<br>
> endfor<br>
> endfor<br>
> endfor<br>
> endfor<br>
> endfor<br>
> endfor<br>
> endfor<br>
> endfor<br>
> endfor<br>
> endfor<br>
> endfor<br>
> endfor<br>
> endfor<br>
> endfor<br>
> endfor

Sat, 13 Mar 2010 13:54:02 +0000
Re: Pi approximation function optimization
http://www.mathworks.com/matlabcentral/newsreader/view_thread/276324#726070
John D'Errico
"Sadik " <sadik.hava@gmail.com> wrote in message <hng3aa$fr9$1@fred.mathworks.com>...<br>
> Hi Jared,<br>
> <br>
> 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!]<br>
> <br>
<br>
But then your solution will take a half day to solve.<br>
Since I don't believe that giving a solution to someone<br>
who is trying to learn actually helps them at all, all I<br>
will do is to suggest that there are far better ways to<br>
approach it.<br>
<br>
Be creative. There is at least one solution with error<br>
as low as:<br>
<br>
error =<br>
8.49968984084626e11<br>
<br>
This took 11 lines of code to generate, and 0.23<br>
seconds of cpu time.<br>
<br>
John

Sat, 13 Mar 2010 21:40:26 +0000
Re: Pi approximation function optimization
http://www.mathworks.com/matlabcentral/newsreader/view_thread/276324#726141
Mark Shore
"John D'Errico" <woodchips@rochester.rr.com> wrote in message <hng5dq$h4b$1@fred.mathworks.com>...<br>
> "Sadik " <sadik.hava@gmail.com> wrote in message <hng3aa$fr9$1@fred.mathworks.com>...<br>
> > Hi Jared,<br>
> > <br>
> > 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!]<br>
> > <br>
> <br>
> But then your solution will take a half day to solve.<br>
> Since I don't believe that giving a solution to someone<br>
> who is trying to learn actually helps them at all, all I<br>
> will do is to suggest that there are far better ways to<br>
> approach it.<br>
> <br>
> Be creative. There is at least one solution with error<br>
> as low as:<br>
> <br>
> error =<br>
> 8.49968984084626e11<br>
> <br>
> This took 11 lines of code to generate, and 0.23<br>
> seconds of cpu time.<br>
> <br>
> John<br>
<br>
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.