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?

>>25
The set of integers (and rationals) is countably infinite, meaning that every element in them is finite. Unlike the set of real numbers which is uncountably infinite, meaning that some elements are of infinite length.