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

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Wed, Oct 28, 2015 at 02:38:43PM +0100, Peter Bruin wrote:
> Hi Bill,
> 
> > as I understand, x[i] is treated as a ulong, and not as a long.  The
> > meaning of "here $k$ may be any positive \kbd{long}." should be
> > clarified to be more explicit when k is equal or larger than
> > BITS_IN_LONG
> >
> > But more importantly, the fromdigits_2k_zv should be called
> > zv_fromdigits_2k, because the input is a zv and not the output.
> >
> > And in fact, more accurately, it should be nv_fromdigits_2k because
> > the entries are treated as unsigned.  (the original functions
> > binary_2k_zv and binary_zv have the same problem)
> 
> Here are updated patches (the first for the fromdigits_2k and binary_2k
> functions, the second to use them in FlxqM_mul_Kronecker).  Apart from
> simply renaming fromdigits_2k_zv to nv_fromdigits_2k, I clarified the
> documentation as follows:
> 
> --- a/doc/usersch5.tex
> +++ b/doc/usersch5.tex
> @@ -2373,9 +2373,11 @@
>  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}.
> +\fun{GEN}{nv_fromdigits_2k}{GEN x, long k} as \tet{fromdigits_2k}, but
> +with $x$ being a \typ{VECSMALL} and each $x[i]$ being a \kbd{ulong}
> +with $0\leq x[i] < 2^{\min\{k,\tet{BITS_IN_LONG}\}}$.  Here $k$ may be
> +any positive \kbd{long}, and the $x[i]$ are regarded as $k$-bit
> +integers by truncating or extending with zeroes.
>  
>  \subsec{Integer valuation}
>  For integers $x$ and $p$, such that $x\neq 0$ and $|p| > 1$, we define
> 
> I hope this addresses your point.

Yes, this is much clearer.

However 
make test-digits
fails
and
? fromdigits([1,0,1],2)
%1 = 7
is not good.

the line 166 in fromdigits_2k
  if (k == 1) return bits_to_int(x, l);

does not seem correct.

Cheers,
Bill.

PS: next time, you might want to look at 'git format-patch' to generate the patches.
Also, you should try 'make checkspaces'.