May be md5 the first hundred and last hundred mb's? Add 10 samples from the middle of the movie taken at equal distances calculated based on the size of the file.

Having said that I don't mind having to compute 4gb md5's, since that also helps me to check the integrity of the file at a later date.