image thumbnail

Variable Precision Integer Arithmetic

version 1.45 (2.86 MB) by John D'Errico
Arithmetic with integers of fully arbitrary size. Arrays and vectors of vpi numbers are supported.

16.9K Downloads

Updated 27 Jan 2015

View License

Editor's Note: This file was selected as MATLAB Central Pick of the Week

Every once in a while, I've wanted to do arithmetic with large integers with magnitude exceeding that which can fit into MATLAB's standard data types. Since I don't have the symbolic toolbox, the simple solution was to write it in MATLAB. I did that in these tools which are entirely written in MATLAB, so there is no need for compiled code.
Arithmetic is simple with the vpi tools.
A = vpi(17)^17
ans =
827240261886336764177

17 + A^17
ans =
39786732894291535047752038041559739510060813980024082
30012867731573722066105737100731556603857745946047229
53759676529121155309750944582301597489457676380805029
59227566911971103003303064782118652210655457390045806
99039190393572334521701109889855832341416056005878848
49943142324389193616484809157960034059531548585473213
36465170635561696613297503569949729314

There are also a few nice add ons, for example a tool to compute exact binomial coefficients for large arguments, or large factorials, or convert binary numbers with thousands of digits to decimal (vpi) form.

For example, the existing nchoosek function in matlab gets upset for even reasonably small binomial coefficients.

nchoosek(100,50)
Warning: Result may not be exact. Coefficient is greater than 1.000000e+15
and is only accurate to 15 digits.
> In nchoosek at 66
ans =
1.0089e+29

However, nchoosek has no such issues on vpi numbers.

nchoosek(vpi(100),50)
ans =
100891344545564193334812497256

Similarly, the computation of factorial(171) will cause an overflow. While I'll admit that there are many good ways to avoid this problem, the factvpi function has no problems at all.

factorial(171)
ans =
Inf

factorial(vpi(171))
ans =
12410180702176678234248405241031039926166055775016931
85388951803611996075221691752992751978120487585576464
95950167038705280988985869071076733124203221848436431
04735778899685482782907545415619648521534683180442932
39598173696899657235903947616152278558180061176365108
428800000000000000000000000000000000000000000

There are now GCD and LCM tools, both of which can accept more than two input arguments.

lcm(vpi(123452356),12344332,65364467)
ans =
3557547184310976844988

I've also put in some tools that can test for primality. For example, the Mersenne prime:

p = vpi(2)^127 - 1
ans =
170141183460469231731687303715884105727

isprime(p)
ans =
1

Factoring of vpi numbers is now implemented.

factor(vpi('1234567890123456789'))
ans =
3 3 101 3541 3607 3803 27961

Vectors or arrays of vpi numbers work very nicely now.

A = vpi(eye(3))*3 + 1
A =
4 1 1
1 4 1
1 1 4

A^17
ans =
5642305908354 5642176768191 5642176768191
5642176768191 5642305908354 5642176768191
5642176768191 5642176768191 5642305908354

Dozens of other tools are also included. I've even included a tool just for fun that will convert a number into a readable text version of it as a large integer.

vpi2english(vpi('12000000110022987'))
ans =
twelve quadrillion, one hundred ten million, twenty two thousand, nine hundred eighty seven

For those Project Euler solvers around, vpi makes many of the problems easy to solve.

Addenda - Ben Petschel has graciously given me code for unique and sortrows operations on vpi arrays. Many thanks to Ben!

Cite As

John D'Errico (2021). Variable Precision Integer Arithmetic (https://www.mathworks.com/matlabcentral/fileexchange/22725-variable-precision-integer-arithmetic), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2007b
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

VariablePrecisionIntegers/html/