4 ms·
It's much easier to remember and apply the corresponding finite state machine, where you just keep track of the remainder mod 7 that you've seen thus far. Exam
by shasta 16y ago
It's much easier to remember and apply the corresponding finite state machine, where you just keep track of the remainder mod 7 that you've seen thus far. Example: 48193. What's the remainder mod 7?
48 mod 7 = 6 -- First two digits
61 mod 7 = 5 -- Remainder thus far, appending next digit
59 mod 7 = 3 -- Remainder thus far, appending next digit
33 mod 7 = 5 -- Remainder thus far, appending next digit
No more digits, so the answer is 5.
(Edit: I did figure that you were almost certainly being sarcastic. I just wanted to point out that in its corresponding FSM form, we've memorized the transitions as children.)
- eru 16y agoYes, that's much easier. My comment wasn't meant to be serious. Check out how long that regular expression is. (Though it can be simplified further.) I actually generated the regular expression linked by compiling the finite state machine.
- pronoiac 16y agoYou're doing all the work of dividing by 7. There are shortcuts to checking divisibility [1] - 2, 3, 5, & 9 have the easiest shortcuts - but 7 is a complicated case, which I'd probably just divide out anyway. [1] http://en.wikipedia.org/wiki/Divisibility_rule#Divisibility_by_7 http://en.wikipedia.org/wiki/Divisibility_rule#Divisibility_...
- eru 16y agoNo, he's not doing the work of dividing by seven. That would need memory of around the same size as your number of digits of your input number. His state machine only reads one digit at a time and only needs to store a less-than-one-digit state. My regular expression is a joke on the usual divisibility rules. By the way, you can find your own divisibility rules. They are actually easy to find and prove, if you know a bit about cyclic groups / calculating with modulo. E.g. the rule for divisibility by F in hexadecimal is the same as the one for 9 in decimal. Divisibility by 11 or 101 or 1001, or 9, 99, 999 is also really simple.