mersenneforum.org very long binary representation to decimal
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2014-08-17, 11:20 #1 davar55     May 2004 New York City 5·7·112 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 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?
2014-08-17, 11:45   #2
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

1166210 Posts

Quote:
 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.

 2014-08-17, 15:24 #3 jasonp Tribal Bullet     Oct 2004 32×5×79 Posts See here.
2014-08-17, 21:40   #4
davar55

May 2004
New York City

10000100010112 Posts

Quote:
 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.

2014-08-17, 23:04   #5
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

2×3,343 Posts

Quote:
 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.

 2014-08-18, 01:23 #6 jasonp Tribal Bullet     Oct 2004 32·5·79 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 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. Last fiddled with by jasonp on 2014-08-18 at 07:01
2014-08-19, 15:14   #7
davar55

May 2004
New York City

5×7×112 Posts

Quote:
 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.

2014-08-19, 15:24   #8
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

2·3,343 Posts

Quote:
 Originally Posted by davar55 Could you give me another hint?
http://mathworld.wolfram.com/NumberT...Transform.html

2014-08-19, 15:27   #9
davar55

May 2004
New York City

5×7×112 Posts

Quote:
 Originally Posted by retina http://mathworld.wolfram.com/NumberT...Transform.html

2014-08-19, 15:35   #10
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

2·3,343 Posts

Quote:
 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.

2014-08-19, 17:19   #11
davar55

May 2004
New York City

5·7·112 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Puzzles 9 2013-02-13 17:17 ET_ Miscellaneous Math 40 2010-06-06 12:55 only_human Miscellaneous Math 9 2009-02-23 00:11 TTn 15k Search 0 2004-12-18 21:10 ixfd64 Math 2 2003-10-16 13:40

All times are UTC. The time now is 08:44.

Mon Feb 6 08:44:56 UTC 2023 up 172 days, 6:13, 1 user, load averages: 0.73, 0.74, 0.82

Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ  ยฑ โ รท ร ยท โ โ โฐ โ โ โ โ โ โค โฅ โฆ โง โจ โฉ โบ โป โผ โฝ โ โ โ โ ยฒ ยณ ยฐ
โ  โ ยฐ โ ~ โ โ โซ
โก โ โ โ โ โช โซ โโ โโ โ โ โ โ โง โจ โฉ โช โจ โ โ ๐ ๐ ๐ โฒ โณ
โ โ โ โฆ โฃ โฉ โช โ โ โ โ โ โ โ โ โ โ โ โ โ โ โค โ โ โ โต โถ โท โธ ๐
ยฌ โจ โง โ โ โ โ โ โ โ โ โ โด โต โค โฅ โข โจ โซค โฃ โฆ โฏ โฎ โฐ โฑ
โซ โฌ โญ โฎ โฏ โฐ โ โ ฮด โ โฑ โ โ
๐ข๐ผ ๐ฃ๐ฝ ๐ค๐พ ๐ฅ๐ฟ ๐ฆ๐๐ ๐ง๐ ๐จ๐ ๐ฉ๐๐ ๐ช๐ ๐ซ๐ ๐ฌ๐ ๐ญ๐ ๐ฎ๐ ๐ฏ๐ ๐ฐ๐ ๐ฑ๐ ๐ฒ๐ ๐ด๐๐ ๐ต๐ ๐ถ๐ ๐ท๐๐ ๐ธ๐ ๐น๐ ๐บ๐