Re: Faster digits and fromdigits in base 2^k, and FlxqM_mul_Kronecker

[Peter Bruin <P.J.Bruin@math.leidenuniv.nl>]

Bonjour,

Peter Bruin <P.J.Bruin@math.leidenuniv.nl> wrote:

> The functions digits(x,b) and fromdigits(x,b) are currently not very
> fast when b is a power of 2.  I am attaching a patch (digits_2k.patch)
> that contains
>
> - reimplementations of binary_2k, binary_2k_zv
> - new functions fromdigits_2k, fromdigits_2k_zv
> - a 2-line addition to fromdigits to use the new fromdigits_2k

[...]

> The only thing that is still missing is the documentation for the new
> functions fromdigits_2k and fromdigits_2k_zv.

The documentation for the new functions is in the attached file
doc_fromdigits.patch.  In the process I found a few typos, which are
fixed in doc_typos.patch.

Thanks,

Peter


commit 925a49c3139f115ce41849567a00c4da8da16396
Author: Peter Bruin <P.J.Bruin@math.leidenuniv.nl>
Date:   Sat Oct 10 09:20:55 2015 +0200

    document fromdigits_2k, fromdigits_2k_zv

diff --git a/doc/usersch5.tex b/doc/usersch5.tex
index 46637f3..a7801c5 100644
--- a/doc/usersch5.tex
+++ b/doc/usersch5.tex
@@ -2347,7 +2347,7 @@ shifts the mantissa
 $$f, s[m], s[m+1],\ldots s[M]$$
 right by $n$ bits.
 
-\subsec{From \typ{INT} to bits}
+\subsec{From \typ{INT} to bits or digits in base $2^k$ and back}
 
 \fun{GEN}{binary_zv}{GEN x} given a \typ{INT} $x$, return a \typ{VECSMALL} of
 bits, from most significant to least significant.
@@ -2368,6 +2368,15 @@ proper \kbd{GEN}), return the integer $\sum_{i = 1}^l x[i] 2^{l-i}$, as a
 \fun{ulong}{bits_to_u}{GEN v, long l} same as \tet{bits_to_int}, where
 $l < \tet{BITS_IN_LONG}$, so we can return an \kbd{ulong}.
 
+\fun{GEN}{fromdigits_2k}{GEN x, long k} converse of \tet{binary_2k};
+given a \typ{VEC} $x$ of length $l$ and a positive \kbd{long} $k$,
+where each $x[i]$ is a \typ{INT} with $0\leq x[i] < 2^k$, return the
+integer $\sum_{i = 1}^l x[i] 2^{k(l-i)}$, as a \typ{INT}.
+
+\fun{GEN}{fromdigits_2k_zv}{GEN x, long k} as \tet{fromdigits_2k}, but
+with $x$ being a \typ{VECSMALL} and each $x[i]$ being a \kbd{long}
+with $0\leq x[i] < 2^k$; here $k$ may be any positive \kbd{long}.
+
 \subsec{Integer valuation}
 For integers $x$ and $p$, such that $x\neq 0$ and $|p| > 1$, we define
 $v_p(x)$ to be the largest integer exponent $e$ such that $p^e$ divides $x$.

commit dd0de7650c09310dff719360ee0c8ef92818e621
Author: Peter Bruin <P.J.Bruin@math.leidenuniv.nl>
Date:   Sat Oct 10 09:21:07 2015 +0200

    typos in doc

diff --git a/doc/usersch5.tex b/doc/usersch5.tex
index a7801c5..003fd5f 100644
--- a/doc/usersch5.tex
+++ b/doc/usersch5.tex
@@ -2358,7 +2358,7 @@ most significant to least significant.
 
 \fun{GEN}{binary_2k_zv}{GEN x, long k} given a \typ{INT} $x$, and $0 < k <
 \tet{BITS_IN_LONG}$, return a \typ{VECSMALL} of digits of $x$ in base $2^k$, as
-\typ{ulong}s, from most significant to least significant.
+\kbd{long}s, from most significant to least significant.
 
 \fun{GEN}{bits_to_int}{GEN x, long l} given a vector $x$ of $l$ bits (as a
 \typ{VECSMALL} or even a pointer to a part of a larger vector, so not a
@@ -2910,11 +2910,11 @@ computes the Euclidean quotient and remainder of $x$ by $y$. As
 \kbd{sdivss\_rem} otherwise.
 
 \fun{GEN}{divsi_rem}{long s, GEN y, long *r} computes the Euclidean quotient
-and remainder of the \typ{long}~\kbd{s} by the \kbd{GEN}~\kbd{y}. As
+and remainder of the \kbd{long}~\kbd{s} by the \kbd{GEN}~\kbd{y}. As
 \kbd{sdivss\_rem} otherwise.
 
 \fun{GEN}{divss_rem}{long x, long y, long *r} computes the Euclidean quotient
-and remainder of the \typ{long}~\kbd{x} by the \kbd{long}~\kbd{y}. As
+and remainder of the \kbd{long}~\kbd{x} by the \kbd{long}~\kbd{y}. As
 \kbd{sdivss\_rem} otherwise.
 \smallskip
 \fun{GEN}{truedvmdii}{GEN x, GEN y, GEN *r}, as \kbd{dvmdii} but with a