Division Algorithm

How does one divide a by b, given there is not division operation (i.e. C64 or NES)?

So far I got the following algorithm:
def div(a,b):
if a < b: return 0
if b == 0: raise Exception('Division by zero.')
q = 1
t = a
while t>>1 >= b:
t >>= 1
q <<= 1
return q + div(a-q*b,b)

guess it is O(n), where n is the number of bits in a. But NES also has no multiplication opcode, so q*b will require O(log2(n)) additions. How does one implement it properly? How CPUs implement division?

>>17
stop being a pedantic anus. addition, division and multiplication for n-bit integers can be constant time. they can't be for general-case bignums, but that's not what he was referring to and you know it