Arithmetic operations with arbitrary precision
I decided to write this small library in 2000, after watching a rerun of “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, Euler’s identity, a reference to the P versus NP problem, and so on. Among these mathematical references, a disturbing numerical formula attracted my attention:
The previous statement is obviously a joke, since it contradicts Fermat’s Last Theorem. However, evaluating both sides of the equation with a scientific calculator, one can fall for it. Try with Google, for example:
The problem with is that a normal calculator doesn’t handle the enough amount of significant figures. Given the fact that both sides of the equality share the 9 first digits, the result is, apparently, the same. Here is the full 40-digit result:
The main trouble stems obviously from a spatial limitation of the display, unable to represent all the computed figures in scientific notation. But even if our device had a larger screen, the above formulas couldn’t be properly evaluated due to the internal floating point storage precision.
Even though there are numerous tools able to perform arithmetic operations with arbitrary big integers (like the phyton language, or GNU bc), I found interesting, as part of my learning process, to write a lightweight and generic library to deal with this and other similar problems.
In this post I will present the library code and its basic structure, and in future publications we will try to improve its efficiency and show some practical examples.
The library works with natural binary-coded decimal (NBCD) format, with sign and module agreement, so an arbitrarily big integer can be encoded in a - long enough - BCD digit sequence.
In order to handle fractional numbers, the library uses fixed-point arithmetic, therefore the format - the BCD sequence - is divided into integer and fractional parts. This way, fractional numbers can be approximated with arbitrary precision by simply allocating enough memory in the fractional part. This scheme can deal with arbitrary-sized 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 library is coded in C++, but without exploiting many of the features of the language.
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, instead of two per byte.
config.h is a configuration point, where we can set the number of digits assigned to the integer and fractional parts in the format.
test.cc contains a main function with an example application: it evaluates both sides of the former equation , and verifies its falseness. At least 40 digits are needed to carry out the operation, so the default configuration, which reserves 50 digits for both the integer and fractional parts, is enough for our purposes.
The rest of the files implement several operations.
addsub.cc: addition and subtraction.
convert.cc: conversion between bignumbers and floating point numbers.
- Library hosted on github.com (the code explained here is tagged as 1.0.0, the posterior code can contain improvements explained in future posts)
- Source code
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.