Algorithm for printing decimal value of a huge(over 128bits) binary number?

Question

TLDR, at the bottom :)

Brief: I am in a process of creating an basic arithmetic library(addition, subtraction, ...) for handling huge numbers. One of the problem i am facing is printing these huge binary numbers into decimal.

I have huge binary number stored in an array of uint64_t. e.g.

uint64_t a[64] = {0};

Now, the goal is to print the 64*64bits binary number in the console/file as its decimal value.

Initial Work: To elaborate the problem I want to describe how I printed hex value.

int i;
int s = 1;
a[1] = (uint64_t)0xFF;
for(i = s; i>= 0; i--)
{
    printf("0x%08llX, ", a[i]);
}

Output:

0x000000FF, 0x00000000, 

Similarly for printing OCT value I can just take LSB 3 bits from a[64], print decimal equivalent of those bits, 3 bits right shift all the bits of a[64] and keep repeating until all the values of a[64] has been printed. (print in revers order to keep first Oct digit on the right)

I can print Hex and Oct value of a binary of unlimited size just by repeating this unit algorithm, but I could not find/develop one for Decimal which I can repeat over and over again to print a[64](or something bigger).

What I have thought of: My initial idea was to keep subtracting

max_64 =(uint64)10000000000000000000; //(i.e.10^19)

the biggest multiple of 10 inside uint64_t, from a until the value inside a is smaller than max_64 (which is basically equivalent of rem_64 = a%max_64 ) and print the rem_64 value using

printf("%019llu",rem_64);

which is the 1st 19 decimal digits of the number a.

Then do an arithmetic operation similar to (not the code):

a = a/max_64; /* Integer division(no fractional part) to remove right most 19 dec digits from 'a' */

and keep repeating and printing 19 decimal digits. (print in such a way that first found 19 digits are on the right, then next 19 digits on its left and so on...).

The problem is this process is to long and I don't want to use all these to just print the dec value. And was looking for a process which avoids using these huge time consuming arithmetic operations.

What I believe is that there must be a way to print huge size just by repeating an algorithm (similar to how Hex and Oct can be printed) and I hope someone could point me to the right direction.

What my library can do(so far):

• Add (Using Full-Adder)
• Sub (Using Full-subtractor)
• Compare (by comparing array size and comparing array elements)
• Div (Integer division, no fractional part)
• Modulus (%)
• Multiplication (basically adding from several times :( )

I will write code for other operations if needed, but I would like to implement the printing function independent of the library if possible.

Consider the problem like this: You have been given a binary number X of n bits (1<=n<=64*64) you have to print out X in decimal. You can use existing library if absolutely needed but better if unused.

TLDR: Any code, reference or unit algorithm which I can repeat for printing decimal value of a binary of too big and/or unknown size would be much helpful. Emphasis on algorithm i.e. I don't need a code if some one could describe a process I will be able to implement it. Thanks in advance.

Answer 1

When faced with such doubts, and given that there are many bigint libraries out there, it is interesting to look into their code. I had a look at Java's BigInteger, which has a toString method, and they do two things:

• for small numbers, they bite the bullet and do something similar to what you proposed - straightforward link-by-link base conversion, outputting decimal numbers in each step.

• for large numbers, they use the recursive Schönhage algorithm, which they quote in the comments as being referred to in, among other places,

Knuth, Donald, The Art of Computer Programming, Vol. 2, Answers to Exercises (4.4) Question 14.