Why did I get this [1, 2, 4, 8, 16, 1, 16, 8, 4, 2, 1]?

Question

After a lot of trial and error, I found the following lines of python code,

for N in range(2**1,2**3): print [(2**n % (3*2**(2*N - n))) % (2**N-1) for n in range(2*N+1)] 

which produce the following conclusion,

 [1, 2, 1, 2, 1] [1, 2, 4, 1, 4, 2, 1] [1, 2, 4, 8, 1, 8, 4, 2, 1] [1, 2, 4, 8, 16, 1, 16, 8, 4, 2, 1] [1, 2, 4, 8, 16, 32, 1, 32, 16, 8, 4, 2, 1] [1, 2, 4, 8, 16, 32, 64, 1, 64, 32, 16, 8, 4, 2, 1] 

i.e. degrees from 2 to 2**(N-1) , 1 and degrees of two inverse. This is exactly what I need for my problem (related to fft and wavelet). However, I'm not quite sure why this works? The final modulo operation, which I understand, is provided by 1 in the middle of the series. Factor 3 in the first modulo operation gives me headaches. Can anyone suggest an explanation? In particular, what is the connection between my base 2 and factor 3?

Answer 1

First of all, as others have said, much simpler implementations are possible, and you should probably use them.

But to answer your question, this is why you get this result:

When n <N:

2 ⁿ % (3 * 2 ^2N-n ) = 2 ⁿ since 2 ⁿ <3 * 2 ^2-N-p . Then 2 ⁿ % (2 ^N -1) = 2 ⁿ giving the expected result.

When n = N :

2 ^N % (3 * 2 ^2N-N ) = 2 ^N and 2 ^N % (2 ^N -1) = 1.

When N <n <= 2N:

Let n = 2N - k. Then:

2 ⁿ % (3 * 2 ^2N-n ) = 2 ^2N-k % (3 * 2 ^k ) = 2 ^k * (2 ^2N-2k % 3) = 2 ^k * (4 ^Nk % 3)

Any degree of 4 is equal to 1 modulo 3 (since 4 = 1 (mod 3), therefore 4 ^m = 1 ^m = 1 (mod 3) as Well). Thus, the final result is 2 ^k = 2 ^2N-n as expected.

Using other numbers:

If you use base a instead of 2, and number b instead of 3, the last part will give you:

a ^k * ((a ² ) ^Nk % b)

So, you need to choose b as any factor ² -1, which guarantees that ((a ² ) ^Nk % b) = 1 for any k.

Answer 2

While I love smart solutions just like the next geek, why don't you use a simple solution if you have trouble understanding your own code? It will be much easier to maintain, and it will not be so slower:

 def fft_func(ex): if ex == 0: return [0, 0, 0] else: return [2**n for n in range(0, ex+1)] + [1] + [2**n for n in range(ex, -1, -1)] 

Answer 3

The simplest way to create this list is:

 for N in range(2**1,2**3): print [2**((N-abs(Nk))%N) for k in range(2*N+1)]