From owner-freebsd-hackers Mon Aug 3 12:15:52 1998 Return-Path: Received: (from majordom@localhost) by hub.freebsd.org (8.8.8/8.8.8) id MAA19809 for freebsd-hackers-outgoing; Mon, 3 Aug 1998 12:15:52 -0700 (PDT) (envelope-from owner-freebsd-hackers@FreeBSD.ORG) Received: from smtp01.primenet.com (smtp01.primenet.com [206.165.6.131]) by hub.freebsd.org (8.8.8/8.8.8) with ESMTP id MAA19751 for ; Mon, 3 Aug 1998 12:15:34 -0700 (PDT) (envelope-from tlambert@usr07.primenet.com) Received: (from daemon@localhost) by smtp01.primenet.com (8.8.8/8.8.8) id MAA21780; Mon, 3 Aug 1998 12:14:56 -0700 (MST) Received: from usr07.primenet.com(206.165.6.207) via SMTP by smtp01.primenet.com, id smtpd021700; Mon Aug 3 12:14:48 1998 Received: (from tlambert@localhost) by usr07.primenet.com (8.8.5/8.8.5) id MAA00830; Mon, 3 Aug 1998 12:14:42 -0700 (MST) From: Terry Lambert Message-Id: <199808031914.MAA00830@usr07.primenet.com> Subject: Re: Fast FFT routines with source? To: malte.lance@gmx.net Date: Mon, 3 Aug 1998 19:14:42 +0000 (GMT) Cc: luoqi@watermarkgroup.com, reilly@zeta.org.au, hackers@FreeBSD.ORG, jgrosch@mooseriver.com, shocking@prth.pgs.com In-Reply-To: <13765.46057.61247.598795@neuron.webmore.de> from "Malte Lance" at Aug 3, 98 03:08:11 pm X-Mailer: ELM [version 2.4 PL25] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: owner-freebsd-hackers@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG > > Code samples (yes, they are samples, I never use them as they are) in NR > > are horrible, but no other book could beat NR on explaining how an > > algorithm works (have you read the FFT section in Sedgewick's Algorithms? > > Instead of explaining how *FFT* works, it tries to explain what are > > roots of unity, does that belong to a high school Algebra book?) > > Don't know about US-highschools. > > To know "how FFT works", you have to know what this nasty > numbers in the frequency-domain stand for and where they come > from. Also you need to know why you are able to reuse > intermediary calculation-results (bit-reversion/reordering). > The answers to this questions are easy, when you have knowledge > about unit-roots and exponentials. Unit-roots and exponentials > are really not that hard, that they shouldn't be explained in a > basic-level analysis or algebra book. I have to agree here. It's no use having a hammer if you don't know how it works. You don't necessarily have to know why it works, of course, unless you are concerned with being the most efficient carpenter you can be. I consistently find Sedgewick's book useful; despite the title, it has very little direct relationship to C++ (or any other implementation language). In particular, if you ever want to know "what's Terry on about?" when I talk about "Hamiltonian Cycles" and "Warshal's Algorithm" and "O(3) Algorithms for Transitive Closure" and "Directed Acyclic Graph", this is the book to read. Terry Lambert terry@lambert.org --- Any opinions in this posting are my own and not those of my present or previous employers. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message