3 ms·
Wrong. 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)
by aaaaaaaaaaab 4y ago
Wrong. 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.