Re: [PATCHES] Numeric improvements

[Ludovic Courtès]

Hi,

Mark H Weaver <address@hidden> skribis:

> Here are ten patches to improve numerics.  Among other things, this
> eliminates the known obstacles to linking with mini-gmp
> <http://bugs.gnu.org/10519>, fixes several problems with our number
> printer <http://bugs.gnu.org/13757>, adds 'round-ash', and speeds up
> handling of exact rationals.

Ten patches!

> Still to be done: add more tests to ensure full coverage of all code
> paths.  It's possible that there are some bugs lurking.  However, I
> wanted to post it now to allow review and possible work on mini-gmp
> integration.

Which of these patches are needed for mini-gmp integration?  It would
probably be easier to discuss things separately, by small chunks.

Overall I think I’m mostly incompetent on the numeric stuff, so I’d
mostly comment on form.

At first sight, it seems that there are few tests added, in particular
for the number printer.  I think tests must be added along with the
patches that claim to fix something.

> From cd9784ed33d78e6647a752123bf7be91d65b5c96 Mon Sep 17 00:00:00 2001
> From: Mark H Weaver <address@hidden>
> Date: Sun, 3 Mar 2013 04:34:17 -0500
> Subject: [PATCH 01/10] Improve code in scm_gcd for inum/inum case
>
> * libguile/numbers.c (scm_gcd): Improve implementation of inum/inum case
>   to be more clear and efficient.

This one looks OK, and should be covered by the tests, according to
<http://hydra.nixos.org/build/4268423/download/2/coverage/libguile/numbers.c.gcov.html>.

Did you measure the performance difference?

> From f6201616f7304979a31ab41814e2b297f74a3484 Mon Sep 17 00:00:00 2001
> From: Mark H Weaver <address@hidden>
> Date: Sun, 3 Mar 2013 04:34:50 -0500
> Subject: [PATCH 02/10] Optimize and simplify fractions code
>
> * libguile/numbers.c (scm_exact_integer_quotient): New internal static
>   function that computes the quotient of two exact integers when the
>   remainder is known in advance to be zero.  For large integers this can
>   be implemented more efficiently than when the remainder is unknown.
>
>   (scm_i_make_ratio_already_reduced): New internal static function that
>   creates a ratio when the numerator and denominator are already known
>   to be reduced to lowest terms (i.e. when their gcd is 1).  This can be
>   used in several places to avoid unnecessary gcd computations.
>
>   (scm_i_make_ratio): Rewrite in terms of
>   scm_i_make_ratio_already_reduced.  Don't bother checking to see if the
>   denominator divides the numerator evenly.  This is wasted effort in
>   the common case.  Instead, compute the gcd, reduce to lowest terms
>   (using scm_exact_integer_quotient), and let
>   scm_i_make_ratio_already_reduced do the integer check (by checking for
>   a unit denominator).
>
>   (scm_integer_expt): Optimize fraction case by (a/b)^n ==> (a^n)/(b^n),
>   to avoid needless effort to reduce intermediate products to lowest
>   terms.  If a and b have no common factors, then a^n and b^n have no
>   common factors.  Use scm_i_make_ratio_already_reduced to construct the
>   final result, so that no gcd computations are needed to exponentiate a
>   fraction.
>
>   (scm_abs, scm_magnitude, scm_difference): Use
>   scm_i_make_ratio_already_reduced to avoid wasteful gcd computations
>   when negating fractions.
>
>   (do_divide): Use scm_i_make_ratio_already_reduced to avoid wasteful
>   gcd computations when taking the reciprocal of a fraction or integer.

Can you fold the explanations as comments?  In particular those that
explain the implementation strategy, and why it’s more efficient this way.

> +/* scm_i_make_ratio_already_reduced makes a ratio more efficiently,
> +   when the following conditions are known in advance:
> +
> +    1. numerator and denominator are exact integers
> +    2. numerator and denominator are reduced to lowest terms: gcd(n,d) == 1
> +*/
>  static SCM
> -scm_i_make_ratio (SCM numerator, SCM denominator)
> -#define FUNC_NAME "make-ratio"
> +scm_i_make_ratio_already_reduced (SCM numerator, SCM denominator)

Please use imperative-tense sentences above functions to describe what
they do, without repeating the function name; also make sure to
introduce the arguments in the description, written in capital letters
(info "(standards) Comments").

Some helper functions introduced by the patches lack a comment.

> address@hidden {Scheme Procedure} round-ash n count
> address@hidden {C Function} scm_round_ash (n, count)
> +Return @math{round(@var{n} * address@hidden)}, but computed
> +more efficiently.  @var{n} and @var{count} must be exact
> +integers.
> +
> +With @var{n} viewed as an infinite-precision twos-complement
> +integer, @code{round-ash} means a left shift introducing zero
> +bits when @var{count} is positive, or a right shift rounding
> +to the nearest integer (with ties going to the nearest even
> +integer) when @var{count} is negative.  This is a rounded
> +``arithmetic'' shift.
> +
> address@hidden
> +(number->string (round-ash #b1 3) 2)     @result{} \"1000\"
> +(number->string (round-ash #b1010 -1) 2) @result{} \"101\"
> +(number->string (round-ash #b1010 -2) 2) @result{} \"10\"
> +(number->string (round-ash #b1011 -2) 2) @result{} \"11\"
> +(number->string (round-ash #b1101 -2) 2) @result{} \"11\"
> +(number->string (round-ash #b1110 -2) 2) @result{} \"100\"
> address@hidden lisp
> address@hidden deffn

What was the rationale for ‘round-ash’?

It seems to address to do two things differently from ‘ash’: it’s more
efficient, and it rounds when right-shifting.  The “more efficient” bit
is an implementation detail that should also benefit to ‘ash’ (as a user
I don’t want to have to choose between efficient and non-rounding.)

WDYT?

OK, these are just random comments for now.

Thanks for making Guile benefit from your expertise in this domain!

Ludo’.