Faster-Than-Fast Fourier Transform 271
First time accepted submitter CanEHdian writes "MIT news reports on research done resulting in a Faster-than-fast Fourier Transform algorithm. 'At the Association for Computing Machinery's Symposium on Discrete Algorithms (SODA) this week, a group of MIT researchers will present a new algorithm that, in a large range of practically important cases, improves on the fast Fourier transform. Under some circumstances, the improvement can be dramatic — a tenfold increase in speed. The new algorithm could be particularly useful for image compression, enabling, say, smartphones to wirelessly transmit large video files without draining their batteries or consuming their monthly bandwidth allotments.'"
transmit large video files (Score:2, Insightful)
In before _____.
Key phrase:
"smartphones to wirelessly transmit large video files without ... consuming their monthly bandwidth allotments."
Everyone see the connection to the Copyright Mayhem this week?
Bueller?
Re:Can it be done effectivly without an FPU? (Score:5, Insightful)
DSP with Arduino
What is wrong with this picture?
Processors used in Arduino (Atmel 8-bit AVR series) are minimal, general-purpose microcontrollers, a replacement for earlier PIC microcontrollers. Using them for DSP is only slightly less stupid than building DSP boards entirely out of individual discrete transistors. There is A WHOLE FUCKING CATEGORY OF IC dedicated to DSP, plenty of microcontroller-style yet high-performance SoC suitable for DSP, and FPGA with DSP-specific blocks.
But noooo, ignorant people such as yourself, would rather recommend the most un-DSP-ish device in the world just because it comes bundled with Java-based IDE that runs on your beloved wiiiiiiiiindows and has the ugliest editor ever written since xedit.
Re:Potentially huge digital A/V benefits (Score:5, Insightful)
Video encoding doesn't scale well to multiple cores either,
Welp, that is patently false. Video encoding is embarassingly parallel in any case where video has keyframes and the video is sufficiently long to hand a roughly equal number of chunks of video (keyframe to keyframe) to each core.
Comment removed (Score:5, Insightful)
Re:Can it be done effectivly without an FPU? (Score:5, Insightful)
Slashdot could really use a +1 Insightful but Unnecessarily Dickish mod.
Re:Can it be done effectivly without an FPU? (Score:4, Insightful)
While I too am sick of seeing dinky little Arduino projects, there are plenty of good reasons to be doing FFT on low power micros.
For example, the company I work for designs battery powered wireless sensors: They have to be compact, consume minimal power and have minimal components for manufacture. We've got a single ATMega processor that sits between a sensor and a radio, doing, among other things, FFT and other 'DSP' functions to compress the data before we spend our precious milliamps transmitting it.
It really is the cheapeast, lowest power way to get the job done, sometimes a hardware DSP is overkill.
Re:Security (Score:5, Insightful)
One of the compelling mathematical insights of Fourier's mathematics is that convolution is a multiplication in a complementary space (spectrum vs frequency). Along with the insight that multiplication in radix space is addition in logarithm space, these completely transformed (pun intended) the human understanding of space and the numbers with which we describe it.