3 ms·
You can derive a relationship between division and shift-add-multiply in a cute way by noting that 1 1 1 1 --- - --- = --- --- (a-b)
by marginalia_nu 4y ago
You can derive a relationship between division and shift-add-multiply in a cute way by noting that
1 1 1 1
--- - --- = --- --- (a-b)
b a b a
Move 1/a to the right hand side
1 1 1 1
--- = --- + --- --- (a-b)
b a b a
[X]
Substitute 1/b marked with X for the RHS and you get
1 1 (a-b) 1 1
--- = --- + ----- (1 + --- --- (a-b))
b a a^2 b a
Repeat and eventually you get
__
1 \ -(n+1) n
--- = > a (a-b)
b /_
n=0...inf
For example with b=3 and a=2, you get
1 1 1 1
--- = --- - --- + --- -+ ...
3 2 4 16
Word of warning though, this method tend to produce nasty carry errors.