Message Boards Message Boards

0
|
5791 Views
|
6 Replies
|
4 Total Likes
View groups...
Share
Share this post:

comparing execution times Bairstow method

Posted 10 years ago

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:
POSTED BY: Luis Ledesma
6 Replies

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 BY: Daniel Lichtblau
Posted 10 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 advance

attached my file so they can make comparisons

Attachments:
POSTED BY: Luis Ledesma
Posted 10 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 BY: Luis Ledesma

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 BY: Daniel Lichtblau
Posted 10 years ago

Thanks Daniel, I obtained the code of this video code Bairstow, I think it can serve as a reference

POSTED BY: Luis Ledesma

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

POSTED BY: Daniel Lichtblau
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract