Ling Long Kai Fang BigNum to ASCII String

[dedndave]

Ray (and Drizz, too - lol)
i have been working out the details of this buffer size calculation

if the maximum decimal string length can be found by:
L = Trunc( 8 * B * Log₁₀(2) ) + 1
or
L = Trunc( b * Log₁₀(2) ) + 1

then it seems to make sense that the minimum decimal string length can be found by:
L = Trunc( (8 * B - 1) * Log₁₀(2) ) + 1
or
L = Trunc( (b - 1) * Log₁₀(2) ) + 1

where:
L = decimal string length
B = binary bytes
b = binary bits

the logic behind this is that the minimum for N bits is the same as the maximum for N-1 bits
a decimal rollover never occurs simultaneously with a binary rollover
for example, the decimal string length for, say, 01111111 is the same as for 10000000

[raymond]

Why not simply
L = Trunc( b * Log₁₀(2) )
for the minimum.

Your other suggestion may be correct if you are trying to determine the exact number of digits. However, if you only need the information to allocate sufficient memory, that +/-1 seems relatively immaterial for big numbers.

[dedndave]

i am not allocating the memory - the caller does that
in this case, i want to verify that they allocated sufficient buffer space to evaluate the input without overflow
making a calculation at the front end speeds things up considerably
because it eliminates the need to check for buffer overflow inside the math conversion loop
there is some additional testing at the very end of the routine during ASCII conversion
that cannot be avoided because N bits can yield a string with a length variation of 1 byte
even that test is simplified if i know in advance they may only be 1 byte short
but, it would be nice to reject a large integer early if the buffer is short
if someone wants to evaluate an extremely large integer, it can take a while to process
i am trying to come up with an equation that works over a wide range of input lengths
my equation may not be correct, either - lol - we all know how well my equations work out
i may write a little program to test the two equations against each other
and spit out the first length where they yield different results, then see which is valid

[raymond]

in this case, i want to verify that they allocated sufficient buffer space to evaluate the input without overflow

Then use your formula for the maximum to verify if sufficient memory has been allocated. You could also add 1 for a minus sign when handling negative numbers.

[dedndave]

well - if they have a buffer large enough for the minimum of a certain sized integer, i have to try and evaluate it
yes - got the minus sign - lol
that was the easiest part, as i use an XOR mask to handle the signed integers
it is a dword: -1 for negatives, otherwise it's 0
all i have to do to add the length for the minus sign is subtract that XOR mask - no testing or branching   :bg
i have the code for the length now - it is a little hairy because of register usage, but i got it ~35 clock cycles
got the fast scanner re-written - it is very fast, now
i just need a little time to finish the doc's for it
that will be LLKF version 2
i want to take some of the code and tricks from the new one, and apply them to version 1, as well
when i am done, we will have a divide-and-conquer, and 2 versions of LLKF to compare
i want to break them out and make graphs for each in 3 sections;
1) initialization, 2) math loop, 3) ASCII conversion loop
the divide-and-conquer combines the math loop with the ASCII conversion
otherwise, the ASCII conversion is the same as for the base 100,000,000 LLKF
so, i can subtract the ASCII time to estimate the math time
then, the graphs will show how they each perform over a range of input sizes
we can see if there is an advantage to processing 9-digit intermediates over 8-digit
it should be interesting to see how they compare

[dedndave]

FINALLY !!!!
i got the base 1,000,000,000 ling long kai fang routines finished !!!! - lol
there are three routines:
signed
unsigned
signed/unsigned mode selectable
that way, you can pick the one that best suits your app
the unsigned version is slightly faster - the mode selectable version requires an additional parameter

you can find the attachment on the first post of the thread, or here...
http://www.masm32.com/board/index.php?action=dlattach;topic=12363.0;id=6926

[jj2007]

or here...
http://www.masm32.com/board/index.php?action=dlattach;topic=12363.0;id=6925

Direct links to attachments work only on your own puter, Dave: "You are not allowed to access this section"
:thumbu

[dedndave]

i changed the file Jochen - set the timestamps
try it again - notice the new number

[jj2007]

Interesting. It works ::)

[dedndave]

rolling your eyes at my code again ? - lol
i know - you are talking about the link   :bg

My appologies to Hutch for mis-spelling his name
it will be corrected on the next update

[dedndave]

oh - i forgot to mention
the new base 1,000,000,000 version is ~20% faster than the current base 100,000,000 version
that comparison is made using 1024-bit all 1's unsigned integers
however, that is a little misleading
i have learned a few new trix while writing the base 1,000,000,000 code
i need to apply some of those trix to the base 100,000,000 routine to make a fair comparison
working on it.......

[dedndave]

i was having a little fun with bignums and ling long kai fang
a friend of mine (a C programmer) was interested in calculating the odds of creating the first DNA
he wanted to evaluate some rather large exponentials (his numbers - not mine - lol)
i wrote a special little ling long kai fang routine that converts from a variable base to do the unsigned integer exponentiation
then, i used the LLKF9 routine to evaluate the resulting integers
these values are calculated and evaluated to full precision
(i.e., the last one is evaluated to the full 821727 decimal places)
scientific notation is used to abbreviate the results for display

22^300          Binary Exponential Length: 168 Bytes
5.330945549698723250305294228225903087386839891140036229539747963875875010e+402

44^300          Binary Exponential Length: 205 Bytes
1.085932787261652233516845109331492005702511128627953792159861291779059911e+493

22^500000       Binary Exponential Length: 278715 Bytes
2.189833539391172228072796932353901294631929097129937858803130860608658e+671211

44^500000       Binary Exponential Length: 341215 Bytes
2.178929073473699914235546735939051662312488506450443207720800467312438e+821726

i will post the code after some clean-up

[dedndave]

and here it is !
a freebie for you guys - an integer exponentiation routine
i haven't optimized it, although, i doubt i can squeeze a lot out of it
i did not bother adding the timing routines - it was just something fun to do

source code included...

[dedndave]

update
found a little bug that arose only for exponent value = 4,294,967,295
improved the app notes
managed to squeeze a slight speed improvement out of the exponentiation loop

[herge]

 Hi dedndave:

Code Select Expand


       Bignum Unsigned Integer Exponentiation Demo - DednDave - Dec 2009

          These values are calculated and evaluated at full precision.
            (i.e., 44^500000 is calculated to 821727 decimal places)
       Scientific notation is used to abbreviate the results for display.

      In this version, I am reasonably pleased with the performance of the
exponentiation routine (completion is indicated by display of the Exponential
   Integer Size). I have not spent any time optimizing this routine, as yet.

    The integer to decimal ASCII routine takes much longer to evaluate the
    large integers. The last two examples generate some very long strings.

22^300      Exponential Integer Size: 168 Bytes
5.330945549698723250305294228225903087386839891140036229539747963875875010e+402

44^300      Exponential Integer Size: 205 Bytes
1.085932787261652233516845109331492005702511128627953792159861291779059911e+493

22^500000      Exponential Integer Size: 278715 Bytes
2.189833539391172228072796932353901294631929097129937858803130860608658e+671211

44^500000      Exponential Integer Size: 341215 Bytes
2.178929073473699914235546735939051662312488506450443207720800467312438e+821726

Press any key to continue ...



Regards herge