[erlang-questions] Integer square root
Bob Ippolito
bob@REDACTED
Tue Jan 26 02:46:00 CET 2010
On Mon, Jan 25, 2010 at 5:26 PM, Kenji Rikitake <kenji.rikitake@REDACTED> wrote:
> Very long time ago I was trying to solve the square root
> problem, but I didn't because handling in the float numbers
> gave the sufficient precision for me.
>
> In general, a quick method of
> solving X when Y = X * X and Y is given (X, Y are bignums) as:
>
> 1) Obtain approximation of X by float sqrt of Y
> separately to significand and exponent
> (note: IEEE754 format has its own limits in
> the digits of exponent too)
>
> 2) applying Newton-Raphson method so that
> Xnew = (X + (Y / X)) / 2
>
> 3) Repeat finding Xnew on 2) until Xnew =:= X
>
> Things you need to invent:
>
> * bignum integer dividing program
> (bignum / bignum -> bignum (+ remainder, maybe))
> (This is NOT provided by Erlang)
Sure it is, div and rem work with bignums. Not sure about how
efficient it is relative to other bignum implementations but it works.
-bob
More information about the erlang-questions
mailing list