[m-rev.] for review: float__pow: accept negative exponent; Russian peasants alg

Ralph Becket rafe at cs.mu.OZ.AU
Thu Feb 28 11:27:50 AEDT 2002


Peter Moulder, Wednesday, 27 February 2002:
> This diff has two parts: one is just to implement the russian peasants
> algorithm (O(lg Exp) instead of current O(Exp); comments in the code
> suggest that int__mod etc. weren't available when float__pow was written);
> the other change involves an interface change, in that I'm proposing
> accepting negative exponents instead of either throwing an exception
> (current CVS version) or calling error/1 (0.10.1 version).

I wrote pretty much the same thing a couple of weeks ago, but never got
around to checking it in:

    %
    % NOTE: the following should probably go in float.m
    %

:- func integer `power` int = integer.

X `power` N =
    ( if N >= 0 then X `pos_power` N else 1.0 / (X `pos_power` (-N)) ).


:- func integer `pos_power` int = integer.

X `pos_power` N =
    ( if      N = 0   then 1.0
      else if even(N) then XPowHalfN * XPowHalfN
      else                 XPowHalfN * XPowHalfN * X
    )
 :-
    XPowHalfN = X `pos_power` (N // 2).


    %
    % NOTE: this should probably go in int.m
    %

:- pred even(int).
:- mode even(in) is semidet.

even(X) :-
    X /\ 1 = 0.

> +float__acc_pow(Acc0, Base, Exp) = Ans :-
> +	( Exp = 0 ->
> +		Ans = Acc0
> +	;
> +		( Exp /\ 1 \= 0 ->
> +			Acc1 = Base * Acc0
> +		;
> +			Acc1 = Acc0
> +		),
> +		Ans = float__acc_pow(Acc1, Base * Base,
> +				     unchecked_right_shift(Exp, 1))
> +	).

In the interests of clarity, I'd rather see you use Exp // 2 than
unchecked_right_shift(Exp, 1) and let the compiler do the obvious
optimization.

Similarly, I'd like to see even/1 go in int.m rather than use the idiom
Exp /\ 1 = 0.

My last (very minor) niggle is that I feel the compiler should perform
accumulator introduction automatically...  Since it *can* do such a
thing, I'd like to see it happen in the library at least since the
head recursive code is easier to read.

- Ralph
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------



More information about the reviews mailing list