Some questions, big numbers library

[peter_k]

Hi,

I've to implement fast library for big numbers arithmetics. I'll store
the number in the table of unsigned long variables. And now i've a
question: what will be faster:

a) storing in one cell of the table values from 0 to 999999999
so for example number 1111222233334444 will look in table:
[233334444] [1111222] // <- i'm reversing the cell's order
+ using this method conversion number<->ascii string will be fast
+ the arithmetic (for example multiplication) will be slow (because for
carrying detection i'll have to divide a lot by 1000000000)

b) storing in one cell of the table values from 0 to (2^32)-1 (so all
bit's combination). But in this method i have to change base from
decimal to binary, which is too slow for very big numbers
so for example number 1111222233334444 will look in table:
[111111001010100110] [10010110011111000000001010101100] // <- this
numbers are in binary
+ using this method conversion number<->ascii string will be slow
+ the arithmetic (for example multiplication) will be fast

In my program i'm running a lot of arithmetic algorithms, and at the
ending i'm printing the result. I was thinking that second method
will be much faster, but... Converting from number to ascii string
takes a lot lot of time (when number has more than 100000 digits). Do
anyone have fast base converting algorithm for very long numbers or
should i use method a) ?

Hope you have understand this...

Greets&Thanks&Happy Easter
peter_k

 

[websnarf]

I've to implement fast library for big numbers arithmetics. I'll store
the number in the table of unsigned long variables. And now i've a
question: what will be faster:

a) storing in one cell of the table values from 0 to 999999999
so for example number 1111222233334444 will look in table:
[233334444] [1111222] // <- i'm reversing the cell's order
+ using this method conversion number<->ascii string will be fast
+ the arithmetic (for example multiplication) will be slow (because for
carrying detection i'll have to divide a lot by 1000000000)

b) storing in one cell of the table values from 0 to (2^32)-1 (so all
bit's combination). But in this method i have to change base from
decimal to binary, which is too slow for very big numbers
so for example number 1111222233334444 will look in table:
[111111001010100110] [10010110011111000000001010101100] // <- this
numbers are in binary
+ using this method conversion number<->ascii string will be slow
+ the arithmetic (for example multiplication) will be fast

In my program i'm running a lot of arithmetic algorithms, and at the
ending i'm printing the result. I was thinking that second method
will be much faster, but... Converting from number to ascii string
takes a lot lot of time (when number has more than 100000 digits). Do
anyone have fast base converting algorithm for very long numbers or
should i use method a) ?

You should use method b).

Assuming you've implemented division with modulo, the fast way of
converting base is to recursively split the number in halves at a time.
So you figure out what is the largest 10**(2**i) less than your
number. You divide the number by this 10**(2**i) giving you a top half
(the result of the division) and a bottom half (the remainder after
division). Then recursively call self on the top half, and recursively
call with zero-extensions on the bottom half (the zero-extension form
would then follow a similar recusive pattern as well).

Once you get below, 10**(2**3) you can use 32 bit integers straight,
and once you get to either 10**(2**2) or 10**(2**1) (whichever is your
preference) you can do the conversion through a straight table lookup.
Obviously you can completely inline these tail cases.

The ultimate overall performance for this will be approximately twice
the time taken to do the single division at the beginning. I found
that in practice this is "fast enough".

It is not worth the ridiculous performance hit of the sub-optimal
internal representation on the bulk majority of your operations just
for the purpose faster conevrsions. This is why BCD arithmetic is
marginalized these days (and actually used for *accuracy* purposes, not
speed purposes.)