"
 COPYRIGHT (c) 1994 by Claus Gittinger
              All Rights Reserved

 This software is furnished under a license and may be used
 only in accordance with the terms of that license and with the
 inclusion of the above copyright notice.   This software may not
 be provided or otherwise made available to, or used by, any
 other person.  No title to or ownership of the software is
 hereby transferred.
"

Integer subclass:#LargeInteger
         instanceVariableNames:'sign digitByteArray'
         classVariableNames:''
         poolDictionaries:''
         category:'Magnitude-Numbers'
!

LargeInteger comment:'

COPYRIGHT (c) 1994 by Claus Gittinger
              All Rights Reserved

$Header: /cvs/stx/stx/libbasic/LargeInteger.st,v 1.10 1994-06-02 11:20:42 claus Exp $
'!

!LargeInteger class methodsFor:'documentation'!

documentation
"
    This class provides arbitrary precision integers. These are represented as:
      sign (-1/0/+1) and, if sign ~~ 0
      a ByteArray of digits with 8 bits per element; 
      least significant  8 bits at index 1 ...

    This is definitely not a good (fast) implementation -
    but ok for now, since LargeIntegers are not used very often.
    It will be reimplemented when everything else runs fine and a need arises
    (or someone rewrites it and sends me the code :-).

    For real speed, its implementation should be mapped onto a tuned arbitrary
    precision math package (maybe even special-cased for 32 and 64 bit large-ints,
    since those are the most common).
"
! !

!LargeInteger class methodsFor:'instance creation'!

value:aSmallInteger
    "create and return a new LargeInteger with value taken from
     the argument, aSmallInteger"

    ^ self basicNew value:aSmallInteger

    "LargeInteger value:3689"
!

new:numberOfDigits
    "catch creation message"

    self error:'LargeIntegers cannot be created with new'
!

new
    "catch creation message"

    self error:'LargeIntegers cannot be created with new'
!

valueLow:lowBits hi:hiBits
    "create and return a new LargeInteger with value taken from
     the two 16-bit signed args. This method is called from the runtime
     system, when an integer result has to be converted to a Large."

    hiBits < 0 ifTrue:[
        ^ ((self value:hiBits negated) * 16r10000 + lowBits) negated
    ].
    ^ (self value:hiBits) * 16r10000 + lowBits
!

unsignedValueLow:lowBits hi:hiBits
    "create and return a new LargeInteger with value taken from
     the two 16-bit unsigned args. This method is called from the runtime
     system, when an integer result has to be converted to a Large."

    ^ (self value:hiBits) * 16r10000 + lowBits
!

sign:s value16:ll value16:ml value16:mh value16:hh
    "create and return a new LargeInteger, with value taken from the
     four 16-bit unsigned value-args.
     This is sent internally, when a 64bit result has been created in
     SmallInteger multiplication"

    |newLarge digitBytes|

    newLarge := self basicNew numberOfDigits:8.
    newLarge sign:s.
    digitBytes := newLarge digits.
    digitBytes at:1 put:(ll bitAnd:16rFF).
    digitBytes at:2 put:((ll bitShift:-8) bitAnd:16rFF).
    digitBytes at:3 put:(ml bitAnd:16rFF).
    digitBytes at:4 put:((ml bitShift:-8) bitAnd:16rFF).
    digitBytes at:5 put:(mh bitAnd:16rFF).
    digitBytes at:6 put:((mh bitShift:-8) bitAnd:16rFF).
    digitBytes at:7 put:(hh bitAnd:16rFF).
    digitBytes at:8 put:((hh bitShift:-8) bitAnd:16rFF).
    ^ newLarge
! !

!LargeInteger methodsFor:'arithmetic'!

// aNumber
    "return the quotient of the receiver and the argument, aNumber"

    |otherSign|

    otherSign := aNumber sign.

    (aNumber class == SmallInteger) ifTrue:[
        (aNumber abs between:1 and:16r3fffff) ifTrue:[
            sign < 0 ifTrue:[
                (sign == otherSign) ifTrue:[^ (self negated absFastDiv:aNumber negated) at:1].
                ^ ((self negated absFastDiv:aNumber) at:1) negated
            ].
            (sign == otherSign) ifTrue:[^ (self absFastDiv:aNumber) at:1].
            ^ ((self absFastDiv:aNumber negated) at:1) negated
        ]
    ].

    (aNumber class == self class) ifTrue:[
        sign < 0 ifTrue:[
            (sign == otherSign) ifTrue:[^ (self negated absDiv:aNumber negated) at:1].
            ^ ((self negated absDiv:aNumber) at:1) negated
        ].
        (sign == otherSign) ifTrue:[^ (self absDiv:aNumber) at:1].
        ^ ((self absDiv:aNumber negated) at:1) negated
    ].

    ^ self retry:#// coercing:aNumber
!

+ aNumber
    "return the sum of the receiver and the argument, aNumber"

    |otherSign|

    (aNumber class == SmallInteger) ifTrue:[
        ^ self sumFromInteger:aNumber
    ].
    (aNumber class == self class) ifFalse:[
        ^ self retry:#+ coercing:aNumber
    ].
    otherSign := aNumber sign.

    (sign > 0) ifTrue:[
        "I am positive"
        (otherSign > 0) ifTrue:[^ self absPlus:aNumber].
        (otherSign < 0) ifTrue:[^ self absMinus:aNumber].
        ^ self
    ].
    (sign == 0) ifTrue:[^ aNumber].
    "I am negative"
    (otherSign > 0) ifTrue:[^ aNumber absMinus:self].
    (otherSign < 0) ifTrue:[^ (self absPlus:aNumber) negated].
    ^ self
!

* aNumber
    "return the product of the receiver and the argument, aNumber"

    |otherSign|

    (aNumber class == SmallInteger) ifTrue:[
        ^ self productFromInteger:aNumber
    ].

    (aNumber class == self class) ifFalse:[
        ^ self retry:#* coercing:aNumber
    ].
    otherSign := aNumber sign.
   
    (sign == 0) ifTrue:[^ 0].
    (sign == otherSign) ifTrue:[^ self absMul:aNumber].
    (otherSign == 0) ifTrue:[^ 0].
    ^ (self absMul:aNumber) negated
!

\\ aNumber
    "return the remainder of division of the receiver by the argument, aNumber"

    |otherSign|

    otherSign := aNumber sign.
    (aNumber class == SmallInteger) ifTrue:[
        (aNumber abs between:1 and:16r003fffff) ifTrue:[
            sign < 0 ifTrue:[
                (sign == otherSign) ifTrue:[^ (self negated absFastDiv:aNumber negated) at:2].
                ^ ((self negated absFastDiv:aNumber) at:2) negated
            ].
            (sign == otherSign) ifTrue:[^ (self absFastDiv:aNumber) at:2].
            ^ ((self absFastDiv:aNumber negated) at:2) negated
        ]
    ].
    (aNumber class == self class) ifTrue:[
        sign < 0 ifTrue:[
            (sign == otherSign) ifTrue:[^ (self negated absDiv:aNumber negated) at:2].
            ^ ((self negated absDiv:aNumber) at:2) negated
        ].
        (sign == otherSign) ifTrue:[^ (self absDiv:aNumber) at:2].
        ^ ((self absDiv:aNumber negated) at:2) negated
    ].

    ^ self retry:#\\ coercing:aNumber
!

- aNumber
    "return the difference of the receiver and the argument, aNumber"

    |otherSign|

    (aNumber class == self class) ifFalse:[
        ^ self retry:#- coercing:aNumber
    ].
    otherSign := aNumber sign.
    (sign > 0) ifTrue:[
        "I am positive"
        (otherSign > 0) ifTrue:[^ self absMinus:aNumber].
        (otherSign < 0) ifTrue:[^ self absPlus:aNumber].
        ^ self
    ].
    (sign == 0) ifTrue:[^ aNumber negated].
    "I am negative"
    (otherSign > 0) ifTrue:[^ (self absPlus:aNumber) negated].
    (otherSign < 0) ifTrue:[^ (self absMinus:aNumber) negated].
    ^ self
!

/ aNumber
    "return the quotient of the receivers and the argument, aNumber"

    aNumber isInteger ifTrue:[
        ^ (Fraction numerator:self
                  denominator:aNumber) reduced
    ].

    "this is a q&d hack - we loose lots of precision here ..."
    ^ (self asFloat / aNumber asFloat)
!

negated
    "return a LargeInteger with value negated from receivers value"

    |newNumber|

    (sign == 0) ifTrue:[^ 0].
    newNumber := self shallowCopy.
    newNumber sign:(sign negated).
    ^ newNumber
! !

!LargeInteger methodsFor:'double dispatching'!

sumFromInteger:anInteger
    "sent, when anInteger does not know how to add the receiver.
     Return the sum of the receiver and the argument, aSmallInteger"

    |result resultDigitByteArray
     len     "{ Class: SmallInteger }"
     index   "{ Class: SmallInteger }"
     carry   "{ Class: SmallInteger }"
     sum     "{ Class: SmallInteger }" |

    sign == anInteger sign ifFalse:[
        anInteger == 0 ifTrue:[
            ^ self
        ].
        ^ anInteger retry:#+ coercing:self
    ].

    len := digitByteArray size.
    result := self class basicNew numberOfDigits:(len + 4).
    result sign:sign.
    resultDigitByteArray := result digits.

    carry := anInteger abs.
    index := 1.

    [carry ~~ 0] whileTrue:[
        sum := (digitByteArray basicAt:index) + (carry bitAnd:16rFF).
        resultDigitByteArray basicAt:index put:(sum bitAnd:16rFF).
        carry := (sum bitShift:-8) + (carry bitShift:-8).
        index := index + 1
    ].
    [index <= len] whileTrue:[
        resultDigitByteArray basicAt:index 
                                 put:(digitByteArray basicAt:index).
        index := index + 1
    ].
    ^ result normalize
!

productFromInteger:anInteger
    "sent, when anInteger does not know how to multiply the receiver.
     Return the product of the receiver and the argument, aSmallInteger"

    |num result 
     resultDigitByteArray
     val     "{ Class: SmallInteger }"
     len     "{ Class: SmallInteger }"
     carry   "{ Class: SmallInteger }"
     prod    "{ Class: SmallInteger }" 
     ok|

    "multiplying by a small integer is done here"

    "trivial cases"
    anInteger == 0 ifTrue:[^ 0].
    anInteger == 1 ifTrue:[^ self].

    num := anInteger abs.
    (num > 16r3FFFFF) ifTrue:[
        "if num is too big (so that multiplying by a byte could create a Large)"

        ^ anInteger retry:#* coercing:self
    ].

    len := digitByteArray size.

    result := self class basicNew numberOfDigits:(len + 4).

    "used to be the following. replaced, to avoid another multiplication"
"
    result sign:(sign * anInteger sign).
"
    anInteger < 0 ifTrue:[
        sign < 0 ifTrue:[
            result sign:1
        ] ifFalse:[
            result sign:-1
        ].
    ] ifFalse:[
        result sign:sign
    ].

    resultDigitByteArray := result digits.

    carry := 0.
    val := num.

    ok := false.
%{
    if (_isSmallInteger(len)
     && _isSmallInteger(val)
     && __isByteArray(_INST(digitByteArray))
     && __isByteArray(resultDigitByteArray)) {
	int _l = _intVal(len);
	int _v = _intVal(val);
	unsigned _carry = 0;
	unsigned _prod;
	unsigned char *digitP = _ByteArrayInstPtr(_INST(digitByteArray))->ba_element;
	unsigned char *resultP = _ByteArrayInstPtr(resultDigitByteArray)->ba_element;

	while (_l-- > 0) {
	    _prod = *digitP++ * _v + _carry;
	    *resultP++ = _prod & 0xFF;
	    _carry = _prod >> 8;
	}
	while (_carry) {
	    *resultP++ = _carry & 0xFF;
	    _carry >>= 8;
	}
	ok = true;
    }
%}.
    ok ifFalse:[
        1 to:len do:[:i |
            prod := (digitByteArray basicAt:i) * val + carry.
            resultDigitByteArray basicAt:i put:(prod bitAnd:16rFF).
            carry := prod bitShift:-8.
        ].
        [carry ~~ 0] whileTrue:[
            len := len + 1.
            resultDigitByteArray basicAt:len put:(carry bitAnd:16rFF).
            carry := carry bitShift:-8
        ].
    ].
    ^ result normalize
! !

!LargeInteger methodsFor:'coercing & converting'!

coerce:aNumber
    "return the argument as a LargeInteger"

    ^ aNumber asLargeInteger
!

value:aSmallInteger
    "return a new LargeInteger with value taken from a SmallInteger"

    |absValue 
     index "{ Class: SmallInteger }"|

    (aSmallInteger == 0) ifTrue: [
        digitByteArray := nil.
        sign := 0.
        ^ self
    ].
    (aSmallInteger < 0) ifTrue: [
        sign := -1.
        absValue := aSmallInteger negated
    ] ifFalse: [
        sign := 1.
        absValue := aSmallInteger
    ].
    digitByteArray := ByteArray new:4.
    index := 1.
    [absValue == 0] whileFalse: [
        digitByteArray at:index put:(absValue bitAnd:16rFF).
        absValue := absValue bitShift:-8.
        index := index + 1
    ].
    [index <= 4] whileTrue:[
        digitByteArray at:index put:0.
        index := index + 1
    ]
!

asSmallInteger
    "return a SmallInteger with same value as myself - the result
     is invalid if the receivers value cannot be represented
     as a SmallInteger"

    |value|

    value := 0.
    (sign == 0) ifFalse:[
        digitByteArray reverseDo:[:aDigit |
            value := (value times:256) + aDigit 
        ].
        (sign < 0) ifTrue:[
            value := value negated
        ]
    ].
    ^ value
!

asLargeInteger
    "return a LargeInteger with same value as myself - thats me"

    ^ self
!

asFloat
    "return a Float with same value as myself"

    |newFloat|

    newFloat := 0.0.
    (sign == 0) ifFalse:[
        digitByteArray reverseDo:[:aDigit |
            newFloat := (newFloat * 256.0) + aDigit asFloat
        ].
        (sign < 0) ifTrue:[
            newFloat := newFloat negated
        ]
    ].
    ^ newFloat
! !

!LargeInteger methodsFor:'byte access'!

digitLength
    "return the number bytes used by this Integer"

    ^ digitByteArray size
!

digitAt:index
    "return 8 bits of value, starting at byte index"

    index > digitByteArray size ifTrue:[^ 0].
    ^ digitByteArray at:index
!

digitAt:index put:aByte
    "set the 8 bits, index is a byte index"

    digitByteArray at:index put:aByte
! !

!LargeInteger methodsFor:'private'!

normalize
    "if the receiver can be represented as a SmallInteger, return
     a SmallInteger with my value; otherwise return self with leading
     zeros removed"

    |index "{ Class: SmallInteger }" 
     val   "{ Class: SmallInteger }" |

    index := digitByteArray size.
    [(index > 0) and:[(digitByteArray at:index) == 0]] whileTrue:[
        index := index - 1
    ].
    (index == 1) ifTrue:[
        ^ (digitByteArray at:1) * sign
    ].
    (index == 2) ifTrue:[
        ^ ((digitByteArray at:2) bitShift:8) + (digitByteArray at:1) * sign
    ].
    (index == 3) ifTrue:[
        val := digitByteArray at:3.
        val := (val bitShift:8) + (digitByteArray at:2).
        val := (val bitShift:8) + (digitByteArray at:1).
        ^ val * sign
    ].
    index == 4 ifTrue:[
        (digitByteArray at:4) < 16r3F ifTrue:[
            val := digitByteArray at:4.
            val := (val bitShift:8) + (digitByteArray at:3).
            val := (val bitShift:8) + (digitByteArray at:2).
            val := (val bitShift:8) + (digitByteArray at:1).
            ^ val * sign
        ]
    ].
    (index == 0) ifTrue:[
        ^ 0
    ].
    (index ~~ digitByteArray size) ifTrue:[
        digitByteArray := digitByteArray copyFrom:1 to:index
    ].
    ^ self
!

absFastDiv:aSmallInteger
    "return an array with two LargeIntegers representing
     abs(self) // aSmallInteger and abs(self) \\ aSmallInteger"

    |tmp1     "{ Class: SmallInteger }"
     prevRest "{ Class: SmallInteger }"
     count    "{ Class: SmallInteger }"
     newDigitByteArray result
     ok|

    aSmallInteger == 0 ifTrue:[
        ^ DivisionByZeroSignal raise
    ].

"This cannot happen (if always normalized)
    self < aSmallInteger ifTrue:[
        ^ Array with:0 with:self
    ].
"
    count := digitByteArray size.
    result := self class basicNew numberOfDigits:count.
    result sign:1.
    newDigitByteArray := result digits.
    ok := false.
%{
    if (__isByteArray(_INST(digitByteArray))
     && __isByteArray(newDigitByteArray)
     && _isSmallInteger(count)
     && _isSmallInteger(aSmallInteger)) {
        unsigned int rest = 0;
        int index = _intVal(count);
        int divisor = _intVal(aSmallInteger);
        unsigned char *digitBytes = _ByteArrayInstPtr(_INST(digitByteArray))->ba_element;
        unsigned char *resultBytes = _ByteArrayInstPtr(newDigitByteArray)->ba_element;

        while (index > 0) {
            unsigned int t;

            index--;
            t = digitBytes[index];
            t = t | (rest << 8);
            resultBytes[index] = t / divisor;
            rest = t % divisor;
        }
        prevRest = _MKSMALLINT(rest);
        ok = true;
    }
%}.
    "
     slow code - not normally reached
     (could also do a primitiveFailure here)
    "
    ok ifTrue:[
        prevRest := 0.
        count to:1 by:-1 do:[:i |
            tmp1 := digitByteArray at:i.
            tmp1 := (tmp1 + (prevRest * 256)).
            newDigitByteArray at:i put:tmp1 // aSmallInteger.
            prevRest := (tmp1 \\ aSmallInteger).
        ]
    ].

    ^ Array with:(result normalize) with:prevRest
!

absMul:aLargeInteger
    "return a LargeInteger representing abs(self) * abs(theArgument)"

    |result otherDigitByteArray resultDigitByteArray
     idx      "{ Class: SmallInteger }"
     carry    "{ Class: SmallInteger }"
     len1     "{ Class: SmallInteger }"
     len2     "{ Class: SmallInteger }"
     dstIndex "{ Class: SmallInteger }"
     prod     "{ Class: SmallInteger }"
     v        "{ Class: SmallInteger }"|

    len1 := digitByteArray size.
    otherDigitByteArray := aLargeInteger digits.
    len2 := otherDigitByteArray size.

    result := LargeInteger basicNew numberOfDigits:(len1 + len2 + 1).
    result sign:1.
    resultDigitByteArray := result digits.

    1 to:len1 do:[:index1 |
        1 to:len2 do:[:index2 |
            dstIndex := index1 + index2 - 1.
            prod := (digitByteArray basicAt:index1) * (otherDigitByteArray basicAt:index2).
            prod := prod + (resultDigitByteArray basicAt:dstIndex).
            resultDigitByteArray basicAt:dstIndex put:(prod bitAnd:16rFF).
            carry := prod bitShift:-8.
            carry ~~ 0 ifTrue:[
                idx := dstIndex + 1.
                [carry ~~ 0] whileTrue:[
                    v := (resultDigitByteArray basicAt:idx) + carry.
                    resultDigitByteArray basicAt:idx put:(v bitAnd:255).
                    carry := v bitShift:-8.
                    idx := idx + 1
                ]
            ]
        ]
    ].
    ^ result normalize
!

sign:aNumber
    sign := aNumber
!

numberOfDigits:nDigits
    digitByteArray := ByteArray new:nDigits
!

numberOfDigits
    ^ digitByteArray size
!

digits
    ^ digitByteArray
!

absLess:aLargeInteger
    "return true, if abs(self) < abs(theArgument)"

    |len1 "{ Class: SmallInteger }"
     len2 "{ Class: SmallInteger }"
     d1   "{ Class: SmallInteger }"
     d2   "{ Class: SmallInteger }"
     otherDigitByteArray |

    len1 := digitByteArray size.
    otherDigitByteArray := aLargeInteger digits.
    len2 := otherDigitByteArray size.

    [(digitByteArray basicAt:len1) == 0] whileTrue:[
        len1 := len1 - 1
    ].
    [(otherDigitByteArray basicAt:len2) == 0] whileTrue:[
        len2 := len2 - 1
    ].
    (len1 < len2) ifTrue:[^ true].
    (len1 > len2) ifTrue:[^ false].

    [len1 > 0] whileTrue:[
        d1 := digitByteArray basicAt:len1.
        d2 := otherDigitByteArray basicAt:len1.
        (d1 < d2) ifTrue:[^ true].
        (d1 > d2) ifTrue:[^ false].
        len1 := len1 - 1
    ].
    ^ false
!

absPlus:aLargeInteger
    "return a LargeInteger representing abs(self) + abs(theArgument)"

    |result done otherDigitByteArray resultDigitByteArray
     len1  "{ Class: SmallInteger }"
     len2  "{ Class: SmallInteger }"
     index "{ Class: SmallInteger }"
     carry "{ Class: SmallInteger }"
     sum   "{ Class: SmallInteger }" |

    len1 := digitByteArray size.
    otherDigitByteArray := aLargeInteger digits.
    len2 := otherDigitByteArray size.

    result := self class basicNew 
                           numberOfDigits:((len1 max: len2) + 1).
    result sign:1.
    resultDigitByteArray := result digits.

    index := 1.
    carry := 0.

    done := false.
    [done] whileFalse:[
        sum := carry.
        (index <= len1) ifTrue:[
            sum := sum + (digitByteArray basicAt:index).
            (index <= len2) ifTrue:[
                sum := sum + (otherDigitByteArray basicAt:index)
            ]
        ] ifFalse:[
            (index <= len2) ifTrue:[
                sum := sum + (otherDigitByteArray basicAt:index)
            ] ifFalse:[
                "end reached"
                done := true
            ]
        ].
        (sum >= 16r100) ifTrue:[
            carry := 1.
            sum := sum - 16r100
        ] ifFalse:[
            carry := 0
        ].
        resultDigitByteArray basicAt:index put:sum.
        index := index + 1
    ].
    ^ result normalize
!

absEq:aLargeInteger
    "return true, if abs(self) = abs(theArgument)"

    |len1 "{ Class: SmallInteger }"
     len2 "{ Class: SmallInteger }"
     d1   "{ Class: SmallInteger }"
     d2   "{ Class: SmallInteger }"
     otherDigitByteArray |

    len1 := digitByteArray size.
    otherDigitByteArray := aLargeInteger digits.
    len2 := otherDigitByteArray size.

    [(digitByteArray basicAt:len1) == 0] whileTrue:[
        len1 := len1 - 1
    ].
    [(otherDigitByteArray basicAt:len2) == 0] whileTrue:[
        len2 := len2 - 1
    ].
    (len1 ~~ len2) ifTrue:[^ false].
    [len1 > 0] whileTrue:[
        d1 := digitByteArray basicAt:len1.
        d2 := otherDigitByteArray basicAt:len1.
        (d1 ~~ d2) ifTrue:[^ false].
        len1 := len1 - 1
    ].
    ^ true
!

absMinus:aLargeInteger
    "return a LargeInteger representing abs(self) - abs(theArgument)"

    |result done
     otherDigitByteArray resultDigitByteArray
     len1   "{ Class: SmallInteger }"
     len2   "{ Class: SmallInteger }"
     index  "{ Class: SmallInteger }"
     borrow "{ Class: SmallInteger }"
     diff   "{ Class: SmallInteger }"
     sum    "{ Class: SmallInteger }"
     carry  "{ Class: SmallInteger }" |

    len1 := digitByteArray size.
    otherDigitByteArray := aLargeInteger digits.
    len2 := otherDigitByteArray size.

    result := self class basicNew 
                           numberOfDigits:((len1 max: len2) + 1).
    result sign:1.
    resultDigitByteArray := result digits.

    index := 1.
    borrow := 0.

    done := false.
    [done] whileFalse:[
        diff := borrow.
        (index <= len1) ifTrue:[
            diff := diff + (digitByteArray basicAt:index).
            (index <= len2) ifTrue:[
                diff := diff - (otherDigitByteArray basicAt:index)
            ]
        ] ifFalse:[
            (index <= len2) ifTrue:[
                diff := diff - (otherDigitByteArray basicAt:index)
            ] ifFalse:[
                "end reached"
                done := true
            ]
        ].
        (diff < 0) ifTrue:[
            borrow := -1.
            diff := diff + 16r100
        ] ifFalse:[
            borrow := 0
        ].
        resultDigitByteArray basicAt:index put:diff.
        index := index + 1
    ].
    (borrow ~~ 0) ifTrue:[
        result sign: -1.
        carry := 0.
        1 to:(index - 1) do:[:i |
            sum := ((resultDigitByteArray at:i) + carry - 16r100) negated.
            resultDigitByteArray at:i put:sum.
            carry := 1
        ]
    ].
    ^ result normalize
!

absDiv:anInteger
    "return an array with two LargeIntegers representing
     abs(self) // abs(theArgument) and abs(self) \\ abs(theArgument).
     This needs a rewrite."

    |tmp1 tmp2 
     rem 
     count "{ Class: SmallInteger }"
     digit "{ Class: SmallInteger }" |

    anInteger == 0 ifTrue:[
        ^ DivisionByZeroSignal raise
    ].

    self < anInteger ifTrue:[
        ^ Array with:0 with:self
    ].

    tmp1 := self simpleDeepCopy.
    tmp2 := anInteger simpleDeepCopy.
    count := 0.
    [tmp2 < tmp1] whileTrue:[
        tmp2 mul256.
        count := count + 1
    ].

    tmp2 div256.

    rem := 0 asLargeInteger. 
    [count == 0] whileFalse:[
        digit := 0.
        [tmp1 >= tmp2] whileTrue:[
            digit := digit + 1.
            tmp1 := tmp1 - tmp2
        ].
        rem := rem * 256 + digit.
        tmp2 div256.
        count := count - 1
    ].
    ^ Array with:rem with:tmp1 
!

div256
    "destructively divide the receiver by 256.
     private - used for division only"

    digitByteArray replaceFrom:1 with:digitByteArray startingAt:2.
    digitByteArray at:(digitByteArray size) put:0
!

mul256
    "destructively multiply the receiver by 256.
     private - used for division only"

    |newDigits|

    newDigits := ByteArray new:(digitByteArray size + 1).
    newDigits replaceFrom:2 with:digitByteArray startingAt:1.
    newDigits at:1 put:0.
    digitByteArray := newDigits
! !

!LargeInteger methodsFor:'comparing'!

= aNumber
    "return true, if the argument, aNumber has the same value as
     the receiver"

    (aNumber class == self class) ifFalse:[
        aNumber respondsToArithmetic ifFalse:[ ^ false ].
        ^ self retry:#= coercing:aNumber
    ].
    (aNumber sign == sign) ifFalse:[^ false].
    ^ self absEq:aNumber
!

< aNumber
    "return true, if the argument, aNumber is greater than the receiver"

    |otherSign|

    (aNumber class == self class) ifFalse:[
        ^ self retry:#< coercing:aNumber
    ].
    otherSign := aNumber sign.

    (sign > 0) ifTrue:[
        "I am positive"
        (otherSign > 0) ifTrue:[^ self absLess:aNumber].
        ^ false "aNumber is <= 0"
    ].
    (sign == 0) ifTrue:[
        (otherSign > 0) ifTrue:[^ true].
        ^ false
    ].
    "I am negative"
    (otherSign > 0) ifTrue:[^ true].
    (otherSign == 0) ifTrue:[^ true].
    ^ (self absLess:aNumber) not
!

> aNumber
    "return true, if the argument, aNumber is less than the receiver"

    |otherSign|

    (aNumber class == self class) ifFalse:[
        ^ self retry:#> coercing:aNumber
    ].
    otherSign := aNumber sign.

    (sign > 0) ifTrue:[
        "I am positive"
        (otherSign > 0) ifTrue:[^ aNumber absLess:self].
        ^ true "aNumber is <= 0"
    ].
    (sign == 0) ifTrue:[
        "I am zero"
        (otherSign > 0) ifTrue:[^ false].
        ^ true
    ].
    "I am negative"
    (otherSign > 0) ifTrue:[^ false].
    (otherSign == 0) ifTrue:[^ false].
    ^ (self absLess:aNumber) not
! !

!LargeInteger methodsFor:'testing'!

sign
    "return the sign of the receiver"

    ^ sign
!

negative
    "return true, if the receiver is < 0"

    ^ (sign < 0)
!

odd
    "return true if the receiver is odd"

    ^ (digitByteArray at:1) even
!

even
    "return true if the receiver is even"

    ^ (digitByteArray at:1) even
!

positive
    "return true, if the receiver is >= 0"

    ^ (sign >= 0)
!

strictlyPositive
    "return true, if the receiver is > 0"

    ^ (sign > 0)
! !

!LargeInteger methodsFor:'printing & storing'!

storeOn:aStream
    "append a representation of the receiver to aStream, which can
     be used to reconstruct the receiver."

    self printOn:aStream.
    aStream nextPutAll:' asLargeInteger'
! !