Burnikel Ziegler Division

[ytgui]

https://github.com/wyndavies/LongInteger/blob/master/LongIntegers/LongInteger.cpp#L1519 https://github.com/wyndavies/LongInteger/blob/master/LongIntegers/LongInteger.cpp#L2987 https://github.com/python/cpython/blob/master/Objects/longobject.c#L1700 https://github.com/python/cpython/blob/master/Objects/longobject.c#L2770 https://www.geeksforgeeks.org/restoring-division-algorithm-unsigned-integer/ https://www.geeksforgeeks.org/non-restoring-division-unsigned-integer/ https://stackoverflow.com/questions/32744423/big-integer-division-with-operands-aproximately-of-the-same-size https://gmplib.org/~tege/division-paper.pdf https://githu-------------b.com/holiman/uint256/issues/5 https://golang.org/src/math/big/int.go https://golang.org/src/math/big/nat.go (natural number) https://golang.org/src/math/big/arith.go#L254 (impl) https://github.com/igraph/igraph/blob/master/src/bignum.c#L1409

[ytgui]

Burnikel Ziegler

  // Looked at other algorithm (e.g. Newton-Raphson division) and many of them use floating point numbers
  // So we shall move on to Burnikel-Ziegler division

  // The first part is DivTwoDigitsByOne
  // It needs to split the numbers, so we shall test the split code

  // Very much in the testing phase, hence the chaotic layout (plus it is rather hard to understand the paper as I don't really
  // know maths notation - so a lot of trial and error)

  // DivTwoDigitsByOne(AHigh, ALow, B), return quotient Q and remainder S
  //
  // 1) Let [a1,a2] = AH, [a3,a4] = AL, and [b1,b2] = B
  // 2) [q1,R] = DivThreeHalvesByTwo(a1,a2,a3,b1,b2)
  // 3) Let [r1,r2]=R
  // 4) [q2,S] = DivThreeHalvesByTwo(r1,r2,a4,b1,b2)
  // 5) Return Q=[q1,q2] and S

  // DivThreeHalvesByTwo(a1,a2,a3,b1,b2)
  //
  // 6) q=[a1,a2]/b1;
  // 7) c=[a1,a2]-q*b1
  // 8) D=q*b2
  // 9) R=[r1,r2]=[c,a3]-D
  //10) if(R<0) {
  //11)   q--;
  //12)   R+=B;
  //13)   if(R<0) {
  //14)      q--;
  //15)      R+=B;
  //16)   }
  //17) }
  //18) Return quotient q and remainder R

[ytgui]

Knuth's algorithm D

well, it's really difficult

Non Restoring Division

R := N
D := D << n            -- R and D need twice the word width of N and Q
for i = n − 1 .. 0 do  -- for example 31..0 for 32 bits
  if R >= 0 then
    q[i] := +1
    R := 2 * R − D
  else
    q[i] := −1
    R := 2 * R + D
  end if
end

-- Note: N=Numerator, D=Denominator, n=#bits, R=Partial remainder, q(i)=bit #i of quotient.