"

 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  class methodsFor:'documentation'!

copyright

"

 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.

"

!

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

    The implementation is definitely not tuned for high performance

    (some key-methods should be rewritten as primitives),

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

    LargeIntegers are usually not created explicitely, but result from 

    SmallInteger arithmetic overflowing the SmallInteger range.

    Also, results of LargeInteger operations are converted to back to 

    SmallIntegers, when possible (see normalize).

    In contrast to ST-80, there is only one class for LargeIntegers, keeping

    the sign as an instance variable (ST-80 has LargePositiveInteger and

    LargeNegativeInteger). This may change.

    [author:]

        Claus Gittinger

    [see also:]

        Number

        Float Fraction 

        SmallInteger

"

! !

!LargeInteger  class methodsFor:'instance creation'!

new

    "catch creation message"

    self error:'LargeIntegers cannot be created with new'

!

new:numberOfDigits

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

     Notice: this should be only used internally, since such small

     largeIntegers do not normally occur in the system.

     May change without notice."

    ^ self basicNew value:aSmallInteger

    "LargeInteger value:3689"

! !

!LargeInteger  class methodsFor:'queries'!

isBuiltInClass

    "return true if this class is known by the run-time-system.

     Here, true is returned."

    ^ true

    "Modified: 23.4.1996 / 15:59:21 / cg"

! !

!LargeInteger methodsFor:'arithmetic'!

* aNumber

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

    |otherSign|

    (sign == 0) ifTrue:[^ 0].  "cannot happen if correctly normalized"

    "

     this is the common case, multiplying with SmallInteger.

     Use a special method for this case ...

    "

    (aNumber class == SmallInteger) ifTrue:[

	^ self productFromInteger:aNumber

    ].

    "

     if the argument is not a largeInteger, coerce

    "

    (aNumber class == self class) ifFalse:[

	^ self retry:#* coercing:aNumber

    ].

    otherSign := aNumber sign.

    (sign == otherSign) ifTrue:[^ self absMul:aNumber].

    (otherSign == 0) ifTrue:[^ 0].

    ^ (self absMul:aNumber) sign:-1

!

+ aNumber

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

    |otherSign|

    (sign == 0) ifTrue:[^ aNumber].  "cannot happen if correctly normalized"

    "

     this is the common case, adding a SmallInteger.

     Use a special method for this case ...

    "

    (aNumber class == SmallInteger) ifTrue:[

	^ self sumFromInteger:aNumber

    ].

    "

     if the argument is not a largeInteger, coerce

    "

    (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

    ].

    "I am negative"

    (otherSign > 0) ifTrue:[^ aNumber absMinus:self].

    (otherSign < 0) ifTrue:[^ (self absPlus:aNumber) sign:-1].

    ^ self

    "

     SmallInteger maxVal 

     SmallInteger maxVal + 1  

     SmallInteger maxVal + 2 

     SmallInteger minVal    

     SmallInteger minVal - 1

    "

!

- aNumber

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

    |otherSign result|

    (sign == 0) ifTrue:[^ aNumber negated].     "cannot happen if correctly normalized"

    "

     this is the common case, subtracting a SmallInteger.

     Use a special method for this case ...

    "

    (aNumber class == SmallInteger) ifTrue:[

	sign < 0 ifTrue:[

	    aNumber > 0 ifTrue:[

		result := (self absFastPlus:aNumber) sign:-1

	    ] ifFalse:[

		result := (self absFastMinus:aNumber) sign:-1

	    ].

	] ifFalse:[

	    aNumber > 0 ifTrue:[

		result := self absFastMinus:aNumber

	    ] ifFalse:[

		result := self absFastPlus:aNumber

	    ]

	].

	^ result normalize.

    ].

    "

     if the argument is not a largeInteger, coerce

    "

    (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

    ].

    "I am negative"

    (otherSign > 0) ifTrue:[^ (self absPlus:aNumber) negated].

    (otherSign < 0) ifTrue:[^ (self absMinus:aNumber) negated].

    ^ self

    "

     12345678901234567890 - 0     

     12345678901234567890 - 1      

     12345678901234567890 - -1    

     -12345678901234567890 - 1     

     -12345678901234567890 - -1    

     12345678901234567890 - 12345678901234567880     

     12345678901234567890 - 12345000000000000000     

     12345678901234567890 - -87654321098765432110    

     -12345678901234567890 - 87654321098765432110    

     -12345678901234567890 - -12345678901234567880   

     -12345678901234567890 - -12345678901234567980   

    "

!

/ aNumber

    "return the quotient of the receiver 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 divMod d|

    otherSign := aNumber sign.

    "

     this is the common case, dividing by a SmallInteger.

     Use a special method for this case ...

    "

    (aNumber class == SmallInteger) ifTrue:[

	(aNumber abs between:1 and:16r003fffff) ifTrue:[

	    sign < 0 ifTrue:[

		(sign == otherSign) ifTrue:[^ (self absFastDiv:aNumber negated) at:1].

		d := aNumber.

	    ] ifFalse:[

		(sign == otherSign) ifTrue:[^ (self absFastDiv:aNumber) at:1].

		d := aNumber negated

	    ].

	    divMod := self absFastDiv:d.

	    "/ stupid adjust ...

	    (divMod at:2) == 0 ifFalse:[

		^ ((divMod at:1) sign:-1) - 1

	    ].

	    ^ (divMod at:1) sign:-1

	]

    ].

    "

     if the argument is not a largeInteger, coerce

    "

    (aNumber class == self class) ifFalse:[

	^ self retry:#// coercing:aNumber

    ].

    sign < 0 ifTrue:[

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

    ] ifFalse:[

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

    ].

    divMod := self absDiv:aNumber.

    "/ stupid adjust ...

    (divMod at:2) == 0 ifFalse:[

	^ ((divMod at:1) sign:-1) - 1

    ].

    ^ (divMod at:1) sign:-1

    "

     9000000000 // 4000000000   => 2

     -9000000000 // 4000000000  => -3

     9000000000 // -4000000000  => -3

     -9000000000 // -4000000000 => 2

     9000000000 quo: 4000000000   => 2

     -9000000000 quo: 4000000000  => -2

     9000000000 quo: -4000000000  => -2

     -9000000000 quo: -4000000000 => 2

    "

!

\\ aNumber

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

    |otherSign|

    otherSign := aNumber sign.

    "

     this is the common case, dividing by a SmallInteger.

     Use a special method for this case ...

    "

    (aNumber class == SmallInteger) ifTrue:[

	(aNumber abs between:1 and:16r003fffff) ifTrue:[

	    ^ ((self absFastDiv:aNumber) at:2)

	]

    ].

    "

     if the argument is not a largeInteger, coerce

    "

    (aNumber class == self class) ifFalse:[

	^ self retry:#\\ coercing:aNumber

    ].

    ^ ((self absDiv:aNumber) at:2)

    "

     9000000000 \\ 4000000000    => 1000000000

     -9000000000 \\ 4000000000   => 1000000000

     9000000000 \\ -4000000000   => 1000000000

     -9000000000 \\ -4000000000  => 1000000000

     9000000000 rem: 4000000000   => 1000000000 

     -9000000000 rem: 4000000000  => -1000000000

     9000000000 rem: -4000000000  => -1000000000 

     -9000000000 rem: -4000000000 => 1000000000

    "

!

negated

    "return an integer with value negated from the receivers value."

    |newNumber|

    (sign == 0) ifTrue:[^ 0].

    "

     special case for SmallInteger minVal

    "

    sign == 1 ifTrue:[

      digitByteArray size == 4 ifTrue:[

	(digitByteArray at:1) == 0 ifTrue:[

	  (digitByteArray at:2) == 0 ifTrue:[

	    (digitByteArray at:3) == 0 ifTrue:[

	      (digitByteArray at:4) == 16r40 ifTrue:[

		^ SmallInteger minVal

	      ].

	    ]

	  ]

	]

      ]

    ].

    newNumber := self shallowCopy.

    newNumber sign:(sign negated).

    ^ newNumber

!

quo:aNumber

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

    |otherSign d|

    otherSign := aNumber sign.

    "

     this is the common case, dividing by a SmallInteger.

     Use a special method for this case ...

    "

    (aNumber class == SmallInteger) ifTrue:[

	(aNumber abs between:1 and:16r003fffff) ifTrue:[

	    sign < 0 ifTrue:[

		(sign == otherSign) ifTrue:[^ (self absFastDiv:aNumber negated) at:1].

		d := aNumber.

	    ] ifFalse:[

		(sign == otherSign) ifTrue:[^ (self absFastDiv:aNumber) at:1].

		d := aNumber negated.

	    ].

	    ^ ((self absFastDiv:d ) at:1) sign:-1

	]

    ].

    "

     if the argument is not a largeInteger, coerce

    "

    (aNumber class == self class) ifFalse:[

	^ self retry:#quo: coercing:aNumber

    ].

    sign < 0 ifTrue:[

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

    ] ifFalse:[

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

    ].

    ^ ((self absDiv:aNumber) at:1) sign:-1

    "

     9000000000 // 4000000000   => 2

     -9000000000 // 4000000000  => -3

     9000000000 // -4000000000  => -3

     -9000000000 // -4000000000 => 2

     9000000000 quo: 4000000000   => 2

     -9000000000 quo: 4000000000  => -2

     9000000000 quo: -4000000000  => -2

     -9000000000 quo: -4000000000 => 2

    "

!

rem:aNumber

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

    |otherSign|

    otherSign := aNumber sign.

    "

     this is the common case, dividing by a SmallInteger.

     Use a special method for this case ...

    "

    (aNumber class == SmallInteger) ifTrue:[

	(aNumber abs between:1 and:16r003fffff) ifTrue:[

	    sign < 0 ifTrue:[

		(sign == otherSign) ifTrue:[^ (self absFastDiv:aNumber negated) at:2].

		^ ((self absFastDiv:aNumber) at:2) sign:-1

	    ].

	    (sign == otherSign) ifTrue:[^ (self absFastDiv:aNumber) at:2].

	    ^ ((self absFastDiv:aNumber negated) at:2) sign:-1

	]

    ].

    "

     if the argument is not a largeInteger, coerce

    "

    (aNumber class == self class) ifFalse:[

	^ self retry:#\\ coercing:aNumber

    ].

    sign < 0 ifTrue:[

	(sign == otherSign) ifTrue:[^ (self absDiv:aNumber negated) at:2].

	^ ((self absDiv:aNumber) at:2) sign:-1

    ].

    (sign == otherSign) ifTrue:[^ (self absDiv:aNumber) at:2].

    ^ ((self absDiv:aNumber negated) at:2) sign:-1

    "

     9000000000 \\ 4000000000    => 1000000000

     -9000000000 \\ 4000000000   => 1000000000

     9000000000 \\ -4000000000   => 1000000000

     -9000000000 \\ -4000000000  => 1000000000

     9000000000 rem: 4000000000   => 1000000000 

     -9000000000 rem: 4000000000  => -1000000000

     9000000000 rem: -4000000000  => -1000000000 

     -9000000000 rem: -4000000000 => 1000000000

    "

! !

!LargeInteger methodsFor:'byte access'!

digitAt:index

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

    index > digitByteArray size ifTrue:[^ 0].