4 ms·
And which you can use to do actual multiplication, using the DFT and inverse DFT, if you let $f$ and $g$ be polynomials over, say $Z/(2^k +1), where the modulus
by Paul-Craft 3y ago
And which you can use to do actual multiplication, using the DFT and inverse DFT, if you let $f$ and $g$ be polynomials over, say $Z/(2^k +1), where the modulus is selected such that $2^k$ is the word size of your machine.
- CyberDildonics 3y agoIsn't this just a complicated way of saying a computer can do multiplication?
- Paul-Craft 3y agoNo. It's saying a computer can do multiplication really fast by doing a bunch of additions, without having to worry about carries, instead.
- CyberDildonics 3y agoComputers can do multiplication really fast without doing additions, you just have to use SIMD instructions that are already on the CPU.
- deleted 3y ago[deleted]