bugGNU Octave - Bugs: bug #49026, function fft return wrong result...

 
 

bug #49026: function fft return wrong result or crash if n=1 and dim>2

Submitter:  None
Submitted:  Thu 08 Sep 2016 05:36:07 AM UTC
   
 
Category:  Octave Function Severity:  4 - Important
Priority:  5 - Normal Item Group:  Segfault, Bus Error, etc.
Status:  Fixed Assigned to:  None
Originator Name:  Originator Email:  -email is unavailable-
Open/Closed:  * Closed Release:  * 4.0.3
Operating System:  * GNU/Linux Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Mon 24 Oct 2016 04:35:18 PM UTC, comment #4: 

I ran through the original examples again, no segfaults or FPEs now, and results look good at a glance, thanks for taking care of this.

Mike Miller <mtmiller>
Group Member
Mon 24 Oct 2016 04:05:34 PM UTC, comment #3: 

I committed the patch on the stable branch here (http://hg.savannah.gnu.org/hgweb/octave/rev/655157b34a9f) since I hate to see segfaults.

Fixed, closing report.

Rik <rik5>
Group administrator
Fri 21 Oct 2016 07:11:23 PM UTC, comment #2: 

The problem seems to be in do_fft in libinterp/corefcn/fft.cc.  I quote the code, along for the first case for real FFT of single matrices.


  if (n_points < 0)
    n_points = dims(dim);
  else
    dims(dim) = n_points;

  if (dims.any_zero () || n_points == 0)
    {
      if (arg.is_single_type ())
        return octave_value (FloatNDArray (dims));
      else
        return octave_value (NDArray (dims));
    }

  if (arg.is_single_type ())
    {
      if (arg.is_real_type ())
        {
          FloatNDArray nda = arg.float_array_value ();

          nda.resize (dims, 0.0);
          retval = (type != 0 ? nda.ifourier (dim) : nda.fourier (dim));
        }


The original array was a 4-D array (2x4x2x2).  The call to fft


fft (x,1,4)


has asked to use just a single point along the fourth (last) dimension.  In the C++ code,


    dims(dim) = n_points;


the final dimension is set to 1 so the new dimensions are 2x4x2x1.

Eventually, nda.resize is called, and Octave knows to trim singleton dimensions, so the matrix becomes a 3-D matrix 2x4x2.  You can check and find that fft works correctly when the dimension is not the trailing dimension.

That's the problem.  I can see a few solutions.  First, from someone who understands the FFT well, if I take an FFT with a single point, is the result really just an indexing operation?  In this example


fft (x,1,4) === x(:,:,:,1)  ???


If that is the case, then maybe we can implement that equivalent index operation on an octave_value in C++ only when n_points == 1.  This wouldn't be too much of a hassle because there is already a special case for n_points == 0.

Second, maybe there is a way to resize an array and avoid trimming singleton dimensions.

Third, and least interesting, each fourier and ifourier routine in liboctave needs to be updated to handle this special case.

I'm attaching a patch that works for me.  Mike, can you test it?

Since this is a crash I would apply it to the stable branch if it passes QC.

(file #38789)

Rik <rik5>
Group administrator
Thu 08 Sep 2016 06:18:19 PM UTC, comment #1: 

I do get the same incorrect results, and I get the floating point exception only when running octave-cli, not when liboctgui is loaded. Confirmed in both 4.0.3 and default branch.

Mike Miller <mtmiller>
Group Member
Thu 08 Sep 2016 05:36:07 AM UTC, original submission:  

wrong result:

octave:1> x=rand(3,4,2), fft(x,1,3)
x =

ans(:,:,1) =

   0.017138   0.462852   0.363441   0.922481
   0.140206   0.042190   0.956938   0.162861
   0.116520   0.675517   0.028859   0.152628

ans(:,:,2) =

   0.3657579   0.5745495   0.1027223   0.4093351
   0.9649254   0.7427751   0.0049076   0.5797570
   0.9617079   0.3918733   0.6584627   0.9648994

ans =

   0   0   0   0
   0   0   0   0
   0   0   0   0

octave:2> x=rand(2,4,1,2), fft(x,1,4)
x =

ans(:,:,1,1) =

   0.25452   0.96034   0.12719   0.37965
   0.35650   0.90113   0.25084   0.62313

ans(:,:,1,2) =

   0.49780   0.79052   0.71106   0.28961
   0.23440   0.68358   0.77451   0.79083

ans = [](0x0)


crash:

octave:1> x=rand(2,4,2,2), fft(x,1,4)
x =

ans(:,:,1,1) =

   0.2503632   0.9714970   0.7993745   0.0039809
   0.6455604   0.8834564   0.9793053   0.2731584

ans(:,:,2,1) =

   0.82234   0.84438   0.22820   0.52942
   0.71028   0.34665   0.24366   0.80572

ans(:,:,1,2) =

   0.589032   0.046873   0.646299   0.279528
   0.072980   0.606222   0.339875   0.582812

ans(:,:,2,2) =

   0.16773   0.22497   0.50414   0.44783
   0.95144   0.84045   0.29088   0.78029

panic: Floating point exception -- stopping myself...
attempting to save variables to 'octave-workspace'...
save to 'octave-workspace' complete


octave:1> x=rand(1,4,2,2), fft(x,1,4)
x =

ans(:,:,1,1) =

   0.991429   0.046931   0.686220   0.749211

ans(:,:,2,1) =

   0.13584   0.96292   0.59547   0.51085

ans(:,:,1,2) =

   0.903782   0.350536   0.011354   0.730583

ans(:,:,2,2) =

   0.97086   0.55458   0.90932   0.18700

panic: Floating point exception -- stopping myself...
attempting to save variables to 'octave-workspace'...
save to 'octave-workspace' complete


my version:

octave:1> ver
----------------------------------------------------------------------
GNU Octave Version: 4.0.3
GNU Octave License: GNU General Public License
Operating System: Linux 3.16.0-4-amd64 #1 SMP Debian 3.16.36-1+deb8u1 (2016-09-03) x86_64
----------------------------------------------------------------------
no packages installed.



ii  liboctave3:amd64                      4.0.3-1~bpo8+1                       amd64        Shared libraries of the GNU Octave language
ii  octave                                4.0.3-1~bpo8+1                       amd64        GNU Octave language for numerical computations
ii  octave-common                         4.0.3-1~bpo8+1                       all          architecture-independent files for octave
ii  octave-doc                            4.0.3-1~bpo8+1                       all          PDF documentation on the GNU Octave language
ii  octave-info                           4.0.3-1~bpo8+1                       all          GNU Info documentation on the GNU Octave language


Anonymous

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #38789:  fft.cset added by rik5 (5KiB - application/octet-stream)

 

Depends on the following items: None found

Digest:
   bug dependencies.

 

Carbon-Copy List
  • -email is unavailable- added by rik5 (Updated the item)
  • -email is unavailable- added by mtmiller (Posted a comment)
  • -email is unavailable- added by None (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 8 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2016-11-21 rik5 Dependencies- bugs #43673 is dependent
    2016-10-24 rik5 StatusPatch Submitted Fixed
        Open/ClosedOpen Closed
    2016-10-21 rik5 Attached File- Added fft.cset, #38789
        StatusConfirmed Patch Submitted
    2016-09-08 mtmiller Severity3 - Normal 4 - Important
        Item GroupIncorrect Result Segfault, Bus Error, etc.
        StatusNone Confirmed

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code