The Trunk: Kernel-ul.939.mcz

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"!