"

 COPYRIGHT (c) 1988 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 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 :-).

$Header: /cvs/stx/stx/libbasic/Attic/LargeInt.st,v 1.7 1994-02-25 12:58:55 claus Exp $

'!

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

! !

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

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

!

// aNumber

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

    |otherSign|

    otherSign := aNumber sign.

    (aNumber class == SmallInteger) 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 == LargeInteger) 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 remainder of division of the receiver by the argument, aNumber"

    |otherSign|

    otherSign := aNumber sign.

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

!

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

     otherDigitArray |

    len1 := digitArray size.

    otherDigitArray := aLargeInteger digits.

    len2 := otherDigitArray size.

    [(digitArray basicAt:len1) == 0] whileTrue:[

        len1 := len1 - 1

    ].

    [(otherDigitArray basicAt:len2) == 0] whileTrue:[

        len2 := len2 - 1

    ].

    (len1 ~~ len2) ifTrue:[^ false].

    [len1 > 0] whileTrue:[

        d1 := digitArray basicAt:len1.

        d2 := otherDigitArray 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 }"

     otherDigitArray |

    len1 := digitArray size.

    otherDigitArray := aLargeInteger digits.

    len2 := otherDigitArray size.

    [(digitArray basicAt:len1) == 0] whileTrue:[

        len1 := len1 - 1

    ].

    [(otherDigitArray basicAt:len2) == 0] whileTrue:[

        len2 := len2 - 1

    ].

    (len1 < len2) ifTrue:[^ true].

    (len1 > len2) ifTrue:[^ false].

    [len1 > 0] whileTrue:[

        d1 := digitArray basicAt:len1.

        d2 := otherDigitArray 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 otherDigitArray resultDigitArray

     len1  "{ Class: SmallInteger }"

     len2  "{ Class: SmallInteger }"

     index "{ Class: SmallInteger }"

     carry "{ Class: SmallInteger }"

     sum   "{ Class: SmallInteger }" |

    len1 := digitArray size.

    otherDigitArray := aLargeInteger digits.

    len2 := otherDigitArray size.

    result := LargeInteger basicNew 

                           numberOfDigits:((len1 max: len2) + 1).

    result sign:1.

    resultDigitArray := 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 + (otherDigitArray basicAt:index)

            ]

        ] ifFalse:[

            (index <= len2) ifTrue:[

                sum := sum + (otherDigitArray basicAt:index)

            ] ifFalse:[

                "end reached"

                done := true

            ]

        ].

        (sum > 9999) ifTrue:[

            carry := 1.

            sum := sum - 10000

        ] ifFalse:[

            carry := 0

        ].

        resultDigitArray basicAt:index put:sum.

        index := index + 1

    ].

    ^ result normalize

!

absMinus:aLargeInteger

    "return a LargeInteger representing abs(self) - abs(theArgument)"

    |result done

     otherDigitArray resultDigitArray

     len1   "{ Class: SmallInteger }"

     len2   "{ Class: SmallInteger }"

     index  "{ Class: SmallInteger }"

     borrow "{ Class: SmallInteger }"

     diff   "{ Class: SmallInteger }"

     sum    "{ Class: SmallInteger }"

     carry  "{ Class: SmallInteger }" |

    len1 := digitArray size.

    otherDigitArray := aLargeInteger digits.

    len2 := otherDigitArray size.