3 ms·
> Multiplying 1024 bits by 1024 bits the naive way on a 32 bit processor involves 1024 multiply operations. That's 1024 32-to-64-bit wide multiply operations.
by jcranmer 6y ago
> Multiplying 1024 bits by 1024 bits the naive way on a 32 bit processor involves 1024 multiply operations.
That's 1024 32-to-64-bit wide multiply operations. On x86, where regular mul is wide (it sets both edx and eax), that's the same as a regular operation. Some architectures that have just a MUL and a MULH instruction would make it two instructions. If you have neither, that would require 3 multiply instructions plus a few shifts.
> Even in 2003, they were typically pipelined with a throughput of one multiply per cycle[1], so you should be able to do that in ~1040 clock cycles.
The inner loop is much more than a wide multiply. You have to load the two words you're multiplying (although one of them should already be loaded in the outer loop). Then you need to two adds-with-carry, store the results back. Next you need to handle the extra carry bit, which in the most naïve case is another load, add-with-carry, store. And finally, you need the regular loop management instructions.
That's 4 loads, 3 stores, 3 adds, and 1 multiply, repeated 1024 times. I don't know the exact port availability and timing of Pentium 3 processors, but if there's only one load /store port, and it's a 4-cycle latency operation, you're looking at probably 25-ish cycles per inner loop iteration, or about 25,000 clock cycles.