| 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 (372 kB) |
| DOI: | 10.1007/978-3-030-34029-2_25 |
| 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 (Slides) |
| BibLATEX: | @inproceedings{Kat2019C,
author = {Jyrki Katajainen},
title = {Hacker's multiple-precision integer-division program in close
scrutiny},
booktitle = {Proceedings of the 18th International Symposium on Experimental
Algorithms},
series = {Lecture Notes in Computer Science},
volume = {11544},
publisher = {Springer},
year = {2019},
pages = {376--391},
}
|