bugGNU Octave - Bugs: bug #51241, Infinite loop in normest1

 
 

bug #51241: Infinite loop in normest1

Submitter:  Guillaume <gyom>
Submitted:  Thu 15 Jun 2017 02:43:23 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Fixed Assigned to:  None
Originator Name:  Guillaume Open/Closed:  * Closed
Release:  * dev Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Fri 16 Jun 2017 04:05:14 PM UTC, comment #20: 

I modified the placement of the comments to be clearer and pushed it to the stable branch here (http://hg.savannah.gnu.org/hgweb/octave/rev/4ce622b7b930).  I also pulled it through to the development branch.  Thanks for the very quick fix Marco (< 24 hours from reporting bug to a verified solution).

Rik <rik5>
Group administrator
Fri 16 Jun 2017 02:49:39 PM UTC, comment #19: 

Thanks Marco, I applied your patch and the issue disappeared.

Guillaume <gyom>
Fri 16 Jun 2017 11:09:45 AM UTC, comment #18: 

Here it is my patch.

(file #40926)

Marco Caliari <caliari>
Group Member
Fri 16 Jun 2017 08:22:18 AM UTC, comment #17: 

Thanks Marco, I can also confirm it works with your suggestion.

Guillaume <gyom>
Thu 15 Jun 2017 08:21:57 PM UTC, comment #16: 

@Marco: Your suggested change works for me.

Also, your suggested test case fails reliably, but I agree with Dmitri that it is likely to be a problem to put a test which may hang Octave in the general test suite.

Rik <rik5>
Group administrator
Thu 15 Jun 2017 08:16:15 PM UTC, comment #15: 

rand('seed',1);, condest (a) hangs reliably for me, but I am not
sure this is a good test for unattended build servers.

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Thu 15 Jun 2017 08:06:55 PM UTC, comment #14: 

I think that the reason is not the misplaced i++, but the wrong maximum number of unparallel columns 2^(n-1) (in the comment it is written parallel, this is also wrong). I propose to modify


imax = min (t, 2 ^ (n - 1));


to


imax = min (t, 2 ^ (n - 1) - n);


If it works for you, I will make a patch. How is it possible to add a test for this bug? For instance, I can always reproduce it with


rand('seed',1);, condest (a)


Is it true for everybody?

Marco Caliari <caliari>
Group Member
Thu 15 Jun 2017 04:36:30 PM UTC, comment #13: 

@Rik: Thanks. Your fix seems to work for me. I add Marco to this report in case he can comment on it.

Guillaume <gyom>
Thu 15 Jun 2017 04:36:19 PM UTC, comment #12: 

Adding Marco Caliari to the CC list since he provided the patch for the original function.


changeset:   22183:bfb1b089c230
user:        Marco Caliari <marco.caliari@univr.it>
date:        Mon Jul 25 14:50:29 2016 +0100
summary:     New function normest1 as replacement for onenormest (patch #8837)


The patch was applied after 4.0.3 and before 4.2.0 so it fits the timeline for the introduction of the regression in behavior.


Rik <rik5>
Group administrator
Thu 15 Jun 2017 04:32:39 PM UTC, comment #11: 

Bug seems to have been introduced between 4.0.3 and 4.2.0.

Rik <rik5>
Group administrator
Thu 15 Jun 2017 04:11:44 PM UTC, comment #10: 

Attached is a diff which moves the increment i++ outside of the else branch so that it always takes place.  That solves the issue for me, and 'test normest1' and 'test condest' still pass.  But since I didn't write this code I don't really know if what I'm proposing is correct.

(file #40921)

Rik <rik5>
Group administrator
Thu 15 Jun 2017 04:08:38 PM UTC, comment #9: 

I don't understand the algorithm, but here is a dump of the variables.


debug> i
i =  2
debug> imax
imax =  3
debug> p
p = 0
debug> S
S =

   1   1  -1
  -1   1   1
  -1  -1   1

debug> Sold
Sold =

   1   1  -1
   1  -1  -1
   1   1   1



The issue is this expression


any (abs (S(:,i)' * Sold) == n)


which is always true.  I wonder if the code should read


if (expression)
  ## i-th column of S parallel to previous one
  do stuff...
endif
i++;


rather than


if (expression)
  ## i-th column of S parallel to previous one
  do stuff...
else
  i++;
endif



Rik <rik5>
Group administrator
Thu 15 Jun 2017 04:01:34 PM UTC, comment #8: 

Within normest1, the problem is this section of code


          while (i <= imax)
            ## The maximum number of parallel columns of length n with entries
            ## {-1,1} is 2^(n-1). Therefore, if the number of columns of S is
            ## greater than 2^(n-1), for sure some of them are parallel to some
            ## columns of Sold. Don't even try to change them (i <= 2^(n-1)).
            ## Now, check if S(:,i) is parallel to any previous column of S
            p = (any (abs (S(:,i)' * S(:,1:i-1)) == n));
            if (p || (any (abs (S(:,i)' * Sold) == n)))
              ## i-th column of S parallel to a previous or to a
              ## column of Sold: change it.
              S(:,i) = sign (2*rand (n, 1)-1);
            else
              i++;
            endif
          endwhile


If the first branch of the if statement is taken, then the variable i is never incremented.

Rik <rik5>
Group administrator
Thu 15 Jun 2017 03:56:58 PM UTC, comment #7: 

I used dbstep to step through the code.  The line that hangs is


[Ainv_norm, v, w] = normest1 (solve, t, [], varargin{4:end});


normest1.m is an m-file and it does have while loops so that is probably where the problem lies.

Rik <rik5>
Group administrator
Thu 15 Jun 2017 03:38:42 PM UTC, comment #6: 

There are calls to rand(), see the help text:


## Algorithm Note: @code{condest} uses a randomized algorithm to approximate
## the 1-norms.


Guillaume <gyom>
Thu 15 Jun 2017 03:36:54 PM UTC, comment #5: 

There are "lu" and "\" in the code which are iterative and thus can hang. What puzzles me is the randomness of this.

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Thu 15 Jun 2017 03:33:03 PM UTC, comment #4: 

I can confirm it on this cset as well:

[dima@i7 gcc_default]$ hg id
b0e9c030f063 tip @
[dima@i7 gcc_default]$ ./run-octave --no-gui
GNU Octave, version 4.3.0+
Copyright (C) 2016 John W. Eaton and others.
This is free software; see the source code for copying conditions.
There is ABSOLUTELY NO WARRANTY; not even for MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  For details, type 'warranty'.

Octave was configured for "x86_64-pc-linux-gnu".

Additional information about Octave is available at http://www.octave.org.

Please contribute if you find this software useful.
For more information, visit http://www.octave.org/get-involved.html

Read http://www.octave.org/bugs.html to learn how to submit bug reports.
For information about changes from previous versions, type 'news'.

octave:1> a = [146.50 3.2070e-61 0;3.2070e-61 147.50 0;0 0 144.00];
octave:2> condest(a)
^C
octave:2> condest(a)
^C
octave:2> condest(a)
^C
octave:2> condest(a)
ans =  1.0243
octave:3> condest(a)
ans =  1.0243
octave:4> condest(a)



Dmitri A. Sergatskov <dasergatskov>
Thu 15 Jun 2017 03:21:22 PM UTC, comment #3: 

For reference, I am using cset 23604:b0e9c030f063.  You might try updating to that version as this bug seems to be present for 4.2.1 but not on the latest development tip.

Rik <rik5>
Group administrator
Thu 15 Jun 2017 03:19:21 PM UTC, comment #2: 

I can confirm the behaviour with 4.2.1

Dmitri.

Dmitri A. Sergatskov <dasergatskov>
Thu 15 Jun 2017 03:14:28 PM UTC, comment #1: 

This works for me.  I also don't see any for/while/do-until loops in condest.m so I don't see how it could get caught in an infinite loop.

Maybe try stepping through the code using the debugger and seeing what statement causes the hang for you.

Rik <rik5>
Group administrator
Thu 15 Jun 2017 02:43:23 PM UTC, original submission:  

In a random way, condest seems to get stuck in a loop:


a = [146.50 3.2070e-61 0;3.2070e-61 147.50 0;0 0 144.00];
condest(a)


It returns 1.0243 or never returns.

Guillaume <gyom>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #40926:  normest1_marco.diff added by caliari (2KiB - application/x-tex)
file #40921:  normest1.diff added by rik5 (540B - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by caliari (Posted a comment)
  • -email is unavailable- added by rik5
  • -email is unavailable- added by dasergatskov (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by gyom (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 11 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2017-06-16 rik5 StatusPatch Submitted Fixed
        Open/ClosedOpen Closed
    2017-06-16 caliari Attached File- Added normest1_marco.diff, #40926
        StatusIn Progress Patch Submitted
    2017-06-16 rik5 StatusPatch Submitted In Progress
    2017-06-15 rik5 Carbon-Copy- Added caliari
    2017-06-15 rik5 Attached File- Added normest1.diff, #40921
        StatusConfirmed Patch Submitted
    2017-06-15 rik5 SummaryInfinite loop in condest Infinite loop in normest1
    2017-06-15 rik5 StatusWorks For Me Confirmed
    2017-06-15 rik5 StatusNone Works For Me

    Back to the top

    Powered by Savane 3.13-4b48.
    Corresponding source code