Re: octave "Most Wanted" feature

[robert bristow-johnson]

> Date: Tue, 28 Nov 2006 15:18:26 -0500
> From: "Tom Holroyd (NIH/NIMH) [E]" <address@hidden>
> Subject: Re: octave "Most Wanted" feature
> 
> robert bristow-johnson wrote:
> >> Could you allow,
> >>
> >>    > octave_index_origin (0);
> >> or
> >>    > octave_index_origin (1);      (the default)
> >
> >
> > or even     > octave_index_origin (-256);
> 
> Er, no. There are two choices, 0 and 1. There are no other choices.

er no, Dr. Holroyd, you're mistaken.  there is no more need to restrict the 
Index Origin to 0 or to 0 and 1 than there is to restrict it to 1.

or are you saying that Octave presently supports 0-Index_Origin?  i hadn't 
thought it could.

> And you 
> certainly would not want to have different index origins for the rows and 
> columns of the same matrix!

what's wrong with that?  if i had a non-square two dimensional array 
representing a spectrogram of audio where the original audio was defined with 
some negative Index Origin, i might want the "time" dimension to preserve the 
same Index Origin but the "frequency" dimension to begin with index 0.

> What would be the point?

i'm not sure that you get it.  did you read the initial post i put here?  the 
point is so that the indices can be directly meaningful to the interpretation 
of the data that they are associated with.  the point is so that the 
expressions in Octave (or MATLAB, i wish) would more closely resemble the 
mathematical expressions of the same quantity as expressed in the textbooks and 
the literature.  i made two *very* clear examples regarding the DFT and 
discrete-convolution (which are fundamental in DSP) where MATLAB (and Octave) 
gets it wrong.  and it gets it wrong because the indexing is hard-wired to 
start at 1.

> You can define your own 
> indexing functions to do that if you want to.

what do you mean by that?  i have to offset the index in my code.  sure i can 
get that to work (if i find the bugs from having to offset indices) but the 
expressions in Octave are not similar to the corresponding expressions in the 
lit.

> > ... imagining that Octave is written in C or C++
> 
> If you don't know that, then ... EOF

my, that's friendly (and open-minded).  listen, i can download the Octave 
source, too (and i did) and peak at a couple of the makefiles (and i did) and 
it appears that most or all of the Octave source is in C or C++.  but this GNU 
and linux thing is so big that i really don't know the extent of it.  maybe 
there's some Fortran code tucked away back there that is built with a GNU 
Fortran compiler and linked in with the rest of the project.  this project is 
*huge*.  i really don't have the foggiest idea where to look for these basic 
operations (and was hoping that someone who does know might tell me).

i'm not a computer scientist, i'm an electrical engineer who does signal 
processing for music and audio.  i actually really want to have the computer 
serve ME (by allowing me to express mathematical ideas in the concise manner we 
do on the whiteboard) and not have to serve the computer (by being force to 
express mathematical ideas with unnecessary limitations imposed by whatever 
language).  i am no slouch.  i have a unique (hyphenated) last name and if you 
Google it.  i have some publication record.  i am a reviewer for the Journal of 
the Audio Engineering Society.  i usually know what i am talking about.

many times, in MATLAB, i have windowed off a piece of audio, run that windowed 
snippet into the fft() function, then abs(), then max() to get the maximum 
value and the frequency of the maximum value (from the index) which i will use 
in further calculation.  problem is that if i forget to subtract this unnatural 
1 offset from the index of the max value, my frequency calculation will be off 
and i will get suboptimal results even though my MATLAB equations _appear_ 
correct when compared to the the literature (this might be about a 
phase-vocoder).  once i knew for weeks that there was this tiny error in my 
calculation (because i could test it on a known sinusoid) but couldn't for the 
life of me find where this error was until finally when i saw a small obscure 
place where i forgot to adjust the index returned from max() by that little 1.

also i have had to take non-causal impulse responses (that were nicely 
symmetrical about t=0) and offset them by a known amount so that they could be 
represented as a MATLAB variable.  but then, when i would look at the transfer 
function of that offset impulse response, there was an extraneous linear-phase 
factor in it due to this offset that shouldn't be there.  sure, we can account 
for this when we remember that MATLAB forces us to change our notation, but 
that is US serving the computer, not the computer serving US.

in the comp.dsp newsgroup, we make jokes about this "feature" in MATLAB and 
occasionally people post questions about why there MATLAB program is giving 
them inaccurate results where it is later discovered it is due to this 
unnatural offset of 1.

please read the original post.  i spell out what the problem is with MATLAB 
(and then Octave, by association), why the problem is a problem, and how MATLAB 
(or Octave) can be adapted in a backward-compatible manner to fix this.  I have 
thought about this problem (regarding MATLAB, not Octave) for a decade and a 
half.  i know what i'm talking about (but i realize that you might not know 
that i know what i'm talking about) regarding this.  it doesn't have to break 
Octave.  it doesn't have to make any existing Octave programs fail that work 
presently.  it's an *extension*, not a change.  but since it involves the 
indexing, it's an extension that involves changes or patches pretty deep inside 
of Octave.  but i am confident, it can be done that would have no effect (other 
than a very, very, tiny speed thing because when individual elements of an 
array are accessed, that "1" that must be subtracted would have to be looked up 
in the hidden structure of an Octave variable rather than be a constant) on 
existing Octave programs.


> Date: Tue, 28 Nov 2006 21:37:10 +0100
> From: David Bateman <address@hidden>
> Subject: Re: octave "Most Wanted" feature
> 
> robert bristow-johnson wrote:
> 
> > Yes, it requires rewriting a few parts deep inside of Octave (but in such a 
> > way as to preserve backward compatibility which we all
> > should consider to be super-important).
> 
> If we accept that all indices are either 1 or 0 indexed,

why restrict the Index Origin to be either 1 or 0?  if you're going to allow 
for 0-origin arrays, why not arrays with Index Origin = -32768 ?

> then no I don't
> think there are that many changes to the C++ code of octave. Essential
> the idx-vector class would have a flag on how the indexing is done.

i don't know how to find that in the code.  where is the main structure or 
object definition for an Octave variable. (where the number of dimensions is 
set and the sizes of rows, columns, and other dimensions is defined?  that is 
where to start with this.)

> There will be several functions that do a +1 to return values in C++,
> such as find or sort that would need to respect the default indexing
> type, and that'll lead to the potential for many errors. The basic code
> itself in liboctave is all zero indexed based, and that shouldn't change.

does this mean that the C/C++ code that addresses elements of an Octave 
variable is 0-based and that an adjustment of 1 is made when translating that 
index to the Octave program?  if so, i suspected as much.

> However, I think this is a case where matlab compatibility will cause
> much pain. This idea would condemn all of the octave script files to
> special case of one- or zero-based index, making the code harder to
> maintain and slower.

i don't understand what you mean.  i am proposing a backward compatible 
extension.  if someone wants to use arrays with a different Index Origin, after 
creating the array, they have to call a not-yet-existing function that will 
reset the Index Origin (for some particular dimension) to a non-1 value.

> Basically, my feeling we can't support both one and
> zero indexing, and matlab has to make to move first...

they won't.  their pride and stubborness is enormous.  shall i dig out my old 
emails with Cleve Moler.  finally, after finally admitting that this would not 
break existing MATLAB programs (that would never use non-1-origin arrays), 
Cleve just said that it would be another language.  "it wouldn't be MATLAB." or 
something like that.  i cannot see how that would be expected to be very 
convincing.

I believe that, since Octave is open-source (but the source is so big, i can't 
find my way around anywhere in it), this could be fixed first in MATLAB.  we 
could define a new "fft" (i would call it "dft()") and other DSP functions that 
use more naturally defined indices.  DSP engineers using Octave would catch on 
and appreciate this.  the MathWorks people would hear about this thing that 
Octave does and MATLAB doesn't and then either profit-motive or shame will 
finally persuade them to fix it there.  again, as Eric Jacobsen, literally the 
"Minister of Algorithms" at Intel said:

     "Legacy of a bad idea, in my opinion, is a poor excuse for
      continuing along ad nauseum with the bad idea.  At some point
      it is a benefit to correct the bad idea, and the longer one
      waits to do it the more painful it is."

That is what this is about.

> Note that I have experience in fortran programming and see no issue
> between one and zero indexing as such, as long as we stick one of these.

no.  why must we be shackled to either 0 or 1?

> I would of course have preferred that both C and fortran were consistent
> in their indexing.

given the choice, the C way *is* better as Edsger Dykstra has spelled out:

http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html
or
http://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF

but we need not be restricted to only those two choices.


> Date: Tue, 28 Nov 2006 16:15:35 -0500
> From: "John W. Eaton" <address@hidden>
> Subject: Re: octave "Most Wanted" feature
> 
> You definitely do NOT want to set a global index base,

agree fully.

> but I think it
> would be acceptable to set a local index base for a given variable,
> the same as it works in Fortran.  In that case, yes, you can have
> different index bases for each dimension of a multidimensional array.

yea!

and, each Octave variable has at least 2 dimensions (rows, columns).  even 
scalers.  at least that's true for MATLAB and i presumed true for Octave.  now 
i dunno what meaning there would be to setting the Index Origin to the two 
dimensions of a 1x1 Octave "array", but these 1x1 arrays are dealt with a 
little differently anyway.

> It makes perfect sense to be able to do this kind of thing (think
> about points on a grid going from x_min to x_max and y_min to y_max).

i'm glad you can see the sense of this (that Cleve could not).

> I don't see how changing the index base could cause trouble since the
> change in indexing would only affect the variable in the local scope.
> The default value would remain 1.

that default value set to 1 is critical to make things backward compatible.

> But even so, I've not given it a
> lot of thought, and suspect there would be some problems in the
> details of implementing a feature like this.

i didn't say it would be a cakewalk, extending some functions to work with 
arrays with non-1-origin might not work, and those functions can return an 
error message just like when you try to do some other arithmetic with arrays 
that do not have the correct size/shape.  it's still backward compatible.

i don't know why there is opposition to this idea amoung MATLAB users and, 
apparently, some Octave users/developers/maintainers.

Thank you Dr. Eaton for saying what you have.  I have thought about this very 
carefully, and even though I recognise my limitation in dealing with the source 
code, I am convinced that this can be done, will make Octave better, will be 
greatly appreciated by DSP engineers, and will be backward compatable.

thank you for the consideration.


> Date: Tue, 28 Nov 2006 16:47:31 -0500 (EST)
> From: Przemek Klosowski <address@hidden>
> Subject: Re: octave "Most Wanted" feature
> 
> One interesting application of an offset that is neither 0 nor 1 is
> used for memory allocation in Numerical Recipes. For example, they
> allocate a 128-element vector and then subtract 128 from the
> allocation pointer 'v', to access v(129..256). Ugly hack, but it
> simplifies array offset expressions sometimes.

ugly hack to get the "correctly" offsetted array pointer to start with, but 
it's not ugly in the usage.  at least you can do it in C (because there is no 
index checking against limits in C) and i have done this many times regarding 
the FFT as has Q. Spencer below:


> Date: Tue, 28 Nov 2006 15:59:18 -0600
> From: Quentin Spencer <address@hidden>
> Subject: Re: octave "Most Wanted" feature
> Message-ID: <address@hidden>
>
> Another example the output of the fftshift function, which moves the DC
> frequency to the middle of a vector. Using a negative index origin would
> make it possible for the index to correspond directly to the frequency.




--

r b-j                  address@hidden

"Imagination is more important than knowledge."