'From Squeak3.10beta of 22 July 2007 [latest update: #7159] on 6 July 2008 at 12:49:52 am'!
"Change Set: Integer-fastPrint-M6887-nice
Date: 5 February 2008
Author: nice
This patch accelerates LargeInteger printString in any base.
It also accelerates printString of SmallInteger in all base but 10, which already has a better performance.
It also provide a new method #numberOfDigitsInBase: for counting number of digits necessary to print an Integer in any base.
"!
!Integer methodsFor: 'printing' stamp: 'nice 2/15/2008 22:14'!
numberOfDigitsInBase: b
"Return how many digits are necessary to print this number in base b.
This does not count any place for minus sign, radix prefix or whatever.
Note that this algorithm may cost a few operations on LargeInteger."
| nDigits q |
self negative ifTrue: [^self negated numberOfDigitsInBase: b].
self < b ifTrue: [^1].
b isPowerOfTwo ifTrue: [^self highBit + b highBit - 2 quo: b highBit - 1].
"A conversion from base 2 to base b has to be performed.
This algorithm avoids Float computations like (self log: b) floor + 1,
1) because they are inexact
2) because LargeInteger might overflow
3) because this algorithm might be cheaper than conversion"
"Make an initial nDigits guess that is lower than or equal to required number of digits"
b = 10
ifTrue: [nDigits := ((self highBit - 1) * 3 quo: 10) + 1. "This is because 1024 is a little more than a kilo"]
ifFalse: [nDigits := self highBit quo: b highBit].
"See how many digits remains above these first nDigits guess"
q := self quo: (b raisedTo: nDigits).
^q = 0
ifTrue: [nDigits]
ifFalse: [nDigits + (q numberOfDigitsInBase: b)]! !
!Integer methodsFor: 'printing' stamp: 'nice 2/15/2008 21:49'!
printOn: aStream
^self printOn: aStream base: 10! !
!Integer methodsFor: 'printing' stamp: 'nice 2/15/2008 21:49'!
printString
"For Integer, prefer the stream version to the string version for efficiency"
^String streamContents: [:str | self printOn: str base: 10]! !
!Integer methodsFor: 'printing-numerative' stamp: 'nice 2/15/2008 21:52'!
printOn: aStream base: base
^self subclassResponsibility! !
!Integer methodsFor: 'printing-numerative' stamp: 'nice 2/15/2008 21:44'!
printOn: aStream base: b nDigits: n
"Append a representation of this number in base b on aStream using nDigits.
self must be positive."
self subclassResponsibility! !
!LargePositiveInteger methodsFor: 'printing' stamp: 'nice 7/6/2008 00:06'!
printOn: aStream base: b
"Append a representation of this number in base b on aStream.
In order to reduce cost of LargePositiveInteger ops, split the number in approximately two equal parts in number of digits."
| halfDigits halfPower head tail nDigitsUnderestimate |
nDigitsUnderestimate := b = 10
ifTrue: [((self highBit - 1) * 3 quo: 10) + 1 "because 1024 is almost a kilo"]
ifFalse: [self highBit quo: b highBit].
"splitting digits with a whole power of two is more efficient"
halfDigits := 1 bitShift: nDigitsUnderestimate highBit - 2.
halfDigits <= 1
ifTrue: ["Hmmm, this could happen only in case of a huge base b... Let lower level fail"
^self printOn: aStream base: b nDigits: (self numberOfDigitsInBase: b)].
"Separate in two halves, head and tail"
halfPower := b raisedToInteger: halfDigits.
head := self quo: halfPower.
tail := self - (head * halfPower).
"print head"
head printOn: aStream base: b.
"print tail without the overhead to count the digits"
tail printOn: aStream base: b nDigits: halfDigits! !
!LargePositiveInteger methodsFor: 'printing' stamp: 'nice 7/5/2008 23:23'!
printOn: aStream base: b nDigits: n
"Append a representation of this number in base b on aStream using n digits.
In order to reduce cost of LargePositiveInteger ops, split the number of digts approximatily in two
Should be invoked with: 0 <= self < (b raisedToInteger: n)"
| halfPower half head tail |
n <= 1 ifTrue: [
n <= 0 ifTrue: [self error: 'Number of digits n should be > 0'].
"Note: this is to stop an infinite loop if one ever attempts to print with a huge base
This can happen because choice was to not hardcode any limit for base b
We let Character>>#digitValue: fail"
^Character digitValue: self].
halfPower := n bitShift: -1.
half := b raisedToInteger: halfPower.
head := self quo: half.
tail := self - (head * half).
head printOn: aStream base: b nDigits: n - halfPower.
tail printOn: aStream base: b nDigits: halfPower! !
!LargePositiveInteger methodsFor: 'printing' stamp: 'nice 7/6/2008 00:34'!
printStringBase: base
"For LargeIntegers, it's faster to use the stream version.
This reproduces Number implementation to avoid speed down if one defines Integer>>#printStringBase:
This method should be removed if Integer>>#printStringBase: is removed.
Note: tests preallocating stream space with exact numberOfDigitsInBase: did not gain speed"
^String streamContents: [:str | self printOn: str base: base]! !
!LargeNegativeInteger methodsFor: 'printing' stamp: 'nice 2/15/2008 21:47'!
printOn: aStream base: b
"Append a representation of this number in base b on aStream."
aStream nextPut: $-.
self abs printOn: aStream base: b! !
!SmallInteger methodsFor: 'printing' stamp: 'nice 2/15/2008 22:22'!
numberOfDigitsInBase: b
"Return how many digits are necessary to print this number in base b.
Mostly same as super but an optimized version for base 10 case"
b = 10 ifFalse: [^super numberOfDigitsInBase: b].
self < 0 ifTrue: [^self negated numberOfDigitsInBase: b].
^self decimalDigitLength! !
!SmallInteger methodsFor: 'printing' stamp: 'nice 2/15/2008 21:43'!
printOn: aStream base: b
"Append a representation of this number in base b on aStream."
self < 0
ifTrue: [aStream nextPut: $-.
aStream nextPutAll: (self negated printStringBase: b).
^self].
"allocating a String seems faster than streaming for SmallInteger"
aStream nextPutAll: (self printStringBase: b)! !
!SmallInteger methodsFor: 'printing' stamp: 'nice 2/15/2008 21:42'!
printOn: aStream base: b nDigits: n
"Append a representation of this number in base b on aStream using nDigits.
self must be positive."
"allocating a String seems faster than streaming for SmallInteger"
aStream nextPutAll: (self printStringBase: b nDigits: n)! !
!SmallInteger methodsFor: 'printing' stamp: 'nice 7/6/2008 00:48'!
printStringBase: b
"Return a String representation of this number in base b.
For SmallIntegers, it is more efficient to print directly in a String,
rather than using a Stream like super."
self < 0
ifTrue: [^ '-'
, (self negated printStringBase: b)].
self < b
ifTrue: [^ String
with: (Character digitValue: self)].
^ self printStringBase: b nDigits: (self numberOfDigitsInBase: b)! !
!SmallInteger methodsFor: 'printing' stamp: 'nice 2/15/2008 21:39'!
printStringBase: b nDigits: n
"Return a string representation of this number in base b with n digits (left padded with 0).
Should be invoked with: 0 <= self < (b raisedToInteger: n)."
| integer next result |
result := String new: n.
integer := self.
n to: 1 by: -1 do: [:i |
next := integer // b.
result byteAt: i put: (Character digitValue: (integer - (next * b))).
integer := next].
^result! !
Integer removeSelector: #printStringBase:!