mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2014-08-17, 11:20   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

3·1,409 Posts
Default 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?
davar55 is offline   Reply With Quote
Old 2014-08-17, 11:45   #2
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

100111011000012 Posts
Default

Quote:
Originally Posted by davar55 View Post
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.
xilman is offline   Reply With Quote
Old 2014-08-17, 15:24   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

22·881 Posts
Default

See here.
jasonp is offline   Reply With Quote
Old 2014-08-17, 21:40   #4
davar55
 
davar55's Avatar
 
May 2004
New York City

3×1,409 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
davar55 is offline   Reply With Quote
Old 2014-08-17, 23:04   #5
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

25·173 Posts
Default

Quote:
Originally Posted by davar55 View Post
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.
retina is offline   Reply With Quote
Old 2014-08-18, 01:23   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

22×881 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2014-08-19, 15:14   #7
davar55
 
davar55's Avatar
 
May 2004
New York City

102038 Posts
Default

Quote:
Originally Posted by retina View Post
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.
davar55 is offline   Reply With Quote
Old 2014-08-19, 15:24   #8
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

25×173 Posts
Default

Quote:
Originally Posted by davar55 View Post
Could you give me another hint?
http://mathworld.wolfram.com/NumberT...Transform.html
retina is offline   Reply With Quote
Old 2014-08-19, 15:27   #9
davar55
 
davar55's Avatar
 
May 2004
New York City

3×1,409 Posts
Default

Quote:
Originally Posted by retina View Post
Thanks in advance of reading it.
davar55 is offline   Reply With Quote
Old 2014-08-19, 15:35   #10
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

25×173 Posts
Default

Quote:
Originally Posted by davar55 View Post
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.
retina is offline   Reply With Quote
Old 2014-08-19, 17:19   #11
davar55
 
davar55's Avatar
 
May 2004
New York City

422710 Posts
Default

Quote:
Originally Posted by retina View Post
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.
davar55 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Playing with decimal representation Nick Puzzles 9 2013-02-13 17:17
Square numbers and binary representation ET_ Miscellaneous Math 40 2010-06-06 12:55
2-d binary representation only_human Miscellaneous Math 9 2009-02-23 00:11
Binary representation prime number of 1's. TTn 15k Search 0 2004-12-18 21:10
decimal-binary prime pairs ixfd64 Math 2 2003-10-16 13:40

All times are UTC. The time now is 18:53.

Thu Jul 9 18:53:08 UTC 2020 up 106 days, 16:26, 1 user, load averages: 1.78, 2.08, 1.99

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.