"

 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.

"

"{ Package: 'stx:libbasic' }"

"{ NameSpace: Smalltalk }"

Integer subclass:#LargeInteger

	instanceVariableNames:'sign digitByteArray'

	classVariableNames:'UseKarazuba'

	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

      the absolute value in a ByteArray of digits with 8 bits per element;

      least significant 8 bits at index 1...

    The implementation is not completely tuned for high performance

    (more key-methods should be rewritten as primitives), although the

    common operations have been pretty tuned for some architectures.

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

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

    which keeps the sign as an instance variable

    (ST-80 has LargePositiveInteger and LargeNegativeInteger).

    Another possible change is to use 2's complement instead of sign-magnitude

    representation, and to use the underlying CPU's native byte order (instead of LSB).

    This would allow us to use modern CPU vector/longword operations, at least for 64 and

    128 bit numbers (which make up almost all instances in practice).

    As all of these are transparent to the outside world, any of it may or may not

    change in the future.

    [author:]

	Claus Gittinger

    [see also:]

	Number

	Float Fraction FixedPoint

	SmallInteger

"

!

testing

"

   test largeInt multiplication & division

   (at least, test if they have not both errors which anull each other ;-)

   |last v|

   v := last := 1.

   2 to:3000 do:[:i |

       i printCR.

       v := v * i.

       (v / i) ~= last ifTrue:[

	   self halt

       ].

       last := v.

   ]

   test addition, subtraction:

   SmallInteger maxVal                -> 1073741823

   SmallInteger maxVal + 1            -> 1073741824

   SmallInteger maxVal + 2            -> 1073741825

   (SmallInteger maxVal + 2) - 2      -> 1073741823

   SmallInteger minVal                -> -1073741824

   SmallInteger minVal - 1            -> -1073741825

   SmallInteger minVal - 2            -> -1073741826

   (SmallInteger minVal - 2) + 2      -> -1073741824

   1234567890 + 10                    -> 1234567900

   1111111111 + 1111111111            -> 2222222222

   1111111111 - 1111111111            -> 0

   1111111111 - 2222222222            -> -1111111111

   1111111111 * 2                     -> 2222222222

   1111111111 * -2                    -> -2222222222

   1111111111 * 1111111111            -> 1234567900987654321

   1234567900987654321 // 1111111111  -> 1111111111

   1234567900987654321 \\ 1111111111  -> 0

   1234567900987654322 \\ 1111111111  -> 1

   1234567900987654421 \\ 1111111111  -> 100

   addition:

   (16rFFFFFFF0 + 1          ) hexPrintString -> 'FFFFFFF1'

   (16rFFFFFFFF + 1          ) hexPrintString -> '100000000'

   (16rFFFFFFFF + 2          ) hexPrintString -> '100000001'

   (16rFFFFFFFF + 16rFFFFFF  ) hexPrintString -> '100FFFFFE'

   (16rFFFFFFFF + 16rFFFFFFFF) hexPrintString -> '1FFFFFFFE'

   20 factorial         -> 2432902008176640000

   20 factorial + 10000 -> 2432902008176650000

   20 factorial               hexPrintString -> '21C3677C82B40000'

   (20 factorial + 16rFFFF)   hexPrintString -> '21C3677C82B4FFFF'

   (20 factorial + 16rFFFFFF) hexPrintString -> '21C3677C83B3FFFF'

   test comparison:

   -1234567890 >  -1234567890         false

   -1234567890 >= -1234567890         true

   -1234567890 <  -1234567890         false

   -1234567890 <= -1234567890         true

   -1234567890 =  -1234567890         true

   -1234567890 ~= -1234567890         false

   -1234567890 >  -1234567891         true

   -1234567890 >= -1234567891         true

   -1234567890 <  -1234567891         false

   -1234567890 <= -1234567891         false

   -1234567890 =  -1234567891         false

   -1234567890 ~= -1234567891         true

   -1234567891 >  -1234567890         false

   -1234567891 >= -1234567890         false

   -1234567891 <  -1234567890         true

   -1234567891 <= -1234567890         true

   -1234567891 =  -1234567890         false

   -1234567891 ~= -1234567890         true

    1234567890 >  -1234567890         true

    1234567890 >= -1234567890         true

    1234567890 <  -1234567890         false

    1234567890 <= -1234567890         false

    1234567890 =  -1234567890         false

    1234567890 ~= -1234567890         true

   -1234567890 >  1234567890          false

   -1234567890 >= 1234567890          false

   -1234567890 <  1234567890          true

   -1234567890 <= 1234567890          true

   -1234567890 =  1234567890          false

   -1234567890 ~= 1234567890          true

    1234567890 >  1234567890          false

    1234567890 >= 1234567890          true

    1234567890 <  1234567890          false

    1234567890 <= 1234567890          true

    1234567890 =  1234567890          true

    1234567890 ~= 1234567890          false

   -1234567890 >  -10                 false

   -1234567890 >= -10                 false

   -1234567890 <  -10                 true

   -1234567890 <= -10                 true

   -1234567890 =  -10                 false

   -1234567890 ~= -10                 true

   -1234567890 >  10                  false

   -1234567890 >= 10                  false

   -1234567890 <  10                  true

   -1234567890 <= 10                  true

   -1234567890 =  10                  false

   -1234567890 ~= 10                  true

   -10 >  -1234567890                 true

   -10 >= -1234567890                 true

   -10 <  -1234567890                 false

   -10 <= -1234567890                 false

   -10 =  -1234567890                 false

   -10 ~= -1234567890                 true

    10 >  -1234567890                 true

    10 >= -1234567890                 true

    10 <  -1234567890                 false

    10 <= -1234567890                 false

    10 =  -1234567890                 false

    10 ~= -1234567890                 true

    1234567890 >  -10                 true

    1234567890 >= -10                 true

    1234567890 <  -10                 false

    1234567890 <= -10                 false

    1234567890 =  -10                 false

    1234567890 ~= -10                 true

    1234567890 >  10                  true

    1234567890 >= 10                  true

    1234567890 <  10                  false

    1234567890 <= 10                  false

    1234567890 =  10                  false

    1234567890 ~= 10                  true

   -10 >   1234567890                 false

   -10 >=  1234567890                 false

   -10 <   1234567890                 true

   -10 <=  1234567890                 true

   -10 =   1234567890                 false

   -10 ~=  1234567890                 true

    10 >   1234567890                 false

    10 >=  1234567890                 false

    10 <   1234567890                 true

    10 <=  1234567890                 true

    10 =   1234567890                 false

    10 ~=  1234567890                 true

"

! !

!LargeInteger class methodsFor:'instance creation'!

digitBytes:aByteArrayOfDigits

    "create and return a new LargeInteger with digits (lsb-first)

     from the argument, aByteArray.

     The byteArray argument provides the unsigned magnitude in lsb-first order."

    ^ self basicNew setDigits:aByteArrayOfDigits

    "

     LargeInteger digitBytes:#[16rFF 16rFF 16rFF 16rFF 16rFF 16rFF 16rFF 16rFF]

     (LargeInteger digitBytes:#[16r12 16r34 16r56 16r78 16r90]) hexPrintString

    "

    "Modified: / 8.5.1998 / 21:40:41 / cg"

!

digitBytes:aByteArrayOfDigits MSB:msb

    "create and return a new LargeInteger with digits (which may be in either msb/lsb order)

     from the argument, aByteArray.

     The byteArray argument provides the unsigned magnitude in the specified byte order."

    |digits|

    msb == false ifTrue:[

	digits := aByteArrayOfDigits

    ] ifFalse:[

	digits := aByteArrayOfDigits reversed

    ].

    ^ self basicNew setDigits:digits

    "

     (LargeInteger digitBytes:#[16r10 16r20 16r30 16r40] MSB:false) hexPrintString

     (LargeInteger digitBytes:#[16r10 16r20 16r30 16r40] MSB:true) hexPrintString

    "

!

digitBytes:aByteArrayOfDigits sign:sign

    "create and return a new sign-magnitude LargeInteger with digits (lsb-first)

     from the argument, aByteArray.

     The byteArray argument provides the unsigned magnitude in lsb-first order."

    ^ self basicNew setDigits:aByteArrayOfDigits sign:sign

    "

     LargeInteger digitBytes:#[16rFF 16rFF 16rFF 16rFF 16rFF 16rFF 16rFF 16rFF]

     (LargeInteger digitBytes:#[16r12 16r34 16r56 16r78 16r90]) hexPrintString

    "

    "Modified: / 8.5.1998 / 21:40:41 / cg"

!

new

    "catch creation message.

     LargeIntegers are only created by system code, which

     uses basicNew and cares for correct initialization."

    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.

	(They are used by myself)

     May change/be removed without notice."

    ^ self basicNew value:aSmallInteger

    "LargeInteger value:3689"

    "Modified: / 8.5.1998 / 21:40:41 / cg"

! !

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

    |otherSign numberClass|

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

    "

     this is the common case, multiplying with SmallInteger.

     Use a special method for this case ...

    "

    ((numberClass := aNumber class) == SmallInteger) ifTrue:[

	^ self productFromInteger:aNumber

    ].

    "

     if the argument is not a largeInteger, coerce

    "

    (numberClass == self class) ifFalse:[

	^ self retry:#* coercing:aNumber

    ].

    otherSign := aNumber sign.

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

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

    ^ (self absMul:aNumber) setSign:-1

!

+ aNumber

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

    |otherSign numberClass|

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

    "

     this is the common case, adding a SmallInteger.

     Use a special method for this case ...

    "

    ((numberClass := aNumber class) == SmallInteger) ifTrue:[

	^ self sumFromInteger:aNumber

    ].

    "

     if the argument is not a largeInteger, coerce

    "

    (numberClass == self class) ifFalse:[

	^ self retry:#+ coercing:aNumber

    ].

    otherSign := aNumber sign.

    (sign > 0) ifTrue:[

	"I am positive"

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

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

	^ self

    ].

    "I am negative"

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

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

    ^ self

    "

     SmallInteger maxVal

     SmallInteger maxVal + 1

     SmallInteger maxVal + 2

     SmallInteger minVal

     SmallInteger minVal - 1

    "

    "Modified: / 9.1.1998 / 13:26:28 / cg"

!

- aNumber

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

    |otherSign numberClass|

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

    "

    ((numberClass := aNumber class) == SmallInteger) ifTrue:[

	sign > 0 ifTrue:[

	    aNumber > 0 ifTrue:[

		^ self absFastMinus:aNumber sign:1

	    ].

	    ^ self absFastPlus:aNumber sign:1

	].

	aNumber > 0 ifTrue:[

	    ^ self absFastPlus:aNumber sign:-1

	].

	^ self absFastMinus:aNumber sign:-1

    ].

    "

     if the argument is not a largeInteger, coerce

    "

    (numberClass == self class) ifFalse:[

	^ self retry:#- coercing:aNumber

    ].

    otherSign := aNumber sign.

    (sign > 0) ifTrue:[

	"I am positive"

	(otherSign > 0) ifTrue:[

	    "+large - +large"

	    ^ self absMinus:aNumber sign:1

	].

	(otherSign < 0) ifTrue:[

	    "+large - -large"

	    ^ self absPlus:aNumber sign:1

	].

	"should not happen"

	^ self

    ].

    "I am negative"

    (otherSign > 0) ifTrue:[

	"-large - +large"

	^ self absPlus:aNumber sign:-1

    ].

    (otherSign < 0) ifTrue:[

	"-large - -large"

	^ self absMinus:aNumber sign:-1

    ].

    ^ self

    "

     12345678901234567890 - 0

     12345678901234567890 - 1

     12345678901234567890 - -1

     -12345678901234567890 - 1

     -12345678901234567890 - -1

     12345678901234567890 - 12345678901234567880

     12345678901234567890 - 12345000000000000000

     12345678901234567890 - -87654321098765432110

     -12345678901234567890 - 87654321098765432110

     -12345678901234567890 - -12345678901234567880

     -12345678901234567890 - -12345678901234567980

    "

    "Modified: 20.10.1996 / 18:42:16 / cg"

!

/ aNumber

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

    aNumber isInteger ifTrue:[

	^ Fraction numerator:self denominator:aNumber

    ].

    aNumber isFraction ifTrue:[

	^ Fraction numerator:(self * aNumber denominator) denominator:(aNumber numerator)