[ Content | View menu ]

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.

7 Comments

  1. Comment by P O'Grady:

    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.”

    February 5, 2008 @ 16:10
  2. Comment by Ben:

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

    February 6, 2008 @ 00:58
  3. Comment by Nic:

    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.

    January 12, 2009 @ 17:28
  4. Comment by Mark:

    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.

    January 12, 2009 @ 23:25
  5. Comment by Sebastien Tandel:

    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.

    February 25, 2012 @ 12:10
  6. Comment by Mark Mzyk:

    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.

    February 27, 2012 @ 09:47
  7. Comment by njlarsson:

    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″.

    April 30, 2012 @ 06:11