This is a small arbitrary-precision extension for uLisp, for calculating with large integers. It is designed to work on any 32-bit uLisp platform. To add these functions:
- Uncomment #define extensions at the start of the main uLisp source file.
- Compile and upload uLisp with the file Bignums.ino included in the same folder as the uLisp source file for your platform.
The bignum functions will then be added to the built-in functions in uLisp.
Here is the Bignums Extension: Bignums.ino.
Or get it from GitHub at: https://github.com/technoblogy/ulisp-bignums.
Introduction
I’ve been trying to think of a good example to test the new Extensions File feature introduced in uLisp Release 4.4, and thought it would be interesting to add an arbitrary precision package.
It’s similar in function to the uLisp example program Infinite precision arithmetic, but with the following differences:
- It’s written in C, so faster.
- Numbers are packed as efficiently as possible, 32 bits per Lisp object.
- It supports a wider range of functions, including division, modulus, comparisons, and bitwise logical functions.
It was inspired by Kokke’s tiny-bignum-c library on GitHub; his clearly-written routines made me hopeful that this was a project I could complete in a weekend. My library follows the logic of his routines, but rewritten to use uLisp lists rather than C arrays for storing the bignums.
My aim was to make the functions simple to understand, rather than optimising the routines. In particular, I know there are clever ways to improve the bignum multiplication and division; this is left as an exercise for the reader. One of the slowest operations is using $bignum-string to convert a bignum to decimal, because it needs to perform repeated divisions.
Even if you’re not interested in arbitrary-precision arithmetic, but would like to make your own extensions to uLisp, this example should be useful in showing:
- How to interface C routines with uLisp.
- How to build a list within a C function.
- How to construct a uLisp string from within a C function.
- How to call the garbage collector from C.
I’ve included detailed comments to explain non-obvious features.
Approach
This set of uLisp functions use uLisp lists to represent bignums, and takes advantage of the list handling and garbage collection to allow you to work with arbitrarily large numbers, limited only by the amount of Lisp workspace.
The bignum versions of the uLisp functions have the same names as their integer equivalents, but with a ‘$’ prefix. The library provides the following functions:
| Function | Description |
|---|---|
| ($bignum int) | Converts an integer to a bignum. |
| ($integer bignum) | Converts a bignum to an integer. |
| ($bignum-string bignum [base]) | Converts a bignum to a string; the base is 10 (default) or 16. |
| ($string-bignum bignum [base]) | Converts a string to a bignum; the case is 10 (default) or 16. |
| ($zerop bignum) | Tests whether a bignum is zero, allowing for trailing zeros. |
| ($+ bignum1 bignum2) | Adds two bignums and returns the sum as a new bignum. |
| ($- bignum1 bignum2) | Subtracts two bignums and returns the difference as a new bignum. |
| ($* bignum1 bignum2) | Multiplies two bignums and returns the product as a new bignum. |
| ($/ bignum1 bignum2) | Divides two bignums and returns the quotient as a new bignum. |
| ($mod bignum1 bignum2) | Divides two bignums and returns the remainder as a new bignum. |
| ($= bignum1 bignum2) | Returns t if the two bignums are equal. |
| ($< bignum1 bignum2) | Returns t if bignum1 is less than bignum2. |
| ($> bignum1 bignum2) | Returns t if bignum1 is greater than bignum2. |
| ($logand bignum1 bignum2) | Returns the logical AND of two bignums. |
| ($logior bignum1 bignum1) | Returns the logical inclusive OR of two bignums. |
| ($logxor bignum1 bignum2) | Returns the logical exclusive OR of two bignums. |
| ($ash bignum shift) | Returns bignum shifted by shift bits; positive means left. |
Implementation
Representation
The bignums are represented using standard lists of 32-bit integers. They are packed as efficiently as possible, 32 bits per Lisp object, with the least significant word of a bignum stored in the head or car of the list, and the most significant word in the tail. For example, the following list represents 3 + 17 x 2^32, or 73014444035:
'(3 17)
Garbage collection
Some of the C functions in this arbitrary-precision arithmetic package build temporary lists to hold bignums used during the calculations. Because garbage collection doesn’t occur automatically in C functions, as it does when executing Lisp code, it’s possible for a “no room” error to occur even when there’s plenty of workspace. The solution is to manually call the garbage collector within the C functions. To reduce the time overhead of garbage collections the package includes a function maybe_gc() which only performs a garbage collection if less than 1/16th of the workspace remains.
Examples
In the following examples I’ve followed the convention that variables representing bignums are prefixed with ‘$’, although this isn’t required. The timings were all obtained on an ATSAMD51 board (Adafruit ItsyBitsy M4 Express).
Factorial
The following routine $fact returns the factorial of an integer as a bignum:
(defun $fact (n)
(let (($result ($bignum 1)))
(dotimes (i n $result)
(setq $result ($* $result ($bignum (1+ i)))))))
For example, to find factorial 100 and return it as string representing a decimal number:
> (time ($bignum-string ($fact 100)))
"933262154439441526816992388562667004907159682643816214685929638952175999932299156089
41463976156518286253697920827223758251185210916864000000000000000000000000"
Time: 233 ms
Exponent
The following routine $expt finds x^y for integer x and y:
(defun $expt (x y)
(let (($e ($bignum 1))
($f ($bignum x)))
(loop
(when (zerop y) (return $e))
(when (oddp y) (setq $e ($* $e $f)))
(setq $f ($* $f $f) y (ash y -1)))))
For example, to find 7^160:
> (time ($bignum-string ($expt 7 160)))
"164318477493817185791700041055654480634183741959952349706976467123320756556228789187
7564323818254449486910838997871467298047369612896001"
Time: 153 ms
Square root
The following routine $sqrt calculates the square root of a bignum using the Newton–Raphson method:
(defun $sqrt ($a)
(let* (($1 ($bignum 1))
($high $a)
($low ($bignum 0))
($mid ($+ ($ash $high -1) $1)))
(loop
(unless ($> $high $low) (return))
(if ($> ($* $mid $mid) $a)
(setq $high ($- $mid $1))
(setq $low $mid))
(setq $mid ($+ ($+ $low ($ash ($- $high $low) -1)) $1)))
$low))
For example:
> (time ($bignum-string ($sqrt ($string-bignum "152415787532388367501905199875019052100"))))
"12345678901234567890"
Time: 32 ms
Further suggestions
The library could be modified to run on 8/16-bit versions of uLisp by making the fundamental building block of bignums uint16_t rather than uint32_t.
I was planning to use the package to write a Lisp example to calculate pi to a large number of digits, but ran out of time. Perhaps someone would like to contribute this. For a good summary of the available algorithms see Meet π on Guy Fernando’s i4cy.com site.