The trick is really just about realizing that you can re-write a number like 1234 as a polynomial like 1 * 10^3 + 2 * 10^2 + 3 * 10^1 + 4 * 10^0.
The complexity of such a program would be mostly done at compile time, layouting the instructionflow into the memory.
Data would have physics, as in the parallel nature of this "simulation" pumping data through would add something roughly similar to our physics to the behaviour. Interaction between parallel processed elements has a scope, like a lightcone in our physics. (SumOf(NrOfCores*LargestChunkOfData))
If you want to safely remove or place new data into the whole affair, one just leaves large enough "gaps" in the datastream that can be assumed to firewall.
In my undergrad time i build a little comp science experiment. Nothing fenzy, just a idealized, parallel "Engine", copying datachunks of size from Buffer A to Buffer B.
Even just this has interesting interaction behaviour. Like sand at the beach, the data get sorted by size after intervals. One also insert "dark matter" aka dead chunks into the buffers, which has the effect of "accelerating" large chunks of data, while the small chunks stay put. All of this is from the point of view of the buffer of course, in which time is one "total copying from a to b".
Sorry i found this fascinating, even though it might be of no value besides distraction at all.
From the paper: "Note that this error is due to the limited precision in which we can represent numbers on computers, it does not occur in exact arithmetic."
But of course, exact reals (twiddle factors aren't rational) are rife with undecidability if not uncomputability.
“Regular” multiplication could mean n^2 for standard paper arithmetic, n^1.6 for karatsuba, and a few other n^y algorithms with y>1
However as usual in this analysis we have dropped constant factors and the constant factors for FFT are high so you have to be multiplying numbers with at least hundreds of digits if not thousands.
Note that the base of the digits isn’t relevant for analytical performance, as it’s a constant factor change
I'd probably just do a giant shift and add loop.