 # A uLisp extension for arbitrary-precision arithmetic

#1

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.

uLisp on the Raspberry Pico W: higher precision?
#2

I think it’s a good addition. Support for big numbers is one of the appealing features of Lisp.

#3

hi,

amazing job with uLisp! thanks for making this amazing project.

i tried compiling this in Teensyduino for Teensy 4.1 and got the below errors.

any help appreciated thanks :)

Bignums:563: error: redefinition of ‘tbl_entry_t* tables []’
563 | tbl_entry_t tables[] = {lookup_table, lookup_table2};
| ^~~~~~
/Users/dave/Documents/LISP/uLisp/installs/ARM-4-4c/ulisp-arm/ulisp-arm.ino:6529:14: note: 'tbl_entry_t
tables ’ previously defined here
6529 | tbl_entry_t tables[] = {lookup_table, NULL};
| ^~~~~~
Bignums:564: error: redefinition of ‘const unsigned int tablesizes []’
564 | const unsigned int tablesizes[] = { arraysize(lookup_table), arraysize(lookup_table2) };
| ^~~~~~~~~~
/Users/dave/Documents/LISP/uLisp/installs/ARM-4-4c/ulisp-arm/ulisp-arm.ino:6530:20: note: ‘const unsigned int tablesizes ’ previously defined here
6530 | const unsigned int tablesizes[] = { arraysize(lookup_table), 0 };
| ^~~~~~~~~~
Bignums:566: error: redefinition of 'tbl_entry_t
table(int)’
566 | const tbl_entry_t *table (int n) {
| ^~~~~
/Users/dave/Documents/LISP/uLisp/installs/ARM-4-4c/ulisp-arm/ulisp-arm.ino:6532:20: note: ‘tbl_entry_t* table(int)’ previously defined here
6532 | const tbl_entry_t *table (int n) {
| ^~~~~
Bignums:570: error: redefinition of ‘unsigned int tablesize(int)’
570 | unsigned int tablesize (int n) {
| ^~~~~~~~~
/Users/dave/Documents/LISP/uLisp/installs/ARM-4-4c/ulisp-arm/ulisp-arm.ino:6536:14: note: ‘unsigned int tablesize(int)’ previously defined here
6536 | unsigned int tablesize (int n) {
| ^~~~~~~~~
Bignums:566: warning: ‘tbl_entry_t* table(int)’ defined but not used
566 | const tbl_entry_t *table (int n) {
| ^~~~~
redefinition of ‘tbl_entry_t* tables []’

#4

Did you uncomment the directive at the start of the uLisp source?

``````// #define extensions
``````

If you get it working on Teensy 4.1 I’d be interested in how quickly it runs the examples.

#5

thanks, that fixed it. here are some quick tests:

factorial =>

59911> (time (\$bignum-string (\$fact 100)))
“93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000”
Time: 16 ms

59911> (time (\$bignum-string (\$fact 500)))
“1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000”
Time: 5.4 s

59911> (time (\$bignum-string (\$fact 1000)))
“402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000”
Time: 67.0 s

expt =>

59846> (time (\$bignum-string (\$expt 7 160)))
“1643184774938171857917000410556544806341837419599523497069764671233207565562287891877564323818254449486910838997871467298047369612896001”
Time: 12 ms

59846> (time (\$bignum-string (\$expt 9 999)))
“194207916858072401073330513240517841169895831937243168645765334645631807358586165476831829984964567897289883410682808509863485381763945405279379355788182053541434708898886353264614403164257835946591015853500491562156765579388944516423770646547300211711400609344237550775485394558425026601257627110879613741893863295847627378504481736441703291029360564416718984718052676789493826372811349572386149787861703350363229770343522164432121091627871310618608734044108407173015970850780786711471108639762810760748899301375323974504010469298672123113693793242558662498267897607159946316136440215024585534972601864730717278590674861331708227340510282977338127859756479389076075528672989549862138485404935127984793120586289288424045660573066638008624179879066798350622453419082976217706653276687992598885030141711458658381360884807741768071789239593772708382532520992894115725948613681993478965648216640862698897925988931145600683858128653568049999074868783790048889”
Time: 3.2 s

square root =>

59752> (time (\$bignum-string (\$sqrt (\$string-bignum “152415787532388367501905199875019052100”))))
“12345678901234567890”
Time: 2 ms

#6

That’s pretty fast! Thanks.

#7

There’s a more detailed description of the arbitrary-precision arithmetic routines here:

Arbitrary-precision arithmetic extension

I’d welcome any suggestions for improvements!

#8

Here’s a function that uses the arbitrary-precision arithmetic extension to factorise large numbers, using Pollard’s rho algorithm:

``````(defun \$gcd (a b)
(let (temp)
(loop
(when (\$zerop b) (return a))
(setq temp b b (\$mod a b) a temp))))

(defun \$pollard-rho (n)
(let* ((\$1 (\$bignum 1))
(x (\$bignum 2))
(y (\$bignum 2))
(d (\$bignum 1))
(\$g (lambda (x) (\$mod (\$+ (\$* x x) \$1) n))))
(loop
(unless (\$= d \$1) (return))
(setq x (\$g x))
(setq y (\$g (\$g y)))
(setq d (\$gcd (if (\$> x y) (\$- x y) (\$- y x)) n)))
(if (\$= d n) nil d)))
``````

For example, it takes 10 minutes on an ATSAMD51 board to find the smallest factor of the ninth Fermat number, which has 155 digits and is:

13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097

Here’s the definition of fermat (it needs expt defined earlier):

``````(defun \$fermat (n) (\$+ (\$expt 2 (expt 2 n)) (\$bignum 1)))
``````

and here’s the factor:

``````> (time (\$bignum-string (\$pollard-rho (\$fermat 9))))
"2424833"
Time: 607.9 s
``````

#9

this thread really takes me back to my undergrad days 89-93 learning functional languages, we did some Lisp, but mainly it was ML. one of our assignments was implementing something like this for arbitrary arithmetic, although i cant remember how we did it…

these tests & previous ones for teensy 4.1 are at 600mhz. have done these ones with 3 optimizations. i did have a go overclocking, but i’m not convinced the teensy is stable for overclocking yet, so i’ll keep at 600mhz for now, as i only have the one unit.

note how on teensy “fastest” is not as fast as “faster”… which seems like strange terminology :) also done ItsyBItsy M4 120mhz with 3 optimizations. note these optimizations are in the order listed in Arduino/Teensyduino IDE to make it easier for anyone looking at the menu.

Teensy 4.1 =>

Mersenne primes
(time (mersenne))
snipped long output

“faster”
Time: 1.4 s
“fast”
Time: 3.0 s
“fastest”
Time: 1.5 s

Fermat
58413> (time (\$bignum-string (\$pollard-rho (\$fermat 9))))
“2424833”

“faster”
Time: 46.4 s
“fast”
Time: 92.5 s
“fastest”
Time: 47.5 s

ItsyBitsy M4 =>

Mersenne primes

“fast” (-02)
Time: 13.5 s
“faster” (-03)
Time: 10.1 s
“fastest” (-0fast)
Time: 9.7 s

Fermat

“fast” (-02)
Time: 421.8 s
“faster” (-03)
Time: 329.7 s
“fastest” (-0fast)
Time: 321.3 s

i probably should have done those as a table… the ItsyBitsy is a SAMD51 and my times are quite different though. what did you run your tests / examples on?

the only difference i can think though is i’ve manually typed in the " and \ chars to get it into my LispLibrary.h, which is pasted below to save folks the typing.

i’m working on some lisp code at the moment and converting it over to uLisp to put in the LispLibrary.h is getting a bit time consuming manually typing the conversion. what would be great for us is a pre-processor or a little script example that could take already written lisp code and add the " chars and put in any needed escape chars … anyway, one to think about, unfortunately not something i have time to investigate at the moment :)

for the LispLibrary.h with " and \ chars added =>

“(defun \$fact (n)”
" (let ((\$result (\$bignum 1)))"
" (dotimes (i n \$result)"
" (setq \$result (\$* \$result (\$bignum (1+ i)))))))"

“(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)))))"

“(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))"

“(defun mersenne ()”
" (dolist (m '(2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203))"
" (let ((\$p (\$- (\$expt 2 m) (\$bignum 1))))"
" (format t “~4a ~a~%” m (\$bignum-string \$p)))))"

“(defun \$gcd (a b)”
" (let (temp)"
" (loop"
" (when (\$zerop b) (return a))"
" (setq temp b b (\$mod a b) a temp))))"

“(defun \$pollard-rho (n)”
" (let* ((\$1 (\$bignum 1))"
" (x (\$bignum 2))"
" (y (\$bignum 2))"
" (d (\$bignum 1))"
" (\$g (lambda (x) (\$mod (\$+ (\$* x x) \$1) n))))"
" (loop"
" (unless (\$= d \$1) (return))"
" (setq x (\$g x))"
" (setq y (\$g (\$g y)))"
" (setq d (\$gcd (if (\$> x y) (\$- x y) (\$- y x)) n)))"
" (if (\$= d n) nil d)))"

“(defun \$fermat (n) (\$+ (\$expt 2 (expt 2 n)) (\$bignum 1)))”

#10

another quick test. pretty respectable on the Raspberry Pi Pico [M0+ 133mhz]

Mersenne primes
(-0)
Time: 20.1 s
(-02)
Time: 12.7 s
(-03)
Time: 12.5 s
(-0fast)
Time: 12.0 s

Fermat
(-0)
Time: 637.1 s
(-02)
Time: 416.0 s
(-03)
Time: 427.3 s
(-0fast)
Time: 410.7 s

#11

i got these interesting results from Adafruit Neo Trinkey [M0+ 48mhz]

Mersenne primes

2 3

3 7

5 31

7 127

13 8191

17 131071

19 524287

31 2147483647

61 2305843009213693951

89 618970019642690137449562111

107 162259276829213363391578010288127

127 170141183460469231731687303715884105727

521 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151

607 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127

Error: ‘\$*’ no room

this was quite a challenge for it, just over an hour, i was just about to kill it :)
Fermat
Time: 3786.9 s

#12

the ItsyBitsy is a SAMD51 and my times are quite different though. what did you run your tests / examples on?

I used the Adafruit SAMD Boards core version 1.7.2, and I see that the core is now at version 1.7.11. Also, I left the Optimize setting at Small (-Os) (standard).

I’ll try the other settings, and the latest version of the core, and report back.

#13

http://www.ulisp.com/show?1FHA

(time (fac 26))
403291461126605635584000000

Time: 1.3 s

anything larger gives a stack overflow.

(time (iex 2 64))
18446744073709551616

Time: 2.0 s

bonus extra to see what was the highest from 9 before a stack overflow
(time (iex 9 31))
381520424476945831628649898809

Time: 2.1 s

highest iex possible before stack overflow in the Mersenne listing:

(time (iex 2 127))
170141183460469231731687303715884105728

Time: 3.8 s

#14

the ItsyBitsy is a SAMD51 and my times are quite different though. what did you run your tests / examples on?

@clob Yes, I get closer to your timings if I use the Optimize settings.