Re: Anyone familiar with polygcd?

[Doug Stewart]

On Sun, Oct 5, 2014 at 12:55 PM, Daniel J Sebald <address@hidden> wrote:

On 08/05/2014 03:26 PM, Rik wrote:

On 08/05/2014 10:30 AM, John W. Eaton wrote:

On 07/07/2014 01:57 PM, Rik wrote:

All,

I'm getting occasional failures from the test code in polygcd.  It seems to
happen about 10% of the time according to the following code:

for i = 1:100
    bm(i) = test ("polygcd");
endfor
sum (bm)

The test that fails is

%!test
%! for ii=1:10
%!   p  = (unique (randn (10, 1)) * 10).';
%!   p1 = p(3:end);
%!   p2 = p(1:end-2);
%!   assert (polygcd (poly (-p1), poly (-p2)), poly (- intersect (p1, p2)),
sqrt (eps));
%! endfor

[snip]

Michael Godfrey filed a bug report with some more information
(https://savannah.gnu.org/bugs/?42742).

I put a simple changeset with that bug report.  It changes the "* 10" multiplier above to "* 3" and I've not seen a failure with 100,000 tests.  When the multiplier is 10, there are so many roots significantly greater than 1 that the coefficients of poly(-p) become very large making the polygcd() routine fail.  From what I can tell, the underlying algorithm is better than others I've tried.

Dan

With a multiplier of 15 I see 90% failure

and with a multiplier of 5 I saw 1 failure at 2500 tries.

with *3 I see no failures yet!

Doug