division-free binary-to-decimal conversion
Zimmermann Paul
Paul.Zimmermann at inria.fr
Mon Oct 7 08:36:17 CEST 2013
Niels,
> From: nisse at lysator.liu.se (Niels Möller)
> Date: Mon, 07 Oct 2013 08:20:13 +0200
>
> Zimmermann Paul <Paul.Zimmermann at inria.fr> writes:
>
> > with Cyril Bouvier we have written a preprint describing several division-free
> > algorithms to convert from binary to decimal (the mp?_get_str routines):
> >
> > http://www.loria.fr/~zimmerma/papers/get_str.pdf
>
> I've had a first reading. Seems to give impressive speedups. And nice
> with another application of mulmid.
>
> I think I noticed one typo: On page 3, the second inequality just
> after Eq. (3), should probably say 0 <= y/2^n < 1, not 0 <= y b^k / 2^n
> < 1.
>
> Regards,
> /Niels
0 <= y b^k / 2^n < 1 is correct. When a = b^k (or 0), Eq. (3) reads
b^k - d < y b^k / 2^n < b^k + 1, which modulo b^k means that either
b^k - d < y b^k / 2^n < b^k, or 0 <= y b^k / 2^n < 1.
Best regards,
Paul
PS: 0 <= y/2^n < 1 would be always true, since y/2^n approximates a/b^k, and we
assumed a < b^k.
More information about the gmp-devel
mailing list