'From Squeak3.10beta of 22 July 2007 [latest update: #7159] on 15 February 2008 at 10:49:59 pm'!
"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)]! !
!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: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! !
!SmallInteger methodsFor: 'printing' stamp: 'nice 2/15/2008 21:40'!
printStringBase: b
"Return a String representation of this number in base b."
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: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)! !
!LargePositiveInteger methodsFor: 'printing' stamp: 'nice 2/15/2008 21:46'!
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"
| halfPower half head tail |
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 2/15/2008 21:46'!
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."
| halfPower half head tail |
halfPower := ((b = 10
ifTrue: [((self highBit - 1) * 3 quo: 10) + 1 "because 1024 is almost a kilo"]
ifFalse: [self highBit quo: b highBit]) -1) asSmallerPowerOfTwo.
half := b raisedToInteger: halfPower.
head := self quo: half.
tail := self - (head * half).
head printOn: aStream base: b.
tail printOn: aStream base: b nDigits: halfPower! !
!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! !
!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! !
!Integer methodsFor: 'printing-numerative' stamp: 'nice 2/15/2008 21:53'!
printStringBase: base
"For Integer, prefer the stream version to the string version for efficiency"
^String streamContents: [:str | self printOn: str base: base]! !