Hi, Does anyone know of working and tested code (C/C++/pseudo/...) for doing a fast 1-D DCT ? I know about the Numerical Recipes code, but that has a rather restrictive license... I also have DCT and IDCT working already using the straight implementation from the formulas, but I'd be interested in fast versions (like there exist for FFT for powers of 2). Thanks in advance! Koen
Fast 1-D DCT algorithms
Started by ●March 11, 2005
Reply by ●March 11, 20052005-03-11
"Koen" <no@ssppaamm.com> writes:> Hi, > > Does anyone know of working and tested code (C/C++/pseudo/...) for doing a > fast 1-D DCT ? > I know about the Numerical Recipes code, but that has a rather restrictive > license... > I also have DCT and IDCT working already using the straight implementation > from the formulas, but I'd be interested in fast versions (like there exist > for FFT for powers of 2). > Thanks in advance!http://home.earthlink.net/~yatescr/fftk.c Have at it, and good luck. By the way, when I implemented this in 1989, my computer was a 286 PC AT without the floating-point chip. A 1024-point FFT took over a minute. When I bought my 287 chip, the time went down to 10 seconds - I was elated! -- Randy Yates Sony Ericsson Mobile Communications Research Triangle Park, NC, USA randy.yates@sonyericsson.com, 919-472-1124
Reply by ●March 11, 20052005-03-11
Our FFTW (www.fftw.org) has fast DCTs (types I-IV) for all n (not just powers of 2). There are also a bunch of other free libraries that supply DCTs (e.g. FFTPACK, Ooura's code, etc.) Regards, Steven G. Johnson
Reply by ●March 11, 20052005-03-11
(That's pretty slow! Cooley and Tukey's 1965 implementation could do a 2048-point FFT in 1.2 seconds on an IBM 7095. See http://www.ph.utexas.edu/~itiq/chiu/cooley/p301.jpg) (Note that the OP was asking for a DCT code, not a plain FFT.)
Reply by ●March 11, 20052005-03-11
stevenj@alum.mit.edu writes:> (That's pretty slow! Cooley and Tukey's 1965 implementation could do a > 2048-point FFT in 1.2 seconds on an IBM 7095. See > http://www.ph.utexas.edu/~itiq/chiu/cooley/p301.jpg)Using double precision floating-point? I couldn't tell from the book scan.> (Note that the OP was asking for a DCT code, not a plain FFT.)Doh! -- Randy Yates Sony Ericsson Mobile Communications Research Triangle Park, NC, USA randy.yates@sonyericsson.com, 919-472-1124
Reply by ●March 11, 20052005-03-11
Randy Yates wrote: ...> By the way, when I implemented this in 1989, my computer was > a 286 PC AT without the floating-point chip. A 1024-point FFT > took over a minute. When I bought my 287 chip, the time went > down to 10 seconds - I was elated!Ah, Randy! Those were the days! Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●March 11, 20052005-03-11
The IBM 7095 had both 36-bit single precision and 72-bit double precision floating-point arithmetic. The C & T paper doesn't say which one they used, but I'm guessing that they used single precision on the principle that they would have bragged if they had used double.
Reply by ●March 11, 20052005-03-11
stevenj@alum.mit.edu writes:> The IBM 7095 had both 36-bit single precision and 72-bit double > precision floating-point arithmetic. The C & T paper doesn't say which > one they used, but I'm guessing that they used single precision on the > principle that they would have bragged if they had used double.Hmm. Still, I think 24 years later we would have been doing better. Maybe I'm mis-remembering (maybe it wasn't 1024 points). It's only been 17 freakin' years (yikes!). Or did I do something wrong? Note that my computation time includes computing the twiddle factors. -- Randy Yates Sony Ericsson Mobile Communications Research Triangle Park, NC, USA randy.yates@sonyericsson.com, 919-472-1124
Reply by ●March 11, 20052005-03-11
"Koen" <no@ssppaamm.com> wrote in message news:d0rrt4$19i$1@gaudi2.UGent.be...> Hi, > > Does anyone know of working and tested code (C/C++/pseudo/...) for doing a > fast 1-D DCT ?<snip> I don't know of any "working and tested" pseudo-code for _anything_! Sometimes it sure would be nice to have a pseudo-code compiler! :-) To Koen, sorry I don't have an answer for you. -Jon
Reply by ●March 11, 20052005-03-11
stevenj@alum.mit.edu wrote:> The IBM 7095 had both 36-bit single precision and 72-bit double > precision floating-point arithmetic. The C & T paper doesn't say which > one they used, but I'm guessing that they used single precision on the > principle that they would have bragged if they had used double. >36 bits in binary, and not 32 bits in hexadecimal, had just enough precision that the need for double precision was much less common. The folks on 48 bit machines had trouble understanding why one used double precision and the folks on 60 bit machines considered double precision an obscure form of showing off that was totally unrelated to the real world. The 7090 was a 3 index version of the later 7094 which had 7 index registers. (Is the 9095 for real of just a typo?) 360 model numbers often ended in 5 like 360/65 which was a popular model. 360/75 was hardwired and faster and 360/85 was an early example of the use of memory caches.
