[phobos] FFT

[Don Clugston]

On 2 August 2010 06:10, Andrei Alexandrescu <andrei at erdani.com> wrote:
> It would be useful to compare this against the other FFTs that have been
> talked about. I don't mean to discourage! I think the typical user of FFT
> would put no price on readability and would be interested exclusively in
> speed. If your implementation is within the ballpark, then great. If it's
> considerably slower, then I think people won't say "well it's slower but I
> like the elegance inside it".
>
> Andrei

I agree with that, although I think there are FFT use cases which rate
convenience over speed, especially if the speed is only a factor of
three slower than worlds' best practice.
We can assume that any usage of FFTs which is really speed critical
will be using FFTW (or a similar library). So a Phobos FFT should not
be aimed at power users. It might even be used for testing (do I need
an FFT here?) which is basically what you've ended up doing.
(My philosophy for std.bigint is the same; power users will use GMP,
but for casual usage, GMP is overkill and a nuisance to set up).
OTOH I think we need to be careful, it still needs to be much better
than something which users could write themselves in a few hours...

>
> On 08/01/2010 06:31 PM, David Simcha wrote:
>>
>> Ok, here's the code, I've got it down to about 800 milliseconds for a
>> 2^20 double[] -> Complex!double[] transform. In comparison, the R
>> statistics package, which is probably very heavily optimized and uses (I
>> think) GCC as its compiler can do a similar transform in ~610
>> milliseconds, so my code isn't blindingly fast, but it's not
>> unreasonably slow.
>>
>> On 8/1/2010 5:21 PM, Jason Spencer wrote:
>>>
>>> I don't have much of an opinion on adding to Phobos, but I'd
>>> definitely be
>>> interested in seeing the code. I'm starting to do some scientific
>>> computing
>>> using D, and that would be a great learning reference for me.
>>>
>>> Jason
>>>
>>>
>>> ----- Original Message ----
>>>>
>>>> From: David Simcha<dsimcha at gmail.com>
>>>> To: Discuss the phobos library for D<phobos at puremagic.com>
>>>> Sent: Sun, August 1, 2010 1:32:38 PM
>>>> Subject: Re: [phobos] FFT
>>>>
>>>> Speed-wise, I've just been goofing around for the past hour or so and
>>>> I've sped
>>>> it up 2x. It now does 1 size 2 ^^ 20 double[] -> Complex!double FFT
>>>> in about
>>>> 880 milliseconds.
>>>>
>>>> On 8/1/2010 3:36 PM, Walter Bright wrote:
>>>>>
>>>>> David Simcha wrote:
>>>>>>
>>>>>> As I am no longer going to use FFTs in my kernel density lib,
>>>>>> improving
>>>>
>>>> this FFT code will be bumped down my hacking to-do list. Does what I
>>>> have now
>>>> sound better than nothing by a large enough margin to warrant
>>>> inclusion in
>>>> std.numeric, or does it sound too primitive to be widely useful? If
>>>> it sounds
>>>> worth including I'll clean up/document the code and send it to the
>>>> mailing list
>>>> for review. If it sounds too primitive, I'll just scrap it.
>>>>>
>>>>> I don't know enough about FFT's to make any sort of informed comment.
>>>>> _______________________________________________
>>>>> phobos mailing list
>>>>> phobos at puremagic.com
>>>>> http://lists.puremagic.com/mailman/listinfo/phobos
>>>>>
>>>> _______________________________________________
>>>> phobos mailing list
>>>> phobos at puremagic.com
>>>> http://lists.puremagic.com/mailman/listinfo/phobos
>>>>
>>
>>
>>
>> _______________________________________________
>> phobos mailing list
>> phobos at puremagic.com
>> http://lists.puremagic.com/mailman/listinfo/phobos
>
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos
>