Discussion:
FFT Confusion
(too old to reply)
Jacob Chapa
2005-05-01 22:41:13 UTC
Permalink
What exactly is being passed into FFT? IF g and w (omega) are being
given, then what is the use of g? if g and k are given then we can
compute w by: w = g^k mod p
Jacob Chapa
2005-05-02 00:05:26 UTC
Permalink
Post by Jacob Chapa
What exactly is being passed into FFT? IF g and w (omega) are being
given, then what is the use of g? if g and k are given then we can
compute w by: w = g^k mod p
nevermind.
David Zhao
2005-05-02 02:07:54 UTC
Permalink
The fft function receives, in order of its operands:

(1) the polynomial being transformed,
(2) the modulus p over which the transformation is performed, and
(3) a value omega denoting a principal nth root of unity, where n is the
degree-bound of the polynomial.

David
What exactly is being passed into FFT? IF g and w (omega) are being given,
then what is the use of g? if g and k are given then we can compute w by: w
= g^k mod p
chris j
2005-05-02 03:20:03 UTC
Permalink
Do we use the same value of w (omega) through the recursion of fft? In your
exaple w seems to change from 2 to 4.
Post by David Zhao
(1) the polynomial being transformed,
(2) the modulus p over which the transformation is performed, and
(3) a value omega denoting a principal nth root of unity, where n is the
degree-bound of the polynomial.
David
Post by Jacob Chapa
What exactly is being passed into FFT? IF g and w (omega) are being
given, then what is the use of g? if g and k are given then we can
compute w by: w = g^k mod p
Jacob Chapa
2005-05-02 03:39:04 UTC
Permalink
Post by chris j
Do we use the same value of w (omega) through the recursion of fft? In
your exaple w seems to change from 2 to 4.
Post by David Zhao
(1) the polynomial being transformed,
(2) the modulus p over which the transformation is performed, and
(3) a value omega denoting a principal nth root of unity, where n is
the degree-bound of the polynomial.
David
Post by Jacob Chapa
What exactly is being passed into FFT? IF g and w (omega) are being
given, then what is the use of g? if g and k are given then we can
compute w by: w = g^k mod p
w does change.
alex "chimmy chimmy" cheng
2005-05-02 03:57:26 UTC
Permalink
Post by chris j
Do we use the same value of w (omega) through the recursion of fft? In
your exaple w seems to change from 2 to 4.
Post by David Zhao
(1) the polynomial being transformed,
(2) the modulus p over which the transformation is performed, and
(3) a value omega denoting a principal nth root of unity, where n is
the degree-bound of the polynomial.
David
Post by Jacob Chapa
What exactly is being passed into FFT? IF g and w (omega) are being
given, then what is the use of g? if g and k are given then we can
compute w by: w = g^k mod p
Chris,

Clearly you do not understand the project specification. It blatanly
states that w changes to w^2 after an iteration of FFT. I think you
failed to look over it closely enough. Please exhaust all your options
before posting on the newsgroup.
chris j
2005-05-02 03:59:41 UTC
Permalink
hey jake, as I remember it was Li who pointed that out to you. but thanks
:-P
Post by alex "chimmy chimmy" cheng
Post by chris j
Do we use the same value of w (omega) through the recursion of fft? In
your exaple w seems to change from 2 to 4.
Post by David Zhao
(1) the polynomial being transformed,
(2) the modulus p over which the transformation is performed, and
(3) a value omega denoting a principal nth root of unity, where n is the
degree-bound of the polynomial.
David
Post by Jacob Chapa
What exactly is being passed into FFT? IF g and w (omega) are being
given, then what is the use of g? if g and k are given then we can
compute w by: w = g^k mod p
Chris,
Clearly you do not understand the project specification. It blatanly
states that w changes to w^2 after an iteration of FFT. I think you failed
to look over it closely enough. Please exhaust all your options before
posting on the newsgroup.
David Zhao
2005-05-02 05:02:47 UTC
Permalink
Yes, that is correct. In hindsight, I should have done a better job at making
this more explicit.

The key point is that w needs to be a principal nth root of unity, where n is
the length of the powerlist. But in a recursive call, the length of the
powerlist is equal to n/2. But w is a principal nth root of unity; what we
really need is an (n/2)th root of unity.

By the Cancellation Lemma, which we never really stated in the lecture or the
project, if w is an nth root of unity, then w^2 is an (n/2)th root of unity.
Therefore, changing w to w^2 in a recursive call to FFT or IFT will produce the
correct result.

David
Clearly you do not understand the project specification. It blatanly states
that w changes to w^2 after an iteration of FFT. I think you failed to look
over it closely enough. Please exhaust all your options before posting on the
newsgroup.
Jacob Chapa
2005-05-02 04:50:36 UTC
Permalink
hey jake, sorry I jumped to conclusions. It wasn't Li I just asked her.
Please accept my apology.
-chris j
sure, just don't let it happen again.
Li Chua
2005-05-02 16:50:44 UTC
Permalink
bastard. never helping you again -_-;

btw, your partner owes me money.

li
Post by Jacob Chapa
hey jake, sorry I jumped to conclusions. It wasn't Li I just asked her.
Please accept my apology.
-chris j
sure, just don't let it happen again.
chris j >
2005-05-02 04:49:56 UTC
Permalink
hey jake, sorry I jumped to conclusions. It wasn't Li I just asked her.
Please accept my apology.

-chris j
Loading...