## Erlang Integers

Mark Mzyk | February 5, 2008

In my spare time, what little of it there seems to be, I’ve been working my way through the Crosswalk (Programming Erlang). I’m finding Erlang to be a fascinating language, particularly since it is also serving as my introduction to functional programming. One paragraph in particular caught my eye. On page 15, Joe Armstrong writes this:

Erlang uses arbitrary-sized integers for performing integer arithmetic. In Erlang, integer arithmetic is exact, so you don’t have to worry about arithmetic overflows or not being able to represent an integer in a certain word size.

And then Joe moves on to the next topic, like this is no big deal. Wait, you mean I don’t have to wonder if something is greater than the max int?

In fact, the only thing that limits an integer’s size is the amount of memory available on the system. Why isn’t an abstraction like this more wide spread? Why is it still necessary in so many languages for the programmer to have to worry about the max int size? Maybe this is more wide spread and I’m just not knowledgeable enough to know it.

My other thought was how does Erlang achieve this? Well, thanks to my lurking on the Erlang questions mailing list I discovered the answer: Bignum arithmetic. I had never heard of it before, but it’s one of those concepts that seems so intuitive after you read about it, you wonder why you never questioned that an int had to be confined to X number of bytes.

You never know what surprises await when you decide to learn a new programming language.

Filed in: Languages.

Python has this too: if a whole number value grows past the native integer size, it promotes it to a long integer; and http://docs.python.org/lib/typesnumeric.html states that “Long integers have unlimited precision.”

Yeah.. Ruby does this too… Fixnum gets promoted to Bignum.

Arbitrary-sized integer is nice but poorly supported in Erlang.

If one only uses additions or multiplications its okay but

integer power arithmetic operation is not supported. So it

is untrue to say that Erlang can do integer arithmetic of

arbitrary length integers. Even worse, it does not warns you

when it produces a wrong answer. Try the following:

1> math:pow(2,55).

36028797018963970.0

Obviously no integral power of 2 can end by 0.

All integral powers of 2 larger than 55 will give you a result

ending by zero. This is because Erlang has not implemented

an integer power function and relies on a float pow(x,y) function.

This is why the result is a float. Actually it is an IEEE-754 float

number in decimal64 format which means it has a maximum

precision of 16 digits.

Many applications dealing with large integers require true

large integer arithmetic (including power), for example

cryptology applications routinely do arithmetic modular

power operations on very large integers. Though Erlang

allows to write arbitrary large integers and do some basic

operations it surely cannot be said to support arlitrary large

integer arithmetic. For that, one can use mathematica (does

arbitrary large float arithmetic as well) or specialized packages

such as simod/modsim.

Thanks Nic. I didn’t realize there were limitations in Erlang based around this. I wonder now if other languages face the same issues, and if so, which ones.

indeed, all the math functions are based on float operations and not integer because they need float … except for the pow function

However, writing a function that is based on integer operations is almost trivial for exponentiation. Here follows an Erlang implementation of the so called “Right-to-left binary method for exponentiation” in TAOCP volume 2, pg 462.

-module(power).

-compile([pow_bin/2]).

pow_bin(X, N) ->

pow_bin(X, N, 1).

pow_bin(X, N, Acc) when (N rem 2) =:= 0 ->

pow_bin(X * X, N div 2, Acc);

pow_bin(X, N, Acc) ->

NewAcc = Acc * X,

case N div 2 of

0 ->

NewAcc;

_ ->

pow_bin(X * X, N div 2, Acc * X)

end.

Its running complexity is O(lg n) which works pretty well to compute x^n when n is large.

Interesting example Sebastien. I’ve been meaning to pick up The Art of Computer Programming for a while now. This gives me more incentive to do so.

Of course, powers of two are even easier, because you can use the bit shift operator, which does work for big ints.

1> math:pow(2, 55).

36028797018963970.0

2> 1 bsl 55.

36028797018963968

Another phenomenon that can be surprising (it actually mystified me until I read the comments on this blog and experimented some more) is what happens when an integer gets so large that it doesn’t fit into an IEEE-754 float. For instance, I wrote this code for computing binomial coefficients, and logarithms of binomial coefficients:

-module(comb).

-export([binom/2, log_binom/2]).

binom(N, K) when K > N-K ->

binom(N, N-K);

binom(N, K) ->

binom(K, N-K+1, 1, 1).

binom(0, _I, _J, R) ->

R;

binom(M, I, J, R) ->

binom(M-1, I+1, J+1, R * I div J).

log_binom(N, K) when K > N-K ->

log_binom(N, N-K);

log_binom(N, K) ->

log_binom(K, N-K+1, 1, 0).

log_binom(0, _I, _J, R) ->

R;

log_binom(M, I, J, R) ->

log_binom(M-1, I+1, J+1, R + math:log(I) – math:log(J)).

As a sanity check, I verified that math:log(comb:binom(1000, 500)) produces the same result as comb:log_binom(1000, 500), but when I tried math:log(comb:binom(10000, 5000)), I got “bad argument in an arithmetic expression in function math:log/1″.