Read the original, officially approved version of my Master's thesis (pdf) or the version with the latest typo fixes (ps, changelog relative to the official version).
This thesis was the final part of my Master of Science degree in Computer Science and Engineering from the Royal Institute of Technology, Stockholm, Sweden.
I have investigated, theoretically and experimentally, under what circumstances Newton division (inversion of the divisor with Newton's method, followed by division with Barrett's method) is the fastest algorithm for integer division. The competition mainly consists of a recursive algorithm by Burnikel and Ziegler.
For divisions where the dividend has twice as many bits as the divisor, Newton division is asymptotically fastest if multiplication of two n-bit integers can be done in time O(n^c) for c < 1.297, which is the case in both theory and practice. My implementation of Newton division (using subroutines from GMP, the GNU Multiple Precision Arithmetic Library) is faster than Burnikel and Ziegler's recursive algorithm (a part of GMP) for divisors larger than about five million bits (one and a half million decimal digits), on a standard PC.
Jag har undersökt, ur både teoretiskt och praktiskt perspektiv, under vilka omständigheter Newtondivision (invertering av nämnaren med Newtons metod, följd av division med Barretts metod) är den snabbaste algoritmen för heltalsdivision. Den främsta konkurrenten är en rekursiv algoritm av Burnikel och Ziegler.
För divisioner där täljaren har dubbelt så många bitar som nämnaren är Newtondivision snabbast asymptotiskt om multiplikation av två n-bitars heltal kan göras på tid O(n^c) med c < 1.297, vilket är fallet både teoretiskt och i praktiken. Min implementation av Newtondivision (som använder subrutiner från GMP, GNU:s multiprecisionsaritmetikbibliotek) är snabbare än Burnikel och Zieglers rekursiva algoritm (en del av GMP) för nämnare större än cirka fem miljoner bitar (en och en halv miljon decimala siffror), på en vanlig PC.