Hacker’s multiple-precision integer-division program in close scrutiny
Author:Jyrki Katajainen
Published in:Proceedings of the 18th International Symposium on Experimental Algorithms, Lecture Notes in Computer Science 11544, Springer (2019), 376–391
Full text:<pdf.gif>PDF (372 kB)  
Copyright:© Springer Nature Switzerland AG
Abstract:Before the era of ubiquitous computers, the long-division method was presented in primary schools as a paper-and-pencil technique to do whole-number division. In the book "Hacker’s Delight" by Warren [2nd edition, 2013], an implementation of this algorithm was given using the C programming language. In this paper we will report our experiences when converting this program to a generic program-library routine.

The highlights of the paper are as follows: (1) We describe the long-division algorithm—this is done for educational purposes. (2) We outline its implementation—the goal is to show how to use modern C++ to achieve flexibility, portability, and efficiency. (3) We analyse its computational complexity by paying attention to how the digit width affects the running time. (4) We compare the practical performance of the library routine against Warren’s original. It is a pleasure to announce that the library routine is faster. (5) We release the developed routine as part of a software package that provides fixed-width integers of arbitrary length, e.g. a number of type cphstl::<2019> (editor’s note: the non-transliterated form used in the code is cphstl::bbbN<2019>) has 2019 bits and it supports the same operations with the same semantics as a number of type unsigned int.

Related:<html.gif>HTML (Slides)  
  author = {Jyrki Katajainen},
  title = {Hacker's multiple-precision integer-division program in close
  booktitle = {Proceedings of the 18th International Symposium on Experimental
  series = {Lecture Notes in Computer Science},
  volume = {11544},
  publisher = {Springer},
  year = {2019},
  pages = {376--391},
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 2020-05-13.