how to print extended numbers?

[thomas_remkus]

How can I convert an array of DWORDs that create a very large number into a BYTE array? I'm learning about ADC and and would like to print my numbers.

[dedndave]

i would use uhex$, and perhaps left$ and right$ macros, depending on what i wanted
in this example, each byte is seperated by a space character
you may want to add cr/lf's as needed

        mov     eax,SomeDWord
        call    SplitDW
.
.
.
SplitDW PROC

        push    eax
        print   right$(uhex$(eax),2),32           ;byte 0
        mov     eax,[esp]
        print   left$(right$(uhex$(eax),4),2),32  ;byte 1
        mov     eax,[esp]
        print   right$(left$(uhex$(eax),4),2),32  ;byte 2
        pop     eax
        print   left$(uhex$(eax),2),32            ;byte 3
        ret

SplitDW ENDP

[thomas_remkus]

I have the following really big number code (256 bit number):

Code Select Expand

reallyBigNumber DWORD 1, 0, 0, 0, 0, 0, 0, 0

This should result in just the number '1'. But if I had it this way:

Code Select Expand

reallyBigNumber DWORD 0, 0, 0, 0, 0, 0, 0, 1

That's a number that I can't even begin to print. Is there a function available that will allow me to pass in the pointer to my number and my size of DWORDs and maybe load a BYTE buffer with the result?

[cobold]

You could simply dump byte by byte of your bignum as dedndave suggested. But you want to print the decimal representation of bignum, right?

This proc would do it, but you'll have to modify it (because it has msb FIRST, whereas in your bignum MSB is LAST). So you have to reverse the logic of the loop, and then you've got to adjust the parameter names

Code Select Expand


Bin2Dec proc uses ebx ecx edx edi

    LOCAL Ten:  DWORD
    LOCAL Testz:DWORD
   
    mov Ten, 10
    mov edi, OFFSET g_szDecNum    ; a buffer for the decimal representation of bignum
ALIGN 4
OuterLoop:
    xor edx, edx
    mov ecx, LENGTHOF g_dwArray    ; g_dwArray = your bignum, length in BYTES
    mov ebx, OFFSET g_dwArray    ; address of bignum
    mov Testz, 0
ALIGN 4
InnerLoop:
    mov eax, [ebx]
    div Ten
    mov [ebx], eax
    test eax, eax
    jz IL1
    mov Testz,1
ALIGN 4
IL1:
    add ebx, 4
    loop InnerLoop
    mov al,dl
    add al,"0"
    stosb
   
    test Testz,1
    jnz OuterLoop

    mov al,0
    stosb

    invoke szLen,ADDR g_szDecNum
    .if eax > 1
        lea eax,g_szDecNum
        mov eax,rev$(eax)
    .endif
   
    ret
Bin2Dec endp


HTH, cobold

CAUTION: bignum is destroyed after conversion. You might want to save it before!

[dedndave]

reallyBigNumber DWORD 0, 0, 0, 0, 0, 0, 0, 1

that IS a really big number - lol

i thought you just wanted to view the bytes
to make a big decimal string, Cobold's proc looks about right
but, it is good to understand conversion principles, as opposed to taking some proc and copy/paste it into your program

basically, we want to convert a value from base 2 to base 10 - that is the hard part
then, we want to convert the base 10 digits to ASCII characters - that is the easy part

in base 2, each bit is a "digit" - base 10 digits may be expressed as base 2 values, 0000 to 1001
when we use the DIV instruction, we are using a base 2 dividend and divisor to get a base 2 quotient and remainder
quotient + remainder/divisor = dividend/divisor (all base 2 values)
it is important to note that the remainder value alone is somewhat meaningless
we need to know what the divisor is in order to evaluate it, as it represents only a portion of the fractional expression

one way to convert between bases is to use logarithms:
log_m(x) = log_n(x) / log_n(m)
the problem here is that the value you have given as an example is a 225-bit integer (with potential to be 256-bits)
we have no mechanism to load that large of an integer into the FPU if we wanted to get the log

the method Cobold gives is a simple alternative
it is a multiple-precision division loop
we continually divide the value by 10 and use the remainder as a decimal digit
each time we divide, we add a new digit to the decimal string
the first division provides us with the last digit in the result
the last division provides the first digit (highest order)
as we store each decimal digit, we add 30h to it to make it an ASCII character (30h = ASCII "0")
when there is nothing left to divide, we are done

as you can see, there is no way to divide such a large number all at once
even if we could, it may cause an overflow error because the quotient is also too large for a 32-bit register
for example, we can divide a 64-bit number by a 32-bit number
but, if the 64-bit dividend is large and the 32-bit divisor is small (like 10), it can
cause overflow because the resulting quotient must also fit into a 32-bit register
the largest value we can divide by 10 without overflow is 0FFFFFFFFh x 10d + 9, or 42,949,672,959 (36-bits long)

in order to handle larger dividends, we can cascade DIV instructions together, each one performing "partial division"
the inner loop of Cobold's code cascades DIV instructions together to perform this type of multiple-precision division
if we unrolled his inner loop and designed it make a single pass for 256-bit dividends, it might look like this:

DividendA  dd 0FFFFFFFFh,0FFFFFFFFh,0FFFFFFFFh,0FFFFFFFFh,0FFFFFFFFh,0FFFFFFFFh,0FFFFFFFFh,0FFFFFFFFh
DivisorA   dd 10h
QuotientA  dd 8 dup(?)
RemainderA dd ?

        mov     ecx,DivisorA
        xor     edx,edx

        mov     eax,DividendA+28
        div     ecx
        mov     QuotientA+28,eax

        mov     eax,DividendA+24
        div     ecx
        mov     QuotientA+24,eax

        mov     eax,DividendA+20
        div     ecx
        mov     QuotientA+20,eax

        mov     eax,DividendA+16
        div     ecx
        mov     QuotientA+16,eax

        mov     eax,DividendA+12
        div     ecx
        mov     QuotientA+12,eax

        mov     eax,DividendA+8
        div     ecx
        mov     QuotientA+8,eax

        mov     eax,DividendA+4
        div     ecx
        mov     QuotientA+4,eax

        mov     eax,DividendA
        div     ecx
        mov     QuotientA,eax

        mov     RemainderA,edx

the final remainder (RemainderA) is a value from 0 to 9 - a single decimal digit
we would add the ASCII "0" to that remainder and store it as our first digit
in Cobold's code, the new QuotientA value overwrites the old DividendA value on each pass
that way, with each successive pass, we are dividing a value ~1/10th the size of the previous pass
when all the bits in the dividend are 0, there is no more number left to divide, so you know you are done

one way to make Cobold's code faster would be to divide by 100 instead of 10
that way, there are half as many passes in the outer loop
we get 2 decimal digits on each pass - the remainder is now a binary value from 0 to 99
we can use the AAM instruction to split it into 2 decimal digits, then convert and store both at once

        aam                  ;split into 2 digits
        or      ax,3030h     ;make them ASCII
        xchg    al,ah        ;swap the order

then, we store the word from AX into the string instead of a byte from AL
you may have to supress a single leading 0 in the string

[cobold]

ded,

I didn't know that you know so much about number systems. Just want to tell you that I appreciate your post, and that it motivated me to enhance the Bin2Dec proc.

Have a nice day.

rgds
cobol(d) - because I used to code a lot in COBOL - yes I'm not a youngster anymore

[dedndave]

that AAM trick will make it almost twice as fast - gl   :U
btw - there are a bunch of guys in here that know more than i do - lol
and, there are much faster methods to do this
i like this method because it is small and simple and, once you have it debugged, you can depend on the correct result
some of the other methods are questionable, in that regard
and it is impractical to test all possible values
speed isn't usually all that critical with big-nums
it's not like we have to convert 100,000 of these values every day
usually, we only want to convert a few values, and then, only need to do it a few times

[thomas_remkus]

cobold: Thanks for your response. I'll work with that and see what I can come up with. I think I saw a post some time ago about you working on the Euler project puzzles. I'm hoping to get my LARGE number skills up enough to some some of those bad boys. I'm in the learning stage right now of how large numbers can be created and how to convert/express them as strings. Maybe I'm backwards in my thinking of MSB and LSB .. shoot, do I have my array backwards?

dedndave: I'm going to need to print your post and take it with me to lunch today.

With all of the algor speed gurus I thought there might already be something like this created. Add, sub, mul, div .. and so forth. Then a series of functions to convert to and from bytes. If not then ... this is going to be more fun that I thought.

Thanks for the help.

[dedndave]

there are a few guys in here working on their own big-num lib's
Bruce is one (bruce1948)
Steve is another one of them i think (FORTRANS)

http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

near the bottom of that wiki page is a table of bignum libraries
just above that is another table with some calculators and fractals

[FORTRANS]

Hi Dave,

   Yeah, I'm trying to get a consistant set of fixed point
routines put together.  But it's slow going.  I have various
pieces lying around, but now a mish-mash.  You can search
the assembly news groups for stuff as well.  Here is one such.

Code Select Expand


Richard Pavlicek

Below is a fast, compact routine that will write any number in ASCII
decimal up to 64,536 decimal digits!  Hope that's enough. :)

;--- WRITE NUMBER IN ASCII DECIMAL

;--- Call with:
;--- ds:si = pointer to HIGH dword of number
;--- cx = size of number in double words
;--- es:di = END pointer for result string (if di = 0, result is
;---   stored from 0FFFFh downward, allowing maximum 64K digits)

;--- Returns:
;--- es:di = pointer to START of ASCII digit string
;--- cx = number of digits (0 = 64K)

WDECP:
push di ;save to find ASCII digit count later
WDEC1:
push cx ;save dword count
push si ;save high pointer
sub di,8 ;make space for 8 decimal digits
mov ebx,100000000 ;100 million
sub edx,edx ;initialize remainder
WDEC2:
mov eax,[si] ;get dword of dividend
div ebx ;divide by 100 million
mov [si],eax ;save quotient
sub si,4 ;move to next dword (if any)
loop WDEC2 ;repeat

mov eax,edx ;remainder (0-99999999)
sub edx,edx ;extend for division
mov ebx,10000 ;divisor to make 4-digit groups
div ebx ;dx = 0-9999, ax = 0-9999

mov bl,100 ;divisor to make 2-digit groups
div bl ;ah = 0-99, al = 0-99
push ax ;preserve al
mov al,ah ;least significant 2 digits
aam ;ah = 0-9, al = 0-9
xchg al,ah ;reverse order
shl eax,16 ;hold in upper half of eax
pop ax ;restore most significant digits
aam ;ah = 0-9, al = 0-9
xchg al,ah ;reverse order
or eax,30303030h ;make ASCII
mov es:[di],eax ;most significant 4 digits

        mov     ax,dx ;least significant (0-9999)
div bl ;ah = 0-99, al = 0-99
push ax ;preserve al
mov al,ah ;least significant 2 digits
aam ;ah = 0-9, al = 0-9
xchg al,ah ;reverse order
shl eax,16 ;hold in upper half of eax
pop ax ;restore most significant digits
aam ;ah = 0-9, al = 0-9
xchg al,ah ;reverse order
or eax,30303030h ;make ASCII
mov es:[di+4],eax ;least significant 4 digits

pop si ;restore high dword pointer
pop cx ;restore dword count
cmp dword ptr[si],0 ;is high dword zeroed yet?
jne WDEC1 ;no, continue with same count
sub si,4 ;yes, move to next dword (if any)
loop WDEC1 ;reduce count and continue if more

mov al,'0' ;check for leading zeros to cleanup
mov cx,8 ;maximum needed to check
repe scasb ;advances di PAST first non-zero digit
dec di ;point to first non-zero digit in string
pop cx ;restore original pointer (was di)
sub cx,di ;difference = number of ASCII digits
retn



Cheers,

Steve N.

[thomas_remkus]

Thanks!

[dedndave]

good plan - i see he divides by 100000000, then by 10000, then by 100 and uses AAM - to get 8 at a time - lol
i should try 4 at a time with my 64-bit routine - 20 decimal digits max - perfect - 5 passes
thing is - my 64-bit code currently has no memory accesses at all - not even push/pop - all in registers

EDIT - that routine is for 16-bit protected mode programs, Steve ?
it needs a little re-work

[FORTRANS]

Hi Dave,

   I would think 16-bit real mode.  Though, come to think of
it, 16-bit protected mode would be the same except for calls
and returns?  I never used it as-is, just as one of about six to
eight routines to write my own one time.  It was one of the
more interesting ones though.

Regards,

Steve N.

[dedndave]

well - he is using ds:si and es:di, but also using 32-bit registers
the only way i know of mixing them together is 16-bit protected mode - lol
it wouldn't be difficult to make a 32-bit proc out of it

[FORTRANS]

Hi Dave,

   You can use 32-bit instructions and registers in 16-bit real
mode.  I have done so a number of times.  Weird looking but
useful.

it wouldn't be difficult to make a 32-bit proc out of it

   Have at it.  Should be easy (which was one of the reasons
I posted it).  But then it would probably try to print more
than 64,536 decimal digits.

Cheers!

Steve N.