There's a digital version for music DSP nuts in the article by Tim Stilson called
"Analyzing the Moog VCF with consideration to digital implementation".
You can find the paper somewhere around
Stilson's homepage
HINT: it's really simple to implement (~10 LOC), you can get my implementation from deja.com by searching comp.dsp.
(1) AC is slower and more complicated than Huffman
Actually good implementations are very evenly matched in terms of speed. The BIG bonus is that in arithmetic coding the statistical model only has to supply the coder the interval of the symbol to be encoded, in Huffman the statistical model is linked to the encoder so it is _much_ harder to make adaptive. Huffman sucks big time when there's one symbol, which has a probability near 1, which I can imagine happening with a good statistical model.
2) the patent issues suck hard (eg JPEG can use AC instead of Huffman as a backend, but nobody bothers because of licensing)
This I won't deny, but only in the US.
(3) the gain is small enough that it's usually not worth the effort
This is only true when you're trying to do a typical compression task with a fixed distribution and then compare AC to Huffman. In dynamic situations AC is clearly superior.
[about statistical models]
You could apply the MDL principle and use the model that gives the best compression when you take into account the space of the model and the space of the model error. This is computationally expensive.
[transforms]
The decorrelating transforms are as much ad hoc as is finding the statistical model. The transforms are actually a form of statistical model. For instance with the DCT it states that the data can be compactly expressed with the basis vectors of the DCT. The optimum linear transformation Principal Component Transform (PCT) is data-dependent. Estimating the best transform is also a statistical modeling task. Using a DCT may work well for audio/video, but it is not a general solution.
LZW is a general purpose adaptive compression algorithm that can achieve the information theoretic maximum compression for a suitable source. It is based on LZ78 by Lempel and Ziv (IEEE trans. on inf. theory in -78) and modified by Welch (IEEE computer, sometime in the 80's)
The basic idea is to keep an indexed dictionary of strings seen so far (initially contains the alphabet) and then encode the index of the longest string that can be found in the dictionary starting from the current position. Then a new string consisting of the found string and the first unknown symbol (ie. not a suffix to the string) is inserted into the dictionary. So it is basically a method of replacing a string with a single symbol which references the dictionary (thus the name dictionary methods for LZ77 and LZ78). There are a number of modifications to this algorithm, for instance freezing the dictionary and flushing it at certain intervals... in practice the strings could be stored in a trie (you read right: a trie, not tree, but trie is a kind of tree).
LZW is old, nowadays people should use arithmetic coding (which is nearly information theoretically optimal in practice). IMO arithmetic coding and statistical modeling is the way to go. Basically you've got the best engine room possible (arithmetic coding) and then the problem is to add the intelligence (statistical modeling). BTW from what I gather arithmetic coding is also patented, but I don't give a fsck since I live in Europe... AC is pretty old, but it is based on an unpublished work by Elias... so finding prior art might be possible.
And that's another comment I'd like to make. Almost every LISP bigot I've heard of talks about how "beautiful" LISP is. My reaction is, So what if it's beautiful? Computer languages are written to be useful, not just beautiful. Is anyone actually developing anything useful in LISP? I think it's pretty obvious that Perl is very useful.
As for LISP successes (they were asked for in an earlier post): Common Lisp had the first standardized object oriented language (CLOS). There are few, if any, OO languages that can even begin to touch the dynamism possible in CLOS (with the meta-object protocol, of course). EMACS anyone ? Garbage collection hmmm... user extensible programs ? ahem. I think it has been very successful, it just took a lot of flak from the failure of AI in the 80's.
The beauty in LISP is that it is really the language that you want it to be. LISP macros are actually code that transforms expressions into other expressions before evaluation or compilation; so in essence you can write a compiler (yes, LISP is usually compiled to native code) for your own language. This means abstraction without the usual overhead. This property has been used for instance to implement Prolog(ish) compilers on top of LISP.
LISP is the second oldest programming language still in use (Fortran is older) and it has been designed to be extensible; for instance, today's usual plugin hacks with DLL's or.so's are as easy as (load "filename"). Lisp has evolved for 40 years and IMO Common Lisp is a very mature language. All this dynamism is not without a cost however. Real CL systems take up a lot of memory, because the environment is almost like an OS. Imagine keeping GCC in memory for every C program you run.
Why do I like it ? Bottom-up programming, self-modifying programs, goto;), function builders, macros, strong typing, closures, extreme multi-paradigm support... actually I can't specify, it's the whole package that rocks.
As I understand it this doesn't break Shannons theorem (and it says so on the page). AFAIK, Shannon's Theorem says that the amount of information sent in a given amount of bits (or in the continuous version combination of bandwidth and time) depends on the quality of the statistical model of the source (and the noise present on the channel).
An event of probability p requires -log2 p bits to encode in it's most efficient form. There's no lower limit to the amount of bits needed to specify a sequence of events provided that you can estimate the next event's probability close to 1 and succeed every time. If you have a completely accurate model, 0 bits are needed. So this might be an improvement on the statistical model of the source. The theory of information is sound; you can't disprove a mathematical theory once it is proven correct and the proof has no mistakes. The headline has a bit of unwarranted sensationalism:)
Agreed, writing x86 asm is horrible. The machine has too few registers. I could use more registers instead of moving temporary results in and out of memory most of the time.
I have to side with Intel on this one. As much as I like the AMD x86's I'd like to see the architecture dead already and replaced by something better suited for modern applications. The x86 is carrying too much bloat. Perhaps a G4 or an alpha would be a good alternative.
One problem is that software vendors haven't written their programs with portability in mind. IMO fair practice in the software business would be that any user upgrading to a new architecture would get the application for that architecture for free as soon as available. This is one service that open source can provide and commercial applications can't. Backward compatibility sucks; closed source software has turned it into a ball and chain for both the CPU manufacturers and the users. Honestly, I think that AMD has a shot at winning this one, but I sincerely hope they do not.
Well, actually current EU legislation protects programs as literary works. The patent system doesn't allow software patents, but the new proposed utility model (a weaker patent), which has a shorter duration and is easier to get, seems to allow software patents (the proposal from -97 didn't, but the newest version removed all clauses on the exclusion of software from protection). AFAIK the utility model only concerns commercial use (unless they change that in the future). Algorithms won't be protected since they are mathematical methods and are not in the scope of the utility model.
You can read some of the EU patent legislation here. Note that this probably not the whole of the legislation because the WTO agreements in favor of the total economic domination of large corporations seem to change the game a bit (look up the TRIPS agreement)...
They only cover commercial use, not research or other non-commercial use. So hobbyist programmers and free software would be safe from patent lawsuits.
The way you can tell which direction a sound is coming from is by which ear hears the sound louder and which hears it first.
Actually you can tell by the way the sound is reflected from you ears, shoulders and travelling through you skull. You don't need to move to know the direction. The HRTF (head related transfer function) varies also according to the horizontal position of the sound source. It's just that the games don't implement it properly.
Now WHY do we need a totally new API? Because it's hip to use the totally outdated gl style syntax?
Perhaps you want to be stuck with C++ indefinitely ? It's better to write a library in C because
C has a binary standard
C++ doesn't
So you cannot interface with C++ from the programming language of you choice, but most programming languages have the ability to interface with C. In C++ you cannot even guarantee (without CORBA/COM or some other component solution) that you can mix classes between compilers. The reason for the "outdated" syntax is to keep the namespace clean. There isn't much difference between GL::Vertex and glVertex. If you write a library in C++ you still should expose the API in plain C (handle = pointer to object).
Personally I use Common Lisp and other esoteric languages (because IMHO they are better) and they can all interface with C (without ugly kludges) but interfacing with C++ would be a pain. If the interfaces were in C++ there would be a language lock-in, which I think we all want to avoid.
The bottom line is this: OO vs. Anti-OO is a holy war, and the crusades will rage on. If you don't like OO, fine. Write C, or Fortran, or Cobol, or assembler for all I care. Object-oriented languages were created for a reason. Some people find advantages in them. And to those people, all other factors held constant, an OS written in C++ would clearly be an improvement.
But nothing would beat a true LispOS;) About the holy war business. It's not actually Anti-OO, it's more about the place OO has gotten because of agressive marketing. Yes, marketing, the last thing that should affect methodologies.
OO vs. mainstream imperative I understand, since OO offers genuine advantages over static imperative languages, but when people say: "OO means better reusability" and don't qualify the basis of comparison, other equally good methodologies are left in the shadow as well. This infuriates a lot of people (myself included) since this makes it hard to expose people to other ways of software development, since they have already learnt the OO gospel and are prejudiced against other methodologies.
Most programmers have large egos and want to believe that the method they know best is the best method for software development. I'd bet that most OO programmers aren't nearly as good structured programmers as they are OO programmers. If you know one methodology well and the other poorly then it's easier to believe that the methodology you know better is the better methodology rather than that you don't know the other methodology well enough.
Same boring OO gospel again... Compared to mainstream imperative programming (C, Pascal, etc.) maybe, just _don't_ overgeneralize. Show me scientific evidence that OO is better in this respect than logic or functional programming, let alone formal ontology-based approaches. This OO hype makes me sick. Yes, it's easy to show that OO is better when you compare C++ to C or Pascal, then again compare C++ to Prolog or Lisp. The alleged superiority of OO is a gross overgeneralization: C++ is better than C therefore OO is better than non-OO.
Before the dark times software methodology decisions were based on rational evaluation, nowadays it seems to be: "Hurry up and jump on the bandwagon". Witness XP, I remember people writing on comp.object that XP needed to be researched further and about two months later they were teaching XP for PHB's and had a few books published.
Computer programming the way almost all do it - imperative programming - is most definitely not mathematics and the parallel with engineering is a good one. Both are essentially science-based but with a heavy artistic component, both benefit from similar development cycles. And both are legitimate patents.
The point being that algorithms in their purest form can be reduced to mathematical descriptions. If you have ever read Dijkstra (IMHO every CS student should be _required_ to read Dijkstra) you should also know that imperative programs can also be mathematically constructed so that they are correct by construction.
Functional languages are used in serious development, the kind that mainstream imperative and OO programming just can't handle. How about Erlang ? Ericsson uses it in phone switches, hardly a trivial academic task. Functional and other exotic languages are everywhere but you just haven't noticed. There may be job offers for people with Java/C++/Perl/OO/UML/CORBA/WAP/XML/Unix/NT in the papers but that is no indication that functional languages aren't used. People that know special languages get more demanding and interesting jobs through different channels than newspaper ads.
As for patents. The problem, IMO, is the duration and that they can also be used (in the US) to stop non-commercial use as well. The new proposed European utility model would still allow hobbyist use (research/non-commercial), even though it would also allow software patents (though not called patents) for a maximum of 10 years. Previously software patents weren't allowed. The way the U.S. is lobbying for software patents makes me sick. The WTO trade agreement includes parts about intellectual property which is clearly out of line with current European legislation. I'm confident that our leaders will ignorantly accept the goals of the WTO to be good and accept the new patent legislation as a part of the WTO agreement. This kind of bundling is insidious. I wish people would stop consuming mind-numbing entertainment and think for a change. Leaders can not make informed decicions unless people inform them on the possible effects of their decisions. You can bet that the heads of corporations are frequently in touch with the goverments making the decision and this is what common people need to do as well.
Yes, he dissed lisp. Typical ignorance of a mainstream programmer (BTW most LISPs are not strictly FPLs). He also seems to believe the OO gospel from Meyer, GOF, the three amigos and many others. Most of the OO "truths" like "OO offers better reusability" can only be understood in the narrow context of mainstream languages. The marketing clauses have been stated so many times that most people accept them as the truth. Using objects (mainstreamly) forces people to think at a coarser level of abstraction in terms of who tells who to do what. This actually works very well, but the marketing has taken it way out of proportion and nowadays this seems be accepted as the only way to do it. For some applications using a different mindset like streams of data transformed by computational nodes might be more appropriate. It actually doesn't matter as long as it is efficient in modeling the domain and easy to implement in a programming language. It should also be noted that the very concept of object is not defined properly.
The very thing he is talking about, basically building abstractions to express the domain, is at the very root of LISP culture and has been for a long time. In the LISP world this is usually referred to as "building the language toward the problem".
This is actually what most OO people are doing. They are implementing classes that are domain abstractions and then expressing the solution in the formalized language of domain concepts they just built. Often they have to resort to patterns, because of the deficiencies of the language. The patterns don't usually have a meaning in the problem domain, but are only formalized hacks to get around a problem in the language. Some of the problems are caused by the dominant message-passing model of OO and implementation in static languages. This is not to say that patterns are bad, on the contrary, they are very important when developing in a language that needs them or when they actually have a meaning in the problem domain.
The LISP approach to this problem is not to bend around the problem, but to build the suitable constructs into the language to express the solution. Knowing the beauty of the language it is sad that it seems to be doomed to remain the language of the future indefinitely. Maybe this is because the people don't see the language from the parens.
And no one uses it because of efficiency concerns, the instability of the language spec and the large bulk of existing C/C++ code. This should be language agnostic ie. written for C (and then interfaced from other languages). Nice try though...
Why? Intel are pushing IA64, which ISN'T compatible. It can pretend, but not by default. AMD, OTOH, are pushing x86-64, which is a superset of IA32. You just plug it in and use it. Which would you bet on?:)
IMO, It's time to leave the old crappy IA32 behind. Basically the instruction set sucks, totally. Backward compatibility wouldn't be such an issue if software companies were doing things right ie. portable software and you get all ports when you buy the software (and new ones, when they appear). But software isn't portable and this is why we are in this situation. IA32 won't die soon and the only thing that will kill it is changes in the way software is made.
Most software should be architecture (and OS) independent with a simple recompilation required for a port. I think that the GNU tools go a long way towards accomplishing this, since they're quite standardized. I wonder what happened to the ideas of portable GUI toolkits, hardware and OS abstraction layers ? At least M$ isn't aware of them... So here's a free software idea: an industrial-strength portable (yes, that includes Windows98/NT) hardware/GUI/OS/net abstraction library, which looks the same from the application programmer's standpoint no matter where you use it (like an OS compability wrapper). There might already be one, but I haven't heard about it...
3: Wavelets are just cool weight-functions on a regular fourier transform. Weight-functions are often used on General Fourier transforms (using Bessel-functions or such as the base) to make the base functions orthogonal. The nice thing with wavelets is that the 8X8 grids seen in low quality JPEG are gone. low quality compression is just a bit blurry, but never blocky. Since we're still using fourier transforms with wavelets, FFT still works, and we get the n * log(n) performance, and hence the performance compared to JPEG will only be lowered by a constant factor. Not even a large one at that.
A few points: 1) A wavelet basis is a set of orthonormal functions that span L2(R) (the inner product space of integrable functions + some other conditions) and are generated from a single 'mother wavelet' by translations and dilatations. The fourier basis also spans L2(R). 2) The 1D discrete wavelet transform can be implemented with a pyramidal algorithm, where each iteration halves the number of processed elements. Each iteration consists of filtering the sequence with a pair of QMF filters. Less than 2n iterations, O(n)/iteration => the complexity is O(n). 3) as a sidenote, maybe you were thinking of the Gabor transform, which is a precursor of the wavelets. 4) Wavelets can be made lossless, basically you just use enough precision so that the errors cancel out during reconstruction and rounding. The transforms used are usually just multiplications with a matrix and the inverse transforms multiplications with its inverse.
That was pretty much about time someone took the wavelets into image compression.
There has already been a lot of research into the subject. The biggest discoveries would probably be the EZW coder (patent status?) and the SPIHT coder (patent pending at least).
JPEG/MPEG/MP3 uses Fourier transform to transform the image/sound data into their spectral components. But this spectral representation of the data does not say anything about the _locality_ of the frequency components. .
Actually there an uncertainty attached to the time-frequency representation. The more accurate the knowledge of the time the less accurate the frequency and vice versa. The traditional time-domain representation is on the other end with absolute knowledge of the time no knowledge of the frequency and the fourier representation on the other with absolute knowledge of the frequency and no knowledge of the time. This similar to the Heisenberg's uncertainty principle in physics. Wavelet-packet-compression tries to minimize this and find the optimum representation for the information.
Another nice thing about wavelet compression is, that wavelets tend to represent discontinuities well, even with hard compression.
Another advantage is the easy handling of edge discontinuities with biorthogonal wavelets. If the transform frames have ends at different levels then even hard quantization won't move them closer together as in DCT/DFT-based compression and consequently there are less blocking artifacts.
Well as far as I know, the DCT is hundreds of times faster than the wavelet transform.
So an algorithm of complexity O(n) (DWT) is hundreds of times slower than an algorithm of complexity O(n log n) (DCT). Try putting a big N there and watch how the operation count of the DCT goes up. The wavelet transform is a lot faster than DCT.
Compare the CPU usage during mp3 compression to the CPU usage during noise reduction and you'll see the mp3 compression infinitely less intensive than the noise reduction.
Maybe it has got something to do with the complexity of the operations, noice reduction does both forward and backward transforms and a lot of logic in between, this is in no way a valid comparison of the efficiency of the different transforms.
Mp3 compression uses a DCT plus FFT. When they switch to wavelet based compression you can forget about making movies in software.
The MPEG-2 audio layer 3 uses a polyphase filter to do subband decomposition into 32 subbands. Then it does a MDCT (multiply with window function then DCT) on those subbands and then uses a psychoacoustic model to quantize and huffman-code the transformed subbands. The MDCT's overlap to get rid of edge discontinuities (in image compression these are called blocking artifacts) and aliasing. Actually a wavelet coder could be a lot more efficient than a DCT coder, because of the lower algorithmic complexity...
1. Is the 2:1 5/3 'mother wavelet' truly lossless for any and all inputs?
It can be, for instance there's the S+P transform, which is lossless. The compression ratios aren't that much better than with conventional lossless image compression methods.
2. What kind of 'average' compression can we expect? One poster already mentioned that the example had a simple gradient as a background which would certainly compress well.
This is totally data dependent. For instance you can't losslessly compress white noise using any known method. For lossless image compression you'd probably see something like 1.5:1 - 3.5:1 on the average depending on the characteristics of the images.
3. How CPU intensive is it to decode these things? Will MJPEG2000 (or whatever) practically require a hardware decoder for DVD-quality playback?
It depends, I suppose the coding, where they are looking for the best mother wavelet, is the most time consuming. The decoding is probably done in O(n), since the wavelet-transform is O(n). For comparison the DCT in the original JPEG was O(n log n) so the complexity grew as bigger blocks were processed, which is not the case for the wavelet transform. I can't comment more as I haven't seen the spec either.
Sounds like a great way to write non-maintainable code to me. I think I'll pass on this one.
Ever heard of RefactorMercilessly and DoTheSimplestThi ngThatCouldPossiblyWork ? These two together should lead to maintainable code, because XP states that anything that isn't written well should be improved on immediately and the unit testing ensures that the changes are correct. This methodology is probably best suited for development of smallish apps in dynamic languages like Lisp and Smalltalk, where the cost of change is small. Interesting, but not as extreme as the name leads you to believe.
Personally I like the ideas. For some reason big processes like the RUP seem to get in the way of concentrating on the task. Something small, elegant and adaptive probably works better, IMO. At least for small groups of specialists (like games development, etc.). I wonder if there's any methodologist working on processes for Open Source development over the net ? IMO there's a serious need for research in this area...
Re:ML is even better (Was:Why is LISP superior?)
on
RMS The Coder
·
· Score: 1
Can you think of a reason you would want macros when you have real polymorphism and functors?
To write programs that write programs that write programs ? Seriously, powerful macros can encapsulate complex operations to a simpler form, which is easy to use and still remains efficient.
Re:Why is LISP superior?
on
RMS The Coder
·
· Score: 1
LISP does stupid stuff for you - for example, you don't have to keep track of garbage, as you do with C. Perl doesn't garbage collect either (AFAIK), but it does at least have automatic memory allocation.
This is not an improvement on most languages. Most modern...
I wouldn't call it an improvement on other languages since AFAIK Lisp had it first. It's always been the forerunner in language features... BTW the language just turned 40 this year...
Slashdot Mirror
There's a digital version for music DSP nuts in the article by Tim Stilson called "Analyzing the Moog VCF with consideration to digital implementation". You can find the paper somewhere around Stilson's homepage HINT: it's really simple to implement (~10 LOC), you can get my implementation from deja.com by searching comp.dsp.
And you can blame most of it on Rebirth.
(1) AC is slower and more complicated than Huffman
Actually good implementations are very evenly matched in terms of speed. The BIG bonus is that in arithmetic coding the statistical model only has to supply the coder the interval of the symbol to be encoded, in Huffman the statistical model is linked to the encoder so it is _much_ harder to make adaptive. Huffman sucks big time when there's one symbol, which has a probability near 1, which I can imagine happening with a good statistical model.
2) the patent issues suck hard (eg JPEG can use AC instead of Huffman as a backend, but nobody bothers because of licensing)
This I won't deny, but only in the US.
(3) the gain is small enough that it's usually not worth the effort
This is only true when you're trying to do a typical compression task with a fixed distribution and then compare AC to Huffman. In dynamic situations AC is clearly superior.
[about statistical models]
You could apply the MDL principle and use the model that gives the best compression when you take into account the space of the model and the space of the model error. This is computationally expensive.
[transforms]
The decorrelating transforms are as much ad hoc as is finding the statistical model. The transforms are actually a form of statistical model. For instance with the DCT it states that the data can be compactly expressed with the basis vectors of the DCT. The optimum linear transformation Principal Component Transform (PCT) is data-dependent. Estimating the best transform is also a statistical modeling task. Using a DCT may work well for audio/video, but it is not a general solution.
LZW is a general purpose adaptive compression algorithm that can achieve the information theoretic maximum compression for a suitable source. It is based on LZ78 by Lempel and Ziv (IEEE trans. on inf. theory in -78) and modified by Welch (IEEE computer, sometime in the 80's)
The basic idea is to keep an indexed dictionary of strings seen so far (initially contains the alphabet) and then encode the index of the longest string that can be found in the dictionary starting from the current position. Then a new string consisting of the found string and the first unknown symbol (ie. not a suffix to the string) is inserted into the dictionary. So it is basically a method of replacing a string with a single symbol which references the dictionary (thus the name dictionary methods for LZ77 and LZ78). There are a number of modifications to this algorithm, for instance freezing the dictionary and flushing it at certain intervals... in practice the strings could be stored in a trie (you read right: a trie, not tree, but trie is a kind of tree).
LZW is old, nowadays people should use arithmetic coding (which is nearly information theoretically optimal in practice). IMO arithmetic coding and statistical modeling is the way to go. Basically you've got the best engine room possible (arithmetic coding) and then the problem is to add the intelligence (statistical modeling). BTW from what I gather arithmetic coding is also patented, but I don't give a fsck since I live in Europe... AC is pretty old, but it is based on an unpublished work by Elias... so finding prior art might be possible.
And that's another comment I'd like to make. Almost every LISP bigot I've heard of talks about how "beautiful" LISP is. My reaction is, So what if it's beautiful? Computer languages are written to be useful, not just beautiful. Is anyone actually developing anything useful in LISP? I think it's pretty obvious that Perl is very useful.
Let me first quote RMS:
Why isn't it used more ? Read Richard P. Gabriel's article"LISP: Good News, Bad News, How to Win Big" for some of the reasons.As for LISP successes (they were asked for in an earlier post): Common Lisp had the first standardized object oriented language (CLOS). There are few, if any, OO languages that can even begin to touch the dynamism possible in CLOS (with the meta-object protocol, of course). EMACS anyone ? Garbage collection hmmm... user extensible programs ? ahem. I think it has been very successful, it just took a lot of flak from the failure of AI in the 80's.
The beauty in LISP is that it is really the language that you want it to be. LISP macros are actually code that transforms expressions into other expressions before evaluation or compilation; so in essence you can write a compiler (yes, LISP is usually compiled to native code) for your own language. This means abstraction without the usual overhead. This property has been used for instance to implement Prolog(ish) compilers on top of LISP.
LISP is the second oldest programming language still in use (Fortran is older) and it has been designed to be extensible; for instance, today's usual plugin hacks with DLL's or .so's are as easy as (load "filename"). Lisp has evolved for 40 years and IMO Common Lisp is a very mature language. All this dynamism is not without a cost however. Real CL systems take up a lot of memory, because the environment is almost like an OS. Imagine keeping GCC in memory for every C program you run.
Why do I like it ? Bottom-up programming, self-modifying programs, goto ;), function builders, macros, strong typing, closures, extreme multi-paradigm support... actually I can't specify, it's the whole package that rocks.
As I understand it this doesn't break Shannons theorem (and it says so on the page). AFAIK, Shannon's Theorem says that the amount of information sent in a given amount of bits (or in the continuous version combination of bandwidth and time) depends on the quality of the statistical model of the source (and the noise present on the channel).
An event of probability p requires -log2 p bits to encode in it's most efficient form. There's no lower limit to the amount of bits needed to specify a sequence of events provided that you can estimate the next event's probability close to 1 and succeed every time. If you have a completely accurate model, 0 bits are needed. So this might be an improvement on the statistical model of the source. The theory of information is sound; you can't disprove a mathematical theory once it is proven correct and the proof has no mistakes. The headline has a bit of unwarranted sensationalism :)
Agreed, writing x86 asm is horrible. The machine has too few registers. I could use more registers instead of moving temporary results in and out of memory most of the time.
I have to side with Intel on this one. As much as I like the AMD x86's I'd like to see the architecture dead already and replaced by something better suited for modern applications. The x86 is carrying too much bloat. Perhaps a G4 or an alpha would be a good alternative.
One problem is that software vendors haven't written their programs with portability in mind. IMO fair practice in the software business would be that any user upgrading to a new architecture would get the application for that architecture for free as soon as available. This is one service that open source can provide and commercial applications can't. Backward compatibility sucks; closed source software has turned it into a ball and chain for both the CPU manufacturers and the users. Honestly, I think that AMD has a shot at winning this one, but I sincerely hope they do not.
Well, actually current EU legislation protects programs as literary works. The patent system doesn't allow software patents, but the new proposed utility model (a weaker patent), which has a shorter duration and is easier to get, seems to allow software patents (the proposal from -97 didn't, but the newest version removed all clauses on the exclusion of software from protection). AFAIK the utility model only concerns commercial use (unless they change that in the future). Algorithms won't be protected since they are mathematical methods and are not in the scope of the utility model.
You can read some of the EU patent legislation here. Note that this probably not the whole of the legislation because the WTO agreements in favor of the total economic domination of large corporations seem to change the game a bit (look up the TRIPS agreement)...
They only cover commercial use, not research or other non-commercial use. So hobbyist programmers and free software would be safe from patent lawsuits.
The way you can tell which direction a sound is coming from is by which ear hears the sound louder and which hears it first.
Actually you can tell by the way the sound is reflected from you ears, shoulders and travelling through you skull. You don't need to move to know the direction. The HRTF (head related transfer function) varies also according to the horizontal position of the sound source. It's just that the games don't implement it properly.
Now WHY do we need a totally new API? Because it's hip to use the totally outdated gl style syntax?
Perhaps you want to be stuck with C++ indefinitely ? It's better to write a library in C because
- C has a binary standard
- C++ doesn't
So you cannot interface with C++ from the programming language of you choice, but most programming languages have the ability to interface with C. In C++ you cannot even guarantee (without CORBA/COM or some other component solution) that you can mix classes between compilers. The reason for the "outdated" syntax is to keep the namespace clean. There isn't much difference between GL::Vertex and glVertex. If you write a library in C++ you still should expose the API in plain C (handle = pointer to object).Personally I use Common Lisp and other esoteric languages (because IMHO they are better) and they can all interface with C (without ugly kludges) but interfacing with C++ would be a pain. If the interfaces were in C++ there would be a language lock-in, which I think we all want to avoid.
The bottom line is this: OO vs. Anti-OO is a holy war, and the crusades will rage on. If you don't like OO, fine. Write C, or Fortran, or Cobol, or assembler for all I care. Object-oriented languages were created for a reason. Some people find advantages in them. And to those people, all other factors held constant, an OS written in C++ would clearly be an improvement.
But nothing would beat a true LispOS ;) About the holy war business. It's not actually Anti-OO, it's more about the place OO has gotten because of agressive marketing. Yes, marketing, the last thing that should affect methodologies.
OO vs. mainstream imperative I understand, since OO offers genuine advantages over static imperative languages, but when people say: "OO means better reusability" and don't qualify the basis of comparison, other equally good methodologies are left in the shadow as well. This infuriates a lot of people (myself included) since this makes it hard to expose people to other ways of software development, since they have already learnt the OO gospel and are prejudiced against other methodologies.
Most programmers have large egos and want to believe that the method they know best is the best method for software development. I'd bet that most OO programmers aren't nearly as good structured programmers as they are OO programmers. If you know one methodology well and the other poorly then it's easier to believe that the methodology you know better is the better methodology rather than that you don't know the other methodology well enough.
OO code is just so more maintainable.
Same boring OO gospel again... Compared to mainstream imperative programming (C, Pascal, etc.) maybe, just _don't_ overgeneralize. Show me scientific evidence that OO is better in this respect than logic or functional programming, let alone formal ontology-based approaches. This OO hype makes me sick. Yes, it's easy to show that OO is better when you compare C++ to C or Pascal, then again compare C++ to Prolog or Lisp. The alleged superiority of OO is a gross overgeneralization: C++ is better than C therefore OO is better than non-OO.
Before the dark times software methodology decisions were based on rational evaluation, nowadays it seems to be: "Hurry up and jump on the bandwagon". Witness XP, I remember people writing on comp.object that XP needed to be researched further and about two months later they were teaching XP for PHB's and had a few books published.
Computer programming the way almost all do it - imperative programming - is most definitely not mathematics and the parallel with engineering is a good one. Both are essentially science-based but with a heavy artistic component, both benefit from similar development cycles. And both are legitimate patents.
The point being that algorithms in their purest form can be reduced to mathematical descriptions. If you have ever read Dijkstra (IMHO every CS student should be _required_ to read Dijkstra) you should also know that imperative programs can also be mathematically constructed so that they are correct by construction.
Functional languages are used in serious development, the kind that mainstream imperative and OO programming just can't handle. How about Erlang ? Ericsson uses it in phone switches, hardly a trivial academic task. Functional and other exotic languages are everywhere but you just haven't noticed. There may be job offers for people with Java/C++/Perl/OO/UML/CORBA/WAP/XML/Unix/NT in the papers but that is no indication that functional languages aren't used. People that know special languages get more demanding and interesting jobs through different channels than newspaper ads.
As for patents. The problem, IMO, is the duration and that they can also be used (in the US) to stop non-commercial use as well. The new proposed European utility model would still allow hobbyist use (research/non-commercial), even though it would also allow software patents (though not called patents) for a maximum of 10 years. Previously software patents weren't allowed. The way the U.S. is lobbying for software patents makes me sick. The WTO trade agreement includes parts about intellectual property which is clearly out of line with current European legislation. I'm confident that our leaders will ignorantly accept the goals of the WTO to be good and accept the new patent legislation as a part of the WTO agreement. This kind of bundling is insidious. I wish people would stop consuming mind-numbing entertainment and think for a change. Leaders can not make informed decicions unless people inform them on the possible effects of their decisions. You can bet that the heads of corporations are frequently in touch with the goverments making the decision and this is what common people need to do as well.
Man can always beat the machine because man can use the machine but not viceversa.
Yes, he dissed lisp. Typical ignorance of a mainstream programmer (BTW most LISPs are not strictly FPLs). He also seems to believe the OO gospel from Meyer, GOF, the three amigos and many others. Most of the OO "truths" like "OO offers better reusability" can only be understood in the narrow context of mainstream languages. The marketing clauses have been stated so many times that most people accept them as the truth. Using objects (mainstreamly) forces people to think at a coarser level of abstraction in terms of who tells who to do what. This actually works very well, but the marketing has taken it way out of proportion and nowadays this seems be accepted as the only way to do it. For some applications using a different mindset like streams of data transformed by computational nodes might be more appropriate. It actually doesn't matter as long as it is efficient in modeling the domain and easy to implement in a programming language. It should also be noted that the very concept of object is not defined properly.
The very thing he is talking about, basically building abstractions to express the domain, is at the very root of LISP culture and has been for a long time. In the LISP world this is usually referred to as "building the language toward the problem".
This is actually what most OO people are doing. They are implementing classes that are domain abstractions and then expressing the solution in the formalized language of domain concepts they just built. Often they have to resort to patterns, because of the deficiencies of the language. The patterns don't usually have a meaning in the problem domain, but are only formalized hacks to get around a problem in the language. Some of the problems are caused by the dominant message-passing model of OO and implementation in static languages. This is not to say that patterns are bad, on the contrary, they are very important when developing in a language that needs them or when they actually have a meaning in the problem domain.
The LISP approach to this problem is not to bend around the problem, but to build the suitable constructs into the language to express the solution. Knowing the beauty of the language it is sad that it seems to be doomed to remain the language of the future indefinitely. Maybe this is because the people don't see the language from the parens.
It's called "Java". ;-p
And no one uses it because of efficiency concerns, the instability of the language spec and the large bulk of existing C/C++ code. This should be language agnostic ie. written for C (and then interfaced from other languages). Nice try though...
Why? Intel are pushing IA64, which ISN'T compatible. It can pretend, but not by default. AMD, OTOH, are pushing x86-64, which is a superset of IA32. You just plug it in and use it. :)
Which would you bet on?
IMO, It's time to leave the old crappy IA32 behind. Basically the instruction set sucks, totally. Backward compatibility wouldn't be such an issue if software companies were doing things right ie. portable software and you get all ports when you buy the software (and new ones, when they appear). But software isn't portable and this is why we are in this situation. IA32 won't die soon and the only thing that will kill it is changes in the way software is made.
Most software should be architecture (and OS) independent with a simple recompilation required for a port. I think that the GNU tools go a long way towards accomplishing this, since they're quite standardized. I wonder what happened to the ideas of portable GUI toolkits, hardware and OS abstraction layers ? At least M$ isn't aware of them... So here's a free software idea: an industrial-strength portable (yes, that includes Windows98/NT) hardware/GUI/OS/net abstraction library, which looks the same from the application programmer's standpoint no matter where you use it (like an OS compability wrapper). There might already be one, but I haven't heard about it...
A few points:
1) A wavelet basis is a set of orthonormal functions that span L2(R) (the inner product space of integrable functions + some other conditions) and are generated from a single 'mother wavelet' by translations and dilatations. The fourier basis also spans L2(R).
2) The 1D discrete wavelet transform can be implemented with a pyramidal algorithm, where each iteration halves the number of processed elements. Each iteration consists of filtering the sequence with a pair of QMF filters. Less than 2n iterations, O(n)/iteration => the complexity is O(n).
3) as a sidenote, maybe you were thinking of the Gabor transform, which is a precursor of the wavelets.
4) Wavelets can be made lossless, basically you just use enough precision so that the errors cancel out during reconstruction and rounding. The transforms used are usually just multiplications with a matrix and the inverse transforms multiplications with its inverse.
There has already been a lot of research into the subject. The biggest discoveries would probably be the EZW coder (patent status?) and the SPIHT coder (patent pending at least).
Actually there an uncertainty attached to the time-frequency representation. The more accurate the knowledge of the time the less accurate the frequency and vice versa. The traditional time-domain representation is on the other end with absolute knowledge of the time no knowledge of the frequency and the fourier representation on the other with absolute knowledge of the frequency and no knowledge of the time. This similar to the Heisenberg's uncertainty principle in physics. Wavelet-packet-compression tries to minimize this and find the optimum representation for the information.
Another advantage is the easy handling of edge discontinuities with biorthogonal wavelets. If the transform frames have ends at different levels then even hard quantization won't move them closer together as in DCT/DFT-based compression and consequently there are less blocking artifacts.
So an algorithm of complexity O(n) (DWT) is hundreds of times slower than an algorithm of complexity O(n log n) (DCT). Try putting a big N there and watch how the operation count of the DCT goes up. The wavelet transform is a lot faster than DCT.
Maybe it has got something to do with the complexity of the operations, noice reduction does both forward and backward transforms and a lot of logic in between, this is in no way a valid comparison of the efficiency of the different transforms.
The MPEG-2 audio layer 3 uses a polyphase filter to do subband decomposition into 32 subbands. Then it does a MDCT (multiply with window function then DCT) on those subbands and then uses a psychoacoustic model to quantize and huffman-code the transformed subbands. The MDCT's overlap to get rid of edge discontinuities (in image compression these are called blocking artifacts) and aliasing. Actually a wavelet coder could be a lot more efficient than a DCT coder, because of the lower algorithmic complexity...
It can be, for instance there's the S+P transform, which is lossless. The compression ratios aren't that much better than with conventional lossless image compression methods.
This is totally data dependent. For instance you can't losslessly compress white noise using any known method. For lossless image compression you'd probably see something like 1.5:1 - 3.5:1 on the average depending on the characteristics of the images.
It depends, I suppose the coding, where they are looking for the best mother wavelet, is the most time consuming. The decoding is probably done in O(n), since the wavelet-transform is O(n). For comparison the DCT in the original JPEG was O(n log n) so the complexity grew as bigger blocks were processed, which is not the case for the wavelet transform. I can't comment more as I haven't seen the spec either.
Ever heard of RefactorMercilessly and DoTheSimplestThi ngThatCouldPossiblyWork ? These two together should lead to maintainable code, because XP states that anything that isn't written well should be improved on immediately and the unit testing ensures that the changes are correct. This methodology is probably best suited for development of smallish apps in dynamic languages like Lisp and Smalltalk, where the cost of change is small. Interesting, but not as extreme as the name leads you to believe.
Personally I like the ideas. For some reason big processes like the RUP seem to get in the way of concentrating on the task. Something small, elegant and adaptive probably works better, IMO. At least for small groups of specialists (like games development, etc.). I wonder if there's any methodologist working on processes for Open Source development over the net ? IMO there's a serious need for research in this area...
Can you think of a reason you would want macros when you have real polymorphism and functors?
To write programs that write programs that write programs ? Seriously, powerful macros can encapsulate complex operations to a simpler form, which is easy to use and still remains efficient.
I wouldn't call it an improvement on other languages since AFAIK Lisp had it first. It's always been the forerunner in language features... BTW the language just turned 40 this year...