--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/LargeInt.st Fri Jul 16 11:39:45 1993 +0200
@@ -0,0 +1,723 @@
+"
+ COPYRIGHT (c) 1988-93 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 digitArray'
+ classVariableNames:''
+ poolDictionaries:''
+ category:'Magnitude-Numbers'
+!
+
+LargeInteger comment:'
+
+COPYRIGHT (c) 1988-93 by Claus Gittinger
+ All Rights Reserved
+
+This class provides arbitrary precision integers. These are represented as:
+ sign (-1/0/+1) and, if sign ~~ 0
+ an Array of digits with 4 digits per element;
+ least significant 4 digits at index 1 ...
+
+This is definitely not a good (fast) implementation -
+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 :-).
+
+%W% %E%
+'!
+
+!LargeInteger class methodsFor:'instance creation'!
+
+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'
+!
+
+value:aSmallInteger
+ "create and return a new LargeInteger with value taken from
+ the argument, aSmallInteger"
+
+ ^ 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"
+
+ hiBits < 0 ifTrue:[
+ ^ ((self value:hiBits negated) * 16r10000 + lowBits) negated
+ ].
+ ^ (self value:hiBits) * 16r10000 + lowBits
+! !
+
+
+!LargeInteger methodsFor:'coercing & converting'!
+
+coerce:aNumber
+ "return the argument as a LargeInteger"
+
+ ^ aNumber asLargeInteger
+!
+
+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"
+
+ |value|
+
+ value := 0.
+ (sign == 0) ifFalse:[
+ digitArray reverseDo:[:aDigit |
+ value := (value times:10000) + aDigit
+ ].
+ (sign < 0) ifTrue:[
+ value := value negated
+ ]
+ ].
+ ^ value
+!
+
+asFloat
+ "return a Float with same value as myself"
+
+ |newFloat|
+
+ newFloat := 0.0.
+ (sign == 0) ifFalse:[
+ digitArray reverseDo:[:aDigit |
+ newFloat := (newFloat * 10000.0) + aDigit asFloat
+ ].
+ (sign < 0) ifTrue:[
+ newFloat := newFloat negated
+ ]
+ ].
+ ^ newFloat
+!
+
+value:aSmallInteger
+ "return a new LargeInteger with value taken from a SmallInteger"
+
+ |absValue
+ index "{ Class: SmallInteger }"|
+
+ (aSmallInteger == 0) ifTrue: [
+ digitArray := nil.
+ sign := 0.
+ ^ self
+ ].
+ (aSmallInteger < 0) ifTrue: [
+ sign := -1.
+ absValue := aSmallInteger negated
+ ] ifFalse: [
+ sign := 1.
+ absValue := aSmallInteger
+ ].
+ digitArray := Array new:3.
+ index := 1.
+ [absValue == 0] whileFalse: [
+ digitArray at:index put:(absValue \\ 10000).
+ absValue := absValue // 10000.
+ index := index + 1
+ ].
+ [index <= 3] whileTrue:[
+ digitArray at:index put:0.
+ index := index + 1
+ ]
+! !
+
+!LargeInteger methodsFor:'comparing'!
+
+= aNumber
+ "return true, if the argument, aNumber has the same value as
+ the receiver"
+
+ (aNumber class == LargeInteger) 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 greater than the receiver"
+
+ |otherSign|
+
+ (aNumber class == LargeInteger) 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
+! !
+
+!LargeInteger methodsFor:'arithmetic'!
+
++ aNumber
+ "return the sum of the receiver and the argument, aNumber"
+
+ |otherSign|
+
+ (aNumber class == LargeInteger) 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
+ ].
+ (sign == 0) ifTrue:[^ aNumber].
+ "I am negative"
+ (otherSign > 0) ifTrue:[^ aNumber absMinus:self].
+ (otherSign < 0) ifTrue:[^ (self absPlus:aNumber) negated].
+ ^ self
+!
+
+- aNumber
+ "return the difference of the receiver and the argument, aNumber"
+
+ |otherSign|
+
+ (aNumber class == LargeInteger) 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
+ ].
+ (sign == 0) ifTrue:[^ aNumber negated].
+ "I am negative"
+ (otherSign > 0) ifTrue:[^ (self absPlus:aNumber) negated].
+ (otherSign < 0) ifTrue:[^ (self absMinus:aNumber) negated].
+ ^ self
+!
+
+* aNumber
+ "return the product of the receiver and the argument, aNumber"
+
+ |otherSign|
+
+ (aNumber = 10) ifTrue:[
+ ^ self deepCopy mul10
+ ].
+ (aNumber class == LargeInteger) ifFalse:[
+ ^ self retry:#* coercing:aNumber
+ ].
+ otherSign := aNumber sign.
+
+ (sign == 0) ifTrue:[^ 0].
+ (sign == otherSign) ifTrue:[^ self absMul:aNumber].
+ (otherSign == 0) ifTrue:[^ 0].
+ ^ (self absMul:aNumber) negated
+!
+
+/ aNumber
+ "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|
+
+ (aNumber = 10) ifTrue:[
+ ^ self deepCopy div10
+ ].
+ (aNumber class == LargeInteger) ifFalse:[
+ ^ self retry:#// coercing:aNumber
+ ].
+ otherSign := aNumber sign.
+
+ sign < 0 ifTrue:[
+ (sign == otherSign) ifTrue:[^ (self negated absDiv:aNumber negated) at:1].
+ ^ ((self negated absDiv:aNumber) at:1) negated
+ ].
+ (sign == otherSign) ifTrue:[^ (self absDiv:aNumber) at:1].
+ ^ ((self absDiv:aNumber negated) at:1) negated
+!
+
+\\ aNumber
+ "return the remainder of division of the receiver by the argument, aNumber"
+
+ |otherSign|
+
+ (aNumber class == LargeInteger) ifFalse:[
+ ^ self retry:#\\ coercing:aNumber
+ ].
+
+ otherSign := aNumber sign.
+ sign < 0 ifTrue:[
+ (sign == otherSign) ifTrue:[^ (self negated absDiv:aNumber negated) at:2].
+ ^ ((self negated absDiv:aNumber) at:2) negated
+ ].
+ (sign == otherSign) ifTrue:[^ (self absDiv:aNumber) at:2].
+ ^ ((self absDiv:aNumber negated) at:2) negated
+!
+
+negated
+ "return a LargeInteger with value negated from receivers value"
+
+ |newNumber|
+
+ (sign == 0) ifTrue:[^ 0].
+ newNumber := self shallowCopy.
+ newNumber sign:(sign negated).
+ ^ newNumber
+! !
+
+!LargeInteger methodsFor:'bit operations'!
+
+bitAnd:anInteger
+ "q & d hack to make Random work;
+ this works only correctly, if my value can be represented
+ as a SmallInteger"
+
+ ^ self asSmallInteger bitAnd:anInteger
+! !
+
+!LargeInteger methodsFor:'testing'!
+
+sign
+ "return the sign of the receiver"
+
+ ^ sign
+!
+
+odd
+ "return true if the receiver is odd"
+
+ ^ (digitArray at:1) even
+!
+
+even
+ "return true if the receiver is even"
+
+ ^ (digitArray at:1) even
+!
+
+negative
+ "return true, if the receiver is < 0"
+
+ ^ (sign < 0)
+!
+
+positive
+ "return true, if the receiver is >= 0"
+
+ ^ (sign >= 0)
+!
+
+strictlyPositive
+ "return true, if the receiver is > 0"
+
+ ^ (sign > 0)
+! !
+
+!LargeInteger methodsFor:'private'!
+
+absEq:aLargeInteger
+ "return true, if abs(self) = abs(theArgument)"
+
+ |len1 "{ Class: SmallInteger }"
+ len2 "{ Class: SmallInteger }"
+ d1 "{ Class: SmallInteger }"
+ d2 "{ Class: SmallInteger }"
+ otherDigits |
+
+ len1 := digitArray size.
+ otherDigits := aLargeInteger digits.
+ len2 := otherDigits size.
+
+ [(digitArray basicAt:len1) == 0] whileTrue:[
+ len1 := len1 - 1
+ ].
+ [(otherDigits basicAt:len2) == 0] whileTrue:[
+ len2 := len2 - 1
+ ].
+ (len1 ~~ len2) ifTrue:[^ false].
+ [len1 > 0] whileTrue:[
+ d1 := digitArray basicAt:len1.
+ d2 := otherDigits basicAt:len1.
+ (d1 ~~ d2) ifTrue:[^ false].
+ len1 := len1 - 1
+ ].
+ ^ true
+!
+
+absLess:aLargeInteger
+ "return true, if abs(self) < abs(theArgument)"
+
+ |len1 "{ Class: SmallInteger }"
+ len2 "{ Class: SmallInteger }"
+ d1 "{ Class: SmallInteger }"
+ d2 "{ Class: SmallInteger }"
+ otherDigits |
+
+ len1 := digitArray size.
+ otherDigits := aLargeInteger digits.
+ len2 := otherDigits size.
+
+ [(digitArray basicAt:len1) == 0] whileTrue:[
+ len1 := len1 - 1
+ ].
+ [(otherDigits basicAt:len2) == 0] whileTrue:[
+ len2 := len2 - 1
+ ].
+ (len1 < len2) ifTrue:[^ true].
+ (len1 > len2) ifTrue:[^ false].
+
+ [len1 > 0] whileTrue:[
+ d1 := digitArray basicAt:len1.
+ d2 := otherDigits basicAt:len1.
+ (d1 < d2) ifTrue:[^ true].
+ (d1 > d2) ifTrue:[^ false].
+ len1 := len1 - 1
+ ].
+ ^ false
+!
+
+absPlus:aLargeInteger
+ "return a LargeInteger representing abs(self) + abs(theArgument)"
+
+ |result done otherDigits resultDigits
+ len1 "{ Class: SmallInteger }"
+ len2 "{ Class: SmallInteger }"
+ index "{ Class: SmallInteger }"
+ carry "{ Class: SmallInteger }"
+ sum "{ Class: SmallInteger }" |
+
+ len1 := digitArray size.
+ otherDigits := aLargeInteger digits.
+ len2 := otherDigits size.
+
+ result := LargeInteger basicNew
+ numberOfDigits:((len1 max: len2) + 1).
+ result sign:1.
+ resultDigits := result digits.
+
+ index := 1.
+ carry := 0.
+
+ done := false.
+ [done] whileFalse:[
+ sum := carry.
+ (index <= len1) ifTrue:[
+ sum := sum + (digitArray basicAt:index).
+ (index <= len2) ifTrue:[
+ sum := sum + (otherDigits basicAt:index)
+ ]
+ ] ifFalse:[
+ (index <= len2) ifTrue:[
+ sum := sum + (otherDigits basicAt:index)
+ ] ifFalse:[
+ "end reached"
+ done := true
+ ]
+ ].
+ (sum > 9999) ifTrue:[
+ carry := 1.
+ sum := sum - 10000
+ ] ifFalse:[
+ carry := 0
+ ].
+ resultDigits basicAt:index put:sum.
+ index := index + 1
+ ].
+ ^ result normalize
+!
+
+absMinus:aLargeInteger
+ "return a LargeInteger representing abs(self) - abs(theArgument)"
+
+ |result done
+ otherDigits resultDigits
+ len1 "{ Class: SmallInteger }"
+ len2 "{ Class: SmallInteger }"
+ index "{ Class: SmallInteger }"
+ borrow "{ Class: SmallInteger }"
+ diff "{ Class: SmallInteger }"
+ sum "{ Class: SmallInteger }"
+ carry "{ Class: SmallInteger }" |
+
+ len1 := digitArray size.
+ otherDigits := aLargeInteger digits.
+ len2 := otherDigits size.
+
+ result := LargeInteger basicNew
+ numberOfDigits:((len1 max: len2) + 1).
+ result sign:1.
+ resultDigits := result digits.
+
+ index := 1.
+ borrow := 0.
+
+ done := false.
+ [done] whileFalse:[
+ diff := borrow.
+ (index <= len1) ifTrue:[
+ diff := diff + (digitArray basicAt:index).
+ (index <= len2) ifTrue:[
+ diff := diff - (otherDigits basicAt:index)
+ ]
+ ] ifFalse:[
+ (index <= len2) ifTrue:[
+ diff := diff - (otherDigits basicAt:index)
+ ] ifFalse:[
+ "end reached"
+ done := true
+ ]
+ ].
+ (diff < 0) ifTrue:[
+ borrow := -1.
+ diff := diff + 10000
+ ] ifFalse:[
+ borrow := 0
+ ].
+ resultDigits basicAt:index put:diff.
+ index := index + 1
+ ].
+ (borrow ~~ 0) ifTrue:[
+ result sign: -1.
+ carry := 0.
+ 1 to:(index - 1) do:[:i |
+ sum := ((resultDigits at:i) + carry - 10000) negated.
+ resultDigits at:i put:sum.
+ carry := 1
+ ]
+ ].
+ ^ result normalize
+!
+
+absMul:aLargeInteger
+ "return a LargeInteger representing abs(self) * abs(theArgument)"
+
+ |result otherDigits resultDigits
+ len1 "{ Class: SmallInteger }"
+ len2 "{ Class: SmallInteger }"
+ dstIndex "{ Class: SmallInteger }"
+ carry "{ Class: SmallInteger }"
+ prod "{ Class: SmallInteger }" |
+
+ len1 := digitArray size.
+ otherDigits := aLargeInteger digits.
+ len2 := otherDigits size.
+
+ result := LargeInteger basicNew numberOfDigits:(len1 + len2 + 1).
+ result sign:1.
+ resultDigits := result digits.
+
+ "clear result"
+ resultDigits atAllPut:0.
+
+ 1 to:len1 do:[:index1 |
+ 1 to:len2 do:[:index2 |
+ dstIndex := index1 + index2 - 1.
+ prod := (digitArray basicAt:index1) * (otherDigits basicAt:index2).
+ prod := prod + (resultDigits basicAt:dstIndex).
+ resultDigits basicAt:dstIndex put:(prod \\ 10000).
+ carry := prod // 10000.
+ (carry ~~ 0) ifTrue:[
+ resultDigits basicAt:(dstIndex + 1)
+ put:(resultDigits basicAt:(dstIndex + 1)) + carry
+ ]
+ ]
+ ].
+ ^ result normalize
+!
+
+absDiv:anInteger
+ "return an array with two LargeIntegers representing
+ abs(self) // abs(theArgument) and abs(self) \\ abs(theArgument)"
+
+ |tmp1 tmp2
+ rem
+ count "{ Class: SmallInteger }"
+ digit "{ Class: SmallInteger }" |
+
+ self == 0 ifTrue:[^ 0].
+ anInteger == 0 ifTrue:[^ self divideByZeroError].
+
+ self < anInteger ifTrue:[
+ ^ Array with:0 with:self
+ ].
+
+ tmp1 := self deepCopy.
+ tmp2 := anInteger deepCopy.
+ count := 0.
+ [tmp2 < tmp1] whileTrue:[
+ tmp2 mul10.
+ count := count + 1
+ ].
+
+ tmp2 div10.
+
+ rem := 0 asLargeInteger.
+ [count == 0] whileFalse:[
+ digit := 0.
+ [tmp1 >= tmp2] whileTrue:[
+ digit := digit + 1.
+ tmp1 := tmp1 - tmp2
+ ].
+ rem := rem * 10 + digit.
+ tmp2 div10.
+ count := count - 1
+ ].
+ ^ Array with:rem with:tmp1
+!
+
+mul10
+ "destructively multiply the receiver by 10.
+ private - used for division only"
+
+ |carry "{ Class: SmallInteger }"
+ prod "{ Class: SmallInteger }"|
+
+ carry := 0.
+ 1 to:(digitArray size) do:[:index |
+ prod := (digitArray at:index) * 10 + carry.
+ digitArray at:index put:prod \\ 10000.
+ carry := prod // 10000
+ ].
+ carry ~~ 0 ifTrue:[
+ digitArray := digitArray copyWith:carry
+ ]
+!
+
+div10
+ "destructively divide the receiver by 10.
+ private - used for division only"
+
+ |nDigits|
+
+ nDigits := digitArray size.
+ 1 to:(nDigits - 1) do:[:index |
+ digitArray at:index put:((digitArray at:index) // 10
+ + ((digitArray at:index + 1) \\ 10 * 1000))
+ ].
+ digitArray at:nDigits put:(digitArray at:nDigits) // 10
+!
+
+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 }" |
+
+ index := digitArray size.
+ [(index > 0) and:[(digitArray at:index) == 0]] whileTrue:[
+ index := index - 1
+ ].
+ (index == 1) ifTrue:[
+ ^ (digitArray at:1) * sign
+ ].
+ (index == 2) ifTrue:[
+ ^ ((digitArray at:2) * 10000 + (digitArray at:1)) * sign
+ ].
+ (index == 0) ifTrue:[
+ ^ 0
+ ].
+ (index ~~ digitArray size) ifTrue:[
+ digitArray := digitArray copyFrom:1 to:index
+ ].
+ ^ self
+!
+
+digits
+ ^ digitArray
+!
+
+numberOfDigits
+ ^ digitArray size
+!
+
+numberOfDigits:nDigits
+ digitArray := Array new:nDigits
+!
+
+sign:aNumber
+ sign := aNumber
+! !
+
+!LargeInteger methodsFor:'printing & storing'!
+
+storeString
+ "return a string representation of the receiver, which can be
+ used to reconstruct the receiver"
+
+ ^ self printString , ' asLargeInteger'
+!
+
+printString
+ |aString index fourDigits n|
+
+ index := digitArray size.
+ [(index > 1) and:[(digitArray at:index) == 0]] whileTrue:[
+ index := index - 1
+ ].
+ (sign == 0) ifTrue: [^ '0'].
+ (sign == -1) ifTrue: [
+ aString := '-'
+ ] ifFalse: [
+ aString := ''
+ ].
+
+ aString := aString , (digitArray basicAt:index) printString.
+ index := index - 1.
+ [index > 0] whileTrue:[
+ fourDigits := (digitArray basicAt:index) printString.
+ n := fourDigits size.
+ (n < 4) ifTrue:[
+ aString := aString , ('000' copyFrom:n to:3)
+ ].
+ aString := aString , fourDigits.
+ index := index - 1
+ ].
+ ^ aString
+! !