very long binary representation to decimal

[davar55]

How can I convert efficiently from very long binary representation to decimal for output?

I've written (in C) a large-integer calculator. I've found two slow
routines: output_in_decimal(n) and multiply(m,n).
The internal representation is as arrays of 32-bit unsigned longs,
and currently up to one million such longs per big_number.
It works fine on a variety of operations, but starts to slow down
measurably over 100000 digits. In particular, outputting a big_number
alone takes far too long, because my routine loops on dividing by 10 to
get the digits, but each loop must shift the long representation downward,
so the cost is O(n^2) in number of digits or bits. Can anyone suggest a
faster way to get the decimal digits out of an extremely long binary,
without taking the extreme step of changing the representation to
9 decimal digits (999,999,999) per 32-bit word, an idea I'm considering?

[xilman]

Originally Posted by davar55

How can I convert efficiently from very long binary representation to decimal for output?

I've written (in C) a large-integer calculator. I've found two slow
routines: output_in_decimal(n) and multiply(m,n).
The internal representation is as arrays of 32-bit unsigned longs,
and currently up to one million such longs per big_number.
It works fine on a variety of operations, but starts to slow down
measurably over 100000 digits. In particular, outputting a big_number
alone takes far too long, because my routine loops on dividing by 10 to
get the digits, but each loop must shift the long representation downward,
so the cost is O(n^2) in number of digits or bits. Can anyone suggest a
faster way to get the decimal digits out of an extremely long binary,
without taking the extreme step of changing the representation to
9 decimal digits (999,999,999) per 32-bit word, an idea I'm considering?

Best suggestion is to examine the source code of GMP.


IIRC, a divide and conquer approach is used.

[jasonp]

See here.

[davar55]

Originally Posted by xilman

Best suggestion is to examine the source code of GMP.
IIRC, a divide and conquer approach is used.

Thanks. I downloaded gmp.*.tar.bz2, and figured out how to list
its files, of which there are are ~1900. Could you steer me to
which file(s) are most relevant to my problem? (JUst kidding, I'll
try plodding through some of them myself.)

Saw the other post. Could there be a divide and conquer method
that did not use FFT or other float based computing? My original
intent was to do the whole calculator with strictly integer
representations, and only when my basic output_in_decimal routine
turned out so slow AND my recursive Karatsuba implementation
of multiplication didn't zip did I realize I might need a new approach.
But I'd hate to have to redo the whole thing because of a major
change in number representation.

[retina]

Originally Posted by davar55

Could there be a divide and conquer method
that did not use FFT or other float based computing?

NTT uses all integer. And it is only a small amount slower with the right implementation.

[jasonp]

If you want faster asymptotic complexity, the cost is much more complex code. But if you're already contemplating ordinary arithmetic on large numbers, the extra stuff is just a driver routine that uses the same building blocks.

You could probably use recursive Karatsuba multiplication instead of an FFT, or even Schonhage-Strassen, but GMP already does the latter and their implementation will be much faster than yours. With fast multiply code, a million words in size is well into Schonhage-Strassen territory. If you use a floating point FFT, the data can be stored in integer format and transformed to floating point when a multiply starts.

[davar55]

Originally Posted by retina

NTT uses all integer. And it is only a small amount slower with the right implementation.

I couldn't find the NTT referenced on Google. Could you give me
another hint? ANd woud this be another search thru source code,
which I don't particulary relish but hey, if it's there, climb it.

[retina]

Originally Posted by davar55

Could you give me another hint?

http://mathworld.wolfram.com/NumberT...Transform.html

[davar55]

Originally Posted by retina

http://mathworld.wolfram.com/NumberT...Transform.html

Thanks in advance of reading it.

[retina]

Originally Posted by davar55

Thanks in advance of reading it.

It was only a hint (as you asked for). So you need to do a bit more digging if you want to find actual implementation details, algorithms and optimal parameter selections.

[davar55]

Originally Posted by retina

It was only a hint (as you asked for). So you need to do a bit more digging if you want to find actual implementation details, algorithms and optimal parameter selections.

As I said, thanks. I saw it was practically a stub, but if NTT is
a source for algorithms, code, etc. I'll be glad to find out.