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!
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 commits@source.squeak.org 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 largerthan 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 largerthan 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 thispoint self \ 6 is either 1 or 5."
limit := self sqrtFloor. "On 64-bit platforms this could bewritten 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 commits@source.squeak.org 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!
Nice :)
Cheers, Karl
On Thu, Oct 25, 2018 at 6:34 PM Levente Uzonyi leves@caesar.elte.hu wrote:
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 commits@source.squeak.org 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: (incategory '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. SeeisProbablyPrime for a probabilistic
implementation that is much faster for large integers, andthat is correct to an extremely
high statistical level of confidence (effectivelydeterministic)."
+ | 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 numberslarger 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 numberslarger 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 atthis point self \ 6 is either 1 or 5."
+ limit := self sqrtFloor. "On 64-bit platforms this couldbe 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 valuewill 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!
squeak-dev@lists.squeakfoundation.org
-
commits＠source.squeak.org -
karl ramberg -
Levente Uzonyi