[erlang-questions] changes in native functions for the next otp release.

[Richard O'Keefe]

On Jan 23, 2010, at 11:01 PM, Angel wrote:
> Iet ab=N
> let M=(a+1)(b+1);
>
> M=ab+a+b+1  that is N +a +b +1  so M  > N
>
> Ok but in erlang...
>
> Erlang R13B01 (erts-5.7.2) [source] [rq:1] [async-threads:0] [hipe]  
> [kernel-
> poll:false]
>
> Eshell V5.7.2  (abort with ^G)
> 1> N=71641520761751435455133616475667090434063332228247871795429.
> 71641520761751435455133616475667090434063332228247871795429
>
> 2> R0=trunc(math:sqrt(N)).
> 267659337146589062070609641472

At this point you have said
    "please, Erlang, calculate a 53-bit APPROXIMATION to the square
     root of my 197-bit[%] integer, and then chop that back to the
     next smaller integer."
[%] I haven't counted the bits exactly, this is ceiling(59*(10/3)).

The integer square root of N is
267659337146589069735395147283    and Erlang returned
267659337146589062070609641472
                  ^^^^^^^^^^^^^
which is NOT the integer square root of N, because YOU NEVER ASKED
FOR THE INTEGER SQUARE ROOT OF N.  Convert the integer square root
of N to a floating point number and you get
26765933714658906.............
which is as accurate as math:sqrt/1 can possibly make it,
because that's as precise as an IEEE double-precision floating
point number (which is what math:sqrt/1 is DEFINED to return)
can possibly be.

> where is the problem? That's erlang or the gmp library?

Neither.  The problem is that you are confusing a DOUBLE PRECISION
FLOATING POINT square root (which is what math:sqrt/1 is) with an
INTEGER SQUARE ROOT (the integer-sqrt function in Gambit Scheme).
Erlang is correctly doing *precisely* what you told it to do.
>

> this was on R13B1 i think (have to re-test on current versión) is  
> still
> broken.

Nothing is broken.  As far as I know, Erlang doesn't offer, and
nowhere claims to offer, an integer square root function.  What is
broken is the belief that math:sqrt/1 is such a function.

You will have to program your own integer square root function.
>
>
> Im probing some supeesecrete variations of "fermat little's theorem"  
> on RSA
> numbers clearly is a problem if native math:sqrt still broken and port
> latencies (serialitation and parsing) of my actual code begin to  
> annoy me.

You have not yet shown that an integer square root function programmed
in Erlang is too inefficient to use.  While truncate(math:sqrt(N)) may
not be the right answer, it is surely a good start for a (careful!)
Newton-style iteration.
>
>