{{ message }}

Instantly share code, notes, and snippets.

pichi/bignum_root.erl

Forked from jj1bdx/bignum_root.erl
Created Feb 2, 2010
 %% Power function (X ^ Y) and root function (X ^ (1/Y)) for %% integers in Erlang %% by Kenji Rikitake 26-JAN-2010 %% modified by Hynek Vychodil 2-FEB-2010 %% Distributed under MIT license at the end of the source code. -module(bignum_root). -export([power/2, root/2, sqrt/1]). %% computing X ^ Y power(X, Y) when is_integer(X), is_integer(Y), Y >= 0 -> power(X, Y, 1). power(_, 0, Acc) -> Acc; power(X, Y, Acc) when Y rem 2 =:= 1 -> power(X, Y - 1, Acc * X); power(X, Y, Acc) -> power(X * X, Y div 2, Acc). sqrt(X) -> root(X, 2). %% computing X ^ (1/Y) %% with Newton-Raphson method root(X, 1) when is_integer(X) -> X; root(X, 2) when is_integer(X), X > 0 -> sqrt(X, trunc(math:sqrt(X)) + 1); root(X, Y) when is_integer(X), X > 0, is_integer(Y), Y >= 2 -> % estimation of the root by the float calc E = trunc(math:exp(math:log(X) / Y)), root(X, Y, E + 1). root(X, Y, E) -> % Newton-Raphson method of solving (Y)th-root EP = power(E, Y - 1), Err = E * EP - X, E2 = E - Err div (Y * EP), if E2 =/= E -> root(X, Y, E2); Err > 0 -> E - 1; % Solve rounding error true -> E end. sqrt(X, E) -> % Newton-Raphson method of solving square root Err = E * E - X, E2 = E - Err div (2 * E), if E2 =/= E -> sqrt(X, E2); Err > 0 -> E - 1; % Solve rounding error true -> E end. %% MIT License: %% Copyright (c) 2010 by Kenji Rikitake. %% Copyright (c) 2010 by Hynek Vychodil. %% %% Permission is hereby granted, free of charge, to any person %% obtaining a copy of this software and associated documentation %% files (the "Software"), to deal in the Software without %% restriction, including without limitation the rights to use, %% copy, modify, merge, publish, distribute, sublicense, and/or sell %% copies of the Software, and to permit persons to whom the %% Software is furnished to do so, subject to the following %% conditions: %% %% The above copyright notice and this permission notice shall be %% included in all copies or substantial portions of the Software. %% %% THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, %% EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES %% OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND %% NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT %% HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, %% WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING %% FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR %% OTHER DEALINGS IN THE SOFTWARE.

pichi commented Jan 3, 2014

 https://gist.github.com/jj1bdx/293169 has improved root estimation for numbers bigger than 10^300.