4 ms·
It seems like CRC inherently depends on results from earlier calculations, so it would be hard to parallelize like that. You could potentially do multiple indep
by sgtnoodle 4y ago
It seems like CRC inherently depends on results from earlier calculations, so it would be hard to parallelize like that. You could potentially do multiple independent CRC calculations in parallel, but then you're getting into more niche use cases.
- aaaaaaaaaaab 4y agoWrong. CRC is just polynomial division, which is simple to do in a divide and conquer fashion. It's pretty easy to derive CRC(A concat B) from CRC(A) and CRC(B). It needs a multiplication and a XOR.
- sgtnoodle 4y agoah, that's pretty cool! It looks like concatenation is a O(log(n)) operation involving appending a bunch of zeros rather than just a multiplication, though?
- aaaaaaaaaaab 4y agoIt depends. (A(x) mod Q(x)) * (B(x) mod Q(x)) = (A(x) * B(x)) mod Q(x) If the chunk size N is known beforehand you can pre-calculate x^N mod Q(x), so appending N zeros will be an O(1) multiplication. Only if the chunk size is not known, you have to calculate x^N mod Q(x) via modular exponentiation, which is O(log n). But you only need to do this once, and then you can reuse the value for all subsequent chunks.