Slashdot Mirror
Faster-Than-Fast Fourier Transform
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.'"
It doesn't improve the regular FFT but only sparse variants. Image or Audio compression nearly always uses the regular non-sparse FFT.
Jan
So the cat gets transformed even faster.
(apologies to XKCD)
Twitter supports and protects racists - by smearing their critics with the "Hate Speech" label.
Lossy compression such as MP3, AAC, and according to TFS also video compression, are all fundamentally based on FFT (fast fourier transforms). Depending on how well this new specific method works, we could see decreases in the time it takes to encode all this stuff. Which can be quite a long time... have you ever tried to do a 2-pass MPEG 4 conversion on a feature-length digital video? Video encoding doesn't scale well to multiple cores either, so nowadays when performance increases coming mostly from adding more cores... video encoding hasn't been getting faster at the same pace it used to. I'm thinking this new FFT algorithm could make a big difference in encoding speeds.
Additionally, I know lots of audio (and I'm assuming video) effects, DSPs of the kind you find in Adobe Audition, Audacity, et al., rely on FFTs. Computing such effects could get a lot faster. With increases in both the speed of adding effects, and compression afterwards, we might be seeing a significant speedup in the overall digital audio/video-editing process.
Nope. FFTs are used in many fields, but cryptography is not one of them. Not since the old analog radio scramblers of decades past.
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.
Contrary to the popular belief, there indeed is no God.
I'm sure I'm not the only person who completely understands what a FFT does but simply can't get his head around the actual implementations details. I simply don't get how a signal of many mixed frequencies which essentially means the amplitude is moving all over the place can travel through some equations and a neat list of the fundamental and harmonics can pop out. Its mathematical magic to me. Wish I could "get" it. But I guess I'll just have to settle for using it.
While I do argue with your point, there are a ton of devices that would benefit from it. Why do you think the implementations of FFT for 8/16-bit microcontrollers such as the 8051 are so popular? DSPs are popular in applications that make heavy use of FFT, but there are a ton of general purpose implementations that require FFT algoritms, ranging from multitone generation/decoding to D/A conversion. Why should I use 2 ICs (plus assorted external logic) on a given circuit, if I can easily do it in software on my general-purpose microcontroller, that besides the integrated ram and rom, also bundles me with a serial port, multiple I/O ports and a ton of "extra" features, at a fraction of the price?
Well, if for some reason someone is already using Arduino boards to do a bunch of stuff it might make sense if it was just fast enough. But yeah, if you have a choice it doesn't make much sense to pick an Arduino for this task.
So far the only "usefulness" I've seen in the Arduino has been for that retro kick, being artificially limited to the kind of environment I haven't had to work in for a long time, but if I wanted to build something useful I'd probably at least want a 16-bit processor these days, the difference in price is negligible for any hobby project (hell, a 32-bit processor probably wouldn't be a major budget concern considering what you're likely to spend on the rest of your hardware when building something)...
Greylisting is to SMTP as NAT is to IPv4
Nope. FFTs are used in many fields, but cryptography is not one of them. Not since the old analog radio scramblers of decades past.
Informative and wrong. When you calculate powers of 4096 bit numbers, the fastest way to calculate the 4096 bit products is convolution via FFT.
Let me get this straight - you're saying you woke up in the middle of the night intending to take a dump, and somehow ended up posting about complex mathematical algorithms on the Internet instead? Respect.
From what I know, the Great Internet Mersenne Prime Search (GIMPS) uses a Fast Fourier Transform to quickly find the square of a number. This is a required part of the Lucas-Lehmer test (the test that determines if the number is prime).
If this form of FFT can do fast squaring, it will reduce the amount of time taken to find new, large primes.
This is a potentially exciting development in this field.
/^[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,4}$/i
Not every FFT implementation is floating-point (I believe fixed-point implementations are quite more common than floating-point ones), and software-based floating point is not "somewhat slow", is "slow as hell". For many applications, fixed-point and good ol' lookup tables (either complete tables or sample points with interpolation) do the trick rather well.
Nope. FFTs are used in many fields, but cryptography is not one of them. Not since the old analog radio scramblers of decades past.
Informative and wrong. When you calculate powers of 4096 bit numbers, the fastest way to calculate the 4096 bit products is convolution via FFT.
These matrices are not sparse, though, and thus the algorithms under discussion are not suitable, or any faster than FFT.
Comment removed based on user account deletion
The Spectrum Analyser. This is one of the most common uses is staring you right in the face in almost every mp3 player.
The interesting thing is that the greater time window over which the FFT operates, you can observe finer frequency detail within that particular window at the expense of how quickly the graph or bars change over time (in simplistic terms). I wonder how this new algo will change the frequency detail/transient time detail trade-off. Do we see more detail in both domains? Less? The same?
Slashdot could really use a +1 Insightful but Unnecessarily Dickish mod.
A year ago, there was still easily an order of magnitude difference in price going from AVR to 32-bit microcontroller land in base deve hardware alone. You say that for one hobby item the price difference (say $10 --->$100) is neglible, because they are both smallish numbers relative to income... 1) You need to learn multiplication 2) A lot of hobbyists have the desire to do their own version of "ubiquitous" computing.. Your "negligible" price difference theory breaks down in all the cases I'm familiar with.
And please spare me with examples of ultra cheap 32-bit systems, which I know always exist at any given moment. I still remember that time when the TI eval robot had a leaked promo code. That thing took down TIs website and then of course was promptly gone... When assisting a local youth group with a robotics project I looked at numerous "inexpensive" ARM options, only to find that at any given time product availability in this domain is *inconsistent*. Say what you will, but there is almost always an Arduino clone around, and if you fry it, you don't care. If you get a special on a 32-bit ARM system, good luck buying another in 3 months.
In my business, if you absolutely *NEED* a dev board you must still be prepared to pay $300-1000 bucks for the base board alone. I'm a day-job embedded product designer that also works with hobbyists at a hackerspace, so I am not hung up on any one usage and I can tell anybody that thinks that AVRs are irrelevant are still full of shit.. Where is your raspberry pi available for sale, fucker?
The interesting thing is that the greater time window over which the FFT operates, you can observe finer frequency detail within that particular window at the expense of how quickly the graph or bars change over time (in simplistic terms). I wonder how this new algo will change the frequency detail/transient time detail trade-off. Do we see more detail in both domains? Less? The same?
This is a property of the Discrete Fourier transform itself. For a certain window size there are only a discrete number of frequencies that you can calculate.
The larger your window-> The more frequenecies you can see (at the expense of a longer sampling time)
FFT algorithms simply try to compute the DFT quickly, this advance is significant for paractical applications but doesn't change the underlying mathematics.
Multiplications in time domain = convolution in transformed domain
Sometimes it's easier to go to the transformed domain, convolute and then go back to time domain :)
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.
It's more than a property of the DFT - it's a much deeper mathematical truth than that. The same fundamental mathematics is used to derive the uncertainty princible in quantum mechanics: For a signal to be perfectly defined in frequency it must be infinite in time, and vice versa. When you apply the same to quantum wave-functions... the uncertainty limit isn't a limit on measurements. It's a limit on what the universe is capable of representing.
Yes, FFT may be used in cryptography. But this is unrelated, as the first post in this thread talks about security. FFT has no connection to the security of cryptosystems.
As far as I'm aware, the security of *absolutely no* cryptosystem used in practice depends in any way on the FFT.
Yes, FFT gives us a way to multiply big integers quickly. But all cryptosystems that use big integers already *do* assume that everyone *can* multiply big integers quickly. Even if there was a ten-times speedup, this would mean absolutely no danger to their security.
(And one final nitpick: FFT is not the fastest way to multiply 4096-bit integers, those are still considered fairly short and you would probably gain a better performance out of some simpler-but-asymptotically-slower algorithm.)
What is wrong with this picture?
Moderation categories already encompass both categories mentioned, and are an improvement on a simple "like" or "dislike". Adding multiple combinations of moderation (e.g. Insightful + Flamebait or Informative + Troll or any of the other 90 combinations you would needlessly add to the slashdot moderation system) is only slightly less stupid than allowing the herd of cats that is the slashdot moderator community to just create arbitrary moderation categories out of thin air any time they feel like it. There ARE TWO WHOLE FUCKING CATEGORIES OF MODERATION already dedicated to "Insightful but Unnecessarily Dickish", namely Insightful and Flamebait. The general idea is that on average the +1 from the Insightful and the -1 from the Flamebait cancel each other out, and people checking the moderations on their comments over time will come to realize they should be less of a dick but retain their level of insight.
But noooo, ignorant people such as yourself, would rather recommend slashdot implement the most arbitrary and poorly architected moderation system in the world just so you can get the +5 insiiiiiiiiightful. (And even if you would argue that Dickish!=Flamebait you are proposing a new 11th moderation category for "insightful but Unecessarily Dickish" worth a +1, which would result in the sizable misanthropic subset of slashdot users who would actually TRY to get their posts moderated as your wondrous new moderation category, thinking it is an improvement over plain old insightful.)
If I have seen further it is by stealing the Intellectual Property of giants.
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.
--
make install -not war
Slashdot could REALLY use a +1 Insightful but Unnecessarily Dickish mod.
Do you have math showing the compression consumes less power than just transmitting the raw data?
Lots of it, the power budget drives the design of the entire sensor.
The micro-controller uses a lot less energy than the packet radio so it makes sense to process the raw sensor data on-board and transmit information such as fourier coefficients, integrals and other statistics. Every packet saved is another fraciton of a second the radio can be powered down.
It's a fairly common technique with sensor networks to process raw signals at the point of collection and transmit only the useful information, it makes the most use of your bandwidth and in this case energy.
For numbers that are small enough to fit in your processor's registers, multiplication is a constant-time process. But when dealing with numbers much larger than your processor's word-length (more than 4 bytes), you have to resort to the long-mulitplication algorithm. As it turns out, multiplying polynomials is exactly the same as convolution, and is O(n^2), and long multiplication is a special case of polynomial multiplication, where the variable is fixed:
525 * 343 = (5x^2 + 2x + 5) (3x^3 + 4x + 3), for x = 10
So for two large numbers, rather than going through the long process of convolving the digits (long-multiplying), you do the following process:
You can run the same mathematical processes on a TMS320, DSP56K, FPGA, desktop PC, GPGPU video card, embedded ARM, PIC, AVR, even a 4-bit micro if you feel the need.
You can just as well run it on vacuum tubes or relays, however there are no real-world applications for that -- and the same applies for 8-bit microcontrollers.
An AVR has no trouble doing DTMF decoding on values captured from the ADC,
DTMF is specifically designed to be easy to decode with the worst possible limitations on a decoder. Claiming that it makes a microcontroller capable of DSP would be like saying that a lightbulb can be used to calculate exponents because it can produce a close approximation of a black body radiation spectrum.
or running a few DDS channels to generate sine waves and throw them out a PWM channel, despite those being classical DSP applications.
In name only. There is no actual processing involved.
- Signed, someone who does DSP for a living.
So do I, however I don't count trivial operation on tables of precomputed values as "DSP".
Contrary to the popular belief, there indeed is no God.
Only partially true. What many people don't know is that Heisenberg's derivation was slightly wrong because while it modeled the thing being measured with quantum mechanics, it incorrectly modeled the measuring device classically.
A rigorous analysis using qm for both was done Ozawa in 2003 (see http://arxiv.org/abs/1201.1833 which shows the correct uncertainty equations on p. 2).
From http://www.sciencedaily.com/releases/2012/01/120116095529.htm "In order to describe the fundamental uncertainty and the additional disturbance due to the measuring process, both particle and measurement device have to be treated in the framework of quantum theory,...But the product of error and disturbance can be made arbitrarily small -- even smaller than Heisenberg's original formulation"
I think the parent is getting at a problem I see at my job fairly frequently. Professional Firmware and DSP developers that have no knowledge about the effects or consequence of their code on the hardware itself. Ultimately re-implementing something that used to run fine in 1/10th the ram, and 1/40th the processor cycles (or less) in a brand new dual core DSP and still can't figure out why they aren't meeting performance requirements. I've seen these guys demand a bigger, faster, more power hungry CPU to run their code when a previous version that was literally a fraction of the capability ran the same algorithm.
True Story: I'm an FPGA dev, and I was helping out software guys debug why the DSP was completely missing messages and seemed to be dropping data. Turns out doing a thousand lines of heavy DSP INSIDE the interrupt handler is probably going to hang up the CPU and cause it to miss interrupts. The worst part was the blank stares we got when we told them this, and had to explain why that was a bad thing.
It seems the idea of actually writing good, fast, and power efficient code is a dying art because it's perceived as 'not necessary'. In some instances this thinking is correct (e.g. desktop computers), but in the embedded space where you're trying to keep the cost of final products down and minimize power usage, grabbing the fastest DSP part that TI makes is probably not always the best solution... but it's what you get when you think it's automatically OK/good to 'do everything in software'. There are costs and penalties to account for.
For pure hobbyists, none of this really applies, but I suspect that a good many of the people that do this stuff as a hobby are also at least tangentially involved in it in some way at their jobs, so it serves to bring up the considerations.
Same problem as with "Enhance!" in the movies.
The "Fast and Fouriers"?
which is totally what she said