[問題] ACM 128 software CRC

[singlovesong (~"~)]

題目： http://luckycat.kshs.kh.edu.tw/homework/q128.htm

拍謝小弟數學不好

其實是要問數學的＠＠

這題是software CRC 就是一串字串當作傳輸資料

關鍵的code 如下

for(int i = 0; i < s.length(); i++)
           ans = ((ans << 8) + s[i]) % 34943;

ans 一開始是 0

s 是input string   例： s = "ABCDEFGHI"

等於是在做一個超大數的除法求餘數

想要問的是為什麼求大數的餘數只要上面那兩行code 就好呢？

自己測試了一下 A % B != (A<<8) %B

以上面的“ABCDEFGHI” 例子來看 資料有九個bytes 也就是2^72

為什麼上面那樣做左邊高位元的資料還能保持它的餘數是正確的呢？

想知道數學原理是什麼

謝謝！

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 111.184.164.153
→ firejox:其實只是同餘而已...
→ firejox:a%b = n ,(a*t)%b = (n*t)%b
→ angleevil:謝謝firejox
→ singlovesong:看無＠＠ 看懂f大的式子可是不知道跟題目的關連>"<
→ firejox:把A<<8 % B 想成A*256 %B ...
→ singlovesong:AAAAA -> (A<<32 + A<<24 + A<<16 + A<<8 + A) % B
→ singlovesong:實際上是算這個式子 為什麼會等價呢@@?
→ singlovesong:sorry 小弟資質愚鈍
→ firejox:(A<<32 + A<<24 + A<<16 + A<<8 + A)%B 相當於
→ firejox:((A<<32)%B + (A<<24)%B +...+ A%B)%B ...
→ firejox:以上述for 則是 (((..(A%B)<<8+A)%B)...)%B
→ firejox:你把它展開就知道了
→ firejox:http://zh.wikipedia.org/wiki/%E5%90%8C%E9%A4%98
→ singlovesong:謝謝 :P