hg/stx-libbasic: comparison LargeInteger.st

equal deleted inserted replaced

-:f5f8a2f201e5
+:d3fbf4b36be7
 "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"
+"return the quotient of the receiver and the argument, aNumber.
+The result is truncated toward negative infinity and negative,
-|otherSign divMod d rem abs "{ Class: SmallInteger }" |
+if the operands signs differ."
+|otherSign divMod d rem abs "{ Class: SmallInteger }" n|
 otherSign := aNumber sign.
 "
 this is the common case, dividing by a SmallInteger.
 "/ stupid adjust ...
 (divMod at:2) == 0 ifFalse:[
 ^ (rem sign:-1) - 1
 ].
 ^ rem sign:-1
-]
+].
+n := aNumber asLargeInteger.
+] ifFalse:[
+n := aNumber
 ].
 "
 if the argument is not a largeInteger, coerce
 "
-(aNumber class == self class) ifFalse:[
+(n class == self class) ifFalse:[
 ^ self retry:#// coercing:aNumber
 ].
 sign < 0 ifTrue:[
-(sign == otherSign) ifTrue:[^ (self absDiv:aNumber negated) at:1].
+(sign == otherSign) ifTrue:[^ (self absDiv:n negated) at:1].
 ] ifFalse:[
-(sign == otherSign) ifTrue:[^ (self absDiv:aNumber) at:1].
+(sign == otherSign) ifTrue:[^ (self absDiv:n) at:1].
 ].
-divMod := self absDiv:aNumber.
+divMod := self absDiv:n.
 "/ stupid adjust ...
 (divMod at:2) == 0 ifFalse:[
 ^ ((divMod at:1) sign:-1) - 1
 ].
 ^ (divMod at:1) sign:-1
 "
-9000000000 // 4000000000   => 2
+900 // 400
--9000000000 // 4000000000  => -3
+-900 // 400
-9000000000 // -4000000000  => -3
+900 // -400
--9000000000 // -4000000000 => 2
+-900 // -400
-9000000000 quo: 4000000000   => 2
+9000000000 // 4000000000
--9000000000 quo: 4000000000  => -2
+-9000000000 // 4000000000
-9000000000 quo: -4000000000  => -2
+9000000000 // -4000000000
--9000000000 quo: -4000000000 => 2
+-9000000000 // -4000000000
-"
+900 quo: 400
-"Modified: 29.10.1996 / 20:44:23 / cg"
+-900 quo: 400
+900 quo: -400
+-900 quo: -400
+9000000000 quo: 4000000000
+-9000000000 quo: 4000000000
+9000000000 quo: -4000000000
+-9000000000 quo: -4000000000
+"
+"Modified: 5.11.1996 / 14:16:46 / cg"
 !
 \\ aNumber
-"return the remainder of division of the receiver by the argument, aNumber"
+"return the remainder of division of the receiver by the argument, aNumber.
+The sign of the result is that of aNumber."
-|abs|
+|abs rem|
 abs := aNumber abs.
 "
 this is the common case, dividing by a SmallInteger.
 Use a special method for this case ...
 "
 (aNumber class == SmallInteger) ifTrue:[
 (abs between:1 and:16r003fffff) ifTrue:[
-^ ((self absFastDiv:abs) at:2)
+rem := (self absFastDiv:abs) at:2.
-]
+] ifFalse:[
-].
+rem := (self absDiv:abs asLargeInteger) at:2
+].
-"
+] ifFalse:[
-if the argument is not a largeInteger, coerce
+"
-"
+if the argument is not a largeInteger, coerce
-(aNumber class == self class) ifFalse:[
+"
-^ self retry:#\\ coercing:aNumber
+(aNumber class == self class) ifFalse:[
-].
+^ self retry:#\\ coercing:aNumber
+].
-^ ((self absDiv:abs) at:2)
+rem := (self absDiv:abs) at:2.
-"
+].
-9000000000 \\ 4000000000    => 1000000000
--9000000000 \\ 4000000000   => 1000000000
+aNumber negative ifTrue:[
-9000000000 \\ -4000000000   => 1000000000
+^ rem negated
--9000000000 \\ -4000000000  => 1000000000
+].
+^ rem
-9000000000 rem: 4000000000   => 1000000000
--9000000000 rem: 4000000000  => -1000000000
+"
-9000000000 rem: -4000000000  => -1000000000
+900 \\ 400
--9000000000 rem: -4000000000 => 1000000000
+-900 \\ 400
-"
+900 \\ -400
+-900 \\ -400
-"Modified: 29.10.1996 / 20:41:35 / cg"
+9000000000 \\ 4000000000
+-9000000000 \\ 4000000000
+9000000000 \\ -4000000000
+-9000000000 \\ -4000000000
+900 rem: 400
+-900 rem: 400
+900 rem: -400
+-900 rem: -400
+9000000000 rem: 4000000000
+-9000000000 rem: 4000000000
+9000000000 rem: -4000000000
+-9000000000 rem: -4000000000
+"
+"Modified: 5.11.1996 / 13:54:32 / cg"
 !
 divMod:aNumber
 "return an array filled with self // aNumber and
 self \\ aNumber.
 newNumber sign:(sign negated).
 ^ newNumber
 !
 quo:aNumber
-"return the quotient of the receiver and the argument, aNumber"
+"return the quotient of the receiver and the argument, aNumber.
+The result is truncated toward zero (which is different from //, which
+truncates toward negative infinity).
+The results sign is negative if the receiver has a sign
+different from the args sign"
 |otherSign d quo abs "{ Class: SmallInteger }" |
 otherSign := aNumber sign.
 (sign == otherSign) ifTrue:[^ (self absDiv:aNumber) at:1].
 ].
 ^ ((self absDiv:aNumber) at:1) sign:-1
 "
-9000000000 // 4000000000   => 2
+900 // 400
--9000000000 // 4000000000  => -3
+-900 // 400
-9000000000 // -4000000000  => -3
+900 // -400
--9000000000 // -4000000000 => 2
+-900 // -400
-9000000000 quo: 4000000000   => 2
+9000000000 // 4000000000
--9000000000 quo: 4000000000  => -2
+-9000000000 // 4000000000
-9000000000 quo: -4000000000  => -2
+9000000000 // -4000000000
--9000000000 quo: -4000000000 => 2
+-9000000000 // -4000000000
-"
+900 quo: 400
-"Modified: 29.10.1996 / 20:39:09 / cg"
+-900 quo: 400
+900 quo: -400
+-900 quo: -400
+9000000000 quo: 4000000000
+-9000000000 quo: 4000000000
+9000000000 quo: -4000000000
+-9000000000 quo: -4000000000
+"
+"Modified: 5.11.1996 / 14:14:17 / cg"
 !
 rem:aNumber
-"return the remainder of division of the receiver by the argument, aNumber"
+"return the remainder of division of the receiver by the argument, aNumber.
+The returned remainder has the same sign as the receiver."
-|otherSign rem abs "{ Class: SmallInteger }" |
+|rem abs "{ Class: SmallInteger }" |
-otherSign := aNumber sign.
 "
 this is the common case, dividing by a SmallInteger.
-Use a special method for this case ...
+Use special code for this case ...
 "
 (aNumber class == SmallInteger) ifTrue:[
 abs := aNumber.
 abs := abs abs.
 (abs between:1 and:16r003fffff) ifTrue:[
 rem := (self absFastDiv:abs) at:2.
+] ifFalse:[
-sign < 0 ifTrue:[
+rem := (self absDiv:(abs asLargeInteger)) at:2
-(sign == otherSign) ifTrue:[^ rem].
+].
-^ rem sign:-1
+] ifFalse:[
-].
+"
-(sign == otherSign) ifTrue:[^ rem].
+if the argument is not a largeInteger, coerce
-^ rem sign:-1
+"
-]
+(aNumber class == self class) ifFalse:[
-].
+^ self retry:#\\ coercing:aNumber
+].
-"
-if the argument is not a largeInteger, coerce
+rem := (self absDiv:aNumber) at:2
-"
-(aNumber class == self class) ifFalse:[
-^ self retry:#\\ coercing:aNumber
 ].
 sign < 0 ifTrue:[
-(sign == otherSign) ifTrue:[^ (self absDiv:aNumber negated) at:2].
+^ rem sign:-1
-^ ((self absDiv:aNumber) at:2) sign:-1
+].
-].
+^ rem
-(sign == otherSign) ifTrue:[^ (self absDiv:aNumber) at:2].
-^ ((self absDiv:aNumber negated) at:2) sign:-1
+"
+900 \\ 400
-"
+-900 \\ 400
-9000000000 \\ 4000000000    => 1000000000
+900 \\ -400
--9000000000 \\ 4000000000   => 1000000000
+-900 \\ -400
-9000000000 \\ -4000000000   => 1000000000
--9000000000 \\ -4000000000  => 1000000000
+9000000000 \\ 4000000000
+-9000000000 \\ 4000000000
-9000000000 rem: 4000000000   => 1000000000
+9000000000 \\ -4000000000
--9000000000 rem: 4000000000  => -1000000000
+-9000000000 \\ -4000000000
-9000000000 rem: -4000000000  => -1000000000
--9000000000 rem: -4000000000 => 1000000000
+900 rem: 400
-"
+-900 rem: 400
+900 rem: -400
-"Modified: 29.10.1996 / 20:40:33 / cg"
+-900 rem: -400
+9000000000 rem: 4000000000
+-9000000000 rem: 4000000000
+9000000000 rem: -4000000000
+-9000000000 rem: -4000000000
+"
+"Modified: 5.11.1996 / 14:02:59 / cg"
 ! !
 !LargeInteger methodsFor:'byte access'!
 digitAt:index
 "return the argument as a LargeInteger"
 ^ aNumber asLargeInteger
 !
-normalize
+compressed
 "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 }"
 %{  /* NOCONTEXT */
 OBJ t;
 if (__INST(sign) == __MKSMALLINT(0)) {
-	RETURN (__MKSMALLINT(0));
+RETURN (__MKSMALLINT(0));
 }
 t = __INST(digitByteArray);
 if (__isByteArray(t)) {
-	unsigned char *_digitBytes = __ByteArrayInstPtr(t)->ba_element;
+unsigned char *_digitBytes = __ByteArrayInstPtr(t)->ba_element;
-	int _idx = _byteArraySize(t);
+int _idx = _byteArraySize(t);
-	int _val;
+int _val;
-	while ((_idx > 0) && (_digitBytes[_idx - 1] == 0)) {
+while ((_idx > 0) && (_digitBytes[_idx - 1] == 0)) {
-	    _idx--;
+_idx--;
-	}
+}
-	switch (_idx) {
+switch (_idx) {
-	    case 0:
+case 0:
-		RETURN (__MKSMALLINT(0));
+RETURN (__MKSMALLINT(0));
-		break;
+break;
-	    case 1:
+case 1:
-		_val = _digitBytes[0];
+_val = _digitBytes[0];
-		if (__INST(sign) == __MKSMALLINT(-1))
+if (__INST(sign) == __MKSMALLINT(-1))
-		    _val = -_val;
+_val = -_val;
-		RETURN (__MKSMALLINT(_val));
+RETURN (__MKSMALLINT(_val));
-	    case 2:
+case 2:
-		_val = (_digitBytes[1]<<8) + _digitBytes[0];
+_val = (_digitBytes[1]<<8) + _digitBytes[0];
-		if (__INST(sign) == __MKSMALLINT(-1))
+if (__INST(sign) == __MKSMALLINT(-1))
-		    _val = -_val;
+_val = -_val;
-		RETURN (__MKSMALLINT(_val));
+RETURN (__MKSMALLINT(_val));
-	    case 3:
+case 3:
-		_val = (((_digitBytes[2]<<8) + _digitBytes[1])<<8) + _digitBytes[0];
+_val = (((_digitBytes[2]<<8) + _digitBytes[1])<<8) + _digitBytes[0];
-		if (__INST(sign) == __MKSMALLINT(-1))
+if (__INST(sign) == __MKSMALLINT(-1))
-		    _val = -_val;
+_val = -_val;
-		RETURN (__MKSMALLINT(_val));
+RETURN (__MKSMALLINT(_val));
-	    case 4:
+case 4:
-		_val = _digitBytes[3];
+_val = _digitBytes[3];
-		if (_val <= 0x40) {
+if (_val <= 0x40) {
-		    _val = (((((_val<<8) + _digitBytes[2])<<8) + _digitBytes[1])<<8) + _digitBytes[0];
+_val = (((((_val<<8) + _digitBytes[2])<<8) + _digitBytes[1])<<8) + _digitBytes[0];
-		    if (__INST(sign) == __MKSMALLINT(-1))
+if (__INST(sign) == __MKSMALLINT(-1))
-			_val = -_val;
+_val = -_val;
-		    if ((_val >= _MIN_INT) && (_val <= _MAX_INT)) {
+if ((_val >= _MIN_INT) && (_val <= _MAX_INT)) {
-			RETURN (__MKSMALLINT(_val));
+RETURN (__MKSMALLINT(_val));
-		    }
+}
-		}
+}
-		break;
+break;
-	    default:
+default:
-		break;
+break;
-	}
+}
 }
 %}.
 index := digitByteArray size.
 [(index > 0) and:[(digitByteArray at:index) == 0]] whileTrue:[
-	index := index - 1
+index := index - 1
 ].
 (index ~~ digitByteArray size) ifTrue:[
-	digitByteArray := digitByteArray copyFrom:1 to:index
+digitByteArray := digitByteArray copyFrom:1 to:index
 ].
 ^ self
 !
 value:aSmallInteger
 len := len + 1.
 resultDigitByteArray basicAt:len put:(carry bitAnd:16rFF).
 carry := carry bitShift:-8
 ].
 ].
-^ result normalize
+^ result compressed
 !
 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)"
 rem
 count "{ Class: SmallInteger }"
 digit "{ Class: SmallInteger }" |
 anInteger == 0 ifTrue:[
-	^ DivisionByZeroSignal raise
+^ DivisionByZeroSignal raise
+].
+self = anInteger ifTrue:[
+^ Array with:1 with:0
 ].
 tmp1 := self simpleDeepCopy.
 tmp1 sign:1.
 tmp2 := anInteger simpleDeepCopy.
 tmp2 sign:1.
 (tmp1 < tmp2) ifTrue:[
-	^ Array with:0 with:tmp1
+^ Array with:0 with:tmp1
 ].
 count := 0.
 [tmp2 < tmp1] whileTrue:[
-	tmp2 mul256.
+tmp2 mul256.
-	count := count + 1
+count := count + 1
 ].
 tmp2 div256.
 rem := 0 asLargeInteger.
 rem sign:1.
 [count == 0] whileFalse:[
-	digit := 0.
+digit := 0.
-	[tmp1 >= tmp2] whileTrue:[
+[tmp1 >= tmp2] whileTrue:[
-	    digit := digit + 1.
+digit := digit + 1.
-	    tmp1 := tmp1 - tmp2
+tmp1 := tmp1 - tmp2
-	].
+].
-	rem := rem * 256 + digit.
+rem := (rem * 256) + digit.
-	tmp2 div256.
+tmp2 div256.
-	count := count - 1
+count := count - 1
 ].
 ^ Array with:rem with:tmp1
+"Modified: 5.11.1996 / 13:46:14 / cg"
 !
 absEq:aLargeInteger
 "return true, if abs(self) = abs(theArgument)"
 newDigitByteArray at:i put:tmp1 // aSmallInteger.
 prevRest := (tmp1 \\ aSmallInteger).
 ]
 ].
-^ Array with:result normalize with:prevRest
+^ Array with:result compressed with:prevRest
 !
 absFastMinus:aSmallInteger
 "return a LargeInteger representing abs(self) - abs(theArgument).
 The result is not normalized."
 resultDigitByteArray basicAt:index put:(lastDigit := digitByteArray basicAt:index).
 index := index + 1
 ].
 lastDigit == 0 ifTrue:[
-^ result normalize
+^ result compressed
 ].
 ^ result
 "
 12345678900000000000 absFastMinus:1
 12345678900000000000 absFastMinus:255
 (SmallInteger maxVal + 1) absFastMinus:1
 (SmallInteger minVal - 1) absFastMinus:1
 "
-"Modified: 20.10.1996 / 18:40:22 / cg"
+"Modified: 5.11.1996 / 14:09:16 / cg"
 !
 absFastPlus:aSmallInteger
 "return a LargeInteger representing abs(self) + abs(theArgument).
 The result is not normalized."
 resultDigitByteArray basicAt:index put:(lastDigit := digitByteArray basicAt:index).
 index := index + 1
 ].
 lastDigit == 0 ifTrue:[
-^ result normalize
+^ result compressed
 ].
 ^ result
+"Modified: 5.11.1996 / 14:09:19 / cg"
 !
 absLess:aLargeInteger
 "return true, if abs(self) < abs(theArgument)"
 resultDigitByteArray basicAt:index put:(carry bitAnd:16rFF).
 carry := carry bitShift:-8.
 index := index + 1
 ].
 ].
-^ result normalize
+^ result compressed
-"Modified: 1.7.1996 / 21:07:17 / cg"
+"Modified: 5.11.1996 / 14:09:25 / cg"
 !
 absMul:aLargeInteger
 "return a LargeInteger representing abs(self) * abs(theArgument)"
 %{
 if (__isByteArray(__INST(digitByteArray))
 && __isByteArray(otherDigitByteArray)
 && __isByteArray(resultDigitByteArray)
 && __bothSmallInteger(len1, len2)) {
-	unsigned char *myBytes = __ByteArrayInstPtr(__INST(digitByteArray))->ba_element;
+unsigned char *myBytes = __ByteArrayInstPtr(__INST(digitByteArray))->ba_element;
-	unsigned char *otherBytes = __ByteArrayInstPtr(otherDigitByteArray)->ba_element;
+unsigned char *otherBytes = __ByteArrayInstPtr(otherDigitByteArray)->ba_element;
-	unsigned char *resultBytes = __ByteArrayInstPtr(resultDigitByteArray)->ba_element;
+unsigned char *resultBytes = __ByteArrayInstPtr(resultDigitByteArray)->ba_element;
-	int _index1, _index2, _dstIndex, _idx;
+int _index1, _index2, _dstIndex, _idx;
-	unsigned _prod, _carry, _v;
+unsigned _prod, _carry, _v;
-	for (_index1 = 0; _index1 < __intVal(len1); _index1++) {
+for (_index1 = 0; _index1 < __intVal(len1); _index1++) {
-	    for (_index2 = 0; _index2 < __intVal(len2); _index2++) {
+for (_index2 = 0; _index2 < __intVal(len2); _index2++) {
-		_dstIndex = _index1 + _index2;
+_dstIndex = _index1 + _index2;
-		_prod = myBytes[_index1] * otherBytes[_index2];
+_prod = myBytes[_index1] * otherBytes[_index2];
-		_prod += resultBytes[_dstIndex];
+_prod += resultBytes[_dstIndex];
-		resultBytes[_dstIndex] = _prod & 0xFF;
+resultBytes[_dstIndex] = _prod & 0xFF;
-		_carry = _prod >> 8;
+_carry = _prod >> 8;
-		if (_carry) {
+if (_carry) {
-		    _idx = _dstIndex + 1;
+_idx = _dstIndex + 1;
-		    while (_carry) {
+while (_carry) {
-			_v = resultBytes[_idx] + _carry;
+_v = resultBytes[_idx] + _carry;
-			resultBytes[_idx] = _v & 0xFF;
+resultBytes[_idx] = _v & 0xFF;
-			_carry = _v >> 8;
+_carry = _v >> 8;
-			_idx = _idx + 1;
+_idx = _idx + 1;
-		    }
+}
-		}
+}
-	    }
+}
-	}
+}
-	ok = true;
+ok = true;
 }
 %}.
 ok ifFalse:[
-	1 to:len1 do:[:index1 |
+1 to:len1 do:[:index1 |
-	    1 to:len2 do:[:index2 |
+1 to:len2 do:[:index2 |
-		dstIndex := index1 + index2 - 1.
+dstIndex := index1 + index2 - 1.
-		prod := (digitByteArray basicAt:index1) * (otherDigitByteArray basicAt:index2).
+prod := (digitByteArray basicAt:index1) * (otherDigitByteArray basicAt:index2).
-		prod := prod + (resultDigitByteArray basicAt:dstIndex).
+prod := prod + (resultDigitByteArray basicAt:dstIndex).
-		resultDigitByteArray basicAt:dstIndex put:(prod bitAnd:16rFF).
+resultDigitByteArray basicAt:dstIndex put:(prod bitAnd:16rFF).
-		carry := prod bitShift:-8.
+carry := prod bitShift:-8.
-		carry ~~ 0 ifTrue:[
+carry ~~ 0 ifTrue:[
-		    idx := dstIndex + 1.
+idx := dstIndex + 1.
-		    [carry ~~ 0] whileTrue:[
+[carry ~~ 0] whileTrue:[
-			v := (resultDigitByteArray basicAt:idx) + carry.
+v := (resultDigitByteArray basicAt:idx) + carry.
-			resultDigitByteArray basicAt:idx put:(v bitAnd:255).
+resultDigitByteArray basicAt:idx put:(v bitAnd:255).
-			carry := v bitShift:-8.
+carry := v bitShift:-8.
-			idx := idx + 1
+idx := idx + 1
-		    ]
+]
-		]
+]
-	    ]
+]
-	].
+].
 ].
-^ result normalize
+^ result compressed
 !
 absPlus:aLargeInteger
 "return a LargeInteger representing abs(self) + abs(theArgument)"
 index := 1.
 carry := 0.
 done := false.
 [done] whileFalse:[
-	sum := carry.
+sum := carry.
-	(index <= len1) ifTrue:[
+(index <= len1) ifTrue:[
-	    sum := sum + (digitByteArray basicAt:index).
+sum := sum + (digitByteArray basicAt:index).
-	    (index <= len2) ifTrue:[
+(index <= len2) ifTrue:[
-		sum := sum + (otherDigitByteArray basicAt:index)
+sum := sum + (otherDigitByteArray basicAt:index)
-	    ]
+]
-	] ifFalse:[
+] ifFalse:[
-	    (index <= len2) ifTrue:[
+(index <= len2) ifTrue:[
-		sum := sum + (otherDigitByteArray basicAt:index)
+sum := sum + (otherDigitByteArray basicAt:index)
-	    ] ifFalse:[
+] ifFalse:[
-		"end reached"
+"end reached"
-		done := true
+done := true
-	    ]
+]
-	].
+].
-	(sum >= 16r100) ifTrue:[
+(sum >= 16r100) ifTrue:[
-	    carry := 1.
+carry := 1.
-	    sum := sum - 16r100
+sum := sum - 16r100
-	] ifFalse:[
+] ifFalse:[
-	    carry := 0
+carry := 0
-	].
+].
-	resultDigitByteArray basicAt:index put:sum.
+resultDigitByteArray basicAt:index put:sum.
-	index := index + 1
+index := index + 1
 ].
-^ result normalize
+^ result compressed
+"Modified: 5.11.1996 / 14:09:34 / cg"
 !
 div256
 "destructively divide the receiver by 256.
 private - used for division only"
 ! !
 !LargeInteger class methodsFor:'documentation'!
 version
-^ '$Header: /cvs/stx/stx/libbasic/LargeInteger.st,v 1.35 1996-11-01 19:00:10 cg Exp $'
+^ '$Header: /cvs/stx/stx/libbasic/LargeInteger.st,v 1.36 1996-11-05 13:31:25 cg Exp $'
 ! !

changeset 1883	d3fbf4b36be7
parent 1857	94f36a4923db
child 1890	aca066e06680