by piotr5 » Sun Feb 15, 2015 7:31 am
and what makes you think any newton method would be parallellizable? it is true that multiplication is equivalent in speed to division for procedual algorithms, but parallell algorithms are faster than procedual! in parallell you only need 3 steps for multiplication (fft, bit-multiply, un-fft), independent of whatever length -- as long as you match that length with cores, that's constant runtime. can you achieve constant runtime (provided infinite number of cores) for division too? in theory it seems you could (proof-idea: calculate p/q...(p-q+1)/q modulo 2^N in parallell and find the correct number for output), but since no good algorithm (with logarithmic core-count) is known yet, as of yet division is not considered parallellizable -- maybe in future it will be...