[
Date Prev][
Date Next][
Thread Prev][
Thread Next][
Date Index][
Thread Index]
Re: Binary-Decimal conversion for extremely large integers
On 2007-08-09 17:29:14 +0200, Thorsten Siebenborn wrote:
For my arbitrary precision library I need conversion
routines for unlimited integers. AFAIK you can't circumvent
the division by ten, so currently I am extracting the last
decimal digit, subtract it from the integer
and divide the integer by ten with the 1/10 = 51/512*256/255
add-shift method until all decimal digits have been parsed.
Dividing by 10 would lead to a quadratic complexity. You can use
a divide-and-conquer algorithm to get a sub-quadratic complexity.
This is what GMP does.
--
Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.org/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.org/blog/>
Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)