Re^4: Algorithm inspiration required. (Further thoughts on rolling checksums)

NO intervening junk is the correct interpretation

What about presence or absence of preceding junk? If it's absent, i.e. sequence starts at 0, and if stream allows re-reading previous data, then read 2 bytes at 2N, look back at byte at N. Make N = N + 1 now. Update checksums for 0..(N-1) and N..(2N-1) halves (rolling hash). Byte read at "previous N" adds to checksum of half1, and deletes from checksum of half2. 2 bytes add to checksum for half2. Compare 2 checksums. And so on. Only 2 checksums stored at any time. I hope I didn't misunderstood the task to be too simple nor said anything too trivial.

Comment on Re^4: Algorithm inspiration required. (Further thoughts on rolling checksums)

Replies are listed 'Best First'.
Re^5: Algorithm inspiration required. (Further thoughts on rolling checksums) by BrowserUk (Patriarch) on Jun 18, 2018 at 22:50 UTC
if stream allows re-reading previous data, The definition of a stream is you cannot re-read it. I could store the stream to disk, but the cost of repeatedly re-reading large volumes of data is prohibitive. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity. In the absence of evidence, opinion is indistinguishable from prejudice. Suck that fhit	[reply]

Replies are listed 'Best First'.

Re^5: Algorithm inspiration required. (Further thoughts on rolling checksums)
by BrowserUk (Patriarch) on Jun 18, 2018 at 22:50 UTC

if stream allows re-reading previous data,

The definition of a stream is you cannot re-read it. I could store the stream to disk, but the cost of repeatedly re-reading large volumes of data is prohibitive.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.

In the absence of evidence, opinion is indistinguishable from prejudice. Suck that fhit

[reply]