Arbitrary Precision Integer Arithmetic in the Bourne Again Shell (BASH)

This is a brief post on quick ways to perform arbitrary precision integer arithmetic in the GNU Bourne Again Shell (BASH), either at the command prompt or in a shell script. It is partially a followup to the post Floating Point Arithmetic in the Bourne Again Shell (BASH) and overlaps some of the content in this previous post.

The Bourne Again Shell, or bash, is the default command line processor (shell) for Mac OS X, the cygwin environment on MS Windows, and many other Unix and Unix-like systems. Especially if you work with numbers, you may want to perform quick arbitrary precision arithmetic at the command prompt (shell) or in shell scripts. This post covers three ways to perform arbitrary precision arithmetic in bash: the bc arbitrary precision calculator language, the python programming language, and the ruby programming language.

Arbitrary Precision Arithmetic

Most computers and computer programming languages as well as calculator programs default to thirty-two (32) or sixty-four (64) bit integers or floating point numbers. This restricts the range of integers that can be represented and computed correctly with integer numbers and restricts the range and precision of floating point numbers. For example, an unsigned 32 bit integer can only represent the numbers from zero (0) to 4,294,967,296 (two raised to the 32nd power, somewhat over four billion.) An unsigned 64 bit integer can only represent the numbers from zero (0) to 18,446,744,073,709,551,616 (two raised to the 64th power, somewhat over eighteen quintillion).

These huge numbers, especially for sixty-four bit integer and floating point numbers, are far beyond our everyday experience, but they can be encountered in public key cryptography which involves products of huge integers, in computing factorials which grow rapidly, in astronomy or physics, and in various other specialized applications and fields. Factorials arise frequently in probability and statistics. Twenty-one factorial (21! in common mathematical notation) is 51,090,942,171,709,440,000 (over fifty-one quintillion) which is too large for an unsigned 64-bit integer.

Arbitrary precision arithmetic is generally slower than the standard integer or floating point arithmetic on most computers which utilize hardware arithmetic designed for the standard 32 and 64 bit numbers, but it lacks the range and precision limitations of the standard 32 and 64 bit numbers and arithmetic.

Three Ways to Perform Arbitrary Precision Integer Arithmetic in BASH

(1) BC

The following commands show how to raise two to an arbitrary power, an example of arbitrary precision arithmetic, at the bash shell prompt using the bc arbitrary precision calculator language. Note the need to enclose the arithmetic expression in single quotes. Note the use of the backtick MYVAR=`command` syntax to assign the results of the arithmetic to a bash variable.

Also, note that bc uses the caret ^ for raising to a power, not two asterisks — 2**128 for example — as in many computer languages including python and ruby discussed below.

Note that there should be no space between the variable name and the equal sign in the assignment, otherwise an error occurs.

bash$ echo '2^128' | bc -l
340282366920938463463374607431768211456

bash$ MYVAR=`echo '2^128' | bc -l`
bash$ echo $MYVAR
340282366920938463463374607431768211456

BC can be run interactively by typing:

bash$ bc -l
bc 1.06
Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'. 
2^128
340282366920938463463374607431768211456

BC does not have a built-in factorial function but one can be defined:

factorial

define factorial (n) { 
  if (n < 0) {
    print "ERROR: argument is less than zero";
    halt;
  }
  if (n < 2) return 1;
  return n*factorial(n-1);
}

The file factorial above with the definition of the factorial function can be passed to bc at the command line:

bash$ bc -l factorial
factorial(21)
51090942171709440000
factorial(1)
1
factorial(0)
1
factorial(-1)
ERROR: argument is less than zero

The factorial can be computed at the bash command line as follows:

bash$ echo 'factorial(21)' | bc -l factorial
51090942171709440000

(2) PYTHON

The following commands show how to raise two to an arbitrary power using the Python programming language at the bash prompt. Note the use of the backtick myvar=`command` syntax to assign the results of the arithmetic to a bash variable. Python is widely used and frequently already installed on Unix and Unix-like systems.

Note that there should be no space between the variable name and the equal sign in the variable assignment.

bash$ python -c 'print 2**128'
340282366920938463463374607431768211456

bash$ MYVAR=`python -c 'print 2**128'`

bash$ echo $MYVAR
340282366920938463463374607431768211456

This is how to compute a huge factorial in Python (using the Python math package):

bash$ python -c 'import math; print math.factorial(21);'
51090942171709440000

Python can be run interactively as follows:

bash$ python -i
Python 2.7.10 |Anaconda 2.1.0 (x86_64)| (default, May 28 2015, 17:04:42) 
[GCC 4.2.1 (Apple Inc. build 5577)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
Anaconda is brought to you by Continuum Analytics.
Please check out: https://continuum.io/thanks and https://binstar.org
>>> 2**128
340282366920938463463374607431768211456L

(3) RUBY

The following commands show how to raise two (2) to an arbitrary power using the Ruby programming language at the bash prompt. Note the use of the backtick myvar=`command` syntax to assign the results of the arithmetic to a bash variable. Ruby is widely used and sometimes already installed on Unix and Unix-like systems.

Note that there should be no space between the variable name and the equal sign in the variable assignment.


bash$ ruby -e 'print 2**128, "\n" '
340282366920938463463374607431768211456

bash$ MYVAR=`ruby -e 'print 2**128, "\n" '`

bash$ echo $MYVAR
340282366920938463463374607431768211456

Ruby can be run interactively using the irb command:

bash$ irb
irb(main):001:0> print 2**128
340282366920938463463374607431768211456=> nil
irb(main):002:0> 

RUBY does not have a built-in factorial function but you can define one:

factorial.rb

def factorial(n)
        if n<= 1
            1
        else
            n * factorial( n - 1 )
        end
end

The file factorial.rb with the definition of factorial can be pre-loaded into the interactive ruby as follows (note the “./” is IMPORTANT — DO NOT OMIT):

bash$ irb -r ./factorial.rb
irb(main):001:0> factorial(5)
=> 120
irb(main):002:0> factorial(21)
=> 51090942171709440000

This can be done non-interactively at the bash command prompt:

bash$ echo 'factorial(21)' | irb -r ./factorial.rb
Switch to inspect mode.
factorial(21)
51090942171709440000

or with:

bash$ echo 'print factorial(21), "\n"' | ruby -r ./factorial.rb
51090942171709440000

or with:

bash$ ruby -r ./factorial.rb -e 'print factorial(21), "\n"'
51090942171709440000

Conclusion

There are at least three ways to perform arbitrary precision integer arithmetic under the Unix or GNU Bourne Again Shell (bash), either at the command prompt or in shell scripts. These are the bc arbitrary precision calculator language, the python programming language, and the ruby programming language.

BC is the most likely to be pre-installed on a Unix system. BC performs both arbitrary precision integer and floating point arithmetic. Python is now fairly common. RUBY is becoming fairly common, but it is still not as common as Python in the author’s experience.

© 2016 John F. McGowan

About the Author

John F. McGowan, Ph.D. solves problems using mathematics and mathematical software, including developing gesture recognition for touch devices, video compression and speech recognition technologies. He has extensive experience developing software in C, C++, MATLAB, Python, Visual Basic and many other programming languages. He has been a Visiting Scholar at HP Labs developing computer vision algorithms and software for mobile devices. He has worked as a contractor at NASA Ames Research Center involved in the research and development of image and video processing algorithms and technology. He has published articles on the origin and evolution of life, the exploration of Mars (anticipating the discovery of methane on Mars), and cheap access to space. He has a Ph.D. in physics from the University of Illinois at Urbana-Champaign and a B.S. in physics from the California Institute of Technology (Caltech). He can be reached at jmcgowan11@earthlink.net.

One Response

  1. Quantum Mechanic October 1, 2017

Leave a Reply