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

# 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" wrote in message ... > 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 " wrote in message ... > 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" wrote in message ... > "Sadik " wrote in message ... > > 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.