"
 COPYRIGHT (c) 1988-93 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 digitArray'
       classVariableNames:''
       poolDictionaries:''
       category:'Magnitude-Numbers'
!

LargeInteger comment:'

COPYRIGHT (c) 1988-93 by Claus Gittinger
              All Rights Reserved

This class provides arbitrary precision integers. These are represented as:
  sign (-1/0/+1) and, if sign ~~ 0
  an Array of digits with 4 digits per element; 
  least significant 4 digits 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 :-).

%W% %E%
'!

!LargeInteger class methodsFor:'instance creation'!

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'
!

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

    ^ self basicNew value:aSmallInteger

    "LargeInteger value:3689"
!

valueLow:lowBits hi:hiBits
    "create and return a new LargeInteger with value taken from
     the two 16-bit args"

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


!LargeInteger methodsFor:'coercing & converting'!

coerce:aNumber
    "return the argument as a LargeInteger"

    ^ aNumber asLargeInteger
!

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

    ^ self
!

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:[
        digitArray reverseDo:[:aDigit |
            value := (value times:10000) + aDigit 
        ].
        (sign < 0) ifTrue:[
            value := value negated
        ]
    ].
    ^ value
!

asFloat
    "return a Float with same value as myself"

    |newFloat|

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

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

    |absValue 
     index "{ Class: SmallInteger }"|

    (aSmallInteger == 0) ifTrue: [
        digitArray := nil.
        sign := 0.
        ^ self
    ].
    (aSmallInteger < 0) ifTrue: [
        sign := -1.
        absValue := aSmallInteger negated
    ] ifFalse: [
        sign := 1.
        absValue := aSmallInteger
    ].
    digitArray := Array new:3.
    index := 1.
    [absValue == 0] whileFalse: [
        digitArray at:index put:(absValue \\ 10000).
        absValue := absValue // 10000.
        index := index + 1
    ].
    [index <= 3] whileTrue:[
        digitArray at:index put:0.
        index := index + 1
    ]
! !
    
!LargeInteger methodsFor:'comparing'!

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

    (aNumber class == LargeInteger) 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 == LargeInteger) 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
! !

!LargeInteger methodsFor:'arithmetic'!

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

    |otherSign|

    (aNumber class == LargeInteger) 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 difference of the receiver and the argument, aNumber"

    |otherSign|

    (aNumber class == LargeInteger) 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 product of the receiver and the argument, aNumber"

    |otherSign|

    (aNumber = 10) ifTrue:[
        ^ self deepCopy mul10
    ].
    (aNumber class == LargeInteger) 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
    "this is a q&d hack - we loose lots of precision here ..."

    ^ (self asFloat / aNumber asFloat)
!
    
// aNumber
    "return the quotient of the receiver and the argument, aNumber"

    |otherSign|

    (aNumber = 10) ifTrue:[
        ^ self deepCopy div10
    ].
    (aNumber class == LargeInteger) ifFalse:[
        ^ self retry:#// coercing:aNumber
    ].
    otherSign := aNumber sign.

    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
!
    
\\ aNumber
    "return the remainder of division of the receiver by the argument, aNumber"

    |otherSign|

    (aNumber class == LargeInteger) ifFalse:[
        ^ self retry:#\\ coercing:aNumber
    ].

    otherSign := aNumber sign.
    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
!

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:'bit operations'!

bitAnd:anInteger
    "q & d hack to make Random work;
     this works only correctly, if my value can be represented
     as a SmallInteger"

    ^ self asSmallInteger bitAnd:anInteger
! !

!LargeInteger methodsFor:'testing'!

sign
    "return the sign of the receiver"

    ^ sign
!

odd
    "return true if the receiver is odd"

    ^ (digitArray at:1) even
!

even
    "return true if the receiver is even"

    ^ (digitArray at:1) even
!

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

    ^ (sign < 0)
!

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

    ^ (sign >= 0)
!

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

    ^ (sign > 0)
! !

!LargeInteger methodsFor:'private'!

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

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

    len1 := digitArray size.
    otherDigits := aLargeInteger digits.
    len2 := otherDigits size.

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

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

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

    len1 := digitArray size.
    otherDigits := aLargeInteger digits.
    len2 := otherDigits size.

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

    [len1 > 0] whileTrue:[
        d1 := digitArray basicAt:len1.
        d2 := otherDigits 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 otherDigits resultDigits
     len1  "{ Class: SmallInteger }"
     len2  "{ Class: SmallInteger }"
     index "{ Class: SmallInteger }"
     carry "{ Class: SmallInteger }"
     sum   "{ Class: SmallInteger }" |

    len1 := digitArray size.
    otherDigits := aLargeInteger digits.
    len2 := otherDigits size.

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

    index := 1.
    carry := 0.

    done := false.
    [done] whileFalse:[
        sum := carry.
        (index <= len1) ifTrue:[
            sum := sum + (digitArray basicAt:index).
            (index <= len2) ifTrue:[
                sum := sum + (otherDigits basicAt:index)
            ]
        ] ifFalse:[
            (index <= len2) ifTrue:[
                sum := sum + (otherDigits basicAt:index)
            ] ifFalse:[
                "end reached"
                done := true
            ]
        ].
        (sum > 9999) ifTrue:[
            carry := 1.
            sum := sum - 10000
        ] ifFalse:[
            carry := 0
        ].
        resultDigits basicAt:index put:sum.
        index := index + 1
    ].
    ^ result normalize
!

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

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

    len1 := digitArray size.
    otherDigits := aLargeInteger digits.
    len2 := otherDigits size.

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

    index := 1.
    borrow := 0.

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

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

    |result otherDigits resultDigits
     len1     "{ Class: SmallInteger }"
     len2     "{ Class: SmallInteger }"
     dstIndex "{ Class: SmallInteger }"
     carry    "{ Class: SmallInteger }"
     prod     "{ Class: SmallInteger }" |

    len1 := digitArray size.
    otherDigits := aLargeInteger digits.
    len2 := otherDigits size.

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

    "clear result"
    resultDigits atAllPut:0.

    1 to:len1 do:[:index1 |
        1 to:len2 do:[:index2 |
            dstIndex := index1 + index2 - 1.
            prod := (digitArray basicAt:index1) * (otherDigits basicAt:index2).
            prod := prod + (resultDigits basicAt:dstIndex).
            resultDigits basicAt:dstIndex put:(prod \\ 10000).
            carry := prod // 10000.
            (carry ~~ 0) ifTrue:[
                resultDigits basicAt:(dstIndex + 1)
                                 put:(resultDigits basicAt:(dstIndex + 1)) + carry
            ]
        ]
    ].
    ^ result normalize
!

absDiv:anInteger
    "return an array with two LargeIntegers representing
     abs(self) // abs(theArgument) and abs(self) \\ abs(theArgument)"

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

    self == 0 ifTrue:[^ 0].
    anInteger == 0 ifTrue:[^ self divideByZeroError].

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

    tmp1 := self deepCopy.
    tmp2 := anInteger deepCopy.
    count := 0.
    [tmp2 < tmp1] whileTrue:[
        tmp2 mul10.
        count := count + 1
    ].

    tmp2 div10.

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

mul10
    "destructively multiply the receiver by 10.
     private - used for division only"

    |carry "{ Class: SmallInteger }"
     prod  "{ Class: SmallInteger }"|

    carry := 0.
    1 to:(digitArray size) do:[:index |
        prod := (digitArray at:index) * 10 + carry.
        digitArray at:index put:prod \\ 10000.
        carry := prod // 10000
    ].
    carry ~~ 0 ifTrue:[
        digitArray := digitArray copyWith:carry
    ]
!

div10
    "destructively divide the receiver by 10.
     private - used for division only"

    |nDigits|

    nDigits := digitArray size.
    1 to:(nDigits - 1) do:[:index |
        digitArray at:index put:((digitArray at:index) // 10
                                + ((digitArray at:index + 1) \\ 10 * 1000))
    ].
    digitArray at:nDigits put:(digitArray at:nDigits) // 10
!

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 }" |

    index := digitArray size.
    [(index > 0) and:[(digitArray at:index) == 0]] whileTrue:[
        index := index - 1
    ].
    (index == 1) ifTrue:[
        ^ (digitArray at:1) * sign
    ].
    (index == 2) ifTrue:[
        ^ ((digitArray at:2) * 10000 + (digitArray at:1)) * sign
    ].
    (index == 0) ifTrue:[
        ^ 0
    ].
    (index ~~ digitArray size) ifTrue:[
        digitArray := digitArray copyFrom:1 to:index
    ].
    ^ self
!

digits
    ^ digitArray
!

numberOfDigits
    ^ digitArray size
!

numberOfDigits:nDigits
    digitArray := Array new:nDigits
!

sign:aNumber
    sign := aNumber
! !

!LargeInteger methodsFor:'printing & storing'!

storeString
    "return a string representation of the receiver, which can be
     used to reconstruct the receiver"

    ^ self printString , ' asLargeInteger'
!

printString
    |aString index fourDigits n|

    index := digitArray size.
    [(index > 1) and:[(digitArray at:index) == 0]] whileTrue:[
        index := index - 1
    ].
    (sign == 0) ifTrue: [^ '0'].
    (sign == -1) ifTrue: [
        aString := '-'
    ] ifFalse: [
        aString := ''
    ].

    aString := aString , (digitArray basicAt:index) printString.
    index := index - 1.
    [index > 0] whileTrue:[
        fourDigits := (digitArray basicAt:index) printString.
        n := fourDigits size.
        (n < 4) ifTrue:[
            aString := aString , ('000' copyFrom:n to:3)
        ].
        aString := aString , fourDigits.
        index := index - 1
    ].
    ^ aString
! !