Conversion of unsigned longs to String

Discussion in 'Java' started by Allan H Wax, May 20, 2004.

  1. Allan H Wax

    Allan H Wax Guest

    Does anyone have a good reference for something to convert a long as if
    it were an unsigned long to a string. Even better, one that allows me
    to convert it to a number of bases (hex, octal, binary)

    Allan Wax
    Allan H Wax, May 20, 2004
    #1
    1. Advertising

  2. Allan H Wax

    Roedy Green Guest

    On Wed, 19 May 2004 16:07:04 -0700, Allan H Wax
    <> wrote or quoted :

    >Does anyone have a good reference for something to convert a long as if
    >it were an unsigned long to a string. Even better, one that allows me
    >to convert it to a number of bases (hex, octal, binary)


    It is easy to write signed routines if you have unsigned operators but
    not the reverse.

    The easy way is to convert it to a BigInteger and let it worry out it.

    The core of converting long to string is a division /modulus by 10,
    peeling of one digit from the left each time. See any into forth book
    on how it works.

    You can divide a long number by a small one in stages, mimicing what
    you do with long division. I wrote an assembler routine that does it,
    pretty tough slugging though the notes may help.


    Here is a multiprecision divide.

    Not something you want to do just to avoid big int.
    This code is for a 16 bit 8086. your code can be simpler since it
    only has to work for a divisor of 10, a small number.

    Also, since 10 = 8+2, you might think about how you could do division
    with shifts and substracts.



    CHEAD plainFL,UMSLMOD,"UM/MOD",FORTH
    ; ( DON'T CONFUSE THIS WITH MU/MOD !!!)
    ; unsigned divide
    ; ( numerator-64 divisor-32 -- rem-32 quot-32 : unsigned floored
    )
    ; Divide by 0 is officially an error but it is handled
    ; by returning two 0s as a result.
    ; On overflow you just get the low order part of the quotient.
    ; Wasn't I kind?
    ; c.f. MU/MOD which gives 64-bit quotient
    COMMENT |

    Division is complicated, but in many ways it is just a
    mechanization of long division you learned in grade 4. The only
    difference is that we are using base s=2^16 instead of base 10
    numbers. In long division you make a guess at the quotient then
    multiply out then subtract to see how good your guess was. If
    the guess was too big, we try a smaller number. Knuth in The
    Art Of Computer Programming Vol 2 - Seminumerical Algorithms
    pages 229-248 discusses the problem of multiprecision
    arithmetic.

    The worst case is analogous to dividing a 4 digit number by a 2
    digit number, where the answer is guaranteed to be no more than
    2 digits. The Forth-83 standard says it is an error if the
    quotient would overflow. Forth-83 says we are not supposed to
    carry on and compute the low order portion of the overflowed
    quotient and the remainder. But since UM/MOD is used in MOD,
    this seems unreasonable, so what I do is calculate the low order
    2 digits of the quotient in case of overflow and push 0s in case
    of divide by 0. This is a little friendlier than letting the
    divide-by-0 or overflow interrupt take care of it.

    The overflow can be detected early in the game and is handled by
    UM/MOD-OVL high level code so we don't have to ever handle the
    case of more than "2-digits" in the quotient. We can tell right
    at the start if we will have overflow by comparing the high
    order 2 digits with the two digits of the divisor. If they are
    greater or equal to the divisor, we will have trouble.

    Note that MU/MOD does let you get a "4-digit" quotient, but it
    works by using UM/MOD twice.

    In real life, most of the time the dividend and divisor will
    have lots of leading zeroes. Then we may collapse the problem
    to dividing by a 1 digit number. If the problem collapses to
    dividing a 1 or 2 digit by a 1 digit, in most cases this can be
    done with the DIV machine instruction that can divide 32 bits by
    16 bits so long as the quotient is under 16 bits. Again we can
    tell ahead of time if we are safe by comparing high order digit
    of the dividend with the 1-digit divisor. If it is greater or
    equal to the divisor, we would have overflow, and must then
    resort to a longer method.

    Knuth tells us some amazingly good news about guessing. It is
    possible to directly compute a guess that is always within 2 of
    the correct answer, and most of the time bang on. Even if you
    guess wrong, you don't have to remultiply and resubtract! All
    you have do do is add the divisor to your your previous
    difference.

    Ok, what's the catch. First we must have the divisor
    normalized. s is the base=2^16. In other words the divisor
    must be > s/2 for this to work. Not to worry, this is easy to
    arrange. If k is a normalizing number (a power of 2) calculated
    to shift the divisor so that it is > s/2 (ie. leading bit is a
    one) then:

    U / V = kU / kV -- normalizing has no effect
    U mod V= (kU mod kV) / k -- you have to unnormalize at the end

    Multiplying and dividing by k is easy -- we just use shifts.
    The only nasty thing about shifting is that we may have added an
    extra digit to u1 by the shift. Also, even the NEC V20 (which
    has fast single-register multibit shifts) has to do multiple
    register shifts one bit at a time.

    At each stage of the division we are dividing a 3 digit dividend
    by a 2 digit divisor and we are guaranteed the quotient will be one
    digit and the remainder will be one or 2 digits. Now to make a
    guess g for that quotient

    q1
    -------------
    v1v2 / u0 u1 u2
    g * v1v2
    ----------
    r1h r1l


    let U = sý * u0 + s * u1 + u2
    V = s * v1 + v2

    q1 = U / V q1 < s
    r1 = U mod V r1 < V

    Presume U and V are normalized
    so that v1 > s/2 and u0 ó v1

    guess for q = g = ( s * u0 + u1) / v1 if v1 > u0,
    but if v1 = u0 we use s-1 instead. This guess can be computed
    with a single DIV instruction.

    q ó g ó q+2 The true answer q is g, g-1 or g-2.
    g < s

    Knuth gives a technique for refining the guess, but it is really
    only is useful when you are using divisors of >2 digits. All it
    amounts to is testing the two high order digits of the divisor
    before you do a full test.

    We have to compute r1 to see if our guess was too big. We could
    compute r1 in the traditional way by multiplying out our guess
    and subtracting it from the dividend.

    Let us look at this expression algebraically:
    r1 = sý*u0 + s*u1 + u2
    - s*v1*g - v2*g

    This is what Knuth would have us do. However in our case there
    is a shortcut. In the process of computing the guess g we
    incidentally computed the remainder of u0u1 / v1

    r0 = s*u0 + u1 - g*v1

    So we can rewrite the expression as:

    r1 = s*r0 + u2 - v2*g

    This saves us a multiply and a mess of adds over the brute force
    approach.

    If our guess were computed without a division as s-1 we don't
    have r0 sitting around. So what can we do in that case to
    quickly compute r1?

    r1 = sý*v1 + s*u1 + u2
    - s*v1*(s-1) - v2*(s-1)

    because g=s-1 and u0=v1

    r1 = s*(u1-v2+v1) + u2+v2

    In either case, our guess may have been too big.

    If r1 is negative this indicates g is too large. The equivalent
    r1 for g-1 is r1 + sv1 + v2, so we don't have to remultiply out
    if we guessed too large. Why didn't they tell me this in grade
    4?

    If r1 is still negative, we repeat this one more time
    decrementing our guess and guaranteed we are ok now without even
    checking!

    This handles one cycle. We can now "bring down" the next digit
    and append it after our remainder.

    We then have this problem to solve:


    q2
    --------------
    v1v2 / r1h r1l u3
    q2 * v1v2
    ----------
    r2h r2l

    Note that v1 > s/2 and v1 ò r1h so we are right back where we
    started with all the magic necessary normalization conditions
    satisfied except that we already have one digit of the quotient
    calculated.

    We solve this in the same way. Then we are done. Because we
    check for overflow before we start, we are guaranteed the
    quotient has only 2 digits.

    Then we have to normalize the two digit remainder by dividing
    it by k implemented as a quick shift right.

    If we are lucky, (99% of the time) the high order digit of the
    divisor will be 0. Nearly always we are just dividing by 10 in
    order to convert from binary to ASCII decimal. In that case
    life is much simpler. We don't even have to normalize.

    At each stage we have a problem like this to solve:

    q1
    -------------
    v2 / u0 u1 u2
    g * v2
    ----------
    r1

    Because we precheck for overflow, guaranteed u0 = 0 and v1 > u1

    let U = su1 + u2
    V = v2

    q1 = u1 / v2 q1 < s
    r1 = u1 mod v2 r1 < v2

    We guess for q1 = g = (su1 + u2) / v2 This guess is always < s.

    This guess is exact. We don't even have to multiply and
    subtract to get the remainder. It is hanging around as a result
    of computing the guess. The guess can be computed with a single
    DIV instruction.

    We then bring down the digit to the right and repeat once more.

    We can further optimize divisions by checking the special case
    of q being 0. If u1=0 and v2 > u2, we know q=0 and r1 = u2.

    There are two other special cases -- when q=1 and when q=s-1.
    However these cases are rare, so it does not pay to check for
    them. The overhead of checking slows things down in the usual
    case.

    Now putting all this together:

    We first decide whether we will have overflow. If we do, we
    indirectly let MU/MOD handle it. If not, we can now presume
    that the quotient will have only 1 or 2 digits. Then we check
    to see if we have a 1 or 2 digit divisor. We branch to the two
    different algorithms -- the 1-digit being the more common.

    Because the NEC V20 chip is so fast at division (my guess is it
    uses some of the ideas from this algorithm internally), it never
    pays to check for the case where the quotient would be 0.
    However it does pay to check for 1 or 2 digit divisors.

    You may wonder why I documented UM/MOD so fully. It is not
    likely you will ever modify this code, but you may someday port
    this compiler to a different chip, or want to steal this code
    for your C compiler. Then you will bless me for doing this. If
    you are lucky the chip will have a decent 64 bit by 32 bit
    divide and all this can be thrown away to be resurrected when
    you want 128 bit by 64 bit divides. And of course there is
    always the possibility of a bug in this code.

    | ; end of comment
    ; divide u0u1u2u3 by v1v2 to get
    ; quotient q1q2 and remainder r1r2
    ; CX:BX = v1v2 the divisor
    POPDA ; DX:AX = u0u1 high order dividend
    ; low order u2u3 still on stack
    CMP CX,DX ; compare v1 : u0
    JB UMSLMODOVL? ; < have overflow or ö0
    JA UMSLMODSAFE ; > definitely no overflow
    CMP BX,AX ; = compare v2 : u1
    JBE UMSLMODOVL? ; <= have overflow or ö0
    ; we used CMP instruction rather
    ; than SUB SBB and a single JB
    ; because we did not want to destroy
    ; the values of u0u1 v1v2.
    UMSLMODSAFE:
    ; definitely don't have overflow
    ; quotient Q=q1q2 will fit in
    ; two digits for sure

    OR CX,CX ; compare v1 : 0
    JNZ UMSLMODLONG ; <>0 -- use long form
    ; can use 1-digit divisor v2
    ; Note that we are sure u0=0 and
    ; v2 > u1
    ; now we divide u1u2u3 by v2 to
    ; get q1q2
    ; q1 will usually be 0, so we check
    ; for this special case by
    ; checking if
    ; u1=0 and u2<v2 and save
    ; ourselves a divide.
    ; At this point CX=0 BX=v1 DX=0 AX=u1
    POP DX ; DX=u2

    ;>>>>>>>>>>
    IFE (CHIP EQ NECV20) OR (CHIP EQ NECV30) OR (CHIP GE INTEL80386)
    ;; IFE because we BYPASS this code
    ;>>>>>>>>>>
    ; For Nec chip there is no point
    ; in checking for 0 quotients
    ; since divide is faster than the
    checks
    ; so we bypass all this code and
    ; go straight to the
    ; UMSLMODQUICK case with two divisions
    CMP DX,BX ; compare u2 : v2
    JAE UMSLMODQUICK ; >=
    OR AX,AX ; compare u1 : 0
    JNZ UMSLMODQUICK ; not 0
    ; we know now that q1 = 0 and r=u2
    ; all we need do is u2u3 / v2
    ; At this point DX=u2 BX=v2
    POP AX ; AX=u3
    ; check if q2 would be 0. In
    ; that case we don't need to do
    ; any divide at all.
    ; This case is common as # uses UM/MOD
    ; indirectly via MU/MOD. Leading
    ; 0 #'s use two 0-type divides.
    ; #'s normally use 1 zero-type
    ; divide to get the high order
    quotient.
    ; It is also common when MOD
    ; uses UM/MOD on numbers that
    ; are already MODed.
    ; q2 will be 0 if u2:u3 < v2
    ; i.e. u2=0 and u3 < v2
    CMP AX,BX ; compare u3 : v1 - do finer
    ; gauntlet filter first
    JAE UMSLMODVQUICK ; >=
    OR DX,DX ; compare u2 : 0
    JNZ UMSLMODVQUICK ; <>
    UMSLMODUQUICK:
    ; ULTRA QUICK DIVIDE -- No DIV instructions needed. quotient is 0
    ; This is most common case
    ; Note that on the NEC chip it does not pay to check for
    ; the q=0 case
    ; We know q1q2 = 0
    ; remainder is u3 in AX
    PUSH AX ; push r2
    PUSH DI ; push r1 = 0
    CLEAR BX ; BX=q2=DI=0
    CLEAR CX ; CX=q1=DI=0
    QNEXT

    UMSLMODVQUICK :
    ; VERY QUICK DIVIDE -- only one DIV instruction
    ; This is the second most common case.
    ; we know that q2 <> 0.
    ; and q1 = 0 and r=u2
    ; all we need do is u2u3 / v2
    ; At this point DX=u2 BX=v2 AX=u3
    ; note this can often be used even
    ; when u2>0
    ; we have already checked that
    ; q2 is not 0. It does not pay to
    ; check for q2=1 or s-1.
    DIV BX ; DX:AX / BX = u2u3 / v2
    ; DX = rem AX=q2
    PUSH DX ; push r2
    PUSH DI ; push r1 = 0
    MOV BX,AX ; BX=q2=AX
    MOV CX,DI ; CX=q1=DI=0
    QNEXT
    ;>>>>>>>>>>
    ENDIF ; end of code BYPASSED for NECV20
    ;>>>>>>>>>>


    UMSLMODQUICK:
    ; QUICK DIVIDE -- two DIV instructions -- no MUL instructions
    ; we know q1 <> 0, but v1=0
    XCHG DX,AX ; DX=u1 AX=u2
    ; we have already checked
    ; that q1 <> 0, It does not
    ; pay to check for q1=1 or s-1
    DIV BX ; u1u2 / v2
    ; AX=q1 DX=r
    MOV CX,AX ; CX=q1
    POP AX ; AX=u3
    ; It does not pay to check for
    ; q2 = 0,1,s-1 as these
    ; cases happen very rarely
    DIV BX ; DX:AX BX = u2u3 / v2
    ; DX=r2 AX=q2
    MOV BX,AX ; BX=q2
    ; at this point CX:BX = q1q2
    PUSH DX ; push r2
    PUSH DI ; push r1=0
    QNEXT

    UMSLMODOVL?:
    ; May have overflow or ö0
    ; decide which.
    ; CX:BX = v1v2 the divisor
    ; DX:AX = u0u1 high order dividend
    OR BX,BX
    JNZ UMSLMODOVL ; v2 <> 0 - problem was overflow
    OR CX,CX ;
    JNZ UMSLMODOVL ; v1 <> 0 - problem was overflow
    ; v1v2 = 0 - divided by 0

    ; DIVIDED BY 0
    XCHG SP,BP ; u2u3 still on stack, convert
    ; them to r1r2
    CLEAR CX ; q1=0
    CLEAR BX ; q2=0
    CLEAR [BP] ; r1=0
    CLEAR [BP+2] ; r2=0
    XCHG BP,SP
    QNEXT

    UMSLMODOVL:
    ; OVERFLOWED recover by using UM/MOD-OVL
    ; it calls MU/MOD which calls UM/MOD.
    ; We won't get into a loop because of the way
    ; MU/MOD calls UM/MOD guarantees overflow is not possible.
    ; CX:BX = v1v2 the divisor
    ; DX:AX = u0u1 high order dividend
    PUSHDA ; put q0q1 back where they were
    JMP UMSLMODOVL_cfa

    UMSLMODLONG:

    ; LONG DIVIDE -- two DIV instructions and 2 MUL instructions

    ; v1 > 0, so we need a 2-digit divisor
    ; We must divide u0u1u2u3 by v1,v2
    ; We are sure we can get a two digit quotient q1q2
    ; and a two digit remainder r1r2.
    ; First of all we must normalize so that v1>s/2 ie
    ; has a leading 1. We will be shifting v1,v2 left as we
    ; look for the 1. We will also be shifting u0u1u2u3 left.
    ; There is no danger that bits will fall off the end
    ; because we have already checked that v1v2 > u0u1. So
    ; We don't have to worry about having to deal with the
    ; extra digit that Knuth warns about.
    ; This long form is quite complex to follow, but
    ; relatively quick to execute. The traditional methods
    ; would take 3 DIV instructions and 6 MULs to accomplish
    ; the same thing. I have optimized it so that the usual
    ; case does not take branches. There is great parallelism
    ; computing q1 and q2 which could have be implemented as a
    ; loop. I have unravelled that loop for speed.


    XCHG SP,BP ; Save registers. We are about to
    ; use every register as a temporary.
    ; NOTE THAT THE USE OF DS: AND ES:
    ; as scratch registers
    ; is not compatible with
    ; Protected mode.
    PUSH SI ; we can't use Dstack as it has u2u3
    PUSH DS ; which we will want soon
    XCHG BP,SP

    ;
    ; Register usage here
    ; AX=u1 BX=v2 CX=v1 DX=u0 SI=free DI=0 ES=free DS=free stack=u2u3
    ;
    ; CX:BX = v1v2 the divisor
    ; DX:AX = u0u1 high order dividend
    ; Dstack has u2u3 low order dividend
    ;
    ; <<< start of normalization>>>
    ;
    MOV SI,CX ; v1 = SI := CX
    CLEAR CX ; CX counts how much we had to shift
    ; DI still 0
    MOV DI,BX ; v2 = DI := BX
    ; at this point SI:DI has v1v2
    UMSLMODNORMLOOP1:
    SHL DI,1 ; shift v1v2 left one bit
    RCL SI,1
    ; leading 1 bit shifts into carry
    JC UMSLMODLOOP1DONE
    ; jump when found the leading 1-bit
    INC CX ; count another 0-bit
    JMP SHORT UMSLMODNORMLOOP1
    ; loop till find leading 1 bit
    ; guaranteed there is one
    UMSLMODLOOP1DONE:
    ; at this point we have counted
    ; CX properly, but v1,v2 is shifted
    ; one too far left
    RCR SI,1 ; undo the last shift putting
    RCR DI,1 ; carry back into SI.
    ; You might ask why I didn't test
    ; the sign bit instead of the
    ; carry bit. Then I would not have
    ; overshot. RCL does not set
    ; the sign flag. I would have
    ; needed an extra OR in the
    ; tight loop.
    ;
    ; Register usage here
    ; AX=u1 BX=free CX=k DX=u0 SI=v1 DI=v2 ES=free DS=free stack=u2u3
    ;
    MOV DS,CX ; k = DS := CX save the shift count
    MOV ES,SI ; v1 = ES := SI normalized
    ; we need CX and SI for other purposes
    ; temporarily
    POP BX ; u2 = BX was on stack
    POP SI ; u3 = SI was on stack
    PUSH DS ; save k = DS shift count on the stack
    ; this frees up DS
    ;
    ; Register usage here
    ; AX=u1 BX=u2 CX=k DX=u0 SI=u3 DI=v2 ES=v1 DS=free stack=k
    ;
    JCXZ UMSLMODLOOP2BYPASS ; loop shifting u0u1u2u3 left
    UMSLMODNORMLOOP2:
    SHL SI,1 ; treat DX:AX:BX:SI as giant
    RCL BX,1 ; register to hold u0u1u2u3
    RCL AX,1 ; shift left k bits 1 bit at a time
    RCL DX,1 ; We never lose a bit out of DX
    LOOP UMSLMODNORMLOOP2
    UMSLMODLOOP2BYPASS:
    MOV DS,SI ; u3 = DS
    MOV SI,ES ; v1 = SI := ES
    ;
    ; Register usage here
    ; AX=u1 BX=u2 CX=0 DX=u0 SI=v1 DI=v2 ES=free DS=u3 stack=k
    ;
    ;<<< Start of calculation of q1 >>>
    ;
    CMP SI,DX ; compare v1 : u0 SI : DX
    JE UMSLMODGUESS1 ; v1=u0 guess s-1
    ; v1 > u0
    ; Make a guess g as u0u1 / v1. Save the remainder r0
    ; u0 = DX no longer needed
    ; u1 = AX no longer needed
    DIV SI ; u0u1 / v1 = DX:AX / SI
    ; g = AX r0 = DX
    MOV CX,AX ; g = CX := AX
    MOV ES,DX ; r0 = ES := DX
    ;
    ; Register usage here
    ; AX=g BX=u2 CX=g DX=free SI=v1 DI=v2 ES=r0 DS=u3 stack=k
    ;
    ; Compute the remainder r1 as
    ; r1 = s*r0 + u2 - v2*g
    MUL DI ; g = AX; v2 = DI
    ; DX:AX = v2*g
    SUB BX,AX ; r1l = BX := u2 - v2gl
    ; u2 no longer needed
    MOV AX,ES ; r0 = AX := ES
    SBB AX,DX ; r1h = AX := r0 - v2gh
    ; r0 no longer needed
    MOV DX,AX ; r1 = DX:AX
    MOV AX,BX ;
    MOV BX,0 ; keep carry of r1
    SBB BL,BH ; in BL, 0 in BH
    ;
    ; Register usage here
    ; AX=r1l BX=r1carry CX=g DX=r1h SI=v1 DI=v2 ES=free DS=u3 stack=k
    ;

    ; Test the remainder from q1 for being negative

    JL UMSLMODBADQ1 ; BX is signed so no need for JB

    UMSLMODGOODQ1:
    ; We have a perfect guess g for q1, and and a non-negative remainder
    r1
    ; DX:AX = r1
    ; r1 carry is 0
    ; g = q1 = CX
    ;
    ;<<< Start of calculation of q2 >>>
    ;
    ;
    ; Register usage here
    ; AX=r1l BX=free CX=q1 DX=r1h SI=v1 DI=v2 ES=free DS=u3 stack=k
    ;

    MOV BX,DS ; u3 = BX := DS
    MOV DS,CX ; q1 = DS := CX -- save q1
    CMP SI,DX ; compare v1 : r1h SI : DX
    JE UMSLMODGUESS2 ; v1=r1h guess q2 as s-1
    ; v1 > r1h
    ; Make a guess g as r1h r1l / v1. Keep the remainder r0
    ;
    ; Register usage here
    ; AX=r1l BX=u3 CX=free DX=r1h SI=v1 DI=v2 ES=free DS=q1 stack=k
    ;
    DIV SI ; DX:AX / SI = r1h r1l / v2
    ; r1h = DX no longer needed
    ; r1l = AX no longer needed
    ; g = AX r0 = DX
    MOV CX,AX ; g = CX := AX
    MOV ES,DX ; r0 = ES := DX
    ;
    ; Compute the remainder r2 as
    ; r2 = s*r0 + u3 - v2*g
    ;
    ; Register usage here
    ; AX=g BX=u3 CX=g DX=free SI=v1 DI=v2 ES=r0 DS=q1 stack=k
    ;
    MUL DI ; g = AX; v2 = DI
    ; DX:AX = v2*g
    SUB BX,AX ; r2l = BX := u3 - v2gl
    ; u3 no longer needed
    MOV AX,ES ; r0 = AX := ES
    SBB AX,DX ; r2h = AX := r0 - v2gh
    ; r0 no longer needed
    MOV DX,AX ; r2 = DX:AX
    MOV AX,BX ;
    MOV BX,0 ; keep carry of r2
    ; cant use XOR or would wreck carry
    SBB BL,BH ; in BL, 0 in BH
    ;
    ; Register usage here
    ; AX=r2l BX=r2carry CX=g DX=r2h SI=v1 DI=v2 ES=free DS=q1 stack=k
    ;
    ; Test the remainder for q2 for being negative
    JL UMSLMODBADQ2
    ;
    UMSLMODGOODQ2:
    ; We have a perfect guess g=q2, and and a non-negative remainder r2
    ;
    ; Register usage here
    ; AX=r2l BX=free CX=q2 DX=r2h SI=free DI=free ES=free DS=q1 stack=k
    ;
    ; g = q2 = CX
    ; q1 = DS
    MOV BX,CX ; q2 = BX := CX

    ; <<< start of denormalization >>>
    ;
    ; Register usage here
    ; AX=r2l BX=q2 CX=free DX=r2h SI=free DI=free ES=free DS=q1 stack=k
    ;
    ;
    ; r2 = DX:AX needs to be denormalized
    POP CX ; get k bits we shifted
    JCXZ UMSLMODDENORMBYPASS
    UMSLMODDENORMLOOP:
    SHR DX,1 ; r2 = DX:AX - shift right
    RCR AX,1 ; We DONT shift q1q2!!
    LOOP UMSLMODDENORMLOOP
    UMSLMODDENORMBYPASS:
    ; q2 = BX already
    MOV CX,DS ; q1 = CX := DS
    ;
    ; Register usage here
    ; AX=r2l BX=q2 CX=q1 DX=r2h SI=free DI=free ES=free DS=free
    ;
    XCHG SP,BP
    POP DS ; restore DS:SI and DI to usual values
    POP SI
    XOR DI,DI
    XCHG BP,SP
    ;
    PUSHDA ; push normalized remainder
    ; Register usage here
    ; AX=free BX=q2 CX=q1 DX=free SI=std DI=0 ES=free DS=std
    ;
    QNEXT

    ; ----- usual end -----

    UMSLMODGUESS1:

    ; If v1 = u0,
    ; Make a guess for q1 as s-1
    ; Statistically we rarely should execute this code
    ;
    ; Because we used guess s-1 Compute the remainder r1 as
    ; r1 = s*(u1+v1-v2) + u2+v2
    ;
    ; Register usage here
    ; AX=u1 BX=u2 CX=free DX=u0 SI=v1 DI=v2 ES=free DS=u3 stack=k
    ;
    ; u0 no longer needed
    MOV DX,AX ; u1 = DX := AX
    ; u1 no longer needed
    MOV AX,BX ; u2 no longer needed
    XOR BX,BX ; clear BX ready for carry
    ; cannot use DI to clear
    ADD AX,DI ; add on v2
    ADC DX,SI ; add on v1
    ADC BL,BH ; carry in BL, 0 in BH
    SUB DX,DI ; subtract off v2
    ; r1 in DX:AX
    SBB BL,BH ; borrow might be ok if
    ; cancelled by carry
    MOV CX,-1 ; g = CX = s-1 all FFFFs
    ; Test the remainder for being negative
    ;
    ; Register usage here
    ; AX=r1l BX=r1carry CX=g DX=r1h SI=v1 DI=v2 ES=free DS=u3 stack=k
    ;
    JNL UMSLMODGOODQ1 ; remainder was ok
    ; remainder was -ve
    UMSLMODBADQ1:
    ; If remainder is negative, decrement q1 and increment the
    ; remainder by v1v2
    ;
    ; Register usage here
    ; AX=r1l BX=r1carry CX=g DX=r1h SI=v1 DI=v2 ES=free DS=u3 stack=k
    ; ; g = CX, r1 = DX:AX
    ; v1 = SI; v2 = DI
    DEC CX ; g = CX := g - 1
    ADD AX,DI ; AX = r1l + v2
    ADC DX,SI ; DX = r1h + v1
    ADC BL,BH ; BL = r1carry BH=0
    ; Test the remainder for being negative
    JNL UMSLMODGOODQ1
    ; If remainder is still negative, decrement q1 and increment the
    ; remainder by v1v2 again
    DEC CX ; g = CX := g - 1
    ADD AX,DI ; AX = r1l + v2
    ADC DX,SI ; DX = r1h + v1
    ; Don't bother to compute
    ; BL = r1carry
    ; with ADC BL,BH
    ; Remainder guaranteed positive
    ;
    ; Register usage here
    ; AX=r1l BX=free CX=g DX=r1h SI=v1 DI=v2 ES=free DS=u3 stack=k
    ;
    JMP SHORT UMSLMODGOODQ1 ; guaranteed good remainder


    UMSLMODGUESS2:

    ; If v1 = r1h,
    ; Make a guess for q2 as s-1
    ; Statistically we rarely should execute this code
    ;
    ; Because we used guess s-1 Compute the remainder r1 as
    ; r2 = s*(r1l+v1-v2) + u3+v2
    ;
    ; Register usage here
    ; AX=r1l BX=u3 CX=free DX=r1h SI=v1 DI=v2 ES=r0 DS=q1 stack=k
    ;
    ; r1h = DX no longer needed
    MOV DX,AX ; r1l = DX := AX
    ; r1l no longer needed
    MOV AX,BX ; u3 = BX no longer needed
    XOR BX,BX ; clear BX ready for carry
    ; cannot use DI to clear
    ADD AX,DI ; add on v2
    ADC DX,SI ; add on v1
    ADC BL,BH ; keep carry in BL, 0 in BH
    SUB DX,DI ; subtract off v2
    ; r2 in DX:AX
    SBB BL,BH ; borrow might be ok if
    ; cancelled by carry
    MOV CX,-1 ; g = CX = s-1 all FFFFs
    ; Test the remainder for being negative
    ;
    ; Register usage here
    ; AX=r2l BX=r2carry CX=q2 DX=r2h SI=free DI=free ES=free DS=q1 stack=k
    ;
    JNL UMSLMODGOODQ2 ; remainder was ok
    ; remainder was -ve

    UMSLMODBADQ2:
    ; If remainder is negative, decrement guess g for q2 and increment
    the
    ; remainder by v1v2
    ;
    ; Register usage here
    ; AX=r2l BX=r2carry CX=g DX=r2h SI=v1 DI=v2 ES=free DS=q1 stack=k
    ;
    ; ; g = CX, r2 = DX:AX
    ; v1 = SI; v2 = DI
    DEC CX ; g = CX := g - 1
    ADD AX,DI ; AX = r2l + v2
    ADC DX,SI ; DX = r2h + v1
    ADC BL,BH ; BL = r2carry BH=0
    ; Test the remainder for being negative
    JNL UMSLMODGOODQ2
    ; If remainder is still negative, decrement q2 and increment the
    ; remainder by v1v2 again
    DEC CX ; g = CX := g - 1
    ADD AX,DI ; AX = r2l + v2
    ADC DX,SI ; DX = r2h + v1
    ; don't bother computing BL=
    ; r2carry with ADC BL,BH
    ; Register usage here
    ; AX=r2l BX=free CX=g DX=r2h SI=v1 DI=v2 ES=free DS=q1 stack=k
    ;
    ; Don't bother to test the remainder for being negative
    JMP SHORT UMSLMODGOODQ2 ; guaranteed good
    ; <<<< end of UM/MOD >>> Whew!

    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, May 20, 2004
    #2
    1. Advertising

  3. Allan H Wax wrote:
    > Does anyone have a good reference for something to convert a long as if
    > it were an unsigned long to a string. Even better, one that allows me
    > to convert it to a number of bases (hex, octal, binary)


    <http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Long.html#toHexString(long)>
    Thomas Schodt, May 20, 2004
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Twisted

    Arithmetic with longs

    Twisted, Jun 13, 2006, in forum: Java
    Replies:
    25
    Views:
    851
    Oliver Wong
    Jun 19, 2006
  2. Chris
    Replies:
    12
    Views:
    804
    Patricia Shanahan
    Aug 24, 2006
  3. David Geering

    longs, long longs, short short long ints . . . huh?!

    David Geering, Jan 8, 2007, in forum: C Programming
    Replies:
    15
    Views:
    557
    Keith Thompson
    Jan 11, 2007
  4. CFAN
    Replies:
    6
    Views:
    818
    Tor Rustad
    Apr 4, 2007
  5. pozz
    Replies:
    12
    Views:
    738
    Tim Rentsch
    Mar 20, 2011
Loading...

Share This Page