May 24, 2008

Handling very large integers in Erlang

Posted in erlang development tagged , , , , , , , , , , at 5:03 pm by tetontech

As mentioned in a previous post, Erlang appears to handle very large integers whose limit is RAM and other hardware limitations of the machine. In fact I have calculated 50,000! several times on my machine.
Multiplication, subtraction, and addition all work with these numbers without any programmer interference in Erlang. Division and other functionality uses the underlying OS functionality and so do not work with these large numbers.
I have written some code that allows division to work with these large numbers as well as a few other items such as m_choose_n, factorial, and floor. I have not spent time to evaluate speed optimizations for the code other than to use bit shifting to handle the actual division.
The division functions are:

  1. big_rem – similar to mod. It returns only the remainder of the division
  2. big_div_with_rem – returns both an integer quotient and remainder
  3. big_divide – returns a floating point value if it is possible to calculate it or an integer quotient and remainder if it is not possible

The code below is part of my simulation engine written in Erlang and is used in conjunction with the sim_dist library that contains random number distribution streams such as normal, binomial, negative binomial, and other types of streams the code for which will become available on sourceforge when I have finished testing it.
%% Copyright 2008 Lee S. Barney

%% This file is part of erl_sim.

%% erl_sim is free software: you can redistribute it and/or modify
%% it under the terms of the GNU Lesser General Public License as published by
%% the Free Software Foundation, either version 3 of the License, or
%% (at your option) any later version.
%%
%% erl_sim is distributed in the hope that it will be useful,
%% but WITHOUT ANY WARRANTY; without even the implied warranty of
%% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
%% GNU Lesser General Public License for more details.
%%
%% You should have received a copy of the GNU Lesser General Public License
%% along with QuickConnectiPhoneHybrid. If not, see http://www.gnu.org/licenses/.
%% Description: This file contains functions for doing division with very large numbers as well as some other
%% useful functions
-module(sim_math).

%%
%% Include files
%%

%%
%% Exported Functions
%%
-export([big_divide/2, big_div_with_rem/2, big_rem/2, floor/1,
factorial/1, m_choose_n/2]).

%%
%% API Functions
%%

%%
%% TODO: Add description of div_with_rem/function_arity
%%
big_div_with_rem(Dividend, Divisor) ->
if
Divisor /= 0 ->
{ok,New_divisor,Cnt} = count_div_shifts(abs(Dividend), abs(Divisor), 0),
case big_div_with_rem_helper(abs(Dividend), abs(New_divisor),Cnt,0) of
{ok, Quotient, Remainder} when (Dividend < 0) xor (Divisor
{ok,-Quotient,-Remainder};
{ok, Quotient, Remainder} ->
{ok, Quotient, Remainder};
{error,Why} ->
{error,Why};
true ->
{error,"Unknown error"}
end;
true ->
{error,"Division by Zero error"}
end.

%%
%% TODO: Add description of big_divide/function_arity
%%
big_divide(Dividend, Divisor)->
%double limit. Erlang uses underlying system algorithms for floating point mathematics
Limit = math:pow(2,1023),
case big_div_with_rem(Dividend, Divisor) of
{ok,Quotient,Remainder} ->
if
Remainder == 0 ->
{ok, Quotient};

%the quotient must be less than the limit or else and error will happen
%when the result floating point value is added to it
%the remainder and the divisor must be less than the limit or else the
%division will fail.

Remainder < Limit andalso Divisor < Limit andalso Quotient
Result = Remainder/abs(Divisor),
io:format("Remainder/Divisor:~p Quotient:~p~n",[Result,Quotient]),
{ok, Quotient+Result};
true ->
{ok, Quotient,Remainder}
end;
{error,Why} ->
{error,Why}
end.

%%
%% TODO: Add description of big_rem/function_arity
%%
big_rem(A, B) ->
if
B /= 0 ->
{ok,New_divisor,Cnt} = count_div_shifts(abs(A), abs(B), 0),
case big_div_with_rem_helper(abs(A), abs(New_divisor),Cnt,0) of
{ok, Quotient, Remainder} when (A < 0) xor (B
{ok,-Remainder};
{ok, Quotient, Remainder} ->
{ok, Remainder};
{error,Why} ->
{error,Why};
true ->
{error,"Unknown error"}
end;
true ->
{error,"Division by Zero error"}
end.

%%
%% TODO: Add description of floor/function_arity
%%
floor(X) ->
T = trunc(X),
case X - T T - 1;
false -> T
end.

%factorial of N

factorial(N) ->
fact_helper(N, 1).

fact_helper(0, Product) ->
Product;
fact_helper(1, Product) ->
Product;
fact_helper(N, Product) ->
%io:format("N: ~p Product: ~p~n",[N, Product]),
fact_helper(N - 1, Product * N).

m_choose_n(M,N) ->
if
N > M orelse N < 0 orelse M 0;
true ->
factorial(M)/(factorial(N)*factorial(M-N))
end.

%%
%% Local Functions
%%
big_div_with_rem_helper(Dividend, Divisor, Count, Quotient) ->
%io:format("Dividend:~p Divisor:~p Count:~p~n",[Dividend, Divisor, Count, Quotient]),
if
Count
{ok, Quotient, Dividend};
true ->
if
Divisor =
big_div_with_rem_helper(Dividend-Divisor, Divisor bsr 1, Count-1, (Quotient bsl 1) +1);
true ->
big_div_with_rem_helper(Dividend, Divisor bsr 1, Count -1, Quotient bsl 1)
end
end.

count_div_shifts(Dividend, Divisor, Cnt) ->
if
Divisor =
count_div_shifts(Dividend, Divisor bsl 1, Cnt+1);
true ->
{ok,Divisor bsr 1, Cnt -1}
end.

Advertisements

3 Comments »

  1. Per Gustafsson said,

    Erlang has div and rem operators that work on bignums e.g.

    9> F = fun(1,_F2) -> 1; (X,F2) -> X * F2(X-1, F2) end, Fac = fun(X) -> F(X,F) end.
    #Fun
    10> Fac(1000) div Fac(999).
    1000
    11> Fac(1000) rem Fac(999).
    0

  2. tetontech said,

    Yes. I agree with Per that Erlang does have the div and rem operators. They do not however supply a floating point solution when it is possible to do so nor are both the quotient and the remainder available from a single call. In the example source code I should have pointed this out and failed to do so. I also thought that it would be interesting to see how the C library code that is usually used would port to Erlang. I am comparing the speed of the code in this post against the built in div and rem operators and will report this in a later post. I’m sure this code will be slower since the Erlang programmers surely did something similar and it will run natively compiled.

    Thank you Per.

    Since my post was obviously confusing in this respect I apologize.

  3. tetontech said,

    As Per and I expected the code in the main post is much slower than using the div and rem methods. The code below has been modified to be production code.

    %% Copyright 2008 Lee S. Barney

    %% This file is part of erl_sim.

    %% erl_sim is free software: you can redistribute it and/or modify
    %% it under the terms of the GNU Lesser General Public License as published by
    %% the Free Software Foundation, either version 3 of the License, or
    %% (at your option) any later version.
    %%
    %% erl_sim is distributed in the hope that it will be useful,
    %% but WITHOUT ANY WARRANTY; without even the implied warranty of
    %% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    %% GNU Lesser General Public License for more details.
    %%
    %% You should have received a copy of the GNU Lesser General Public License
    %% along with QuickConnectiPhoneHybrid. If not, see http://www.gnu.org/licenses/.
    %% Description: This file contains functions for doing division with very large numbers as well as some other
    %% useful functions
    -module(sim_math).

    %%
    %% Include files
    %%

    %%
    %% Exported Functions
    %%
    -export([big_divide/2, div_with_rem/2, floor/1,
    factorial/1, m_choose_n/2]).

    %%
    %% API Functions
    %%

    %%
    %% TODO: Add description of div_with_rem/function_arity
    %%
    div_with_rem(Dividend, Divisor) ->
    if
    Divisor /= 0 ->
    {ok, Dividend div Divisor, Dividend rem Divisor};
    true ->
    {error,"Division by Zero error"}
    end.

    %%
    %% TODO: Add description of big_divide/function_arity
    %%
    big_divide(Dividend, Divisor)->
    %double limit. Erlang uses underlying system algorithms for floating point mathematics
    Limit = math:pow(2,1023),
    case div_with_rem(Dividend, Divisor) of
    {ok,Quotient,Remainder} ->
    if
    Remainder == 0 ->
    {ok, Quotient};

    %the quotient must be less than the limit or else and error will happen
    %when the result floating point value is added to it
    %the remainder and the divisor must be less than the limit or else the
    %division will fail.

    Remainder < Limit andalso Divisor < Limit andalso Quotient
    Result = Remainder/abs(Divisor),
    %io:format("Remainder/Divisor:~p Quotient:~p~n",[Result,Quotient]),
    {ok, Quotient+Result};
    true ->
    {ok, Quotient,Remainder}
    end;
    {error,Why} ->
    {error,Why}
    end.

    %%
    %% TODO: Add description of floor/function_arity
    %%
    floor(X) ->
    T = trunc(X),
    case X - T T - 1;
    false -> T
    end.

    %factorial of N

    factorial(N) ->
    fact_helper(N, 1).

    fact_helper(0, Product) ->
    Product;
    fact_helper(1, Product) ->
    Product;
    fact_helper(N, Product) ->
    %io:format("N: ~p Product: ~p~n",[N, Product]),
    fact_helper(N - 1, Product * N).

    m_choose_n(M,N) ->
    if
    N > M orelse N < 0 orelse M 0;
    true ->
    factorial(M)/(factorial(N)*factorial(M-N))
    end.

    %%
    %% Local Functions
    %%


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: