division-free binary-to-decimal conversion

[Zimmermann Paul]

       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.