Thread Subject: "Complex Algorithm R&D: Harder Than Many Think" article published

The article "Complex Algorithm R&D: Harder Than Many Think" has been
published on the Math Blog. The article discusses using advanced
mathematics to solve real world problems, including specific examples
in video compression and speech recognition. The article is for a
general audience and may be useful for anyone interested in this
specialized field. The article discusses the mathematical,
scientific, software engineering, project management, and business
issues at an introductory to intermediate level with a minimum of
formulas or technical jargon.

http://math-blog.com/2009/07/20/complex-algorithm-research-and-development-harder-than-many-think/

Sincerely,

John

John wrote:
> The article "Complex Algorithm R&D: Harder Than Many Think" has been
> published on the Math Blog. The article discusses using advanced
> mathematics to solve real world problems, including specific examples
> in video compression and speech recognition. The article is for a
> general audience and may be useful for anyone interested in this
> specialized field. The article discusses the mathematical,
> scientific, software engineering, project management, and business
> issues at an introductory to intermediate level with a minimum of
> formulas or technical jargon.
>
> http://math-blog.com/2009/07/20/complex-algorithm-research-and-development-harder-than-many-think/
>
> Sincerely,
>
> John

I stopped reading at: "object-oriented methods are of limited use in
complex algorithms".


--
Kenneth Sloan KennethRSloan@gmail.com
Computer and Information Sciences +1-205-932-2213
University of Alabama at Birmingham FAX +1-205-934-5473
Birmingham, AL 35294-1170 http://KennethRSloan.com/

On 21 July, 15:13, Kenneth Sloan <KennethRSl...@gmail.com> wrote:
> John wrote:
> > The article "Complex Algorithm R&D: Harder Than Many Think" has been
> > published on the Math Blog.  The article discusses using advanced
> > mathematics to solve real world problems, including specific examples
> > in video compression and speech recognition.  The article is for a
> > general audience and may be useful for anyone interested in this
> > specialized field.  The article discusses the mathematical,
> > scientific, software engineering, project management, and business
> > issues at an introductory to intermediate level with a minimum of
> > formulas or technical jargon.
>
> >http://math-blog.com/2009/07/20/complex-algorithm-research-and-develo...
>
> I stopped reading at: "object-oriented methods are of limited use in
> complex algorithms".

Too true for your taste?

-LV

LudovicoVan wrote:
> On 21 July, 15:13, Kenneth Sloan <KennethRSl...@gmail.com> wrote:
>> John wrote:
>>> The article "Complex Algorithm R&D: Harder Than Many Think" has been
>>> published on the Math Blog. The article discusses using advanced
>>> mathematics to solve real world problems, including specific examples
>>> in video compression and speech recognition. The article is for a
>>> general audience and may be useful for anyone interested in this
>>> specialized field. The article discusses the mathematical,
>>> scientific, software engineering, project management, and business
>>> issues at an introductory to intermediate level with a minimum of
>>> formulas or technical jargon.
>>> http://math-blog.com/2009/07/20/complex-algorithm-research-and-develo...
>> I stopped reading at: "object-oriented methods are of limited use in
>> complex algorithms".
>
> Too true for your taste?
>
> -LV

I did appreciate his comment that programming in C++ does not qualify as
"using object-oriented methods". That part was true enough.

--
Kenneth Sloan KennethRSloan@gmail.com
Computer and Information Sciences +1-205-932-2213
University of Alabama at Birmingham FAX +1-205-934-5473
Birmingham, AL 35294-1170 http://KennethRSloan.com/

On 21 July, 16:19, Kenneth Sloan <KennethRSl...@gmail.com> wrote:
> LudovicoVan wrote:
> > On 21 July, 15:13, Kenneth Sloan <KennethRSl...@gmail.com> wrote:
>
> >> I stopped reading at: "object-oriented methods are of limited use in
> >> complex algorithms".
>
> > Too true for your taste?
>
> I did appreciate his comment that programming in C++ does not qualify as
> "using object-oriented methods".  That part was true enough.

As he is talking about algorithms, I don't see the rationale in your
objection. OO methodologies can help lower the complexity of the
software structure (to a certain extent): there is no specific
connection to algorithms complexity, though.

(BTW: despite widespread sentiment, mostly among the young
professionals, thanks to fake gurus and unscrupolous marketers, even
if OO methodologies have their strengths, an OO-only approach to
software development just leads to monolitic, overengineered
applications, i.e. the opposite of the intended result. But OO and all
the fake gadgets sell so well... Anyway, this is really another story,
just to say that I am under the impression that you may be one of
those OO zealots, as this would explain your pavlovian reaction.)

Am I missing something?

-LV

On Jul 21, 10:03 pm, John <jmcgowa...@gmail.com> wrote:
> The article "Complex Algorithm R&D: Harder Than Many Think" has been
> published on the Math Blog.  The article discusses using advanced
> mathematics to solve real world problems, including specific examples
> in video compression and speech recognition.  The article is for a
> general audience and may be useful for anyone interested in this
> specialized field.  The article discusses the mathematical,
> scientific, software engineering, project management, and business
> issues at an introductory to intermediate level with a minimum of
> formulas or technical jargon.
>
> http://math-blog.com/2009/07/20/complex-algorithm-research-and-develo...

Who but an idiot would suggest this is not very hard? :-\

Steve

On Tue, 21 Jul 2009 08:58:18 -0700, steveu@dis.org wrote:

> On Jul 21, 10:03 pm, John <jmcgowa...@gmail.com> wrote:
>> The article "Complex Algorithm R&D: Harder Than Many Think" has been
>> published on the Math Blog.  The article discusses using advanced
>> mathematics to solve real world problems, including specific examples
>> in video compression and speech recognition.  The article is for a
>> general audience and may be useful for anyone interested in this
>> specialized field.  The article discusses the mathematical, scientific,
>> software engineering, project management, and business issues at an
>> introductory to intermediate level with a minimum of formulas or
>> technical jargon.
>>
>> http://math-blog.com/2009/07/20/complex-algorithm-research-and-
develo...
>
> Who but an idiot would suggest this is not very hard? :-\

Uhh -- management? Particularly upper management after a nice three-
martini lunch with a sales guy from The Mathworks?

--
www.wescottdesign.com

LudovicoVan schrieb:

> Am I missing something?
>
> -LV

Yes,
Probably you think algorithmic complexity has to do with
FORTRAN LINPACK efficiency.

But look at the following: Define the necessary structure
where euclides GCD algorithm works mathematically, you
end up in some axioms.

This axioms can be interpreted by further adding axioms,
so that you arrive at natural numbers, rationals, polynoms,
etc.. And the abstract GCD algorithm serves these
structures, and complexity results can be lifted.

Now look at it OO:

     class EuklideanRingElement {
        gcd;
        abstract div etc..
     }
     class Rational extends EuklideanRingElement {
        div
     }
     class Polynom extends EuklideanRingElement {
        div
     }

Just a guess how OO could come in... See also:
http://www.amazon.com/dp/1558606793, think they would
miss OO very much, many of the algorithms are based
on frameworks...

But cutting an OO framework is Art.

Bye

Kenneth Sloan <KennethRSloan@gmail.com> wrote:

>John wrote:

>http://math-blog.com/2009/07/20/complex-algorithm-research-and-development-harder-than-many-think/

>I stopped reading at: "object-oriented methods are of limited use in
>complex algorithms".

Then there's "The dream algorithm R&D tool would be similar
to Matlab..."

This is a nice article in that it surfaces issues but there
is little in it about which to form, or to support any, conclusions.

(Is is correct to call Visual Basic a "scripting language"? I was
not aware of that terminology.)

I personally find the OO features of C++ sufficient to facilitate
better code organization, more practical maintenance, and
easier handoff than the other languages mentioned.

Steve

steveu@dis.org wrote:

> On Jul 21, 10:03 pm, John <jmcgowa...@gmail.com> wrote:
>
>>The article "Complex Algorithm R&D: Harder Than Many Think" has been
>>published on the Math Blog. The article discusses using advanced
>>mathematics to solve real world problems, including specific examples
>>in video compression and speech recognition. The article is for a
>>general audience and may be useful for anyone interested in this
>>specialized field. The article discusses the mathematical,
>>scientific, software engineering, project management, and business
>>issues at an introductory to intermediate level with a minimum of
>>formulas or technical jargon.
>>
>>http://math-blog.com/2009/07/20/complex-algorithm-research-and-develo...
>
>
> Who but an idiot would suggest this is not very hard? :-\
>

I didn't get the point. This spammer collects clicks or what?

VLV

On 21 July, 17:12, Jan Burse <janbu...@fastmail.fm> wrote:
> LudovicoVan schrieb:
>
> > Am I missing something?
>
> Yes,
> Probably you think algorithmic complexity has to do with
> FORTRAN LINPACK efficiency.

I don't: what are you missing?

> But look at the following: Define the necessary structure
> where euclides GCD algorithm works mathematically, you
> end up in some axioms. <snipped irrelevant code example>

As I've said above (you snipped it): OO methodologies can help lower
the complexity of the software structure (to a certain extent): there
is no specific connection to algorithms complexity, though.

> But cutting an OO framework is Art.

Sure, I agree on that, given that it is by far the most
*intrinsically* complex software methodology, as well as the most
remote to the conceptual problem domain (i.e., the most lower level in
the technical sense), ever. In an analogy (not to be taken too
strictly), OO stands to the broad panorama of software methodologies
and techniques as assembler stands to the programming languages.

-LV

On Jul 21, 9:38 am, LudovicoVan <ju...@diegidio.name> wrote:
> On 21 July, 17:12, Jan Burse <janbu...@fastmail.fm> wrote:
>
> > LudovicoVan schrieb:
>
> > > Am I missing something?
>
> > Yes,
> > Probably you think algorithmic complexity has to do with
> > FORTRAN LINPACK efficiency.
>
> I don't: what are you missing?
>
> > But look at the following: Define the necessary structure
> > where euclides GCD algorithm works mathematically, you
> > end up in some axioms. <snipped irrelevant code example>
>
> As I've said above (you snipped it): OO methodologies can help lower
> the complexity of the software structure (to a certain extent): there
> is no specific connection to algorithms complexity, though.
>
> > But cutting an OO framework is Art.
>
> Sure, I agree on that, given that it is by far the most
> *intrinsically* complex software methodology, as well as the most
> remote to the conceptual problem domain (i.e., the most lower level in
> the technical sense), ever. In an analogy (not to be taken too
> strictly), OO stands to the broad panorama of software methodologies
> and techniques as assembler stands to the programming languages.
>
> -LV

Even Matlab has gone OO now.

Hardy

LudovicoVan schrieb:
> is no specific connection to algorithms complexity, though.

I gave you an example how a connection could be established.

Could you elaborate a little bit, why you are so sure that
the classical Aristotelan thinking in predicates and classes,
which OO is resemblance of, does not go into algorithmic
complexity?

Best Regards

On 21 July, 19:50, HardySpicer <gyansor...@gmail.com> wrote:
> On Jul 21, 9:38 am, LudovicoVan <ju...@diegidio.name> wrote:
> > On 21 July, 17:12, Jan Burse <janbu...@fastmail.fm> wrote:

> > > But cutting an OO framework is Art.
>
> > Sure, I agree on that, given that it is by far the most
> > *intrinsically* complex software methodology, as well as the most
> > remote to the conceptual problem domain (i.e., the most lower level in
> > the technical sense), ever. In an analogy (not to be taken too
> > strictly), OO stands to the broad panorama of software methodologies
> > and techniques as assembler stands to the programming languages.
>
> Even Matlab has gone OO now.

Yes, and I have mentioned market and inflation. But don't get me
wrong, that's not even a criticism to Matlab: I have nothing against
OO programming and methodologies, they surely have their strengths and
intelligence, I am only referring to their mis-use/abuse.

In any case, that was a side issue. The point of contention was this
assertion: "object-oriented methods are of limited use in complex
algorithms". Maybe just a little bit "weak", because, as informal as
it is, I would agree, for the reason I have explained before, i.e.
that OO has properly nothing to do with problems of algorithmic
complexity.

-LV

On 21 July, 20:23, Jan Burse <janbu...@fastmail.fm> wrote:
> LudovicoVan schrieb:
>
> > is no specific connection to algorithms complexity, though.
>
> I gave you an example how a connection could be established.

I have seen no connection there: you have given an example of how one
can avoid some trivial code duplication -- so to say. Indeed, you can
use OO to structure your code, and in that there is a kind of
complexity. But, the GCD algorithm per se, with its own complexity,
remains an independent problem. In a technical jargon, you may be
confusing specification (the "what", here an algorithm) with
implementation (the "how", here a program).

> Could you elaborate a little bit, why you are so sure that
> the classical Aristotelan thinking in predicates and classes,
> which OO is resemblance of, does not go into algorithmic
> complexity?

Can you perhaps rephrase the GCD algorithm in terms of "the classical
Aristotelean thinking in predicates and classes" -- in less than 2^w
words, that is? (In the meatime, as a first approximation, I am
thinking "static" vs "dynamic": apples and oranges.)

-LV

LudovicoVan schrieb:
> I have seen no connection there: you have given an example of how one
> can avoid some trivial code duplication -- so to say. Indeed, you can
> use OO to structure your code, and in that there is a kind of
> complexity. But, the GCD algorithm per se, with its own complexity,
> remains an independent problem. In a technical jargon, you may be
> confusing specification (the "what", here an algorithm) with
> implementation (the "how", here a program).

I was assuming in my example that particular algoritms (=HOW)
were given, and results in the abstract can be "lifted" to
results in the concrete. For example some complexity classes
are closed under certain operations. So when concrete div
is polynominal, and abstract gdc is polynominal in certain way
then also concrete gdc is polynominal.

So, isn't the HOW important in ALGORITHMIC complexity?

Maybe we have different understanding of algorithmic complexity.

Bye

BTW: The distinction specification and implementation has nothing
to do with OO, and it is not a technical jargon. It has to do
with requirements engineering. I would like to stay in the
discussion on the implementation level. OO viewed from the
implementation level, the algorithms that happen on the
implementation level, plus mathematical views on it, but not
business views on it.

Jan Burse schrieb:

> with requirements engineering. I would like to stay in the
> discussion on the implementation level. OO viewed from the

BTW: Where would you locate specs in my example. There
were no specs. It was all assumed to be code, when I
shifted to OO.

Jan Burse schrieb:
> Jan Burse schrieb:
>
>> with requirements engineering. I would like to stay in the
>> discussion on the implementation level. OO viewed from the
>
> BTW: Where would you locate specs in my example. There
> were no specs. It was all assumed to be code, when I
> shifted to OO.
>

Anyway LV, you have disqualified yourself, since you
do not seem to know what an algorithm is...

*plonk* thread.

On 21 July, 21:00, LudovicoVan <ju...@diegidio.name> wrote:
> On 21 July, 20:23, Jan Burse <janbu...@fastmail.fm> wrote:
> > LudovicoVan schrieb:
>
> > > is no specific connection to algorithms complexity, though.
>
> > I gave you an example how a connection could be established.
>
> I have seen no connection there: you have given an example of how one
> can avoid some trivial code duplication -- so to say. Indeed, you can
> use OO to structure your code, and in that there is a kind of
> complexity. But, the GCD algorithm per se, with its own complexity,
> remains an independent problem. In a technical jargon, you may be
> confusing specification (the "what", here an algorithm) with
> implementation (the "how", here a program).

The _what_ is the problem (in the micro, the specification), the _how_
is the solution (in the micro, the implementation). This is how
classical software engineering puts it.

> > Could you elaborate a little bit, why you are so sure that
> > the classical Aristotelan thinking in predicates and classes,
> > which OO is resemblance of, does not go into algorithmic
> > complexity?
>
> Can you perhaps rephrase the GCD algorithm in terms of "the classical
> Aristotelean thinking in predicates and classes" -- in less than 2^w
> words, that is? (In the meatime, as a first approximation, I am
> thinking "static" vs "dynamic": apples and oranges.)

Slightly better might be _structure_ vs _function_, although I am
still not satisfied... Any better "approximation"?

To some it up:

OO is all and only about the _how_: OOA/OOD/OOP are so called
technical activities, contrasted to the conceptual analisys.

OO is, to the best of my knowledge, all and only about _structure_,
the structure of the solution (implementation) at the various levels
of abstraction from OOA down to OOP.

OTOH, that point was interesting: I'd love to see an example, if such
a thing exists, of an algorithmic-like thing where the fact that one
implements it in -say- C++ rather than C makes a difference to the
algorithmic complexity. Hmm, I must be missing something... again...

-LV

LudovicoVan <julio@diegidio.name> wrote:

> I'd love to see an example, if such a thing exists, of an
> algorithmic-like thing where the fact that one implements it in
> -say- C++ rather than C makes a difference to the algorithmic
> complexity.

Sure. Let's say you have a class that has a method called decode()
that performs some algorithm which, many layers deep within the
code, calls a function gcd() which performs the Euclidean algorithm
for computing GCD's. Let us suppose the calls to the decode() method,
such as x.decode() for some object x, occur all over your
code base -- hundreds of times. Now suppose you want
to implement optionally replacing the Euclidean algorithm with a
differently-coded algorithm that computes GCD's by using, say, a
Berlekamp-Massey algorithm; something that is very close functionally
but which may have some different qualities that you need to explore.
You need to run this modification on the entire base, without breaking
the existing version.

You don't want to recode your entire base with its hundreds of
calls to decode().

It should be obvious that in an OO situation the way forward is
clear -- you create a child class that links to a different gcd()
function and you have met your requirement. In a non-OO situation,
it's not so clear. Your solution could end up looking like a major
hack, perhaps passing a new parameter through many layers of
code and editing code everywhere, or perhaps resorting to a kluge
like placing a control parameter in a global variable.

You might say "this has nothing to do with algorithms" but I
would contend it hits pretty close to home, for anyone who must
implement/maintain complex algorithms, or complex systems which embed
algorithms.

Steve

On 21 Jul, 23:37, spop...@speedymail.org (Steve Pope) wrote:

> You might say "this has nothing to do with algorithms" but I
> would contend it hits pretty close to home, for anyone who must
> implement/maintain complex algorithms, or complex systems which embed
> algorithms.

It seems somebody confuse 'algorithm complexity' and
'source code complexity'. An FFT runs in O(NlogN) time
regardless of if it is implemented as OO C++ or spaghetti
code assembly language.

Code readability and maintenance is a completely different
question.

The question is if one wants readable, comprehensible source
code that produces sufficiently fast programs, or as fast
programs as possible, which source code no one understand
or dare touch with a red-hot poker.

Rune

Rune Allnor wrote:

> It seems somebody confuse 'algorithm complexity' and
> 'source code complexity'.

Exactly.

Surprisingly many people don't understand the difference between the
conceptual solution of a problem and the implementation of the known
concept. That's the result of the "multiple choice" schooling style.

VLV

Rune Allnor <allnor@tele.ntnu.no> wrote:

>On 21 Jul, 23:37, spop...@speedymail.org (Steve Pope) wrote:

>> You might say "this has nothing to do with algorithms" but I
>> would contend it hits pretty close to home, for anyone who must
>> implement/maintain complex algorithms, or complex systems which embed
>> algorithms.

>It seems somebody confuse 'algorithm complexity' and
>'source code complexity'. An FFT runs in O(NlogN) time
>regardless of if it is implemented as OO C++ or spaghetti
>code assembly language.

>Code readability and maintenance is a completely different
>question.

I agree you're making a valid distinction, however I do
not believe the OP's use of the word "complex" in the
subject line of this thread is in accordance with your
meaning. I believe the OP's meaning was more along
the lines of "complicated".

Steve

LudovicoVan wrote:
> OTOH, that point was interesting: I'd love to see an example, if such
> a thing exists, of an algorithmic-like thing where the fact that one
> implements it in -say- C++ rather than C makes a difference to the
> algorithmic complexity. Hmm, I must be missing something... again...
>
> -LV

Could you elaborate what you mean by algorithmic complexity?

The article talks about the complexity of an algorithm being how
difficult it is for a human to understand it. Then again, algorithmic
complexity can also mean the asymptotic runtime of a given algorithm vs
some properties of the input (and possibly output).

Let us consider the first interpretation. Humans can keep in mind only a
handful of things (say 5) at any given time: just try how many numbers
you can remember from a sequence of the 20 integers your friend lists to
you (only once). Still, with such restricted abilities, humans can solve
extraordinarily hard problems. The reason for this, I claim, is the
ability of humans to abstract. Rather than taking the problem in its
full detail, you surround parts of the problem with black boxes which
solve these sub-problems. The savings is in that you don't need to
specify _how_ that actually is achieved.

On the other hand, I would describe the evolution of programming
languages as "ever enhancing support for forming abstractions". Over
this background, you'll see that OO is not 'just another paradigm' that
stands equally with procedural paradigm and unstructured code. Rather,
it is an essential idea that makes it possible to build abstractions.

Now to the point. Does it make a difference to algorithmic complexity if
you solve a problem in C or C++? Yes! The difference is that C++ offers
you a way to construct those abstractions that model the corresponding
concepts in your mind. This makes the program easier to understand. This
in turn implies that C++ (vs C) has the potential to lower the
algorithmic complexity (if you use it right).

There are two particularly bothering statements in the article linked in
the OP:

"The term C/C++ is used intentionally to reflect the reality that
object-oriented methods are of limited use in complex algorithms,
although the algorithms are often packaged inside an ?object? for easy
integration into applications."

"C++ is object-oriented. It often has larger memory needs than C and can
be slower."

I already gave my disagreement to the first one. To comment the second:

This shows little experience with C++. C++ is not just object-oriented:
it is multi-paradigm. Of the other paradigms the procedural and generic
programming are of most importance. What he probably refers to is the
abstraction penalty that you might get when programming in terms of your
abstractions. What separates good programmers from the rest is that they
can provide _both_ excellent performance and clear abstractions that map
one-to-one with the mind. In C++, this is achieved by mixing procedural,
object-oriented, and generic programming paradigms. For a prime example,
see the Blitz++ library for working with tensors in the same way as you
do on paper, and do it on par, or even more efficiently, than Fortran
does:

http://www.oonumerics.org/blitz/

P.S. We'll see if it pays out to write to such a largely cross-posted
thread.. I couldn't resist this time :)

--
http://kaba.hilvi.org

In comp.dsp Steve Pope <spope33@speedymail.org> wrote:
(snip)
 
> I agree you're making a valid distinction, however I do
> not believe the OP's use of the word "complex" in the
> subject line of this thread is in accordance with your
> meaning. I believe the OP's meaning was more along
> the lines of "complicated".

So we could have a complex (complicated) O(N logN)
complexity complex FFT algorithm?

-- glen

On 21 July, 22:37, spop...@speedymail.org (Steve Pope) wrote:
> LudovicoVan  <ju...@diegidio.name> wrote:
> > I'd love to see an example, if such a thing exists, of an
> > algorithmic-like thing where the fact that one implements it in
> > -say- C++ rather than C makes a difference to the algorithmic
> > complexity.
>
> Let's say you have a class that has a method called decode()
> [...]
> You don't want to recode your entire base with its hundreds of
> calls to decode().

Surely not. If the flexibility of swapping implementation was known at
specification time, we have to keep in mind that inheritance (and
polymorphism) extend the concept of delegate: the class hierarchy you
have in C++ would be a function pointer in C. If that requirement was
not known, then a more or less significant restructuring of the code
would be needed in any case, that it is C++ or that it is C, as there
is no such thing as painlessly extending a class library that was not
thought for extension in the very first place. OO is more manageable
than Structured when the code base has grown significantly, but it is
encapsulation there that is making the difference.

> You might say "this has nothing to do with algorithms" but I
> would contend it hits pretty close to home, for anyone who must
> implement/maintain complex algorithms, or complex systems which embed
> algorithms.

I have said OO has (properly) nothing to do with _algorithmic
complexity_. Algorithms tout court would have been too ambiguous,
although... Quite like you have put it: complex algorithms vs complex
systems. You encounter them in conjunction, yet they are orthogonal
problems.

-LV

glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote in message <h45g2l$fnj$1@naig.caltech.edu>...
>
> So we could have a complex (complicated) O(N logN)
> complexity complex FFT algorithm?
>

LOL.

Bruno

glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote:

>In comp.dsp Steve Pope <spope33@speedymail.org> wrote:

>(snip)

>So we could have a complex (complicated) O(N logN)
>complexity complex FFT algorithm?

Indeed. :)

S.

On 22 Jul, 00:20, spop...@speedymail.org (Steve Pope) wrote:
> Rune Allnor  <all...@tele.ntnu.no> wrote:
>
> >On 21 Jul, 23:37, spop...@speedymail.org (Steve Pope) wrote:
> >> You might say "this has nothing to do with algorithms" but I
> >> would contend it hits pretty close to home, for anyone who must
> >> implement/maintain complex algorithms, or complex systems which embed
> >> algorithms.
> >It seems somebody confuse 'algorithm complexity' and
> >'source code complexity'. An FFT runs in O(NlogN) time
> >regardless of if it is implemented as OO C++ or spaghetti
> >code assembly language.
> >Code readability and maintenance is a completely different
> >question.
>
> I agree you're making a valid distinction, however I do
> not believe the OP's use of the word "complex" in the
> subject line of this thread is in accordance with your
> meaning.  I believe the OP's meaning was more along
> the lines of "complicated".

I have no idea what the OP means, since 'complex algorithm'
is used in the subject line (hinting at O(N) type problems)
while the quoted article mentions 'source code.'

I don't know who confused what; I only know that I became
confused.

Rune

Kaba wrote:

> LudovicoVan wrote:
>
>>OTOH, that point was interesting: I'd love to see an example, if such
>>a thing exists, of an algorithmic-like thing where the fact that one
>>implements it in -say- C++ rather than C makes a difference to the
>>algorithmic complexity. Hmm, I must be missing something... again...
>>
>>-LV
>
>
> Could you elaborate what you mean by algorithmic complexity?
>
> The article talks about the complexity of an algorithm being how
> difficult it is for a human to understand it.

There is a quantitative measure of the complexity of the source code. It
is called "cyclomatic complexity". There is a good article of Jack
Ganssle about it:

http://www.embedded.com/columns/breakpoint/206901032

> Then again, algorithmic
> complexity can also mean the asymptotic runtime of a given algorithm vs
> some properties of the input (and possibly output).

This is a required number of operations; it has nothing to do neither
with the complexity of the algorithm nor with the complexity of the
partucular realization.


> Now to the point. Does it make a difference to algorithmic complexity if
> you solve a problem in C or C++? Yes!

No!
Does it make a difference if you use a chalk, a pen or a pencil ?


> The difference is that C++ offers
> you a way to construct those abstractions that model the corresponding
> concepts in your mind. This makes the program easier to understand. This
> in turn implies that C++ (vs C) has the potential to lower the
> algorithmic complexity (if you use it right).

To implement an algorithm, you have to encode the same operations in the
same order regardless of the coding language. C++ can take care of some
minor technicalities, but nothing more then that.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

On Tue, 21 Jul 2009 21:37:23 +0000, Steve Pope wrote:

> You don't want to recode your entire base with its hundreds of calls to
> decode().
>
> It should be obvious that in an OO situation the way forward is clear --
> you create a child class that links to a different gcd() function and
> you have met your requirement. In a non-OO situation, it's not so
> clear. Your solution could end up looking like a major hack, perhaps
> passing a new parameter through many layers of code and editing code
> everywhere, or perhaps resorting to a kluge like placing a control
> parameter in a global variable.

This sounds like a classic example of "if all you have is a hammer, all
the worlds problems look like nails".

In a C environment (for example) you wouldn't dream of doing anything so
perverse as writing a new class module with a single function overridden,
and figuring out how to make sure that it was used instead of the real
one, every where a "new foo" was called. You'd just replace the file
that contains your gcd() function with one that contains a version
implemneted with the different algorithm and re-compile. Or something
similar using #ifdef, if your gcd() function sits in the same file as a
bunch of other functions that you want to keep using.

The only thing that OO has going for it, over modular functional methods
is inheritance, and that is the most inappropriately used and poorly
taught feature of any of the OO languages, IMO.

Regarding the initial objection that brought up euclid and the numeric
tower: have you ever tried to actually do it that way? It sounds nice in
theory, but the single-dispatch and non-conformant result type
constraints of some of the popular "object oriented" languages make it
impossible.

If you want a language with a real numeric tower in it, try lisp or
scheme... (Both of which can do OO, and neither of which implements
their numeric towers with their object models.)

Cheers,

--
Andrew

Andrew Reilly <andrew-newspost@areilly.bpc-users.org> wrote:

>On Tue, 21 Jul 2009 21:37:23 +0000, Steve Pope wrote:

>> It should be obvious that in an OO situation the way forward is clear --
>> you create a child class that links to a different gcd() function and
>> you have met your requirement. In a non-OO situation, it's not so
>> clear. Your solution could end up looking like a major hack, perhaps
>> passing a new parameter through many layers of code and editing code
>> everywhere, or perhaps resorting to a kluge like placing a control
>> parameter in a global variable.

>This sounds like a classic example of "if all you have is a hammer, all
>the worlds problems look like nails".
>
>In a C environment (for example) you wouldn't dream of doing anything so
>perverse as writing a new class module with a single function overridden,
>and figuring out how to make sure that it was used instead of the real
>one, every where a "new foo" was called. You'd just replace the file
>that contains your gcd() function with one that contains a version
>implemneted with the different algorithm and re-compile.

You did not read my description of the requirement, wherein the
new algorithm is an option, not a replacement.... one needs
to implement this option without removing the existing functionality.

In any case, I think it's a bit of a stretch to not consider the OO
language features useful in a case like this.

Steve

In comp.dsp Vladimir Vassilevsky <nospam@nowhere.com> wrote:
 
(big snip)
 
< To implement an algorithm, you have to encode the same operations in the
< same order regardless of the coding language. C++ can take care of some
< minor technicalities, but nothing more then that.

Sometimes, but not always. I actually had to fix one like
this that someone wrote once:

   while(fgets(s,sizeof(s),stdin) strcat(t,s);

It might have included tests to make sure that there was
enough room in t for s, and also to remove the extra newline.

Even so, it looks nice and simple, but it is O(n**2),
and it is noticeable before n is 1000000 reading
60 character lines.

Even more, you need to include the complexity of memory allocation,
malloc() in C, new in C++, and even temporary arrays that
Fortran will allocate for some array expressions.

If you don't consider the complexity of your fundamental
operations, then you miss the complexity of the implementation.

-- glen

On 21 July, 23:38, Kaba <n...@here.com> wrote:
> LudovicoVan wrote:
> > OTOH, that point was interesting: I'd love to see an example, if such
> > a thing exists, of an algorithmic-like thing where the fact that one
> > implements it in -say- C++ rather than C makes a difference to the
> > algorithmic complexity. Hmm, I must be missing something... again...
>
> Could you elaborate what you mean by algorithmic complexity?

I was/am meaning it as in computer science.

> humans can solve
> extraordinarily hard problems. The reason for this, I claim, is the
> ability of humans to abstract. Rather than taking the problem in its
> full detail, you surround parts of the problem with black boxes which
> solve these sub-problems. The savings is in that you don't need to
> specify _how_ that actually is achieved.

Indeed, and that's why it has nothing to do with OO.

The fact that OO allows "abstraction" is an incorrect myth:
abstraction, as you realise above, stands at the conceptual level; at
implementation level you deal with generalisation, composition, etc.,
not analysis, nor abstraction.

> On the other hand, I would describe the evolution of programming
> languages as "ever enhancing support for forming abstractions". Over
> this background, you'll see that OO is not 'just another paradigm' that
> stands equally with procedural paradigm and unstructured code. Rather,
> it is an essential idea that makes it possible to build abstractions.

The kind of abstraction you find along the range from low to high
level languages, is of another kind than the above: it's a quality of
languages, not a property of the problem domain. C++ is OO but low
level, i.e. near to the machine. Indeed I have argued that OO in
general is at the lowest level as an approach, and the most complex.

> Now to the point. Does it make a difference to algorithmic complexity
> if you solve a problem in C or C++? Yes!

Of course, not, at least when algorithmic complexity means what I'm
taking it to mean. And I would argue C++ can't even help readability,
OO being a lowest level approach, i.e. the most remote from the
problem domain.

> The difference is that C++ offers
> you a way to construct those abstractions that model the corresponding
> concepts in your mind.

No, that's another the myth. Not only OO has not to do with
abstraction, it is as well the most remote approach w.r.t. the problem
domain.

> This
> in turn implies that C++ (vs C) has the potential to lower the
> algorithmic complexity (if you use it right).

No such conclusion if algorithmic complexity means what I'm taking it
too mean...

-LV

It seems to me that the complexity of an algorithm is
is an independent issue from the issue of whether or
not the algorithm should be implemented using OO
style of programming. OO is needed to make the
implementation more general but comes at the
cost of making the implementation more complex.
For example data, compression and the centroid
decomposition of a tree are both complicated algorithms
but it makes much more sense to use OO for the
centroid algorithm because we want it to work for
different tree structures.

Even for algorithms where we don't need OO to make
it more general, OO can be useful in two ways:

   1) There are many variations of the algorithm
         and we would like to compare them and thus
         need to implement each variation.
        In this situation much code is often shared
        and OO can make this sharing easier.
        I say this from experience.

   2) Complex algorithms often use lots of data structures
        and it helps a lot if those data structures have been written
        using OO to make them easier to apply in a general
        setting. Again, this is from experience.

Ralph Boland

Steve Pope wrote:
> LudovicoVan <julio@diegidio.name> wrote:
>
>> I'd love to see an example, if such a thing exists, of an
>> algorithmic-like thing where the fact that one implements it in
>> -say- C++ rather than C makes a difference to the algorithmic
>> complexity.
>
> Sure. Let's say you have a class that has a method called decode()
> that performs some algorithm which, many layers deep within the
> code, calls a function gcd() which performs the Euclidean algorithm
> for computing GCD's. Let us suppose the calls to the decode() method,
> such as x.decode() for some object x, occur all over your
> code base -- hundreds of times. Now suppose you want
> to implement optionally replacing the Euclidean algorithm with a
> differently-coded algorithm that computes GCD's by using, say, a
> Berlekamp-Massey algorithm; something that is very close functionally
> but which may have some different qualities that you need to explore.
> You need to run this modification on the entire base, without breaking
> the existing version.
>
> You don't want to recode your entire base with its hundreds of
> calls to decode().
>
> It should be obvious that in an OO situation the way forward is
> clear -- you create a child class that links to a different gcd()
> function and you have met your requirement. In a non-OO situation,
> it's not so clear. Your solution could end up looking like a major
> hack, perhaps passing a new parameter through many layers of
> code and editing code everywhere, or perhaps resorting to a kluge
> like placing a control parameter in a global variable.
>
> You might say "this has nothing to do with algorithms" but I
> would contend it hits pretty close to home, for anyone who must
> implement/maintain complex algorithms, or complex systems which embed
> algorithms.

It would be much simpler if it had been coded in Forth to begin with.

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

John <jmcgowan79@gmail.com> wrote in message <8afea0cf-6821-4457-9e5e-f7c073cee38e@l35g2000pra.googlegroups.com>...
> The article "Complex Algorithm R&D: Harder Than Many Think" has been
> published on the Math Blog. The article discusses using advanced
> mathematics to solve real world problems, including specific examples
> in video compression and speech recognition. The article is for a
> general audience and may be useful for anyone interested in this
> specialized field. The article discusses the mathematical,
> scientific, software engineering, project management, and business
> issues at an introductory to intermediate level with a minimum of
> formulas or technical jargon.
>
> http://math-blog.com/2009/07/20/complex-algorithm-research-and-development-harder-than-many-think/
>
> Sincerely,
>
> John

Anyone who feels the need to add PhD to their name has issues. The article itself was an irrelevant, rambling, steaming pile.

- Steve
 GCE (O & A), BEng, ACGI

Jerry Avins <jya@ieee.org> wrote in message <XFt9m.48738$rg4.2592@newsfe02.iad>...
>
> It would be much simpler if it had been coded in Forth to begin with.
>
> Jerry
> --
> Engineering is the art of making what you want from things you can get.
> ??????????????????????????????????????????????????????????????????????
This is the only contribution to this thread that I understood:-(

More power to your stacks Jerry

Regards

Dave Robinson

"John" <jmcgowan79@gmail.com> wrote in message
news:8afea0cf-6821-4457-9e5e-f7c073cee38e@l35g2000pra.googlegroups.com...
> The article "Complex Algorithm R&D: Harder Than Many Think" has been
> published on the Math Blog. The article discusses using advanced
> mathematics to solve real world problems, including specific examples
> in video compression and speech recognition. The article is for a
> general audience and may be useful for anyone interested in this
> specialized field. The article discusses the mathematical,
> scientific, software engineering, project management, and business
> issues at an introductory to intermediate level with a minimum of
> formulas or technical jargon.
>
> http://math-blog.com/2009/07/20/complex-algorithm-research-and-development-harder-than-many-think/
>
> Sincerely,
>
> John

"Complex algorithms are already in widespread use in commercial
applications. Prominent examples include the video compression algorithms
that enable BluRay, DVD Video, YouTube, and many other modern digital video
systems. The US DVD Video market is around $25 billion per year (2007).
Although limited, speech recognition such as now frequently encountered in
telephone help and customer service systems is another example. Other
examples include encryption, seismic modeling used in oil and gas
exploration, sophisticated financial models, traffic models, and many
others."


Could somebody please explain to me what possible relationship could exist
between creating video codecs, speech recognition software and traffic
modeling software?

And if he thinks they are "complex algorithms", I daresay he has never done
any games programming or compiler support.

Rune Allnor ha scritto:
> On 21 Jul, 23:37, spop...@speedymail.org (Steve Pope) wrote:
>
>> You might say "this has nothing to do with algorithms" but I
>> would contend it hits pretty close to home, for anyone who must
>> implement/maintain complex algorithms, or complex systems which embed
>> algorithms.
>
> It seems somebody confuse 'algorithm complexity' and
> 'source code complexity'. An FFT runs in O(NlogN) time
> regardless of if it is implemented as OO C++ or spaghetti
> code assembly language.
>
> Code readability and maintenance is a completely different
> question.
>
> The question is if one wants readable, comprehensible source
> code that produces sufficiently fast programs, or as fast
> programs as possible, which source code no one understand
> or dare touch with a red-hot poker.
>
> Rune

Very interesting discussion...
I understand this point of view where there is a distinction between 1
)"How to find a solution" and 2) "How to implement the solution" .
The computational theory give you the tools to solve the point 1)
indipendently from the language used (you need only the universality )
and the point 2) the OOP and other paradigm give you the tools to solve
the point 2) .
In the past I thought the same but following the evolution of OOP also
in C++ I think this not true and that the evolution of OOP is going in
the direction to solve the point 1) .
Using genericity and classes abstraction is possible to write programs
with complexity for examples O(N^2) without knowing the real complexity
of the compiled program and the final complexity can be O(N) or
O(Log(N)) . This is possible becouse using the characteristic of the
classes and the usage of the instanced objects is possible to demand to
the precompiler to find an implementation with low complexity using
classical deductive inference rules.
So you can write programs with complexity O(N^2) but the final
complexity can change depending on objects used in the abstract program
and the precompiler ( translator c++ into c for example ) has the new
function to find the best implementation.
I think this is possible also nowaday with the C++ .

Denis.

On 22 Jul, 01:16, Andrew Reilly <andrew-newsp...@areilly.bpc-
users.org> wrote:

> The only thing that OO has going for it, over modular functional methods
> is inheritance, and that is the most inappropriately used and poorly
> taught feature of any of the OO languages, IMO.

The one factor that really sets C and C++ apart, is that
classes in C++ become types, like float, int and char in C.

This has some interesting consequences, since argument
type matching all of a sudden becomes a universal technique,
and function name clashes can be resolved by the compiler,
not the programmer.

For instance:

/////////////////////////////////////////////
class MyClass{/* */};

double max(const double a, const double b)
{/* */}

int max(const int a, const int b)
{/* */}

MyClass max(const MyClass a, MyClass b)
{/* */}
/////////////////////////////////////////////

All these functions exist in the same program and
be used interchangeably. The compiler analyzes
any call to max() it finds, and selects what version
from the types of the arguments in any partiular
call. And of course, templates are the way forward:

template<typename T>
T max(const T a, const T b){/* */}

With one of these available, the programmer only
has to make his class have a '>' operator defined,
and one can call max() on his class.

In C the situation above would require a dedicated
function with a distinct name for every possible case.

And do note that the only 'classical' OO concept
that is used here, is 'polymorpism.' Not 'inheritance.'
Not 'encapsualization.'

One very intricate problem where these techniques
came in handy, was filter design. The 'classical'
digital filters come in four flavours: Low-Pass (LP),
High-Pass (HP), Band-Pass (BP) and Band-Stop (BS).
The design methods come in two general categories,
IIR and FIR. Each of these categories include several
types of filters (Butterworth, Chebychev, Hann,
Hamming...). Even worse, the FIR filters (but not the
IIRs) can be designed according to impulse response
types 1-4, while the IIRs (but not the FIRs) can be
fine-tuned in certain details to the specification.

So if one wants to make *one* filter design algorithm
that is called like

Filter = ComputeFilterCoefficients('Butterworth','LP',details)

one has three levels of switch constructs that are
orthogonal, and another two conditional layers that
that may or may not be pertinent, depending on the
general design type.

Yes, it is possible to implement this in procedural
languages, but the design techniques available in C++
ensures that the programmer keeps the overview of what
is going on.

Because of the C++ argument type matching in function
calls, it is possible to implement this filter design
program without any switch constructs at all. Everything
is done in terms of the data types of the objects:

- The user specifies an LP filter, so only functions
  that accept arguments of type LPSpec are called
- The user specifies a Butterworth design, so only
  functions that accept arguments of type IIR::ButterDesign
  are called.

Moreover, it is the *compiler*, not the programmer, that
both assembles the execution path *and* ensures that all
this is correct.

Believe me, it's quite a burden that has been lifted
off the programmer's shoulders.

Only after one has got all this in place does inheritance
play a part. When one wants to add another filter type
to the design routine library, one just implements a couple
of virtual functions and recompile.

Absolutely everything is already taken care of. No need
to poke in existing, working code. No risk to forget one
of 8 necessary modifications. No risk of modifying the
wrong spot. No risk of doing the wrong modification.

Rune

On 22 July, 11:25, Rune Allnor <all...@tele.ntnu.no> wrote:

> In C the situation above would require a dedicated
> function with a distinct name for every possible case.

No, it wouldn't.

> And do note that the only 'classical' OO concept
> that is used here, is 'polymorpism.' Not 'inheritance.'
> Not 'encapsualization.'

Apart that there is no polymorphism without inheritance: Formally,
encapsulation is the base concept in OO, inheritance and polymorphism
only come later, in Stroustrup's extended universe.

> Absolutely everything is already taken care of.

Absolutely everything? Why are you testing, then? Why is there a QA?
(How is it that we are constantly doing overtime? How is it that
projects are constantly under-budgeted and over budget? That quality
is generally too low and the software market is in complete chaos? And
most people is "doing OO".)

In particular, OO programming per se cannot ensure the correctness of
a software program: you only have static type checking, which is just
part of the story of correctness, and not even the most amazing.

-LV