20140817, 11:20  #1 
May 2004
New York City
2×3^{2}×5×47 Posts 
very long binary representation to decimal
How can I convert efficiently from very long binary representation to decimal for output?
I've written (in C) a largeinteger calculator. I've found two slow routines: output_in_decimal(n) and multiply(m,n). The internal representation is as arrays of 32bit 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 32bit word, an idea I'm considering? 
20140817, 11:45  #2  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
3^{3}·5·7·11 Posts 
Quote:
IIRC, a divide and conquer approach is used. 

20140817, 21:40  #4  
May 2004
New York City
1086_{16} Posts 
Quote:
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. 

20140817, 23:04  #5 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2·3^{3}·109 Posts 

20140818, 01:23  #6 
Tribal Bullet
Oct 2004
2^{2}×883 Posts 
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 SchonhageStrassen, 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 SchonhageStrassen 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. Last fiddled with by jasonp on 20140818 at 07:01 
20140819, 15:14  #7  
May 2004
New York City
2·3^{2}·5·47 Posts 
Quote:
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. 

20140819, 15:24  #8 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
13376_{8} Posts 

20140819, 15:27  #9  
May 2004
New York City
4230_{10} Posts 
Quote:


20140819, 15:35  #10 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2×3^{3}×109 Posts 

20140819, 17:19  #11  
May 2004
New York City
1086_{16} Posts 
Quote:
a source for algorithms, code, etc. I'll be glad to find out. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Playing with decimal representation  Nick  Puzzles  9  20130213 17:17 
Square numbers and binary representation  ET_  Miscellaneous Math  40  20100606 12:55 
2d binary representation  only_human  Miscellaneous Math  9  20090223 00:11 
Binary representation prime number of 1's.  TTn  15k Search  0  20041218 21:10 
decimalbinary prime pairs  ixfd64  Math  2  20031016 13:40 