--- a/LargeInteger.st Thu Dec 07 22:32:49 1995 +0100
+++ b/LargeInteger.st Thu Dec 07 22:38:49 1995 +0100
@@ -33,10 +33,6 @@
"
!
-version
- ^ '$Header: /cvs/stx/stx/libbasic/LargeInteger.st,v 1.20 1995-11-11 15:23:45 cg Exp $'
-!
-
documentation
"
This class provides arbitrary precision integers. These are represented as:
@@ -65,88 +61,18 @@
"
! !
-!LargeInteger class methodsFor:'queries'!
-
-isBuiltInClass
- "this class is known by the run-time-system"
-
- ^ true
-! !
-
!LargeInteger class methodsFor:'instance creation'!
-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"
-!
-
-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'
!
-valueLow:lowBits hi:hiBits
- "create and return a new LargeInteger with value taken from
- the two 16-bit args, where the sign of the high bits determines
- the sign of the result.
- The largeinteger is normalized (but not to a smallInteger).
- This method is called from the runtime system (+, -),
- when an integer result has to be converted to a Large.
- May change without notice."
-
- |newLarge|
-
- hiBits < 0 ifTrue:[
- newLarge := self unsignedValueLow:lowBits hi:(hiBits negated).
- newLarge sign:-1.
- ^ newLarge
- ].
- ^ self unsignedValueLow:lowBits hi:hiBits
-!
+new:numberOfDigits
+ "catch creation message"
-unsignedValueLow:lowBits hi:hiBits
- "create and return a new LargeInteger with value taken from
- the two 16-bit unsigned args.
- The largeinteger is normalized (but not to a smallInteger).
- This method is called from the runtime system (+, -),
- when an integer result has to be converted to a Large.
- May change without notice."
-
- |bytes b1 b2 b3 b4|
-
- b4 := (hiBits bitShift:-8) bitAnd:16rFF.
- b3 := hiBits bitAnd:16rFF.
- b2 := (lowBits bitShift:-8) bitAnd:16rFF.
- b1 := lowBits bitAnd:16rFF.
-
- b4 ~~ 0 ifTrue:[
- bytes := ByteArray with:b1 with:b2 with:b3 with:b4
- ] ifFalse:[
- b3 ~~ 0 ifTrue:[
- bytes := ByteArray with:b1 with:b2 with:b3
- ] ifFalse:[
- b2 ~~ 0 ifTrue:[
- bytes := ByteArray with:b1 with:b2
- ] ifFalse:[
- bytes := ByteArray with:b1
- ]
- ]
- ].
- ^ (self basicNew) setDigits:bytes
+ self error:'LargeIntegers cannot be created with new'
!
sign:s value16:ll value16:ml value16:mh value16:hh
@@ -250,10 +176,108 @@
newLarge := self basicNew setDigits:digitBytes.
s < 0 ifTrue:[newLarge sign:s].
^ newLarge
+!
+
+unsignedValueLow:lowBits hi:hiBits
+ "create and return a new LargeInteger with value taken from
+ the two 16-bit unsigned args.
+ The largeinteger is normalized (but not to a smallInteger).
+ This method is called from the runtime system (+, -),
+ when an integer result has to be converted to a Large.
+ May change without notice."
+
+ |bytes b1 b2 b3 b4|
+
+ b4 := (hiBits bitShift:-8) bitAnd:16rFF.
+ b3 := hiBits bitAnd:16rFF.
+ b2 := (lowBits bitShift:-8) bitAnd:16rFF.
+ b1 := lowBits bitAnd:16rFF.
+
+ b4 ~~ 0 ifTrue:[
+ bytes := ByteArray with:b1 with:b2 with:b3 with:b4
+ ] ifFalse:[
+ b3 ~~ 0 ifTrue:[
+ bytes := ByteArray with:b1 with:b2 with:b3
+ ] ifFalse:[
+ b2 ~~ 0 ifTrue:[
+ bytes := ByteArray with:b1 with:b2
+ ] ifFalse:[
+ bytes := ByteArray with:b1
+ ]
+ ]
+ ].
+ ^ (self basicNew) setDigits:bytes
+!
+
+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"
+!
+
+valueLow:lowBits hi:hiBits
+ "create and return a new LargeInteger with value taken from
+ the two 16-bit args, where the sign of the high bits determines
+ the sign of the result.
+ The largeinteger is normalized (but not to a smallInteger).
+ This method is called from the runtime system (+, -),
+ when an integer result has to be converted to a Large.
+ May change without notice."
+
+ |newLarge|
+
+ hiBits < 0 ifTrue:[
+ newLarge := self unsignedValueLow:lowBits hi:(hiBits negated).
+ newLarge sign:-1.
+ ^ newLarge
+ ].
+ ^ self unsignedValueLow:lowBits hi:hiBits
+! !
+
+!LargeInteger class methodsFor:'queries'!
+
+isBuiltInClass
+ "this class is known by the run-time-system"
+
+ ^ true
! !
!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"
@@ -360,32 +384,16 @@
"
!
-* aNumber
- "return the product of the receiver and the argument, aNumber"
-
- |otherSign|
-
- (sign == 0) ifTrue:[^ 0]. "cannot happen if correctly normalized"
+/ aNumber
+ "return the quotient of the receivers and the argument, aNumber"
- "
- this is the common case, multiplying with SmallInteger.
- Use a special method for this case ...
- "
- (aNumber class == SmallInteger) ifTrue:[
- ^ self productFromInteger:aNumber
+ aNumber isInteger ifTrue:[
+ ^ (Fraction numerator:self
+ denominator:aNumber) reduced
].
- "
- 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
+ "this is a q&d hack - we loose lots of precision here ..."
+ ^ (self asFloat / aNumber asFloat)
!
// aNumber
@@ -462,18 +470,6 @@
^ ((self absDiv:aNumber negated) at:2) sign:-1
!
-/ 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)
-!
-
negated
"return an integer with value negated from the receivers value."
@@ -502,44 +498,295 @@
^ newNumber
! !
-!LargeInteger methodsFor:'double dispatching'!
+!LargeInteger methodsFor:'byte access'!
+
+digitAt:index
+ "return 8 bits of value, starting at byte index"
+
+ index > digitByteArray size ifTrue:[^ 0].
+ ^ digitByteArray at:index
+!
+
+digitAt:index put:aByte
+ "set the 8 bits, index is a byte index"
+
+ digitByteArray at:index put:aByte
+!
+
+digitLength
+ "return the number bytes used by this Integer"
+
+"/ ^ digitByteArray size
-sumFromInteger:anInteger
- "sent, when anInteger does not know how to add the receiver.
- Return the sum of the receiver and the argument, (which must be a SmallInteger)"
+ "
+ kludge: check if there is a 0-byte ...
+ this allows to ask unnormalized LargeIntegers
+ to be asked for their digitLength
+ "
+ |l "{ Class: SmallInteger }" |
- |result|
+ l := digitByteArray size.
+ [(digitByteArray at:l) == 0] whileTrue:[
+ l := l - 1.
+ ].
+ ^ l
+!
+
+digits
+ "return a byteArray fille with the receivers bits
+ (8 bits of the absolute value per element)"
+
+ ^ digitByteArray
+! !
+
+!LargeInteger methodsFor:'coercing & converting'!
- anInteger > 0 ifTrue:[
- sign < 0 ifTrue:[
- result := (self absFastMinus:anInteger) sign:-1
- ] ifFalse:[
- result := self absFastPlus:anInteger
+asFloat
+ "return a Float with same value as myself.
+ Since floats have a limited precision, you usually loose bits when
+ doing this."
+
+ |newFloat|
+
+ newFloat := 0.0.
+ (sign == 0) ifFalse:[
+ digitByteArray reverseDo:[:aDigit |
+ newFloat := (newFloat * 256.0) + aDigit asFloat
+ ].
+ (sign < 0) ifTrue:[
+ newFloat := newFloat negated
]
- ] ifFalse:[
- anInteger == 0 ifTrue:[
- ^ self
+ ].
+ ^ newFloat
+
+ "
+ 1234567890 asFloat
+ 12345678901234567890 asFloat
+ 12345678901234567890 asFloat asInteger
+ "
+!
+
+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.
+ Q: should we raise an exception if this happens ?"
+
+ |value|
+
+ value := 0.
+ (sign == 0) ifFalse:[
+ digitByteArray reverseDo:[:aDigit |
+ value := (value times:256) + aDigit
].
- sign < 0 ifTrue:[
- result := (self absFastPlus:anInteger abs) sign:-1
- ] ifFalse:[
- result := self absFastMinus:anInteger
+ (sign < 0) ifTrue:[
+ value := value negated
]
].
- ^ result normalize
+ ^ value
+!
+
+coerce:aNumber
+ "return the argument as a LargeInteger"
+
+ ^ aNumber asLargeInteger
+!
+
+normalize
+ "if the receiver can be represented as a SmallInteger, return
+ a SmallInteger with my value; otherwise return self with leading
+ zeros removed"
+
+ |index "{ Class: SmallInteger }"
+ val "{ Class: SmallInteger }" |
+
+%{ /* NOCONTEXT */
+ OBJ t;
+
+ if (_INST(sign) == _MKSMALLINT(0)) {
+ RETURN (_MKSMALLINT(0));
+ }
+
+ t = _INST(digitByteArray);
+ if (__isByteArray(t)) {
+ unsigned char *_digitBytes = _ByteArrayInstPtr(t)->ba_element;
+ int _idx = _byteArraySize(t);
+ int _val;
+
+ while ((_idx > 0) && (_digitBytes[_idx - 1] == 0)) {
+ _idx--;
+ }
+ switch (_idx) {
+ case 0:
+ RETURN (_MKSMALLINT(0));
+ break;
+
+ case 1:
+ _val = _digitBytes[0];
+ if (_INST(sign) == _MKSMALLINT(-1))
+ _val = -_val;
+ RETURN (_MKSMALLINT(_val));
+
+ case 2:
+ _val = (_digitBytes[1]<<8) + _digitBytes[0];
+ if (_INST(sign) == _MKSMALLINT(-1))
+ _val = -_val;
+ RETURN (_MKSMALLINT(_val));
+
+ case 3:
+ _val = (((_digitBytes[2]<<8) + _digitBytes[1])<<8) + _digitBytes[0];
+ if (_INST(sign) == _MKSMALLINT(-1))
+ _val = -_val;
+ RETURN (_MKSMALLINT(_val));
+
+ case 4:
+ _val = _digitBytes[3];
+ if (_val <= 0x40) {
+ _val = (((((_val<<8) + _digitBytes[2])<<8) + _digitBytes[1])<<8) + _digitBytes[0];
+ if (_INST(sign) == _MKSMALLINT(-1))
+ _val = -_val;
+ if ((_val >= _MIN_INT) && (_val <= _MAX_INT)) {
+ RETURN (_MKSMALLINT(_val));
+ }
+ }
+ break;
+
+ default:
+ break;
+ }
+ }
+%}.
+ index := digitByteArray size.
+ [(index > 0) and:[(digitByteArray at:index) == 0]] whileTrue:[
+ index := index - 1
+ ].
+
+ (index ~~ digitByteArray size) ifTrue:[
+ digitByteArray := digitByteArray copyFrom:1 to:index
+ ].
+ ^ self
+!
+
+value:aSmallInteger
+ "return a new LargeInteger with value taken from a SmallInteger.
+ This method will fail, if the argument is not a smallInteger."
+
+ |absValue
+ b1 "{ Class: SmallInteger }"
+ b2 "{ Class: SmallInteger }"
+ b3 "{ Class: SmallInteger }"|
"
- 12345678901234567890
- -12345678901234567890
- 12345678901234567890 sumFromInteger:0
- -12345678901234567890 sumFromInteger:0
- 12345678901234567890 sumFromInteger:1
- 12345678901234567890 sumFromInteger:-1
- -12345678901234567890 sumFromInteger:1
- -12345678901234567890 sumFromInteger:-1
+ could have simply created a 4-byte largeinteger and normalize
+ it; the code below does the normalize right away, avoiding the
+ overhead of producing any intermediate byte-arrays (and the scanning)
"
+ (aSmallInteger == 0) ifTrue: [
+ digitByteArray := #[0].
+ sign := 0.
+ ^ self
+ ].
+ (aSmallInteger < 0) ifTrue: [
+ sign := -1.
+ absValue := aSmallInteger negated
+ ] ifFalse: [
+ sign := 1.
+ absValue := aSmallInteger
+ ].
+ b1 := absValue bitAnd:16rFF.
+ absValue := absValue bitShift:-8.
+ absValue == 0 ifTrue:[
+ digitByteArray := ByteArray with:b1
+ ] ifFalse:[
+ b2 := absValue bitAnd:16rFF.
+ absValue := absValue bitShift:-8.
+ absValue == 0 ifTrue:[
+ digitByteArray := ByteArray with:b1 with:b2
+ ] ifFalse:[
+ b3 := absValue bitAnd:16rFF.
+ absValue := absValue bitShift:-8.
+ absValue == 0 ifTrue:[
+ digitByteArray := ByteArray with:b1 with:b2 with:b3
+ ] ifFalse:[
+ digitByteArray := ByteArray with:b1 with:b2 with:b3 with:absValue
+ ]
+ ]
+ ]
+! !
+
+!LargeInteger methodsFor:'comparing'!
+
+< aNumber
+ "return true, if the argument, aNumber is greater than the receiver"
+
+ |otherSign|
+
+ (aNumber class == self class) 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
!
+= aNumber
+ "return true, if the argument, aNumber has the same value as
+ the receiver"
+
+ (aNumber class == self class) 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 less than the receiver"
+
+ |otherSign|
+
+ (aNumber class == self class) ifFalse:[
+ ^ self retry:#> coercing:aNumber
+ ].
+ otherSign := aNumber sign.
+
+ (sign > 0) ifTrue:[
+ "I am positive"
+ (otherSign > 0) ifTrue:[^ aNumber absLess:self].
+ ^ true "aNumber is <= 0"
+ ].
+ (sign == 0) ifTrue:[
+ "I am zero"
+ (otherSign > 0) ifTrue:[^ false].
+ ^ true
+ ].
+ "I am negative"
+ (otherSign > 0) ifTrue:[^ false].
+ (otherSign == 0) ifTrue:[^ false].
+ ^ (self absLess:aNumber) not
+! !
+
+!LargeInteger methodsFor:'double dispatching'!
+
differenceFromInteger:anInteger
"sent, when anInteger does not know how to subtract the receiver.
Return the result of 'anInteger - self'. The argument must be a SmallInteger."
@@ -664,326 +911,125 @@
].
].
^ result normalize
-! !
-
-!LargeInteger methodsFor:'coercing & converting'!
-
-coerce:aNumber
- "return the argument as a LargeInteger"
-
- ^ aNumber asLargeInteger
-!
-
-value:aSmallInteger
- "return a new LargeInteger with value taken from a SmallInteger.
- This method will fail, if the argument is not a smallInteger."
-
- |absValue
- b1 "{ Class: SmallInteger }"
- b2 "{ Class: SmallInteger }"
- b3 "{ Class: SmallInteger }"|
-
- "
- could have simply created a 4-byte largeinteger and normalize
- it; the code below does the normalize right away, avoiding the
- overhead of producing any intermediate byte-arrays (and the scanning)
- "
- (aSmallInteger == 0) ifTrue: [
- digitByteArray := #[0].
- sign := 0.
- ^ self
- ].
- (aSmallInteger < 0) ifTrue: [
- sign := -1.
- absValue := aSmallInteger negated
- ] ifFalse: [
- sign := 1.
- absValue := aSmallInteger
- ].
- b1 := absValue bitAnd:16rFF.
- absValue := absValue bitShift:-8.
- absValue == 0 ifTrue:[
- digitByteArray := ByteArray with:b1
- ] ifFalse:[
- b2 := absValue bitAnd:16rFF.
- absValue := absValue bitShift:-8.
- absValue == 0 ifTrue:[
- digitByteArray := ByteArray with:b1 with:b2
- ] ifFalse:[
- b3 := absValue bitAnd:16rFF.
- absValue := absValue bitShift:-8.
- absValue == 0 ifTrue:[
- digitByteArray := ByteArray with:b1 with:b2 with:b3
- ] ifFalse:[
- digitByteArray := ByteArray with:b1 with:b2 with:b3 with:absValue
- ]
- ]
- ]
-!
-
-asSmallInteger
- "return a SmallInteger with same value as myself -
- the result is invalid if the receivers value cannot
- be represented as a SmallInteger.
- Q: should we raise an exception if this happens ?"
-
- |value|
-
- value := 0.
- (sign == 0) ifFalse:[
- digitByteArray reverseDo:[:aDigit |
- value := (value times:256) + aDigit
- ].
- (sign < 0) ifTrue:[
- value := value negated
- ]
- ].
- ^ value
-!
-
-asLargeInteger
- "return a LargeInteger with same value as myself - thats me"
-
- ^ self
-!
-
-asFloat
- "return a Float with same value as myself.
- Since floats have a limited precision, you usually loose bits when
- doing this."
-
- |newFloat|
-
- newFloat := 0.0.
- (sign == 0) ifFalse:[
- digitByteArray reverseDo:[:aDigit |
- newFloat := (newFloat * 256.0) + aDigit asFloat
- ].
- (sign < 0) ifTrue:[
- newFloat := newFloat negated
- ]
- ].
- ^ newFloat
-
- "
- 1234567890 asFloat
- 12345678901234567890 asFloat
- 12345678901234567890 asFloat asInteger
- "
!
-normalize
- "if the receiver can be represented as a SmallInteger, return
- a SmallInteger with my value; otherwise return self with leading
- zeros removed"
-
- |index "{ Class: SmallInteger }"
- val "{ Class: SmallInteger }" |
-
-%{ /* NOCONTEXT */
- OBJ t;
+sumFromInteger:anInteger
+ "sent, when anInteger does not know how to add the receiver.
+ Return the sum of the receiver and the argument, (which must be a SmallInteger)"
- if (_INST(sign) == _MKSMALLINT(0)) {
- RETURN (_MKSMALLINT(0));
- }
-
- t = _INST(digitByteArray);
- if (__isByteArray(t)) {
- unsigned char *_digitBytes = _ByteArrayInstPtr(t)->ba_element;
- int _idx = _byteArraySize(t);
- int _val;
-
- while ((_idx > 0) && (_digitBytes[_idx - 1] == 0)) {
- _idx--;
- }
- switch (_idx) {
- case 0:
- RETURN (_MKSMALLINT(0));
- break;
+ |result|
- case 1:
- _val = _digitBytes[0];
- if (_INST(sign) == _MKSMALLINT(-1))
- _val = -_val;
- RETURN (_MKSMALLINT(_val));
-
- case 2:
- _val = (_digitBytes[1]<<8) + _digitBytes[0];
- if (_INST(sign) == _MKSMALLINT(-1))
- _val = -_val;
- RETURN (_MKSMALLINT(_val));
-
- case 3:
- _val = (((_digitBytes[2]<<8) + _digitBytes[1])<<8) + _digitBytes[0];
- if (_INST(sign) == _MKSMALLINT(-1))
- _val = -_val;
- RETURN (_MKSMALLINT(_val));
+ anInteger > 0 ifTrue:[
+ sign < 0 ifTrue:[
+ result := (self absFastMinus:anInteger) sign:-1
+ ] ifFalse:[
+ result := self absFastPlus:anInteger
+ ]
+ ] ifFalse:[
+ anInteger == 0 ifTrue:[
+ ^ self
+ ].
+ sign < 0 ifTrue:[
+ result := (self absFastPlus:anInteger abs) sign:-1
+ ] ifFalse:[
+ result := self absFastMinus:anInteger
+ ]
+ ].
+ ^ result normalize
- case 4:
- _val = _digitBytes[3];
- if (_val <= 0x40) {
- _val = (((((_val<<8) + _digitBytes[2])<<8) + _digitBytes[1])<<8) + _digitBytes[0];
- if (_INST(sign) == _MKSMALLINT(-1))
- _val = -_val;
- if ((_val >= _MIN_INT) && (_val <= _MAX_INT)) {
- RETURN (_MKSMALLINT(_val));
- }
- }
- break;
-
- default:
- break;
- }
- }
-%}.
- index := digitByteArray size.
- [(index > 0) and:[(digitByteArray at:index) == 0]] whileTrue:[
- index := index - 1
- ].
-
- (index ~~ digitByteArray size) ifTrue:[
- digitByteArray := digitByteArray copyFrom:1 to:index
- ].
- ^ self
+ "
+ 12345678901234567890
+ -12345678901234567890
+ 12345678901234567890 sumFromInteger:0
+ -12345678901234567890 sumFromInteger:0
+ 12345678901234567890 sumFromInteger:1
+ 12345678901234567890 sumFromInteger:-1
+ -12345678901234567890 sumFromInteger:1
+ -12345678901234567890 sumFromInteger:-1
+ "
! !
-!LargeInteger methodsFor:'byte access'!
-
-digitLength
- "return the number bytes used by this Integer"
-
-"/ ^ digitByteArray size
-
- "
- kludge: check if there is a 0-byte ...
- this allows to ask unnormalized LargeIntegers
- to be asked for their digitLength
- "
- |l "{ Class: SmallInteger }" |
+!LargeInteger methodsFor:'printing & storing'!
- l := digitByteArray size.
- [(digitByteArray at:l) == 0] whileTrue:[
- l := l - 1.
- ].
- ^ l
-!
-
-digitAt:index
- "return 8 bits of value, starting at byte index"
+storeOn:aStream
+ "append a representation of the receiver to aStream, which can
+ be used to reconstruct the receiver."
- index > digitByteArray size ifTrue:[^ 0].
- ^ digitByteArray at:index
-!
-
-digitAt:index put:aByte
- "set the 8 bits, index is a byte index"
-
- digitByteArray at:index put:aByte
-!
-
-digits
- "return a byteArray fille with the receivers bits
- (8 bits of the absolute value per element)"
-
- ^ digitByteArray
+ self printOn:aStream.
+ aStream nextPutAll:' asLargeInteger'
! !
!LargeInteger methodsFor:'private'!
-sign:aNumber
- sign := aNumber
-!
-
-numberOfDigits:nDigits
- digitByteArray := ByteArray new:nDigits.
- sign := 1.
-!
-
-setDigits:digits
- digitByteArray := digits.
- sign := 1.
-!
-
-absFastPlus:aSmallInteger
- "return a LargeInteger representing abs(self) + abs(theArgument).
- The result is not normalized."
+absDiv:anInteger
+ "return an array with two LargeIntegers representing
+ abs(self) // abs(theArgument) and abs(self) \\ abs(theArgument).
+ This needs a rewrite."
- |result resultDigitByteArray
- len "{ Class: SmallInteger }"
- index "{ Class: SmallInteger }"
- carry "{ Class: SmallInteger }" |
-
- len := digitByteArray size.
-
- result := self class basicNew numberOfDigits:(len + 1).
- resultDigitByteArray := result digits.
+ |tmp1 tmp2
+ rem
+ count "{ Class: SmallInteger }"
+ digit "{ Class: SmallInteger }" |
- index := 1.
- carry := aSmallInteger abs.
+ anInteger == 0 ifTrue:[
+ ^ DivisionByZeroSignal raise
+ ].
- [carry ~~ 0] whileTrue:[
- (index <= len) ifTrue:[
- carry := (digitByteArray basicAt:index) + carry.
- ].
- resultDigitByteArray basicAt:index put:(carry bitAnd:16rFF).
- carry := carry bitShift:-8.
- index := index + 1
- ].
- [index <= len] whileTrue:[
- resultDigitByteArray basicAt:index put:(digitByteArray basicAt:index).
- index := index + 1
+ self < anInteger ifTrue:[
+ ^ Array with:0 with:self
].
- ^ result
+ tmp1 := self simpleDeepCopy.
+ tmp2 := anInteger simpleDeepCopy.
+ count := 0.
+ [tmp2 < tmp1] whileTrue:[
+ tmp2 mul256.
+ count := count + 1
+ ].
+
+ tmp2 div256.
+
+ rem := 0 asLargeInteger.
+ [count == 0] whileFalse:[
+ digit := 0.
+ [tmp1 >= tmp2] whileTrue:[
+ digit := digit + 1.
+ tmp1 := tmp1 - tmp2
+ ].
+ rem := rem * 256 + digit.
+ tmp2 div256.
+ count := count - 1
+ ].
+ ^ Array with:rem with:tmp1
!
-absFastMinus:aSmallInteger
- "return a LargeInteger representing abs(self) - abs(theArgument).
- The result is not normalized."
+absEq:aLargeInteger
+ "return true, if abs(self) = abs(theArgument)"
- |result resultDigitByteArray
- len "{ Class: SmallInteger }"
- index "{ Class: SmallInteger }"
- borrow "{ Class: SmallInteger }"
- diff "{ Class: SmallInteger }" |
+ |len1 "{ Class: SmallInteger }"
+ len2 "{ Class: SmallInteger }"
+ d1 "{ Class: SmallInteger }"
+ d2 "{ Class: SmallInteger }"
+ otherDigitByteArray |
- len := digitByteArray size.
-
- result := self class basicNew numberOfDigits:(len + 1).
- resultDigitByteArray := result digits.
-
- index := 1.
- borrow := aSmallInteger abs.
+ len1 := digitByteArray size.
+ otherDigitByteArray := aLargeInteger digits.
+ len2 := otherDigitByteArray size.
- [borrow ~~ 0] whileTrue:[
- (index <= len) ifTrue:[
- diff := (digitByteArray basicAt:index) - (borrow bitAnd:16rFF).
- borrow := borrow bitShift:-8.
- diff < 0 ifTrue:[
- diff := diff + 256.
- borrow := borrow + 1.
- ]
- ] ifFalse:[
- diff := borrow bitAnd:255.
- borrow := borrow bitShift:-8.
- ].
- resultDigitByteArray basicAt:index put:diff.
- index := index + 1
+ [(digitByteArray basicAt:len1) == 0] whileTrue:[
+ len1 := len1 - 1
+ ].
+ [(otherDigitByteArray basicAt:len2) == 0] whileTrue:[
+ len2 := len2 - 1
].
- [index <= len] whileTrue:[
- resultDigitByteArray basicAt:index put:(digitByteArray basicAt:index).
- index := index + 1
+ (len1 ~~ len2) ifTrue:[^ false].
+ [len1 > 0] whileTrue:[
+ d1 := digitByteArray basicAt:len1.
+ d2 := otherDigitByteArray basicAt:len1.
+ (d1 ~~ d2) ifTrue:[^ false].
+ len1 := len1 - 1
].
-
- ^ result
-
- "
- 12345678900000000000 absFastMinus:1
- 12345678900000000000 absFastMinus:1000000
- 12345678900000000000 absFastMinus:255
- (SmallInteger maxVal + 1) absFastMinus:1
- (SmallInteger minVal - 1) absFastMinus:1
- "
+ ^ true
!
absFastDiv:aSmallInteger
@@ -1049,6 +1095,190 @@
^ Array with:(result normalize) with:prevRest
!
+absFastMinus:aSmallInteger
+ "return a LargeInteger representing abs(self) - abs(theArgument).
+ The result is not normalized."
+
+ |result resultDigitByteArray
+ len "{ Class: SmallInteger }"
+ index "{ Class: SmallInteger }"
+ borrow "{ Class: SmallInteger }"
+ diff "{ Class: SmallInteger }" |
+
+ len := digitByteArray size.
+
+ result := self class basicNew numberOfDigits:(len + 1).
+ resultDigitByteArray := result digits.
+
+ index := 1.
+ borrow := aSmallInteger abs.
+
+ [borrow ~~ 0] whileTrue:[
+ (index <= len) ifTrue:[
+ diff := (digitByteArray basicAt:index) - (borrow bitAnd:16rFF).
+ borrow := borrow bitShift:-8.
+ diff < 0 ifTrue:[
+ diff := diff + 256.
+ borrow := borrow + 1.
+ ]
+ ] ifFalse:[
+ diff := borrow bitAnd:255.
+ borrow := borrow bitShift:-8.
+ ].
+ resultDigitByteArray basicAt:index put:diff.
+ index := index + 1
+ ].
+ [index <= len] whileTrue:[
+ resultDigitByteArray basicAt:index put:(digitByteArray basicAt:index).
+ index := index + 1
+ ].
+
+ ^ result
+
+ "
+ 12345678900000000000 absFastMinus:1
+ 12345678900000000000 absFastMinus:1000000
+ 12345678900000000000 absFastMinus:255
+ (SmallInteger maxVal + 1) absFastMinus:1
+ (SmallInteger minVal - 1) absFastMinus:1
+ "
+!
+
+absFastPlus:aSmallInteger
+ "return a LargeInteger representing abs(self) + abs(theArgument).
+ The result is not normalized."
+
+ |result resultDigitByteArray
+ len "{ Class: SmallInteger }"
+ index "{ Class: SmallInteger }"
+ carry "{ Class: SmallInteger }" |
+
+ len := digitByteArray size.
+
+ result := self class basicNew numberOfDigits:(len + 1).
+ resultDigitByteArray := result digits.
+
+ index := 1.
+ carry := aSmallInteger abs.
+
+ [carry ~~ 0] whileTrue:[
+ (index <= len) ifTrue:[
+ carry := (digitByteArray basicAt:index) + carry.
+ ].
+ resultDigitByteArray basicAt:index put:(carry bitAnd:16rFF).
+ carry := carry bitShift:-8.
+ index := index + 1
+ ].
+ [index <= len] whileTrue:[
+ resultDigitByteArray basicAt:index put:(digitByteArray basicAt:index).
+ index := index + 1
+ ].
+
+ ^ result
+!
+
+absLess:aLargeInteger
+ "return true, if abs(self) < abs(theArgument)"
+
+ |len1 "{ Class: SmallInteger }"
+ len2 "{ Class: SmallInteger }"
+ d1 "{ Class: SmallInteger }"
+ d2 "{ Class: SmallInteger }"
+ otherDigitByteArray |
+
+ len1 := digitByteArray size.
+ otherDigitByteArray := aLargeInteger digits.
+ len2 := otherDigitByteArray size.
+
+ [(digitByteArray basicAt:len1) == 0] whileTrue:[
+ len1 := len1 - 1
+ ].
+ [(otherDigitByteArray basicAt:len2) == 0] whileTrue:[
+ len2 := len2 - 1
+ ].
+ (len1 < len2) ifTrue:[^ true].
+ (len1 > len2) ifTrue:[^ false].
+
+ [len1 > 0] whileTrue:[
+ d1 := digitByteArray basicAt:len1.
+ d2 := otherDigitByteArray basicAt:len1.
+ (d1 < d2) ifTrue:[^ true].
+ (d1 > d2) ifTrue:[^ false].
+ len1 := len1 - 1
+ ].
+ ^ false
+!
+
+absMinus:aLargeInteger
+ "return a LargeInteger representing abs(self) - abs(theArgument)"
+
+ |result done
+ otherDigitByteArray resultDigitByteArray
+ len1 "{ Class: SmallInteger }"
+ len2 "{ Class: SmallInteger }"
+ index "{ Class: SmallInteger }"
+ borrow "{ Class: SmallInteger }"
+ diff "{ Class: SmallInteger }"
+ sum "{ Class: SmallInteger }"
+ carry "{ Class: SmallInteger }" |
+
+ len1 := digitByteArray size.
+ otherDigitByteArray := aLargeInteger digits.
+ len2 := otherDigitByteArray size.
+
+ result := self class basicNew numberOfDigits:((len1 max: len2) + 1).
+ resultDigitByteArray := result digits.
+
+ index := 1.
+ borrow := 0.
+
+ done := false.
+ [done] whileFalse:[
+ diff := borrow.
+ (index <= len1) ifTrue:[
+ diff := diff + (digitByteArray basicAt:index).
+ (index <= len2) ifTrue:[
+ diff := diff - (otherDigitByteArray basicAt:index)
+ ]
+ ] ifFalse:[
+ (index <= len2) ifTrue:[
+ diff := diff - (otherDigitByteArray basicAt:index)
+ ] ifFalse:[
+ "end reached"
+ done := true
+ ]
+ ].
+"/ workaround for
+"/ gcc code generator bug
+"/
+
+(diff >= 0) ifTrue:[
+ borrow := 0
+] ifFalse:[
+ borrow := -1.
+ diff := diff + 16r100
+].
+"/ (diff < 0) ifTrue:[
+"/ borrow := -1.
+"/ diff := diff + 16r100
+"/ ] ifFalse:[
+"/ borrow := 0
+"/ ].
+ resultDigitByteArray basicAt:index put:diff.
+ index := index + 1
+ ].
+ (borrow ~~ 0) ifTrue:[
+ result sign: -1.
+ carry := 0.
+ 1 to:(index - 1) do:[:i |
+ sum := ((resultDigitByteArray at:i) + carry - 16r100) negated.
+ resultDigitByteArray at:i put:sum.
+ carry := 1
+ ]
+ ].
+ ^ result normalize
+!
+
absMul:aLargeInteger
"return a LargeInteger representing abs(self) * abs(theArgument)"
@@ -1123,67 +1353,6 @@
^ result normalize
!
-absLess:aLargeInteger
- "return true, if abs(self) < abs(theArgument)"
-
- |len1 "{ Class: SmallInteger }"
- len2 "{ Class: SmallInteger }"
- d1 "{ Class: SmallInteger }"
- d2 "{ Class: SmallInteger }"
- otherDigitByteArray |
-
- len1 := digitByteArray size.
- otherDigitByteArray := aLargeInteger digits.
- len2 := otherDigitByteArray size.
-
- [(digitByteArray basicAt:len1) == 0] whileTrue:[
- len1 := len1 - 1
- ].
- [(otherDigitByteArray basicAt:len2) == 0] whileTrue:[
- len2 := len2 - 1
- ].
- (len1 < len2) ifTrue:[^ true].
- (len1 > len2) ifTrue:[^ false].
-
- [len1 > 0] whileTrue:[
- d1 := digitByteArray basicAt:len1.
- d2 := otherDigitByteArray basicAt:len1.
- (d1 < d2) ifTrue:[^ true].
- (d1 > d2) ifTrue:[^ false].
- len1 := len1 - 1
- ].
- ^ false
-!
-
-absEq:aLargeInteger
- "return true, if abs(self) = abs(theArgument)"
-
- |len1 "{ Class: SmallInteger }"
- len2 "{ Class: SmallInteger }"
- d1 "{ Class: SmallInteger }"
- d2 "{ Class: SmallInteger }"
- otherDigitByteArray |
-
- len1 := digitByteArray size.
- otherDigitByteArray := aLargeInteger digits.
- len2 := otherDigitByteArray size.
-
- [(digitByteArray basicAt:len1) == 0] whileTrue:[
- len1 := len1 - 1
- ].
- [(otherDigitByteArray basicAt:len2) == 0] whileTrue:[
- len2 := len2 - 1
- ].
- (len1 ~~ len2) ifTrue:[^ false].
- [len1 > 0] whileTrue:[
- d1 := digitByteArray basicAt:len1.
- d2 := otherDigitByteArray basicAt:len1.
- (d1 ~~ d2) ifTrue:[^ false].
- len1 := len1 - 1
- ].
- ^ true
-!
-
absPlus:aLargeInteger
"return a LargeInteger representing abs(self) + abs(theArgument)"
@@ -1232,118 +1401,6 @@
^ result normalize
!
-absMinus:aLargeInteger
- "return a LargeInteger representing abs(self) - abs(theArgument)"
-
- |result done
- otherDigitByteArray resultDigitByteArray
- len1 "{ Class: SmallInteger }"
- len2 "{ Class: SmallInteger }"
- index "{ Class: SmallInteger }"
- borrow "{ Class: SmallInteger }"
- diff "{ Class: SmallInteger }"
- sum "{ Class: SmallInteger }"
- carry "{ Class: SmallInteger }" |
-
- len1 := digitByteArray size.
- otherDigitByteArray := aLargeInteger digits.
- len2 := otherDigitByteArray size.
-
- result := self class basicNew numberOfDigits:((len1 max: len2) + 1).
- resultDigitByteArray := result digits.
-
- index := 1.
- borrow := 0.
-
- done := false.
- [done] whileFalse:[
- diff := borrow.
- (index <= len1) ifTrue:[
- diff := diff + (digitByteArray basicAt:index).
- (index <= len2) ifTrue:[
- diff := diff - (otherDigitByteArray basicAt:index)
- ]
- ] ifFalse:[
- (index <= len2) ifTrue:[
- diff := diff - (otherDigitByteArray basicAt:index)
- ] ifFalse:[
- "end reached"
- done := true
- ]
- ].
-"/ workaround for
-"/ gcc code generator bug
-"/
-
-(diff >= 0) ifTrue:[
- borrow := 0
-] ifFalse:[
- borrow := -1.
- diff := diff + 16r100
-].
-"/ (diff < 0) ifTrue:[
-"/ borrow := -1.
-"/ diff := diff + 16r100
-"/ ] ifFalse:[
-"/ borrow := 0
-"/ ].
- resultDigitByteArray basicAt:index put:diff.
- index := index + 1
- ].
- (borrow ~~ 0) ifTrue:[
- result sign: -1.
- carry := 0.
- 1 to:(index - 1) do:[:i |
- sum := ((resultDigitByteArray at:i) + carry - 16r100) negated.
- resultDigitByteArray at:i put:sum.
- carry := 1
- ]
- ].
- ^ result normalize
-!
-
-absDiv:anInteger
- "return an array with two LargeIntegers representing
- abs(self) // abs(theArgument) and abs(self) \\ abs(theArgument).
- This needs a rewrite."
-
- |tmp1 tmp2
- rem
- count "{ Class: SmallInteger }"
- digit "{ Class: SmallInteger }" |
-
- anInteger == 0 ifTrue:[
- ^ DivisionByZeroSignal raise
- ].
-
- self < anInteger ifTrue:[
- ^ Array with:0 with:self
- ].
-
- tmp1 := self simpleDeepCopy.
- tmp2 := anInteger simpleDeepCopy.
- count := 0.
- [tmp2 < tmp1] whileTrue:[
- tmp2 mul256.
- count := count + 1
- ].
-
- tmp2 div256.
-
- rem := 0 asLargeInteger.
- [count == 0] whileFalse:[
- digit := 0.
- [tmp1 >= tmp2] whileTrue:[
- digit := digit + 1.
- tmp1 := tmp1 - tmp2
- ].
- rem := rem * 256 + digit.
- tmp2 div256.
- count := count - 1
- ].
- ^ Array with:rem with:tmp1
-!
-
div256
"destructively divide the receiver by 256.
private - used for division only"
@@ -1362,79 +1419,28 @@
newDigits replaceFrom:2 with:digitByteArray startingAt:1.
newDigits at:1 put:0.
digitByteArray := newDigits
-! !
-
-!LargeInteger methodsFor:'comparing'!
+!
-= aNumber
- "return true, if the argument, aNumber has the same value as
- the receiver"
-
- (aNumber class == self class) ifFalse:[
- aNumber respondsToArithmetic ifFalse:[ ^ false ].
- ^ self retry:#= coercing:aNumber
- ].
- (aNumber sign == sign) ifFalse:[^ false].
- ^ self absEq:aNumber
+numberOfDigits:nDigits
+ digitByteArray := ByteArray new:nDigits.
+ sign := 1.
!
-< aNumber
- "return true, if the argument, aNumber is greater than the receiver"
-
- |otherSign|
-
- (aNumber class == self class) 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
+setDigits:digits
+ digitByteArray := digits.
+ sign := 1.
!
-> aNumber
- "return true, if the argument, aNumber is less than the receiver"
-
- |otherSign|
-
- (aNumber class == self class) ifFalse:[
- ^ self retry:#> coercing:aNumber
- ].
- otherSign := aNumber sign.
-
- (sign > 0) ifTrue:[
- "I am positive"
- (otherSign > 0) ifTrue:[^ aNumber absLess:self].
- ^ true "aNumber is <= 0"
- ].
- (sign == 0) ifTrue:[
- "I am zero"
- (otherSign > 0) ifTrue:[^ false].
- ^ true
- ].
- "I am negative"
- (otherSign > 0) ifTrue:[^ false].
- (otherSign == 0) ifTrue:[^ false].
- ^ (self absLess:aNumber) not
+sign:aNumber
+ sign := aNumber
! !
!LargeInteger methodsFor:'testing'!
-sign
- "return the sign of the receiver"
+even
+ "return true if the receiver is even"
- ^ sign
+ ^ (digitByteArray at:1) even
!
negative
@@ -1449,30 +1455,26 @@
^ (digitByteArray at:1) even
!
-even
- "return true if the receiver is even"
-
- ^ (digitByteArray at:1) even
-!
-
positive
"return true, if the receiver is >= 0"
^ (sign >= 0)
!
+sign
+ "return the sign of the receiver"
+
+ ^ sign
+!
+
strictlyPositive
"return true, if the receiver is > 0"
^ (sign > 0)
! !
-!LargeInteger methodsFor:'printing & storing'!
+!LargeInteger class methodsFor:'documentation'!
-storeOn:aStream
- "append a representation of the receiver to aStream, which can
- be used to reconstruct the receiver."
-
- self printOn:aStream.
- aStream nextPutAll:' asLargeInteger'
+version
+ ^ '$Header: /cvs/stx/stx/libbasic/LargeInteger.st,v 1.21 1995-12-07 21:35:26 cg Exp $'
! !