Hacker News new | ask | show | jobs
by marginalia_nu 1210 days 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.