diff options
author | tege <tege@gmplib.org> | 2002-05-06 15:47:14 +0200 |
---|---|---|
committer | tege <tege@gmplib.org> | 2002-05-06 15:47:14 +0200 |
commit | da1bea53b3c28874e5f29dea81bf79dbb6c871be (patch) | |
tree | cb21ff9f79c409a06c992f717bd00cd15b0eae12 /mpn | |
parent | 734fc9d2149b9bb92c92bf39ac99ce17716bf700 (diff) | |
download | gmp-da1bea53b3c28874e5f29dea81bf79dbb6c871be.tar.gz |
Clarify an algorithm description.
Diffstat (limited to 'mpn')
-rw-r--r-- | mpn/generic/get_str.c | 14 |
1 files changed, 8 insertions, 6 deletions
diff --git a/mpn/generic/get_str.c b/mpn/generic/get_str.c index 774a545c5..a84b5ad12 100644 --- a/mpn/generic/get_str.c +++ b/mpn/generic/get_str.c @@ -25,18 +25,20 @@ MA 02111-1307, USA. */ #include "gmp-impl.h" #include "longlong.h" -/* Conversion of U {up,un} to a string in base b. Basic algorithms: +/* Conversion of U {up,un} to a string in base b. Internally, we convert to + base B = b^m, the largest power of b that fits a limb. Basic algorithms: - A) Divide U repeatedly by b, generating an integer quotient and remainder. - Digits come out from right to left. (Used in mpn_sb_divrem_mn.) + A) Divide U repeatedly by B, generating a quotient and remainder, until the + quotient becomes zero. The remainders hold the converted digits. Digits + come out from right to left. (Used in mpn_sb_get_str.) B) Divide U by b^g, for g such that 1/b <= U/b^g < 1, generating a fraction. Then develop digits by multiplying the fraction repeatedly by b. Digits come out from left to right. (Currently not used herein, except for in - code for single limbs.) + code for converting single limbs to individual digits.) - C) Compute b^1, b^2, b^4, ..., b^(2^s), for s such that b^(2^s) > sqrt(U). - Then divide U by b^(2^k), generating an integer quotient and remainder. + C) Compute B^1, B^2, B^4, ..., B^(2^s), for s such that B^(2^s) > sqrt(U). + Then divide U by B^(2^k), generating an integer quotient and remainder. Recursively convert the quotient, then the remainder, using the precomputed powers. Digits come out from left to right. (Used in mpn_dc_get_str.) |