[erlang-questions] Integer square root

[Bob Ippolito]

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