"

 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.