I need to store big numbers in a radixless manner to decrease the amount of time required to output the number in the given radix. I am having difficulty finding documents that outline how this can be done. Any help is appreciated,

Cheers!

Exceter

Cheers!

Exceter

All representations of a number have to have a radix, otherwise you just have a collection of bits or digits that have ambiguous meaning.

Then, why don't you store it as "Base 2" aka "binary" as I suggested?

The digits used in ur radixless number will be reflecting the radix. If u want to store a number radixless u have to have ur own representation and explanation of ur stored number. If u want to store large numbers then u can convert and store it in a large base to lessen ur space complexity. Time complexity as such is a little fuzzy. It is only because to save space ur going for "radixless" style. Well I do not call it radixless but as u mentioned in ur second post easy base convertion from base 2, It will be a radix of 2 then.

Afterall all physical representation is binary :)

To save space increase base/radix and store the number in that base along with ur original base and converted base. Write a functions for interconversion and use of converted data.

Avik.

just missed out, why don't u try representing them with strings. It will also save space but will require considerable effort to check the validity of a number in a given base and other mathematical operations such as multiplication, division, square root , etc.

Avik.

number%radix -> most significant digit

number/radix -> number

number%radix -> next significant digit

number/radix -> number

...

repeat until (number < radix)

This algorithm is valid only for positive ints,shorts or longs. modification for negative numbers is straight forward. algorithm for floats and doubles requires conversion to strings and then converting it as we traverse it.

|-- int --|-- int --|-- int --|-- int --|

MSB LSB

MSB = MostSignificantBit

LSB = LeastSignificantBit

I didn't notice at first that you are the asker ...

I suppose that you already investigated this angle ...

Do you need it for other bases as well ?

Binary to Radix

Conversions from binary to a power-of-2 radix use a simple and fast O(N) bit extraction algorithm.

Conversions from binary to other radices use one of two algorithms. Sizes below GET_STR_PRECOMPUTE_THRESHO

Above GET_STR_PRECOMPUTE_THRESHO

The advantage of this algorithm is that big divisions can make use of the sub-quadratic divide and conquer division (see Divide and Conquer Division), and big divisions tend to have less overheads than lots of separate single limb divisions anyway. But in any case the cost of calculating the powers b^(n*2^i) must first be overcome.

GET_STR_PRECOMPUTE_THRESHO

Since the base case produces digits from least to most significant but they want to be stored from most to least, it's necessary to calculate in advance how many digits there will be, or at least be sure not to underestimate that. For GMP the number of input bits is multiplied by chars_per_bit_exactly from mp_bases, rounding up. The result is either correct or one too big.

Examining some of the high bits of the input could increase the chance of getting the exact number of digits, but an exact result every time would not be practical, since in general the difference between numbers 100... and 99... is only in the last few bits and the work to identify 99... might well be almost as much as a full conversion.

mpf_get_str doesn't currently use the algorithm described here, it multiplies or divides by a power of b to move the radix point to the just above the highest non-zero digit (or at worst one above that location), then multiplies by b^n to bring out digits. This is O(N^2) and is certainly not optimal.

The r/b^n scheme described above for using multiplications to bring out digits might be useful for more than a single limb. Some brief experiments with it on the base case when recursing didn't give a noticable improvement, but perhaps that was only due to the implementation. Something similar would work for the sub-quadratic divisions too, though there would be the cost of calculating a bigger radix power.

Another possible improvement for the sub-quadratic part would be to arrange for radix powers that balanced the sizes of quotient and remainder produced, ie. the highest power would be an b^(n*k) approximately equal to sqrt(t), not restricted to a 2^i factor. That ought to smooth out a graph of times against sizes, but may or may not be a net speedup.

Please provide your email to receive a free trial preview!

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.