# comparing execution times Bairstow method

Posted 9 years ago
5343 Views
|
6 Replies
|
4 Total Likes
|
 Hi all I write because I have a question, I am currently trying to implement the algorithm Bairstow, I am based on an example I found on the internet, but to try to make some modifications the algorithm has become slower, in the notebook I show the algorithm found on the Internet (in a function called bair),and then the attempt to make the fastest algorithm (in a function called bairs), which do not work well. I would like your comments on the possible adjustments that would have to do in my notebook Attachments:
6 Replies
Sort By:
Posted 9 years ago
 C'mon, Luis, look at the printout. The function" bairs" is performing exact arithmetic, on rational numbers that increase in (digit) size. To evade that either alter it to use N, or SetPrecision, or just make the input approximate. In[82]:= Timing[bairs[N@{1, -7, 14, 2, -20}, {5, 3}, 7]] During evaluation of In[82]:= {r,s} {3.62331838565,4.13901345291} During evaluation of In[82]:= {r,s} {2.77031921518,3.78386093002} During evaluation of In[82]:= {r,s} {2.12116775129,3.12004963809} During evaluation of In[82]:= {r,s} {1.23572756992,2.2359435089} During evaluation of In[82]:= {r,s} {0.930633063016,1.93061427513} During evaluation of In[82]:= {r,s} {0.995510055858,1.9955096949} During evaluation of In[82]:= {r,s} {0.999979931134,1.99997993066} During evaluation of In[82]:= El factor cuadratico es: x^2-0.999979931134x-1.99997993066 Out[82]= {0.004000, Null}
Posted 9 years ago
 here is the definition of the function bair bair[pol_, p0_, m_, p_] := Module[{n, a, r, i, s, j, b, c, tol}, tol = 0.0001; n = Length[pol] - 1; (* primer for*)For[i = 0, i <= n, i++, a[i] = SetPrecision[pol[[n - i + 1]], p]]; r = SetPrecision[p0[[1]], p]; s = SetPrecision[p0[[2]], p]; b[0] = SetPrecision[2 tol, p]; b[1] = SetPrecision[2 tol, p]; (* segundo for*)For[j = 1, j <= m, j++, b[n] = SetPrecision[a[n], p]; b[n - 1] = SetPrecision[a[n - 1] + r b[n], p]; (* tercer for*)For[i = n - 2, i >= 0, i--, b[i] = SetPrecision[a[i] + r b[i + 1] + s b[i + 2], p]]; c[n] = SetPrecision[b[n], p]; c[n - 1] = SetPrecision[b[n - 1] + r c[n], p]; (* ultimo for*)For[i = n - 2, i >= 1, i--, c[i] = SetPrecision[b[i] + r c[i + 1] + s c[i + 2], p]]; r = SetPrecision[r + (-b[1] c[2] + b[0] c[3])/(c[2]^2 - c[1] c[3]), p]; s = SetPrecision[s + (-b[0] c[2] + b[1] c[1])/(c[2]^2 - c[1] c[3]), p]]; Print["El factor cuadratico es: x^2", If[-r > 0, "+", ""], -r, "x", If[-s > 0, "+", ""], -s]] now make comparisons runtime between the two functions with the same arguments (* Using the bair function*) Timing[bair[{1, -7, 14, 2, -20}, {5, 3}, 7, 10]] (* Using the bairs function*) Timing[bairs[{1, -7, 14, 2, -20}, {5, 3}, 7]] (* Using the bair function*) Timing[bair[{1, -3, -9, -27, -162}, {2, 7}, 7, 10]] (* Using the bairs function*) Timing[bairs[{1, -3, -9, -27, -162}, {2, 7}, 7]] if anyone has any idea of the situation happens for this time difference, please comment on this, because I have not seen what the conflict to have this result, thanks in advanceattached my file so they can make comparisons Attachments:
Posted 9 years ago
 Thanks for your support Daniel , I have run your code and the method does well, but could you explain to me why is slower compared to where we use cycles For. Example using the function bair[{1,-7,14,2,-20},{0,0,},20,40] work well, but using function bairs[{1,-7,14,2,-20},{0,0,},20] apparently mathematica performs many operations and takes longer to return the result, my question is, why?, if both occupy the same number of iterations in this case 20
Posted 9 years ago
 I'm not convinced that that's a viable reference, at least not for the method in the Wikipedia article. There was loop nesting to three levels in that code. Only two should be necessary. One to compute the new coefficients, and one to iterate some number of times (or until convergence).
Posted 9 years ago
 Thanks Daniel, I obtained the code of this video code Bairstow, I think it can serve as a reference
Posted 9 years ago
 It's difficult to see how you get this code without seeing the reference. I altered it based on a Wikipedia article. bairs[pol_, p0_, m_] := Module[{n, a, r, s, j, b, c, d, f, , g, h, tol}, tol = 1/10000; n = Length[pol] - 1; Table[a[i] = pol[[n - i + 1]], {i, 0, n}]; r = p0[[1]]; s = p0[[2]]; Do[ b[n] = 0; b[n - 1] = 0; Table[b[i] = a[i + 2] + r b[i + 1] + s b[i + 2], {i, n - 2, 0, -1}]; c = a[1] + r*b[0] + s*b[1]; d = a[0] + s*b[0]; f[n] = 0; f[n - 1] = 0; Table[f[i] = b[i + 2] + r f[i + 1] + s f[i + 2], {i, n - 2, 0, -1}]; g = b[1] + r*f[0] + s*f[1]; h = b[0] + s*f[0]; {r, s} = {r, s} + 1/(-s*g^2 + h*(h + r*g))*{{-h, g}, {g*s, -g*r - h}}.{c, d}; Print["{r,s} ", {r, s}], {m}]; Print["El factor cuadratico es: x^2", If[-r > 0, "+", ""], N[-r, 4], "x", If[-s > 0, "+", ""], N[-s, 4]]] This version seems to work reasonably well. It was taken, with very minor adjustment, from:http://en.wikipedia.org/wiki/Bairstow%27s_method