[erlang-questions] Integer square root

Angel Alvarez <>
Tue Jan 26 09:56:46 CET 2010


El Martes, 26 de Enero de 2010 02:26:47 Kenji Rikitake escribió:
> 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)
> 
> FYI
> Kenji Rikitake 

In fact after Richard's call of atention, (How could I made this!!??)
I approached a naive Newton version , but after all Now Its clear 
for me that isqrt() is probably of use in cripto (!) so lloking erlang 
sources (as i use to do for lerarnign porpouses...)

that's it...

The app SSH uses:

isqrt(0) -> 0;
isqrt(1) -> 1;
isqrt(X) when X >= 0 ->
    R = X div 2,
    isqrt(X div R, R, X).
isqrt(Q,R,X) when Q < R ->
    R1 = (R+Q) div 2,
    isqrt(X div R1, R1, X);
isqrt(_, R, _) -> R.


that its entirely on integer domain and supposely handled well by erlang bignums
routines. I tested this with some nig numbers and seems correct.

it doesnt deserve more attention where the fundamental subject its to avoid
making NOVICE MISTAKES (This is me!!!) like forgetting what is not integer arithmetic.

Again Thaks to all!!, for you advice and sugestions

> 
> In the message <>
> dated Mon, Jan 25, 2010 at 07:33:03PM +1300,
> Richard O'Keefe <> writes:
> > Didn't we have exactly this conversation several months ago?
> > At the time I said that it is straightforward to write an
> > integer square root function, and by that I meant >> in Erlang <<,
> > no port programs needed.
> 
> ________________________________________________________________
> erlang-questions mailing list. See http://www.erlang.org/faq.html
> erlang-questions (at) erlang.org
> 
> 



-- 
No imprima este correo si no es necesario. El medio ambiente está en nuestras manos.
__________________________________________

Clist UAH a.k.a Angel
__________________________________________
MySQL5: Vale, corromper los datos de forma silente no era una buena idea despues de todo.


More information about the erlang-questions mailing list