The Trunk: Kernel-ul.1192.mcz

Levente Uzonyi uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-ul.1192.mcz

==================== Summary ====================

Name: Kernel-ul.1192
Author: ul
Time: 24 October 2018, 10:50:43.875546 pm
UUID: 72dfb776-3d77-4b84-9d69-d000e9a67ae1
Ancestors: Kernel-eem.1191

- improved Integer >> #isPrime's performance
- slightly faster Categorizer >> #numberOfCategoryOfElement:

=============== Diff against Kernel-eem.1191 ===============

Item was changed:
  ----- Method: Categorizer>>numberOfCategoryOfElement: (in category 'accessing') -----
  numberOfCategoryOfElement: element
        "Answer the index of the category with which the argument, element, is
        associated."

+       | categoryIndex elementIndex elementArraySize |
-       | categoryIndex elementIndex |
        categoryIndex := 1.
        elementIndex := 0.
+       elementArraySize := elementArray size.
+       [(elementIndex := elementIndex + 1) <= elementArraySize]
-       [(elementIndex := elementIndex + 1) <= elementArray size]
                whileTrue:
                        ["point to correct category"
                        [elementIndex > (categoryStops at: categoryIndex)]
                                whileTrue: [categoryIndex := categoryIndex + 1].
                        "see if this is element"
                        element = (elementArray at: elementIndex) ifTrue: [^categoryIndex]].
        ^0!

Item was changed:
  ----- Method: Integer>>isPrime (in category 'testing') -----
  isPrime
        "Answer true if the receiver is a prime number. See isProbablyPrime for a probabilistic
        implementation that is much faster for large integers, and that is correct to an extremely
        high statistical level of confidence (effectively deterministic)."

+       | probe step limit |
+       self <= 3 ifTrue: [ ^self >= 2 ].
+       self \\ 2 = 0 ifTrue: [ ^false ].
+       self \\ 3 = 0 ifTrue: [ ^false ].
+       self <= 1073741823 ifFalse: [ "1 << 30 - 1. For numbers larger than this (on 64-bit platforms) #isProbablyPrime is usually quicker."
-       self <= 1 ifTrue: [ ^false ].
-       self even ifTrue: [ ^self = 2].
-       self <= 1073741823 ifFalse: [ "1 << 30 - 1. For numbers larger than this, the calculation takes longer than #isProbablyPrime when the receiver is a prime. The absolue turning point is about at 1 << 35 - 1."
                ^self isProbablyPrime ].
+       probe := 5.
+       step := 2. "Step will oscillate between 2 and 4 because at this point self \\ 6 is either 1 or 5."
+       limit := self sqrtFloor. "On 64-bit platforms this could be written as self asFloat sqrt truncated (+ 1), which is faster because it creates no intermediate objects. Knowing that self has at most 30 bits because of the check above, this value will never be larger than 32767."
+       [ probe <= limit ] whileTrue: [
+               self \\ probe = 0 ifTrue: [ ^false ].
+               probe := probe + step.
+               step := 6 - step ].
-       3 to: self sqrtFloor by: 2 do: [ :each |
-               self \\ each = 0 ifTrue: [ ^false ] ].
        ^true!

Item was added:
+ ----- Method: LargeNegativeInteger>>isPrime (in category 'testing') -----
+ isPrime
+
+       ^false!

Hi Karl,

The ultimate tool for such use case is Integer >> #primesUpTo:(do:).
The code below is 3 times faster on my machine:

form := Form extent:8000@8000.
pen := Pen newOnForm: form.
pen up.
pen goto: 100@6000.
pen down.
pen turn: 90.
pen color: Color black.
previousPrime := nil.
Integer primesUpTo: 5000000 do: [ :prime |
        previousPrime ifNotNil: [
                pen
                        go: prime - previousPrime;
                        turn: 90 ].
        previousPrime := prime ].
form writePNGfileNamed: 'Sketch.png'

Levente

On Thu, 25 Oct 2018, karl ramberg wrote:

> Cool. I was just playing with some random crackpot ideas yesterday which involved primes.
> This fix made a nice speed up :-)
>
>    diff := OrderedCollection new.
>    singular := 2.
>    3 to: 5000000 do:[: i | i isPrime ifTrue:[ diff add: i - singular.
> singular := i]].
>   form := Form extent:8000@8000.
>   pen := Pen newOnForm: form.
>   pen up.
>   pen goto: 100@6000.
>   pen down.
>   pen turn: 90.
>   pen color: Color black.
>   diff do:[:i | pen go: i. pen turn: 90].
>   form writePNGfileNamed:  'Sketch.png'
>
> Cheers,
> Karl
>
> On Wed, Oct 24, 2018 at 11:09 PM <[hidden email]> wrote:
>       Levente Uzonyi uploaded a new version of Kernel to project The Trunk:
>       http://source.squeak.org/trunk/Kernel-ul.1192.mcz
>
>       ==================== Summary ====================
>
>       Name: Kernel-ul.1192
>       Author: ul
>       Time: 24 October 2018, 10:50:43.875546 pm
>       UUID: 72dfb776-3d77-4b84-9d69-d000e9a67ae1
>       Ancestors: Kernel-eem.1191
>
>       - improved Integer >> #isPrime's performance
>       - slightly faster Categorizer >> #numberOfCategoryOfElement:
>
>       =============== Diff against Kernel-eem.1191 ===============
>
>       Item was changed:
>         ----- Method: Categorizer>>numberOfCategoryOfElement: (in category 'accessing') -----
>         numberOfCategoryOfElement: element
>               "Answer the index of the category with which the argument, element, is
>               associated."
>
>       +       | categoryIndex elementIndex elementArraySize |
>       -       | categoryIndex elementIndex |
>               categoryIndex := 1.
>               elementIndex := 0.
>       +       elementArraySize := elementArray size.
>       +       [(elementIndex := elementIndex + 1) <= elementArraySize]
>       -       [(elementIndex := elementIndex + 1) <= elementArray size]
>                       whileTrue:
>                               ["point to correct category"
>                               [elementIndex > (categoryStops at: categoryIndex)]
>                                       whileTrue: [categoryIndex := categoryIndex + 1].
>                               "see if this is element"
>                               element = (elementArray at: elementIndex) ifTrue: [^categoryIndex]].
>               ^0!
>
>       Item was changed:
>         ----- Method: Integer>>isPrime (in category 'testing') -----
>         isPrime
>               "Answer true if the receiver is a prime number. See isProbablyPrime for a probabilistic
>               implementation that is much faster for large integers, and that is correct to an extremely
>               high statistical level of confidence (effectively deterministic)."
>
>       +       | probe step limit |
>       +       self <= 3 ifTrue: [ ^self >= 2 ].
>       +       self \\ 2 = 0 ifTrue: [ ^false ].
>       +       self \\ 3 = 0 ifTrue: [ ^false ].
>       +       self <= 1073741823 ifFalse: [ "1 << 30 - 1. For numbers larger than this (on 64-bit platforms) #isProbablyPrime is usually quicker."
>       -       self <= 1 ifTrue: [ ^false ].
>       -       self even ifTrue: [ ^self = 2].
>       -       self <= 1073741823 ifFalse: [ "1 << 30 - 1. For numbers larger than this, the calculation takes longer than #isProbablyPrime when the receiver is a prime. The absolue turning point
>       is about at 1 << 35 - 1."
>                       ^self isProbablyPrime ].
>       +       probe := 5.
>       +       step := 2. "Step will oscillate between 2 and 4 because at this point self \\ 6 is either 1 or 5."
>       +       limit := self sqrtFloor. "On 64-bit platforms this could be written as self asFloat sqrt truncated (+ 1), which is faster because it creates no intermediate objects. Knowing that
>       self has at most 30 bits because of the check above, this value will never be larger than 32767."
>       +       [ probe <= limit ] whileTrue: [
>       +               self \\ probe = 0 ifTrue: [ ^false ].
>       +               probe := probe + step.
>       +               step := 6 - step ].
>       -       3 to: self sqrtFloor by: 2 do: [ :each |
>       -               self \\ each = 0 ifTrue: [ ^false ] ].
>               ^true!
>
>       Item was added:
>       + ----- Method: LargeNegativeInteger>>isPrime (in category 'testing') -----
>       + isPrime
>       +
>       +       ^false!
>
>
>
>