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?

Are we talking floating point division or floor division?

>>2
NES has FPU?

>>3
What's with the self-imposed hardware limitation?

C64 or NES

it's almost 2019 gramps

>>1
https://en.wikipedia.org/wiki/Division_algorithm#Goldschmidt_division

remember when ``divide by zero'' was a popular maymay on le imagereddits?

>>7
I’d rather not.

Shift-and-subtract.

>>7
There is no way to sensibly define division by zero:
https://www.youtube.com/watch?v=J2z5uzqxJNU

use a lookup table

Just a tip: non-constant time division algorithms are trash.

if b == 0: raise Exception('Division by zero.')

Should have used dependent types instead.

>>12
Ok, legit, I want to know how you would program a dependent type on the MOS 6502.
You have full /prog/'s attention.

>>13
Dependent types are about type checking, you do not need any runtime support.

>>14
type check the division operation in MOS 6502 assembly, you autist.

haskal for NES

>>12
Addition, division, and multiplication are by their nature non-constant time. You can't produce N digits in O(1) time. The best known algorithm is still much slower than O(n):
https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm

>>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

>>15
Ok https://www.cs.cmu.edu/~rwh/papers/dtal/icfp01.pdf https://people.eecs.berkeley.edu/~necula/Papers/deptypes_sas05.pdf

>>18
Aren't general-case bignums just n-bit integers?

some NES games had extra chips in the cartridges that could do multiplication

Multiplication with NES: https://www.youtube.com/watch?v=ar9WRwCiSr0

>>20
Only if they're are less than n-bits.

>>23
Integers (and rationals) are finite, so they are always less than n-bit (for a big enough n given n : nat).

>>24

Integers (and rationals) are finite

🤔

>>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.

babby's first set theory

>>26
that's not what countable and uncountable infinity means, anus

>>28
huh?

>>29
what does 'infinite length' even mean? does it mean irrational numbers? if so, you can trivially construct a finite or countably infinite set of irrationals - e.g. a set which consists of integers multiplied by pi. that's still countable. or maybe you mean that its elements are sets of infinite length? that makes even less sense, and you can still trivially construct a countably infinite set of infinite sets - e.g. a set which contains sets of { { 1... ∞ }, {2 ... ∞ }, ... , { n ... ∞ }}

countably infinite sets don't have finite elements, they have finite continuous subsets (not even all subsets - a set of even integers is a subset of set of integers and it's still infinite). in other words, a countably infinite set will have a finite number of elements between two arbitrarily chosen elements - e.g. 'integers larger than 1 and smaller than 10'. in uncountably infinite sets, those subsets can be infinite - e.g. 'real numbers larger than 1 and smaller than 10'. an intuitive way of looking at that would be: if you pick a number from countably infinite set, you can easily point to next/previous number. in an uncountably infinite set, you can't because there's still infinite number of elements between 'current' and 'next'

>>28

infinity

Shalom!

>>30
That actually makes sense.

divide my dubs

>>32
it's really just basic set theory. go study it, it's one of the most fun things in math