Computer Science

« first day (1217 days earlier) ← previous day next day → last day (3211 days later) »

user1667423

1:18 AM

Is there a version of Solomonoff induction on programs less powerful than universal computation?

e.g. primitive recursive, regular, context-free, etc.

10 hours later…

Mary Star

11:09 AM

@vzn It's similar... One of the algorithms is the FFT... dis.uniroma1.it/~sankowski/lecture4.pdf

Could someone take a look at my question:

Q: FFT procedure for evaluationg a polynomial at $N$ Fourier points

The following is the recursive FFT procedure of Algorithm for evaluationg a polynomial of length $N$ at $N$ Fourier points. Algorithm (FFT - fast Fourier transform). Input arguments. $ \ \ $ integer $N=2^m$ $ \ \ $ polynomial $\alpha (x)=\sum_{i=0}^{N-1}\alpha_i x^i$ $ \ \ $...

I am trying to implement the algorithm, but I got stuck...

3 hours later…

Rick Decker

1:57 PM

@MaryStar It's correct so far. Why not continue it? If you do, you'll find that $P(\omega^i)$, for $i=0, 1, 2, 3$ is $[11, 1 + 4\omega, -1, 1 - 4\omega]$, as it should be, if $\omega$ is a primitive fourth root of unity. What's the problem?

Raphael

2:11 PM

@user1667423 I haven't hear from this before, but the Wikipedia article seems to imply that it's a very general model.

Mary Star

@RickDecker But how can we calculate $B_1=B_1+\omega^1 \cdot C_1$ ? Which is the value of $B_1$? Or have I written wrong this formula?

2 hours later…

Rick Decker

3:55 PM

@MaryStar You're mixing the roles of the B arrays. Notice that the recursive definition presented at the top of your post takes two arrays, B and C and in the combination step uses them to produce the output array A. That's not one of the B arrays: it's a new answer array.

vzn

4:30 PM

@MaryStar the algorithm will probably not make much sense unless you understand FFT 1st, do you? try to understand basic FFT algorithm 1st & then see how its applied to the polynomial evaluation.

2 hours later…

Computer Science Meta

6:19 PM

Q: Why was this question re-opened?

Why was this question re-opened? As you can see from the history, I voted to close it, then one moderator closed it, then another moderator re-opened it. The side effect of the re-opening is that I can no longer vote to close it; a mod re-open overrides my vote. This seems like a clear case of...