Arbitrary-precision fixed-point arithmetic library
I decided to write this library in 2000, after watching “The Simpsons” episode “Treehouse of Horror VI”.
In the last story of this episode, Homer Simpson jumps into a three-dimensional world. The full story, and specially this parallel world, are full of mathematical tributes: geometrical shapes, the Euler’s identity, a reference to the P versus NP problem, and so on. Among these mathematical references, a disturbing numerical formula attracted our attention: 178212 + 184112 = 192212
Homer Simpson in a three-dimensional world
The previous affirmation is obviously a joke, since it must be false according to Fermat’s Last Theorem. But if we do the operation with a calculator with less than 10 significant digits, one can believe in its truthfulness, since both sides of the equality match up in the 9 first of their 40 digits.
The equation falseness can only be proved with a calculator capable to handle the enough significant digits, and even though there are numerous tools that can perform calculus with arbitrary precision (like the phyton language, or bc, into the GNU project), I found interesting to design a single and generic library to deal with arbitrary-size numbers, which could solve this kind of problems and another similar challenges.
In this post I will present the library code and its basic structure, and in future publications we will try to improve the algorithms efficiency and we will show some practical examples.
Library specification
A natural binary-coded decimal (NBCD) system has been chosen, with sign and module agreement, so an arbitrarily big integer can be coded with a long enough BCD digit sequence.
Furthermore, in order to handle fractional numbers, the library uses fixed-point arithmetic, therefore the format (the BCD sequence) is divided into whole and fractional parts. Thus, fractional numbers can be approximated with arbitrary precision by simply allocating enough memory in the fractional part. This scheme can deal with arbitrary-size numbers, but in a static way, i.e., having previously allocated the needed memory.
Once the format has been chosen, let us describe some simple arithmetic operations:
- Addition and subtraction: These operations are made by a point-wise addition or subtraction of both BCD sequences, applying a carry propagation from each digit to the next one.
- Multiplication: The operation is performed by a typical long multiplication algorithm.
- Division: The algorithm used is the long division algorithm.
The code
The library is coded in C++, but almost none of the language features are used in this limited version.
A number is coded in BigNumber class, which consists basically in a byte array and a sign flag. For simplicity and clarity, only one decimal digit is coded in each byte. The file bignum.h contains the declaration and bignum.cc contains some basic functions implementation.
The file config.h is a configuration point, where we can set the number of digits assigned to the whole and the fractional parts in the format.
The file test.cc contains a main function with an example application: evaluates both sides of the former equation 178212 + 184112 = 192212, and verifies its falseness. At least 40 digits are needed for doing the calculus (the default configuration reserves 50 digits for both whole and fractional parts).
The rest of the files codify several operations.
- addsub.cc: addition and subtraction.
- mul.cc: multiplication.
- div.cc: division.
- convert.cc: conversion between bignumbers and floating point numbers.
Links
Legal Notice: The Simpsons TM and (C) Fox and its related companies. All rights reserved. Any reproduction, duplication, or distribution in any form is expressly prohibited.
Disclaimer: This web site, its operators, and any content contained on this site relating to The Simpsons are not specifically authorized by Fox.
