Ling Long Kai Fang BigNum to ASCII String

[dedndave]

here is one of the projects I have been working on
this is not the final version, as I think I know a way to speed this up a bit
even still, it is fairly fast
on my p4 prescott, it is around 39,700 clock cycles for a 1024 bit unsigned integer (all 1's)
(that's about twice as fast as my previous divide-and-conquer version)

I want to thank Drizz for his help   :U

this version will handle any practical length integer, signed or unsigned (mode selectable)

EDIT - version 1a - fixed negative value design mistake - see Oct 4, 2009 post for details
EDIT - added the base 1,000,000,000 versions (LLKF9)
NOTE - LLKF9_1 is the one you want - LLKF1a is retained for comaprison purposes only

EDIT - also in this thread, a Ling Long Kai Fang big integer exponental routine
post - http://www.masm32.com/board/index.php?topic=12363.msg100435#msg100435
d/l - http://www.masm32.com/board/index.php?action=dlattach;topic=12363.0;id=7070

[dedndave]

i see people downloading - then no response - lol
that probably means 1 of 2 things:
1) they are so overwhelmed by the magnificance of my coding ability that they are lost for words
2) my code sux rox - lol
i am guessing the latter   :'(

[BlackVortex]

I saw this :

Ling Long Kai Fang BigNum

and I shit brix

[dedndave]

lol - now, that's funny
the math behind it was used by the Chinese as early as the 1st century B.C.
some guy played with it (around 1800 A.D.) and it got his name (William George Horner)
well - sure - back then, it wasn't "discovered" until a white guy played with it - lol
i figure it's about time we give the Chinese their props

[dedndave]

btw - "ling long kai fang" translates to something like "polynomial ladder solution"
it's nothing to be afraid of
they aren't dirty words or anything - lol

[ecube]

Since I can't find anything on google/bing, to summarize this thing it just converts large numbers to an ascii string? is there a max size to the input number? also "39,700 clock" wtf! sounds like this things crunching the cure to aids.  :'(

oh and nice work btw  :U your comments,error checking, and clean code is refreshing.

[dedndave]

lol - thanks E^Cube
well - you must understand - that is a 1024 bit integer - a 309 character string is returned
as for the max size - it is whatever you can fit in there - lol
it does not modify the original, so it does not need to make a copy of it
i have jammed integers over 64 Kb in there and it spits out what looks like the right stuff (150 Kb+ string)
there is also no penalty for negative numbers - should be about the same time
it does not use fpu/mmx/sse - so those registers are free

as for the reference to ling long kai fang - it is out there someplace
the polynomial identity has origins in a very old Chinese book.......

http://en.wikipedia.org/wiki/The_Nine_Chapters_on_the_Mathematical_Art

you might also look for a later Chinese mathematician, Qin Jiushao
he wrote a book in 1247 and used the equation to find roots of a 7th order polynomial
he is the one who called it "ling long kai fang" - which was not really a "title" for it - just a calling name
the guy was a dirty politician, but in his spare time, a great mathematician

my fave is still Archimedes, though - Archie and i go way back - lol - he was way ahead of his time

[ecube]

doesn't 8 bits = 1 byte? and 1024/8 = 128? or how did you get a 309 character string from a 1024 bit interger?

[dedndave]

well - with a 4 byte integer, you can get a 9 byte decimal string (4,294,967,295)
from 64 bits (8 bytes), you can get 20
the decimal string is not as effiecient in terms of storage, because many of the bits are essentially unused
when converting integers, you can estimate the decimal string length by L = 2.414 B (L = decimal string bytes, B = binary integer bytes)

[raymond]

when converting integers, you can estimate the decimal string length by L = 2.414 B (L = decimal string bytes, B = binary integer bytes)

And if anyone is wondering how Dave arrived at that estimate,
2.4 = 8*log₁₀(2) = 8*0.3

[dedndave]

hiya Ray
i dunno - that formula doesn't yeild good results
it always leaves you short
1+sqr(2) ~ 2.414 seems to work better
8*log(2) ~ 2.408

[UtillMasm]

year 1247:
.....
(x1+x2)2=x12+2x1x2+x22=x12+(2x1+x2)x2
.....
X4＋4x1X3＋6x12x2＋4x13x＝N－x14
.....
秦九韶称为"开连枝某乘方"；而方程的奇欢幂系数都是零时，称为"开玲珑某乘方"。
.....
long long ago, hahahah

[MichaelW]

Doing the conversion for a large number of 32-bit integers from a good RNG I get (typically) a mean length of 9.741048 digits, or 2.435262 digits per byte.

Code Select Expand


; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    include \masm32\include\masm32rt.inc
    include \masm32\include\advapi32.inc
    includelib \masm32\lib\advapi32.lib
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    .data
      meanLength    REAL8 ?
      digitsPerByte REAL8 ?
      counts        dd 0, 0
      buff          db 20 dup(0)
    .code
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

;------------------------------------------------------------------------
; This proc collects random bytes generated by the cryptographic service
; provider (CSP), and returns a random 32-bit integer.
;
; Everything is in a single procedure to make automatic release of the
; CSP handle simple. The large buffer is a quick and dirty correction
; for the slowness of the CSP generator.
;------------------------------------------------------------------------

PROV_RSA_FULL EQU 1
CRYPT_VERIFYCONTEXT EQU 0F0000000h

.data
    hProv       dd 0
    rand_buffer dd 10000 dup(0)
    pNext       dd 0
.code

csp_rand proc uses ebx

    mov ebx, pNext

    .IF ebx == 0

         invoke CryptAcquireContext, ADDR hProv,
                                     NULL,
                                     NULL,
                                     PROV_RSA_FULL,
                                     CRYPT_VERIFYCONTEXT
         .IF eax == 0
              ret
         .ENDIF

         invoke CryptGenRandom, hProv, 10000*4, ADDR rand_buffer
         .IF eax == 0
              ret
         .ENDIF

         invoke CryptReleaseContext, hProv, 0

      .ENDIF

      mov eax, [rand_buffer+ebx]
      add ebx, 4
      .IF ebx > 9999*4
          xor ebx, ebx
      .ENDIF

      mov pNext, ebx

      ret

csp_rand endp

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
start:
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

    xor edi, edi
    mov ebx, 1000000
    .WHILE ebx
        call csp_rand
        invoke crt_sprintf, ADDR buff, cfm$("%u"), eax
        add edi, eax
        dec ebx
    .ENDW
    push edi
    fild DWORD PTR [esp]
    pop edi
    fld8 1000000.0
    fdiv
    fst  meanLength
    fld8 4.0
    fdiv
    fstp digitsPerByte
    invoke crt_printf, cfm$("mean length: %f\ndigits per byte: %f\n\n"),
                       meanLength,
                       digitsPerByte

    inkey "Press any key to exit..."
    exit
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
end start


[drizz]

@dedndave,
very nice, but you asm is hard to follow  :P even with all the comments  :P
did you test against "div by 10" routine to see how it performs in comparison to it?


@other,
seriously, N-bit binary number has Trunc(N*Log₁₀(2))+1 decimal digits

[dedndave]

lol UtillMasm - that is: 1247 = x(x(x(1) + 2) + 4) + 7, where x = 10
i was hoping you or Onan (Farabi) could give us a better translation of the phrase "ling long kai fang"
my Chinese is worse than my Masm - lol

Michael,
we are talking about the maximum length
no need to generate random numbers - just set all the bits to 1

Drizz,
after playing with the length formulas - Drizz's is perfecto - lol - i will use that in the future
i checked it against the length of a 65,536 byte integer, which is 157,287 decimal digits
in fact - i will use it to speed up the routine   :U
i can precalculate the required buffer length and avoid checking each time it is lengthened
i just need to use enough precision to make it work with extremely long values (and make sure i include the minus sign - lol)

i had hoped the comments would be enough
but, i do have an outline of the operation that i will add on the next version
it steps through the process and details the number of bits required and maximum values along the way
the version i posted converts base 4,294,967,296 to base 100,000,000, then converts to base 10 in the ASCII loop
i am currently writing a version that converts base 4,294,967,296 to base 1,000,000,000, then to base 10
this will slow down the ASCII loop a little bit, but should speed up the ling long kai fang considerably
it will have an added advantage in that the output string will be left justified in the output buffer field
it will be even harder to follow the code - lol
i will try to explain it's operation thoroughly
i may put it in a seperate read_me file to avoid clutter in the proc

as for comparison to the divide-and-conquer method, i think divide-and-conquer might win out slightly over the current version
well - for shorter integers, anyways
except for negative signed values, where ling long kai fang will always win
it appears that the real advantage of ling long kai fang is more prominent with longer integers
the newer version should beat divide-and-conquer in all cases above 64 bits
before we can really compare, i want to spend time to make divide-and-conquer as fast as i can
i also want to make the routine equal in all other aspects - error checking, no fpu/mmx/sse instructions, etc
it won't take nearly as long because divide-and-conquer is simpler to write

i know Drizz and Jochen probably already have routines for this
but i am guessing they use the fpu or sse registers
this thing could run like a bullet if it were written with sse
i haven't learned sse yet, but i wanted to avoid it for this routine, anyway
a bignum program is likely to use those registers for other purposes (i.e. more time critical than string output)