hg/stx-libbasic: comparison LargeInteger.st

equal deleted inserted replaced

-:34f00359de08
+:9f0914e019a8
 "
 !
 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...
 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
+	Claus Gittinger
 [see also:]
-Number
+	Number
-Float Fraction FixedPoint
+	Float Fraction FixedPoint
-SmallInteger
+	SmallInteger
 "
 !
 testing
 "
 from the argument, aByteArray."
 |digits|
 msb == false ifTrue:[
-digits := aByteArrayOfDigits
+	digits := aByteArrayOfDigits
 ] ifFalse:[
-digits := aByteArrayOfDigits reversed
+	digits := aByteArrayOfDigits reversed
 ].
 ^ self basicNew setDigits:digits
 "
 (LargeInteger digitBytes:#[16r10 16r20 16r30 16r00] MSB:false) hexPrintString
 "Modified: 28.7.1997 / 19:07:55 / cg"
 !
 // aNumber
 "return the integer part of the quotient of the receivers value
 and the arguments value.
 The result is truncated toward negative infinity
 and will be negative, if the operands signs differ.
 The following is always true:
-(receiver // aNumber) * aNumber + (receiver \\ aNumber) = receiver
+	(receiver // aNumber) * aNumber + (receiver \\ aNumber) = receiver
 Be careful with negative results: 9 // 4 -> 2, while -9 // 4 -> -3.
 Especially surprising:
--1 // 10 -> -1 (because -(1/10) is truncated towards next smaller integer, which is -1.
+	-1 // 10 -> -1 (because -(1/10) is truncated towards next smaller integer, which is -1.
--10 // 3 -> -4 (because -(10/3) is truncated towards next smaller integer, which is -4.
+	-10 // 3 -> -4 (because -(10/3) is truncated towards next smaller integer, which is -4.
 See #quo: which returns -2 in the above case and #rem: which is the corresponding remainder."
 |cls divMod quo abs "{ Class: SmallInteger }" n|
 "
 this is the common case, dividing by a SmallInteger.
 Use a special method for this case ...
 "
 (cls == SmallInteger) ifTrue:[
-abs := aNumber.
+	abs := aNumber.
-abs := abs abs.
+	abs := abs abs.
-(abs between:1 and:(SmallInteger maxBytes == 8 ifTrue:16r00ffffffffff ifFalse:16r00ffffff)) ifTrue:[
+	(abs between:1 and:(SmallInteger maxBytes == 8 ifTrue:16r00ffffffffff ifFalse:16r00ffffff)) ifTrue:[
-divMod := self absFastDivMod:abs.
+	    divMod := self absFastDivMod:abs.
-] ifFalse:[
+	] ifFalse:[
-n := abs asLargeInteger.
+	    n := abs asLargeInteger.
-].
+	].
 ] ifFalse:[
-"
+	"
-if the argument is not a largeInteger, coerce
+	 if the argument is not a largeInteger, coerce
-"
+	"
-(cls == self class) ifFalse:[
+	(cls == self class) ifFalse:[
-^ self retry:#// coercing:aNumber
+	    ^ self retry:#// coercing:aNumber
-].
+	].
-n := aNumber
+	n := aNumber
 ].
 divMod isNil ifTrue:[
-divMod := self absDivMod:n.
+	divMod := self absDivMod:n.
 ].
 quo := divMod at:1.
 (sign == aNumber sign) ifFalse:[
-"/ adjust for truncation if negative and there is a remainder ...
+	"/ adjust for truncation if negative and there is a remainder ...
-"/ be careful: there is one special case to care for here:
+	"/ be careful: there is one special case to care for here:
-"/ if quo is maxInt+1, the negation can be represented as a smallInt.
+	"/ if quo is maxInt+1, the negation can be represented as a smallInt.
-quo := quo sign:-1.
+	quo := quo sign:-1.
-(divMod at:2) == 0 ifFalse:[
+	(divMod at:2) == 0 ifFalse:[
-^ quo - 1
+	    ^ quo - 1
-].
+	].
-quo digitLength == SmallInteger maxBytes ifTrue:[
+	quo digitLength == SmallInteger maxBytes ifTrue:[
-^ quo compressed
+	    ^ quo compressed
-].
+	].
 ].
 ^ quo
 "
 (9000000000 // 4000000000)   =   (900 // 400)   ifFalse:[self halt].
 "Modified: / 27.4.1999 / 19:50:26 / stefan"
 !
 \\ aNumber
 "Answer the integer remainder m defined by division with truncation toward
 negative infinity.
 m < |aNumber| AND there is an integer k with (k * aNumber + m) = self
 The returned remainder has the same sign as aNumber.
 The following is always true:
-(receiver // aNumber) * aNumber + (receiver \\ aNumber) = receiver
+	(receiver // aNumber) * aNumber + (receiver \\ aNumber) = receiver
 Be careful with negative results: 9 // 4 -> 2, while -9 // 4 -> -3.
 Especially surprising:
--1 \\ 10 -> 9  (because -(1/10) is truncated towards next smaller integer, which is -1,
+	-1 \\ 10 -> 9  (because -(1/10) is truncated towards next smaller integer, which is -1,
-and -1 multiplied by 10 gives -10, so we have to add 9 to get the original -1).
+			and -1 multiplied by 10 gives -10, so we have to add 9 to get the original -1).
--10 \\ 3 -> 2 (because -(10/3) is truncated towards next smaller integer, which is -4,
+	-10 \\ 3 -> 2 (because -(10/3) is truncated towards next smaller integer, which is -4,
-and -4 * 4 gives -12, so we need to add 2 to get the original -10.
+			and -4 * 4 gives -12, so we need to add 2 to get the original -10.
 See #rem: which is the corresponding remainder for division via #quo:.
 Redefined here for speed."
 |abs rem negativeDivisor|
 aNumber negative ifTrue:[
-negativeDivisor := true.
+	negativeDivisor := true.
-abs := aNumber negated.
+	abs := aNumber negated.
 ] ifFalse:[
-negativeDivisor := false.
+	negativeDivisor := false.
-abs := aNumber.
+	abs := aNumber.
 ].
 "
 this is the common case, dividing by a SmallInteger.
 Use a special method for this case ...
 "
 (aNumber class == SmallInteger) ifTrue:[
-(abs between:1 and:(SmallInteger maxBytes == 8 ifTrue:16r00ffffffffff ifFalse:16r00ffffff)) ifTrue:[
+	(abs between:1 and:(SmallInteger maxBytes == 8 ifTrue:16r00ffffffffff ifFalse:16r00ffffff)) ifTrue:[
-rem := (self absFastDivMod:abs) at:2.
+	    rem := (self absFastDivMod:abs) at:2.
-] ifFalse:[
+	] ifFalse:[
-rem := self absMod:abs asLargeInteger
+	    rem := self absMod:abs asLargeInteger
-].
+	].
 ] ifFalse:[
-"
+	"
-if the argument is not a largeInteger, coerce
+	 if the argument is not a largeInteger, coerce
-"
+	"
-(aNumber class == self class) ifFalse:[
+	(aNumber class == self class) ifFalse:[
-^ self retry:#\\ coercing:aNumber
+	    ^ self retry:#\\ coercing:aNumber
-].
+	].
-rem := self absMod:abs.
+	rem := self absMod:abs.
 ].
 rem = 0 ifFalse:[
-negativeDivisor ifTrue:[
+	negativeDivisor ifTrue:[
-rem := rem sign:-1
+	    rem := rem sign:-1
-].
+	].
-(self negative ~~ negativeDivisor) ifTrue:[
+	(self negative ~~ negativeDivisor) ifTrue:[
-"different sign, so remainder would have been negative.
+	    "different sign, so remainder would have been negative.
-rem has been rounded toward zero, this code will simulate
+	     rem has been rounded toward zero, this code will simulate
-rounding to negative infinity."
+	     rounding to negative infinity."
-rem := aNumber - rem.
+	    rem := aNumber - rem.
-].
+	].
 ].
 ^ rem
 "
 (9000000000 \\ 4000000000)   = (900 \\ 400 * 10000000)  ifFalse:[self halt].
 "Created: / 26.10.1999 / 21:28:06 / stefan"
 !
 divMod:aNumber
 "return an array filled with
-(self // aNumber) and (self \\ aNumber).
+	(self // aNumber) and (self \\ aNumber).
 The returned remainder has the same sign as aNumber.
 The following is always true:
-(receiver // something) * something + (receiver \\ something) = receiver
+	(receiver // something) * something + (receiver \\ something) = receiver
 Be careful with negative results: 9 // 4 -> 2, while -9 // 4 -> -3.
 Especially surprising:
--1 \\ 10 -> 9  (because -(1/10) is truncated towards next smaller integer, which is -1,
+	-1 \\ 10 -> 9  (because -(1/10) is truncated towards next smaller integer, which is -1,
-and -1 multiplied by 10 gives -10, so we have to add 9 to get the original -1).
+			and -1 multiplied by 10 gives -10, so we have to add 9 to get the original -1).
--10 \\ 3 -> 2 (because -(10/3) is truncated towards next smaller integer, which is -4,
+	-10 \\ 3 -> 2 (because -(10/3) is truncated towards next smaller integer, which is -4,
-and -4 * 4 gives -12, so we need to add 2 to get the original -10.
+			and -4 * 4 gives -12, so we need to add 2 to get the original -10.
 This is redefined here for more performance
 (as the remainder is generated as a side effect of division)"
 |cls n|
 ((self < 0) or:[aNumber <= 0]) ifTrue:[
-^ super divMod:aNumber
+	^ super divMod:aNumber
 ].
 "/ only handle the common case here
 cls := aNumber class.
 (cls == SmallInteger) ifTrue:[
-"
+	"
-this is the common case, dividing by a SmallInteger.
+	 this is the common case, dividing by a SmallInteger.
-Use a special method for this case ...
+	 Use a special method for this case ...
-"
+	"
-(aNumber between:1 and:(SmallInteger maxBytes == 8 ifTrue:16r00ffffffffff ifFalse:16r00ffffff)) ifTrue:[
+	(aNumber between:1 and:(SmallInteger maxBytes == 8 ifTrue:16r00ffffffffff ifFalse:16r00ffffff)) ifTrue:[
-^ self absFastDivMod:aNumber abs.
+	    ^ self absFastDivMod:aNumber abs.
-].
+	].
-n := aNumber asLargeInteger.
+	n := aNumber asLargeInteger.
 ] ifFalse:[
-(cls == self class) ifFalse:[
+	(cls == self class) ifFalse:[
-^ super divMod:aNumber
+	    ^ super divMod:aNumber
-].
+	].
-n := aNumber.
+	n := aNumber.
 ].
 ^ self absDivMod:n abs.
 "
 !
 digitAt:index
 "return 8 bits of value, starting at byte index"
+%{
+#ifdef __JAVA__
+return context._RETURN( ((STLargeInteger)self).digitAt( index.intValue() ) );
+#endif
+%}.
 index > digitByteArray size ifTrue:[^ 0].
 ^ digitByteArray at:index
 !
 digitAt:index put:aByte
 "set the 8 bits, index is a byte index"
+%{
+#ifdef __JAVA__
+ERROR("cannot modify the digits of a LargeInteger");
+#endif
+%}.
 digitByteArray at:index put:aByte
 !
 digitByteAt:index
 "return 8 bits of my signed value, starting at byte index.
 For positive receivers, this is the same as #digitAt:;
 for negative ones, the actual bit representation is returned."
 |t digits|
+%{
+#ifdef __JAVA__
+return context._RETURN( ((STLargeInteger)self).digitByteAt( index.intValue() ) );
+#endif
+%}.
 sign >= 0 ifTrue:[
 	index > digitByteArray size ifTrue:[
 	    ^ 0
 	].
 	^ digitByteArray at:index.
 digitBytes
 "return a byteArray filled with the receivers bits
 (8 bits of the absolute value per element).
 Least significant byte is first!!"
+%{
+#ifdef __JAVA__
+return context._RETURN( ((STLargeInteger)self).digitBytes() );
+#endif
+%}.
 ^ digitByteArray
 "Modified: / 5.5.1999 / 14:57:03 / stefan"
 !
 this allows to ask unnormalized LargeIntegers
 for their digitLength
 "
 |l "{ Class: SmallInteger }" |
+%{
+#ifdef __JAVA__
+return context._RETURN( ((STLargeInteger)self).digitLength() );
+#endif
+%}.
 l := digitByteArray size.
 [l ~~ 0 and:[(digitByteArray at:l) == 0]] whileTrue:[
 	l := l - 1.
 ].
 ^ l
 !
 negative
 "return true, if the receiver is < 0"
+%{
+#ifdef __JAVA__
+return context._RETURN( ((STLargeInteger)self).largeValue.signum() < 0 ? STObject.True : STObject.False);
+#endif
+%}.
 ^ (sign < 0)
 !
 odd
 "return true if the receiver is odd"
 !
 positive
 "return true, if the receiver is >= 0"
+%{
+#ifdef __JAVA__
+return context._RETURN( ((STLargeInteger)self).largeValue.signum() >= 0 ? STObject.True : STObject.False);
+#endif
+%}.
 ^ (sign >= 0)
 !
 sign
 "return the sign of the receiver (-1, 0 or 1)"
+%{
+#ifdef __JAVA__
+return context._RETURN( STInteger._new( ((STLargeInteger)self).largeValue.signum() ));
+#endif
+%}.
 ^ sign
 !
 strictlyPositive
 "return true, if the receiver is > 0"
+%{
+#ifdef __JAVA__
+return context._RETURN( ((STLargeInteger)self).largeValue.signum() > 0 ? STObject.True : STObject.False);
+#endif
+%}.
 ^ (sign > 0)
 ! !
 !LargeInteger class methodsFor:'documentation'!
 version
-^ '$Header: /cvs/stx/stx/libbasic/LargeInteger.st,v 1.223 2015-03-25 14:12:51 cg Exp $'
+^ '$Header: /cvs/stx/stx/libbasic/LargeInteger.st,v 1.224 2015-04-19 22:31:45 cg Exp $'
 !
 version_CVS
-^ '$Header: /cvs/stx/stx/libbasic/LargeInteger.st,v 1.223 2015-03-25 14:12:51 cg Exp $'
+^ '$Header: /cvs/stx/stx/libbasic/LargeInteger.st,v 1.224 2015-04-19 22:31:45 cg Exp $'
 ! !

changeset 18235	9f0914e019a8
parent 17648	8d017b41a3c3
child 18237	8457ae63fa44
child 18240	28af09029a8b