[Pkg] The Trunk: Kernel-ul.939.mcz
commits at source.squeak.org
commits at source.squeak.org
Wed Aug 12 21:25:42 UTC 2015
Levente Uzonyi uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-ul.939.mcz
==================== Summary ====================
Name: Kernel-ul.939
Author: ul
Time: 12 August 2015, 10:38:42.576 pm
UUID: 6595484c-9c41-45fe-82f3-c689f7ddffa8
Ancestors: Kernel-eem.938
- Magnitude's spaceship operator uses quick returns.
- Number >> #raisedTo: uses #negative and #isZero, which is faster for LargeIntegers than pure comparison with SmallIntegers.
- faster #primesUpTo:do:, and #largePrimesUpTo:do:
=============== Diff against Kernel-eem.938 ===============
Item was changed:
----- Method: Integer class>>largePrimesUpTo:do: (in category 'prime numbers') -----
largePrimesUpTo: max do: aBlock
"Evaluate aBlock with all primes up to maxValue.
The Algorithm is adapted from http://www.rsok.com/~jrm/printprimes.html
It encodes prime numbers much more compactly than #primesUpTo:
38.5 integer per byte (2310 numbers per 60 byte) allow for some fun large primes.
(all primes up to SmallInteger maxVal can be computed within ~27MB of memory;
+ the regular #primesUpTo: would require one *GIGA*byte).
- the regular #primesUpTo: would require 4 *GIGA*bytes).
Note: The algorithm could be re-written to produce the first primes (which require
the longest time to sieve) faster but only at the cost of clarity."
+ | n limit flags maskBitIndex bitIndex maskBit byteIndex index primesUpTo2310 indexLimit increments incrementIndex |
- | limit flags maskBitIndex bitIndex maskBit byteIndex index primesUpTo2310 indexLimit |
limit := max asInteger - 1.
indexLimit := max asInteger sqrtFloor + 1.
"Create the array of flags."
flags := ByteArray new: (limit + 2309) // 2310 * 60 + 60.
flags atAllPut: 16rFF. "set all to true"
"Compute the primes up to 2310"
primesUpTo2310 := self primesUpTo: 2310.
"Create a mapping from 2310 integers to 480 bits (60 byte)"
maskBitIndex := Array new: 2310.
bitIndex := -1. "for pre-increment"
maskBitIndex at: 1 put: (bitIndex := bitIndex + 1).
maskBitIndex at: 2 put: (bitIndex := bitIndex + 1).
+ index := 1.
+ [ index <= 5 ] whileTrue: [
+ aBlock value: (primesUpTo2310 at: index).
+ index := index + 1 ].
+
+ n := 2.
+ [ n <= 2309 ] whileTrue: [
- 1 to: 5 do:[:i| aBlock value: (primesUpTo2310 at: i)].
-
- index := 6.
- 2 to: 2309 do:[:n|
[(primesUpTo2310 at: index) < n]
whileTrue:[index := index + 1].
n = (primesUpTo2310 at: index) ifTrue:[
maskBitIndex at: n+1 put: (bitIndex := bitIndex + 1).
] ifFalse:[
"if modulo any of the prime factors of 2310, then could not be prime"
(n \\ 2 = 0 or:[n \\ 3 = 0 or:[n \\ 5 = 0 or:[n \\ 7 = 0 or:[n \\ 11 = 0]]]])
ifTrue:[maskBitIndex at: n+1 put: 0]
ifFalse:[maskBitIndex at: n+1 put: (bitIndex := bitIndex + 1)].
].
+ n := n + 1 ].
- ].
"Now the real work begins...
Start with 13 since multiples of 2,3,5,7,11 are handled by the storage method;
+ increment by iterating through increments, which enables us to only check about 20.77% of all numbers."
+ n := 13.
+ increments := #[4 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4 2 4 14 4 6 2 10 2 6 6 4 2 4 6 2 10 2 4 2 12 10 2 4 2 4 6 2 6 4 6 6 6 2 6 4 2 6 4 6 8 4 2 4 6 8 6 10 2 4 6 2 6 6 4 2 4 6 2 6 4 2 6 10 2 10 2 4 2 4 6 8 4 2 4 12 2 6 4 2 6 4 6 12 2 4 2 4 8 6 4 6 2 4 6 2 6 10 2 4 6 2 6 4 2 4 2 10 2 10 2 4 6 6 2 6 6 4 6 6 2 6 4 2 6 4 6 8 4 2 6 4 8 6 4 6 2 4 6 8 6 4 2 10 2 6 4 2 4 2 10 2 10 2 4 2 4 8 6 4 2 4 6 6 2 6 4 8 4 6 8 4 2 4 2 4 8 6 4 6 6 6 2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10 2 6 4 6 2 6 4 2 4 6 6 8 4 2 6 10 8 4 2 4 2 4 8 10 6 2 4 8 6 6 4 2 4 6 2 6 4 6 2 10 2 10 2 4 2 4 6 2 6 4 2 4 6 6 2 6 6 6 4 6 8 4 2 4 2 4 8 6 4 8 4 6 2 6 6 4 2 4 6 8 4 2 4 2 10 2 10 2 4 2 4 6 2 10 2 4 6 8 6 4 2 6 4 6 8 4 6 2 4 8 6 4 6 2 4 6 2 6 6 4 6 6 2 6 6 4 2 10 2 10 2 4 2 4 6 2 6 4 2 10 6 2 6 4 2 6 4 6 8 4 2 4 2 12 6 4 6 2 4 6 2 12 4 2 4 8 6 4 2 4 2 10 2 10 6 2 4 6 2 6 4 2 4 6 6 2 6 4 2 10 6 8 6 4 2 4 8 6 4 6 2 4 6 2 6 6 6 4 6 2 6 4 2 4 2 10 12 2 4 2 10 2 6 4 2 4 6 6 2 10 2 6 4 14 4 2 4 2 4 8 6 4 6 2 4 6 2 6 6 4 2 4 6 2 6 4 2 4 12 2 12].
+ incrementIndex := 1.
+ [ n <= limit ] whileTrue: [
- increment by 2 for odd numbers only."
- 13 to: limit by: 2 do:[:n|
(maskBit := maskBitIndex at: (n \\ 2310 + 1)) = 0 ifFalse:["not a multiple of 2,3,5,7,11"
byteIndex := n // 2310 * 60 + (maskBit-1 bitShift: -3) + 1.
bitIndex := 1 bitShift: (maskBit bitAnd: 7).
((flags at: byteIndex) bitAnd: bitIndex) = 0 ifFalse:["not marked -- n is prime"
aBlock value: n.
"Start with n*n since any integer < n has already been sieved
(e.g., any multiple of n with a number k < n has been cleared
+ when k was sieved); add 2 * n to avoid even numbers and
- when k was sieved); add 2 * i to avoid even numbers and
mark all multiples of this prime. Note: n < indexLimit below
limits running into LargeInts -- nothing more."
n < indexLimit ifTrue:[
index := n * n.
[index <= limit] whileTrue:[
(maskBit := maskBitIndex at: (index \\ 2310 + 1)) = 0 ifFalse:[
byteIndex := (index // 2310 * 60) + (maskBit-1 bitShift: -3) + 1.
maskBit := 255 - (1 bitShift: (maskBit bitAnd: 7)).
flags at: byteIndex put: ((flags at: byteIndex) bitAnd: maskBit).
].
+ index := index + n + n ].
- index := index + (2 * n)].
].
].
].
+ n := n + (increments at: incrementIndex).
+ incrementIndex := incrementIndex + 1.
+ incrementIndex > increments size ifTrue: [ incrementIndex := 1 ] ]!
- ].
- !
Item was changed:
----- Method: Integer class>>primesUpTo:do: (in category 'prime numbers') -----
primesUpTo: max do: aBlock
"Compute aBlock with all prime integers up to the given integer."
"Integer primesUpTo: 100"
+ | index sieve increment limit limitSqrtFloor |
- | index limit limitSqrtFloor sieve increment |
limit := max asInteger.
- limit <= 1 ifTrue: [ ^self ].
"Fall back into #largePrimesUpTo:do: if we'd require more than 100k of memory;
+ the alternative will only requre 2/77th of the amount we need here and is almost as fast."
+ limit <= 100000 ifFalse: [ ^self largePrimesUpTo: limit do: aBlock ].
- the alternative will only requre 1/154th of the amount we need here and is almost as fast."
- limit > 25000 ifTrue:[ ^self largePrimesUpTo: limit do: aBlock ].
limit := limit - 1. "upTo:"
+ limit <= 1 ifTrue: [ ^self ].
+ aBlock value: 2.
+ limit <= 2 ifTrue: [ ^self ].
+ aBlock value: 3.
+ sieve := ByteArray new: limit withAll: 1. "1 = prime, 0 = not prime"
+ sieve at: 1 put: 0.
+ "Filter multiples of 2."
+ index := 4.
+ [ index <= limit ] whileTrue: [
+ sieve at: index put: 0.
+ index := index + 2 ].
+ "Filter multiples of 3."
+ index := 9.
+ [ index <= limit ] whileTrue: [
+ sieve at: index put: 0.
+ index := index + 3 ].
+ "Filter the rest of the primes."
- sieve := Array new: limit withAll: true.
- sieve at: 1 put: false.
- index := 2.
limitSqrtFloor := limit sqrtFloor.
+ index := 5.
+ increment := 2.
- increment := 1.
[ index <= limitSqrtFloor ] whileTrue: [
+ (sieve at: index) = 1 ifTrue: [
+ | originalIndex originalIncrement |
- (sieve at: index) ifTrue: [
- | notPrimeIndex notPrimeIncrement |
aBlock value: index.
+ originalIndex := index.
+ originalIncrement := increment.
+ increment := index + index.
+ index := index * index.
+ [ index <= limit ] whileTrue: [
+ sieve at: index put: 0.
+ index := index + increment ].
+ index := originalIndex.
+ increment := originalIncrement ].
- notPrimeIndex := index * index.
- notPrimeIncrement := increment * index.
- [ notPrimeIndex <= limit ] whileTrue: [
- sieve at: notPrimeIndex put: false.
- notPrimeIndex := notPrimeIndex + notPrimeIncrement ] ].
index := index + increment.
+ increment := 6 - increment ].
+ "No more new primes here."
- increment := 2].
[ index <= limit ] whileTrue: [
+ (sieve at: index) = 1 ifTrue: [
- (sieve at: index) ifTrue: [
aBlock value: index ].
index := index + increment.
+ increment := 6 - increment ]!
- increment := 2]!
Item was changed:
----- Method: Magnitude>><=> (in category 'sorting') -----
<=> anotherObject
"Return a collation order of -1, 0, or 1, indicating whether I should be collated before the receiver, am equal, or after.
See also: http://en.wikipedia.org/wiki/Spaceship_operator"
+ self = anotherObject ifTrue: [ ^0 ].
+ self < anotherObject ifTrue: [ ^-1 ].
+ ^1!
- ^self = anotherObject
- ifTrue: [0]
- ifFalse: [self < anotherObject ifTrue: [-1] ifFalse: [1]]!
Item was changed:
----- Method: Number>>raisedTo: (in category 'mathematical functions') -----
raisedTo: aNumber
"Answer the receiver raised to aNumber."
aNumber isInteger ifTrue: [
"Do the special case of integer power"
^ self raisedToInteger: aNumber].
aNumber isFraction ifTrue: [
"Special case for fraction power"
^ (self nthRoot: aNumber denominator) raisedToInteger: aNumber numerator ].
+ self negative ifTrue: [
- self < 0 ifTrue: [
^ ArithmeticError signal: 'Negative numbers can''t be raised to float powers.' ].
+ aNumber isZero ifTrue: [^ self class one]. "Special case of exponent=0"
- 0 = aNumber ifTrue: [^ self class one]. "Special case of exponent=0"
1 = aNumber ifTrue: [^ self]. "Special case of exponent=1"
+ self isZero ifTrue: [ "Special case of self = 0"
+ aNumber negative
- 0 = self ifTrue: [ "Special case of self = 0"
- aNumber < 0
ifTrue: [^ (ZeroDivide dividend: self) signal]
ifFalse: [^ self]].
^ (aNumber * self ln) exp "Otherwise use logarithms"!
More information about the Packages
mailing list