Squeak-dev May 2019

squeak-dev@lists.squeakfoundation.org

36 participants
153 discussions

The Trunk: KernelTests-nice.364.mcz
by commits＠source.squeak.org 13 May '19

13 May '19

Nicolas Cellier uploaded a new version of KernelTests to project The Trunk: http://source.squeak.org/trunk/KernelTests-nice.364.mcz ==================== Summary ==================== Name: KernelTests-nice.364 Author: nice Time: 13 May 2019, 5:47:01.649569 pm UUID: 48139b72-ab12-d140-af26-7bce15bae277 Ancestors: KernelTests-nice.363 Integer sqrt is now correctly rounded - this is a new feature. That's the case by construction for SmallInteger which rely on Float sqrt but less obvious for LargePositiveInteger, so let's test it =============== Diff against KernelTests-nice.363 =============== Item was added: + ----- Method: LargeNegativeIntegerTest>>testSqrt (in category 'tests - mathematical functions') ----- + testSqrt + self should: [(SmallInteger minVal - 1) sqrt] raise: DomainError! Item was added: + ----- Method: LargePositiveIntegerTest>>assertSqrtCorrectlyRoundedForExponent: (in category 'asserting') ----- + assertSqrtCorrectlyRoundedForExponent: exp + "Requires exp > Float precision, so that f ulp/2 is integer" + {1.5. 1.25 squared. 2.0 predecessor} do: [:sf | + | f xe xp xm | + + f := sf timesTwoPower: exp. + + "make two integers around the pivot" + xe := f asInteger + (f ulp asInteger / 2). + xm := xe squared - 1. + xp := xe squared + 1. + self assert: xe squared sqrt equals: xe. + self assert: xe squared sqrt isInteger. + + "check rounding when result is near f squared" + self assert: xm sqrt equals: f. + self assert: xm sqrt isFloat. + self assert: xp sqrt equals: f successor. + self assert: xp sqrt isFloat. + + "same in the other direction" + xe := f asInteger - (f ulp asInteger / 2). + xm := xe squared - 1. + xp := xe squared + 1. + self assert: xe squared sqrt equals: xe. + self assert: xe squared sqrt isInteger. + + "check rounding when result is near f squared" + self assert: xm sqrt equals: f predecessor. + self assert: xm sqrt isFloat. + self assert: xp sqrt equals: f. + self assert: xp sqrt isFloat].! Item was added: + ----- Method: LargePositiveIntegerTest>>testSqrt (in category 'tests - mathematical functions') ----- + testSqrt + self assert: (SmallInteger maxVal + 1) sqrt equals: (SmallInteger maxVal + 1) asFloat sqrt.! Item was added: + ----- Method: LargePositiveIntegerTest>>testSqrtCorrectlyRounded (in category 'tests - mathematical functions') ----- + testSqrtCorrectlyRounded + self assertSqrtCorrectlyRoundedForExponent: Float precision * 2 - 1. + self assertSqrtCorrectlyRoundedForExponent: Float precision * 2 + 1. + self assertSqrtCorrectlyRoundedForExponent: Float precision * 2 + 3. + self assertSqrtCorrectlyRoundedForExponent: Float precision * 3 // 2. + self assertSqrtCorrectlyRoundedForExponent: Float emax* 2 // 3. "such that asFloat would overflow" + self assertSqrtCorrectlyRoundedForExponent: Float emax.!

1 0

The Trunk: Kernel-nice.1232.mcz
by commits＠source.squeak.org 13 May '19

13 May '19

Nicolas Cellier uploaded a new version of Kernel to project The Trunk: http://source.squeak.org/trunk/Kernel-nice.1232.mcz ==================== Summary ==================== Name: Kernel-nice.1232 Author: nice Time: 13 May 2019, 5:43:37.253569 pm UUID: 880030b9-91d0-244b-9198-b7b6f9454584 Ancestors: Kernel-nice.1231 Make sure that LargePositiveInteger sqrt are always correctly rounded to nearest Float if inexact. Note that I accidentally introduced a rounding bug in LargePositiveInteger sqrt which was not in original Integer>>#sqrt: (self bitAnd: 1) should have been (integerResult bitAnd: 1). Apologizes. But this formulation was subject to double-rounding error anyway (asFloat did perform a second rounding, which may lead to incorrect rounding), so that did not really matter... Concerning performance, here are the bench results, after correcting the original version (I send twice self asFloat, which was a slip, and the original did not test mightBeASquare either when self asFloat = Float infinity) - When (self mighBeASquare), new code is equivalent, and becomes more performant for huge values This is due to sqrtRem which avoids evaluating a #squared for no additional price Note that 7 large ints out of 256 mightBeASquare - else it depends on bit range, new code is : * as performant in range (SmallInteger maxVal highBit + 1 to: Float precision * 2) that's the case of vast majority of large int in a "normal" image * less performant in range (Float precision * 2 + 1 to: Float emax) by 3x to 5x that's because asFloat sqrt is cheaper than sqrtRem * more performant in range (Float emax + 1 to: infinity) by large this is due to evaluating sqrtFloor on a much smaller LargePositiveInteger (but this trick could have been added in inexact-rounding variant too) So the exact rounding: - does not require additional code (both are equivalent) - does not cost any performance penalty in most common cases (small LargePositiveInteger); the penalty is only in medium range (107 to 1023 bits). In a word, it's worth. =============== Diff against Kernel-nice.1231 =============== Item was changed: ----- Method: LargePositiveInteger>>sqrt (in category 'mathematical functions') ----- sqrt "Answer the square root of the receiver. If the square root is exact, answer an Integer, else answer a Float approximation. + Make sure the result is correctly rounded (i.e. the nearest Float to the exact square root)" - Handle some tricky case of Float overflow or inaccuracy" + | floatResult integerResult guardBit highBit sr | + (highBit := self highBit) < (Float precision * 2) - | selfAsFloat floatResult integerResult | - selfAsFloat := self asFloat. - floatResult := self asFloat sqrt. - floatResult isFinite ifTrue: + ["the sqrt of self asFloat is correctly rounded, so use it" + floatResult := self asFloat sqrt. + self mightBeASquare ifFalse: [^floatResult]. - [self mightBeASquare ifFalse: ["we know for sure no exact solution exists, - just answer the cheap float approximation without wasting time." - ^floatResult]. "Answer integerResult in case of perfect square" integerResult := floatResult truncated. + integerResult squared = self ifTrue: [^integerResult]. + ^floatResult]. - integerResult squared = self ifTrue: [^integerResult]]. - - "In this case, maybe it failed because we are such a big integer that the Float method becomes - inexact, even if we are a whole square number. So, try the slower but more general method" - selfAsFloat >= Float maxExactInteger asFloat squared - ifTrue: [ - integerResult := self sqrtFloor. - integerResult squared = self ifTrue: [ - ^integerResult ]. - - "Nothing else can be done. No exact answer means answer must be a Float. - Answer the best we have which is the rounded sqrt." - integerResult := (self bitShift: 2) sqrtFloor. - ^((integerResult bitShift: -1) + (self bitAnd: 1)) asFloat]. + "Eventually use a guard bit for handling correct rounding direction" + guardBit := highBit <= (Float precision + 1 * 2) + ifTrue: + ["Add one guard bit for rounding correctly" + 1] + ifFalse: + [self mightBeASquare + ifTrue: + ["Keep all the bits in case we are a perfect square" + 0] + ifFalse: + ["Remove superfluous bit that won't change the Float approximation" + Float precision + 1 - (highBit // 2)]]. + + "Get truncated sqrt and remainder for the same price" + sr := (self bitShift: guardBit * 2) sqrtRem. + + "Handle case of perfect square" + integerResult := sr first. + sr last isZero ifTrue: [^integerResult bitShift: guardBit negated]. + + "Answer the best we have which is the sqrt correctly rounded at Float precision." + ^((integerResult bitShift: Float precision - integerResult highBit) + + (integerResult bitAt: integerResult highBit - Float precision)) asFloat + timesTwoPower: integerResult highBit - Float precision - guardBit! - "We need an approximate result" - ^floatResult! Item was added: + ----- Method: LargePositiveInteger>>sqrt2 (in category 'mathematical functions') ----- + sqrt2 + "Answer the square root of the receiver. + If the square root is exact, answer an Integer, else answer a Float approximation. + Handle some tricky case of Float overflow or inaccuracy" + + | selfAsFloat floatResult integerResult | + selfAsFloat := self asFloat. + floatResult := selfAsFloat sqrt. + floatResult isFinite + ifTrue: + [self mightBeASquare ifFalse: ["we know for sure no exact solution exists, + just answer the cheap float approximation without wasting time." + ^floatResult]. + "Answer integerResult in case of perfect square" + integerResult := floatResult truncated. + integerResult squared = self ifTrue: [^integerResult]]. + + "In this case, maybe it failed because we are such a big integer that the Float method becomes + inexact, even if we are a whole square number. So, try the slower but more general method" + selfAsFloat >= Float maxExactInteger asFloat squared + ifTrue: [ + integerResult := self sqrtFloor. + integerResult squared = self ifTrue: [ + ^integerResult ]. + + "Nothing else can be done. No exact answer means answer must be a Float. + Answer the best we have which is the rounded sqrt." + integerResult := (self bitShift: 2) sqrtFloor. + ^((integerResult bitShift: -1) + (self bitAnd: 1)) asFloat]. + + "We need an approximate result" + ^floatResult!

1 0

The Inbox: CollectionsTests-mt.309.mcz
by commits＠source.squeak.org 13 May '19

13 May '19

A new version of CollectionsTests was added to project The Inbox: http://source.squeak.org/inbox/CollectionsTests-mt.309.mcz ==================== Summary ==================== Name: CollectionsTests-mt.309 Author: mt Time: 13 May 2019, 9:47:17.18801 am UUID: 9c8aae8c-fcea-3440-967b-50b2fa72a277 Ancestors: CollectionsTests-nice.308 Tests for Collections-mt.833. =============== Diff against CollectionsTests-nice.308 =============== Item was added: + ----- Method: CollectionTest>>testAny (in category 'tests') ----- + testAny + + self + assert: #(1 2) equals: (#(1 2 3 4) any: 2); + assert: #(1 2 3 4) equals: (#(1 2 3 4) any: 4); + should: [#(1 2 3 4) any: 5] raise: Error.! Item was added: + ----- Method: CollectionTest>>testAnyAs (in category 'tests') ----- + testAnyAs + + self + assert: ((#(1 2 3 4) any: 2 as: OrderedCollection) isKindOf: OrderedCollection); + assert: ((#(1 1 2 3 4) any: 2 as: Set) isKindOf: Set); + assert: 1 equals: (#(1 1 1 1) any: 3 as: Set) size.! Item was added: + ----- Method: CollectionTest>>testTake (in category 'tests') ----- + testTake + + self + assert: #(1 2) equals: (#(1 2 3 4) take: 2); + assert: #(1 2) equals: (#(1 2) take: 5).!

2 1

The Trunk: Kernel-nice.1230.mcz
by commits＠source.squeak.org 13 May '19

13 May '19

Nicolas Cellier uploaded a new version of Kernel to project The Trunk: http://source.squeak.org/trunk/Kernel-nice.1230.mcz ==================== Summary ==================== Name: Kernel-nice.1230 Author: nice Time: 12 May 2019, 9:52:59.138604 pm UUID: c5ccb933-92e3-4969-9bb4-05b6794c16bf Ancestors: Kernel-nice.1229 Name: Kernel-nice.1230 Author: nice Time: 12 May 2019, 2:13:29.878804 am UUID: 56e8a3d6-3899-47b1-b828-cf0525f7dec3 Ancestors: Kernel-nice.1229 Revamp sqrt 1) move falback code for missing primitive 55 or 555 in Float and invoke super if primitive fails 2) handle inf and Nan in this fallback code 3) scale to avoid dramatic loss of precision of original Newton-Raphson loop in case of gradual underflow 4) round the result correctly as mandated by IEEE-754 standard. Since Newton-Raphson converges quadratically, it's at most one more iteration than before, plus a somehow germane adjustment... Don't be spare of comments - I re-invented the wheel and this is documented nowhere else. There are many other ways to evaluate a correctly rounded sqrt, but they are all tricky. Another way would be to rely on LargePositiveInteger sqrtFloor, but it won't be possible anymore, because SmallInteger sqrtFloor will now depend onFloat sqrt, and LargePositiveInteger depends on SmallInteger sqrtFloor (by virtue of divide and conquer) - see below. 5) move sqrt, sqrtFloor and sqrtRem implementation in Integer subclasses, so that each one takes its own responsibilities which are not exactly the same... 6) Accelerate SmallInteger sqrtFloor by invoking Float sqrt (the case of absent primitives apart) Provide long explanation telling how it works in 64bits image despite inexact asFloat 7) Accelerate SmallInteger sqrt by not testing the isFinite etc... Provide long explanation why sqrt truncated works in 64bits image despite inexact asFloat Note that 6) and 7) are dead simple versus former super version, only the comment is not... 8) Accelerate LargePositiveInteger sqrtRem and sqrtFloor by removing the harcoded threshold: divide & conquer was faster than Newton-Raphson unconditionnally and asFloat truncated is not a viable option for Large 9) remove sqrtFloorNewtonRaphson now that neither Small nor Large integers use it. It's a heartbreaking change, I had super-optimized it along the years... Note: I could have kept a Newton-Raphson for large, accelerated by seeding the first guess with asFloat sqrt truncated. Up to 106 bits, the single correction of SmallInteger>>sqrtFloor might also work. 10) move the handling of Float overlow/accuracy in LargePositiveInteger sqrt where they belong. It's not about speed-up, it's about putting things at their place. 11) Speed up SmallInteger isAnExactFloat. It's not sqrt related, but I first thought using it before engaging asFloat sqrt truncated, that's the reason why you find it here Congratulations, you reached the end of this commit message! =============== Diff against Kernel-nice.1229 =============== Item was changed: ----- Method: BoxedFloat64>>sqrt (in category 'mathematical functions') ----- sqrt "Answer the square root of the receiver. Optional. See Object documentation whatIsAPrimitive." - | exp guess eps delta | <primitive: 55> + ^super sqrt! - #Numeric. - "Changed 200/01/19 For ANSI <number> support." - "Newton-Raphson" - self <= 0.0 - ifTrue: [self = 0.0 - ifTrue: [^ 0.0] - ifFalse: ["v Chg" - ^ DomainError signal: 'sqrt undefined for number less than zero.']]. - "first guess is half the exponent" - exp := self exponent // 2. - guess := self timesTwoPower: 0 - exp. - "get eps value" - eps := guess * Epsilon. - eps := eps * eps. - delta := self - (guess * guess) / (guess * 2.0). - [delta * delta > eps] - whileTrue: - [guess := guess + delta. - delta := self - (guess * guess) / (guess * 2.0)]. - ^ guess! Item was added: + ----- Method: Float>>sqrt (in category 'mathematical functions') ----- + sqrt + "Fallback code for absent primitives. + Care to answer a correctly rounded result as mandated by IEEE-754." + + | guess selfScaled nextGuess exp secator hi lo remainder maxError | + self <= 0.0 + ifTrue: [self = 0.0 + ifTrue: [^ 0.0] + ifFalse: [^ DomainError signal: 'sqrt undefined for number less than zero.']]. + self isFinite ifFalse: [^self]. + + "scale to avoid loss of precision in case of gradual underflow + (selfScaled between: 1.0 and: 2.0), so it is a good guess by itself" + exp := self exponent // 2. + guess := selfScaled := self timesTwoPower: exp * -2. + + "Use Newton-Raphson iteration - it converges quadratically + (twice many correct bits at each loop)" + [nextGuess := selfScaled - (guess * guess) / (2.0 * guess) + guess. + "test if both guess are within 1 ulp" + (nextGuess + guess) / 2.0 = guess] + whileFalse: + ["always round odd upper - this avoids infinite loop with alternate flip of last bit" + guess := nextGuess + (nextGuess ulp/2.0)]. + + "adjust the rounding - the guess can be 2 ulp up or 1 ulp down + Let u = guess ulp. + if (guess+u/2)^2<self, then guess is under-estimated + if (guess-u/2)^2>self, then guess is over-estimated + Note that they can't be equal (because left term has 55 bits). + (guess+u/2)^2=guess^2 + guess*u + u^2/4 < self + ==> self - guess^2 > guess*u + (guess-u/2)^2=guess^2 - guess*u + u^2/4 > self + ==> guess^2 - self >= guess*u + (guess^2 - self) is evaluated with an emulated fused-multiply-add" + + ["Decompose guess in two 26 bits parts hi,lo + the trick is that they do not necessarily have the same sign + If 53 bits are hi,0,lo => (hi,lo) else hi,1,lo=> (hi+1,-lo)" + secator := "1<<27+1" 134217729.0. + hi := guess * secator. + hi :=hi + (guess - hi). + lo := guess - hi. + + "The operations below are all exact" + remainder := selfScaled - hi squared - (hi * lo * 2.0) - lo squared. + maxError := guess timesTwoPower: 1 - Float precision. + remainder > maxError or: [remainder negated >= maxError]] + whileTrue: [guess :=remainder > 0.0 + ifTrue: [guess successor] + ifFalse: [guess predecessor]]. + + "undo the scaling" + ^ guess timesTwoPower: exp! Item was changed: ----- Method: Integer>>slidingLeftRightRaisedTo:modulo: (in category 'private') ----- slidingLeftRightRaisedTo: n modulo: m "Private - compute (self raisedTo: n) \\ m, Note: this method has to be fast because it is generally used with large integers in cryptography. It thus operate on exponent bits from left to right by packets with a sliding window rather than bit by bit (see below)." | pow j k w index oddPowersOfSelf square | "Precompute powers of self for odd bit patterns xxxx1 up to length w + 1. The width w is chosen with respect to the total bit length of n, such that each bit pattern will on average be encoutered P times in the whole bit sequence of n. This costs (2 raisedTo: w) multiplications, but more will be saved later (see below)." k := n highBit. w := (k highBit - 1 >> 1 min: 16) max: 1. oddPowersOfSelf := Array new: 1 << w. oddPowersOfSelf at: 1 put: (pow := self). square := self * self \\ m. 2 to: oddPowersOfSelf size do: [:i | pow := oddPowersOfSelf at: i put: pow * square \\ m]. "Now exponentiate by searching precomputed bit patterns with a sliding window" pow := 1. [k > 0] whileTrue: [pow := pow * pow \\ m. "Skip bits set to zero (the sliding window)" (n bitAt: k) = 0 ifFalse: ["Find longest odd bit pattern up to window length (w + 1)" j := k - w max: 1. [j < k and: [(n bitAt: j) = 0]] whileTrue: [j := j + 1]. "We found an odd bit pattern of length k-j+1; perform the square powers for each bit (same cost as bitwise algorithm); compute the index of this bit pattern in the precomputed powers." index := 0. [k > j] whileTrue: [pow := pow * pow \\ m. + index := index * 2 + (n bitAt: k). - index := index << 1 + (n bitAt: k). k := k - 1]. "Perform a single multiplication for the whole bit pattern. This saves up to (k-j) multiplications versus a naive algorithm operating bit by bit" pow := pow * (oddPowersOfSelf at: index + 1) \\ m]. k := k - 1]. ^pow! Item was removed: - ----- Method: Integer>>sqrt (in category 'mathematical functions') ----- - sqrt - "Answer the square root of the receiver." - - | selfAsFloat floatResult guess | - selfAsFloat := self asFloat. - floatResult := selfAsFloat sqrt. - - floatResult isInfinite ifFalse: [ - guess := floatResult truncated. - - "If got an exact answer, answer it. Otherwise answer float approximate answer." - guess squared = self - ifTrue: [ ^ guess ]]. - - "In this case, maybe it failed because we are such a big integer that the Float method becomes - inexact, even if we are a whole square number. So, try the slower but more general method" - selfAsFloat >= Float maxExactInteger asFloat squared - ifTrue: [ - guess := self sqrtFloor. - guess squared = self ifTrue: [ - ^guess ]. - - "Nothing else can be done. No exact answer means answer must be a Float. - Answer the best we have which is the rounded sqrt." - guess := (self * 4) sqrtFloor. - ^(guess // 2 + (guess \\ 2)) asFloat]. - - "We need an approximate result" - ^floatResult! Item was changed: ----- Method: Integer>>sqrtFloor (in category 'mathematical functions') ----- sqrtFloor "Return the integer part of the square root of self Assume self >= 0 + The following post-conditions apply: - The following invariants apply: 1) self sqrtFloor squared <= self 2) (self sqrtFloor + 1) squared > self" + self subclassResponsibility! - ^self sqrtFloorNewtonRaphson! Item was removed: - ----- Method: Integer>>sqrtFloorNewtonRaphson (in category 'private') ----- - sqrtFloorNewtonRaphson - "Return the integer part of the square root of self. - Use a Newton-Raphson iteration since it converges quadratically - (twice more bits of precision at each iteration)" - - | guess delta | - guess := 1 bitShift: self highBit + 1 // 2. - [ - delta := guess squared - self // (guess bitShift: 1). - delta = 0 ] whileFalse: [ - guess := guess - delta ]. - ^guess - 1! Item was changed: ----- Method: Integer>>sqrtRem (in category 'mathematical functions') ----- sqrtRem "Return an array with floor sqrt and sqrt remainder. Assume self >= 0. The following invariants apply: 1) self sqrtRem first squared <= self 2) (self sqrtRem first + 1) squared > self 3) self sqrtRem first squared + self sqrtRem last = self" + self subclassResponsibility! - | s | - s := self sqrtFloorNewtonRaphson. - ^{ s. self - s squared } ! Item was changed: ----- Method: LargePositiveInteger>>sqrt (in category 'mathematical functions') ----- sqrt + "Answer the square root of the receiver. + If the square root is exact, answer an Integer, else answer a Float approximation. + Handle some tricky case of Float overflow or inaccuracy" + + | selfAsFloat floatResult integerResult | + selfAsFloat := self asFloat. + floatResult := self asFloat sqrt. + floatResult isFinite + ifTrue: + [self mightBeASquare ifFalse: ["we know for sure no exact solution exists, + just answer the cheap float approximation without wasting time." + ^floatResult]. + "Answer integerResult in case of perfect square" + integerResult := floatResult truncated. + integerResult squared = self ifTrue: [^integerResult]]. + + "In this case, maybe it failed because we are such a big integer that the Float method becomes + inexact, even if we are a whole square number. So, try the slower but more general method" + selfAsFloat >= Float maxExactInteger asFloat squared + ifTrue: [ + integerResult := self sqrtFloor. + integerResult squared = self ifTrue: [ + ^integerResult ]. + + "Nothing else can be done. No exact answer means answer must be a Float. + Answer the best we have which is the rounded sqrt." + integerResult := (self bitShift: 2) sqrtFloor. + ^((integerResult bitShift: -1) + (self bitAnd: 1)) asFloat]. - "If we know for sure no exact solution exists, then just answer the cheap float approximation without wasting time." - | selfAsFloat | - self mightBeASquare - ifFalse: - [selfAsFloat := self asFloat. - selfAsFloat isFinite ifTrue: [^self asFloat sqrt ]]. + "We need an approximate result" + ^floatResult! - "If some exact solution might exist, or self asFloat isInfinite, call potentially expensive super" - ^super sqrt! Item was changed: ----- Method: LargePositiveInteger>>sqrtFloor (in category 'mathematical functions') ----- sqrtFloor + "See super. Use a fast divide and conquer strategy." + - "Like super, but use a faster divide and conquer strategy if it's worth" - - self digitLength >= 64 ifFalse: [^self sqrtFloorNewtonRaphson]. ^self sqrtRem first! Item was changed: ----- Method: LargePositiveInteger>>sqrtRem (in category 'mathematical functions') ----- sqrtRem + "See super. Use a divide and conquer method to perform this operation. - "Like super, but use a divide and conquer method to perform this operation. See Paul Zimmermann. Karatsuba Square Root. [Research Report] RR-3805, INRIA. 1999, pp.8. <inria-00072854> https://hal.inria.fr/inria-00072854/PDF/RR-3805.pdf" | n qr q s r sr a3a2 a1 a0 | "Split self in 4 digits a3,a2,a1,a0 in base b, such that most significant digit a3 >= b/4 It is not a problem to have a3 >= b, so we can round b down to a whole number of bytes n" n := self highBit bitShift: -5. "bitShift: -2 divide in 4 parts, bitShift: -3 round down in bytes" - n >= 16 ifFalse: [^super sqrtRem]. a3a2 := self butLowestNDigits: n * 2. a1 := self copyDigitsFrom: n + 1 to: n * 2. a0 := self lowestNDigits: n. sr := a3a2 sqrtRem. qr := (sr last bitShift: 8 * n) + a1 divideByInteger: (sr first bitShift: 1). q := qr first normalize. s := (sr first bitShift: 8 * n) + q. r := (qr last normalize bitShift: 8 * n) + a0 - q squared. r negative ifTrue: [r := (s bitShift: 1) + r - 1. s := s - 1]. sr at: 1 put: s; at: 2 put: r. ^sr ! Item was changed: ----- Method: SmallFloat64>>sqrt (in category 'mathematical functions') ----- sqrt "Answer the square root of the receiver. Optional. See Object documentation whatIsAPrimitive." - | exp guess eps delta | <primitive: 555> + ^super sqrt! - #Numeric. - "Changed 200/01/19 For ANSI <number> support." - "Newton-Raphson" - self <= 0.0 - ifTrue: [self = 0.0 - ifTrue: [^ 0.0] - ifFalse: ["v Chg" - ^ DomainError signal: 'sqrt undefined for number less than zero.']]. - "first guess is half the exponent" - exp := self exponent // 2. - guess := self timesTwoPower: 0 - exp. - "get eps value" - eps := guess * Epsilon. - eps := eps * eps. - delta := self - (guess * guess) / (guess * 2.0). - [delta * delta > eps] - whileTrue: - [guess := guess + delta. - delta := self - (guess * guess) / (guess * 2.0)]. - ^ guess! Item was added: + ----- Method: SmallInteger>>isAnExactFloat (in category 'testing') ----- + isAnExactFloat + "See super. + When you're small, the fastest way is to try" + + ^self asFloat truncated = self! Item was changed: ----- Method: SmallInteger>>sqrt (in category 'mathematical functions') ----- sqrt + "Answer the square root of the receiver. + If the square root is exact, answer an Integer, else answer a Float approximation" + | floatResult integerResult | self negative ifTrue: [ ^ DomainError signal: 'sqrt undefined for number less than zero.' ]. + floatResult := self asFloat sqrt. + integerResult := floatResult truncated. + "Note: truncated works for 60-bit SmallInteger + If self is a square s^2, but asFloat rounds down, + f = s^2*(1-e), f^0.5 = s*(1-e)^0.5 = s*(1-0.5*e+O(e^2)) + since s asFloat is exact, and e <= 0.5*ulp(1), + s*(1-0.5*e+O(e^2)) always rounds to s" + integerResult * integerResult = self ifTrue: [^integerResult]. + ^floatResult! - ^super sqrt! Item was added: + ----- Method: SmallInteger>>sqrtFloor (in category 'mathematical functions') ----- + sqrtFloor + "See super. Use asFloat sqrt which is known to be exactly rounded. + Adjust the result in case self asFloat is inexact. + An example why it is necessary with 60 bits SmallInteger is: + | i | + i := (1<<28-1) squared - 1. + i asFloat sqrt truncated squared <= i. + What happens is that i and and next perfect square above i, s^2 + are rounded to the same Float f >= s^2. + In other words, asFloat did cross the next perfect square boundary. + The guess is at most off by 1, because the next next perfect square is: + (s + 1) squared = (2*s + s squared + 1) + s squared has at most 60 bits, and 2*s has 31 bits in this case, + s squared highBit - (2*s) highBit < Float precision, + so we are sure that next next perfect square is a different Float." + + | guess | + guess := self asFloat sqrt truncated. + guess * guess > self ifTrue: [^guess - 1]. + ^guess! Item was added: + ----- Method: SmallInteger>>sqrtRem (in category 'mathematical functions') ----- + sqrtRem + "See super" + + | s | + s := self sqrtFloor. + ^{s. self - (s*s)}!

2 1

The Trunk: Kernel-nice.1231.mcz
by commits＠source.squeak.org 12 May '19

12 May '19

Nicolas Cellier uploaded a new version of Kernel to project The Trunk: http://source.squeak.org/trunk/Kernel-nice.1231.mcz ==================== Summary ==================== Name: Kernel-nice.1231 Author: nice Time: 12 May 2019, 10:58:37.936831 pm UUID: fdae6969-331b-4fa3-83b9-4cadb4d84290 Ancestors: Kernel-nice.1230 Oups, I forgot one germane Float sqrt edge case - sorry to double commit. -0.0 sqrt should answer -0.0 (don't ask why, read the standard...) I already corrected original code for inf,nan,gradual underflow (very inaccurate), and incorrectly rounded for a few ETA-floats (ETA is 10^18). I have maybe 20 copies of this fallback code in my change log, and I still missed one case! Note entirely my fault, that's one of the 4 original lines of code that I did not change... =============== Diff against Kernel-nice.1230 =============== Item was changed: ----- Method: Float>>sqrt (in category 'mathematical functions') ----- sqrt "Fallback code for absent primitives. Care to answer a correctly rounded result as mandated by IEEE-754." | guess selfScaled nextGuess exp secator hi lo remainder maxError | self <= 0.0 ifTrue: [self = 0.0 + ifTrue: [^ self] - ifTrue: [^ 0.0] ifFalse: [^ DomainError signal: 'sqrt undefined for number less than zero.']]. self isFinite ifFalse: [^self]. "scale to avoid loss of precision in case of gradual underflow (selfScaled between: 1.0 and: 2.0), so it is a good guess by itself" exp := self exponent // 2. guess := selfScaled := self timesTwoPower: exp * -2. "Use Newton-Raphson iteration - it converges quadratically (twice many correct bits at each loop)" [nextGuess := selfScaled - (guess * guess) / (2.0 * guess) + guess. "test if both guess are within 1 ulp" (nextGuess + guess) / 2.0 = guess] whileFalse: ["always round odd upper - this avoids infinite loop with alternate flip of last bit" guess := nextGuess + (nextGuess ulp/2.0)]. "adjust the rounding - the guess can be 2 ulp up or 1 ulp down Let u = guess ulp. if (guess+u/2)^2<self, then guess is under-estimated if (guess-u/2)^2>self, then guess is over-estimated Note that they can't be equal (because left term has 55 bits). (guess+u/2)^2=guess^2 + guess*u + u^2/4 < self ==> self - guess^2 > guess*u (guess-u/2)^2=guess^2 - guess*u + u^2/4 > self ==> guess^2 - self >= guess*u (guess^2 - self) is evaluated with an emulated fused-multiply-add" ["Decompose guess in two 26 bits parts hi,lo the trick is that they do not necessarily have the same sign If 53 bits are hi,0,lo => (hi,lo) else hi,1,lo=> (hi+1,-lo)" secator := "1<<27+1" 134217729.0. hi := guess * secator. hi :=hi + (guess - hi). lo := guess - hi. "The operations below are all exact" remainder := selfScaled - hi squared - (hi * lo * 2.0) - lo squared. maxError := guess timesTwoPower: 1 - Float precision. remainder > maxError or: [remainder negated >= maxError]] whileTrue: [guess :=remainder > 0.0 ifTrue: [guess successor] ifFalse: [guess predecessor]]. "undo the scaling" ^ guess timesTwoPower: exp!

1 0

The Trunk: KernelTests-nice.363.mcz
by commits＠source.squeak.org 12 May '19

12 May '19

Nicolas Cellier uploaded a new version of KernelTests to project The Trunk: http://source.squeak.org/trunk/KernelTests-nice.363.mcz ==================== Summary ==================== Name: KernelTests-nice.363 Author: nice Time: 12 May 2019, 10:47:16.307052 pm UUID: 6b78d1d7-57ac-4173-ad99-442804a134cf Ancestors: KernelTests-nice.362 Test the fallback code for Float sqrt (used when primitives 55 or 555 are absent) =============== Diff against KernelTests-nice.362 =============== Item was changed: ----- Method: FloatTest>>testIsZero (in category 'tests - zero behavior') ----- testIsZero self assert: 0.0 isZero. + self assert: Float negativeZero isZero. self deny: 0.1 isZero.! Item was added: + ----- Method: FloatTest>>testSqrtFallback (in category 'tests - mathematical functions') ----- + testSqrtFallback + | fallBackMethod | + fallBackMethod := Float>>#sqrt. + {Float fmin. Float fmin * 2.0. Float fmin * 63.0. Float fmax. Float fmax predecessor predecessor. + 1.0. 2.0. 3.0. 4.0. 5.0} + do: [:f | + | s sm sp | + "check against the primitives - if they are absent, it does not test anything..." + s := fallBackMethod valueWithReceiver: f arguments: Array new. + self assert: s equals: f sqrt. + + "in case we don't have the primitive, use exact arithmetic and a bit of logic" + sm := s asTrueFraction - (s ulp asTrueFraction / 2). + sp := s asTrueFraction + (s ulp asTrueFraction / 2). + + self assert: s asTrueFraction squared < f ==> [sp squared > f] + description: '(s)^2 < (s+ulp/2)^2 <= f => s is more than ulp/2 away from the true square root of f'. + self assert: s asTrueFraction squared > f ==> [sm squared < f] + description: 'f <= (s-ulp/2)^2 < (s)^2 ==> s is more than ulp/2 away from the true square root of f']. + self assertIsNegativeZero: (fallBackMethod valueWithReceiver: Float negativeZero arguments: Array new). + self assertIsPositiveZero: (fallBackMethod valueWithReceiver: 0.0 arguments: Array new). + self assert: (fallBackMethod valueWithReceiver: Float nan arguments: Array new) isNaN. + self assert: (fallBackMethod valueWithReceiver: Float infinity arguments: Array new) equals: Float infinity. + self should: [fallBackMethod valueWithReceiver: -2.0 arguments: Array new] raise: DomainError!

1 0

Call for Papers: COP 2019
by Fabio Niephaus 12 May '19

12 May '19

============================================================================ Call for Papers: COP 2019 The 11th International Workshop on Context-Oriented Programming and Advanced Modularity (COP) Co-located with ECOOP 2019 July 15th - 19th, 2019, London, United Kingdom https://2019.ecoop.org/home/COP-2019 ============================================================================ Contextual information plays an ever-increasing role in our information- centric world. Current-day software systems adapt continuously to changing execution and usage contexts, even while running. Unfortunately, mainstream programming languages and development environments still do not support this kind of dynamicity very well, leading developers to implement complex designs to anticipate various dimensions of variability. Context-Oriented Programming directly supports variability at the programming level, depending on a wide range of dynamic attributes. It enables run-time behavior to be dispatched directly on any detected properties of the execution or user context. Since more than a decade, researchers have been working on a variety of notions approaching that idea. Implementations ranging from first prototypes to mature platform extensions used in commercial deployments have illustrated how multidimensional dispatch can be supported effectively to achieve expressive run-time variation in behavior. The previous editions of this workshop at ECOOP (since 2009) have each attracted around 30 participants. The goal of the 11th Workshop on Context-Oriented Programming is to further establish context orientation as a common thread throughout language design, application development, and system support. In 2019 we also hope to advance this vibrant research domain at ECOOP in the versatile city of London. According to Wikipedia, London is considered to be one of the world’s most important global cities and has been termed the world’s most powerful, most desirable, most influential, most visited, most expensive, innovative, sustainable, most investment friendly, most popular for work, and the most vegetarian friendly city in the world, all depending on the context. Call for Papers --------------- COP invites submissions of high-quality papers reporting original research, or describing innovative contributions to, or experience with context- oriented programming, its implementation, and application. Papers that depart significantly from established ideas and practices are particularly welcome. All papers must be original. Submissions must not have been published previously and must not be simultaneously submitted or under review at any other refereed event or publication. The program committee will evaluate each contributed paper based on its relevance, significance, clarity, and originality. Topics ------ Topics of interest to the workshop include, but are not limited to: - Interesting application domains and scenarios for COP; - Programming language abstractions for COP (e.g., dynamic scoping, roles, traits, prototype-based extensions); - Implementation techniques and mechanisms for COP (e.g., different kinds of dynamic, contextual, and multi-dimensional dispatch or pre-dispatch); - Implementation issues for COP (e.g., optimization, VM support, JIT compilation); - Implemented use-cases, case studies, or prototypes of COP; - Theoretical foundations for COP (e.g., semantics, type systems); - Configuration languages (e.g., feature description interpreters, transformational approaches); - Interaction between non-functional programming concerns and COP (e.g., security, persistence, concurrency, distribution); - Modularization approaches for COP (e.g., modules, aspects, features, layers, plugins); Guidelines to apply COP (e.g., best practices, idioms, patterns); - Run-time support for COP (e.g., reflection, dynamic binding); - Tool support (e.g., design tools, IDEs, debuggers); - Support for COP at the modeling level; - Beyond context-oriented behavior adaptation (e.g., UI adaptation, DB adaptation). Submission Guidelines --------------------- Papers are to be submitted via EasyChair. They must be written in English, provided as PDF documents, and follow the new ACM Master Article Template with the sigconf option. They should not exceed 8 pages. Accepted papers will be published in the ACM Digital Library. Submission Site: https://easychair.org/conferences/?conf=cop2019 Template: https://www.acm.org/publications/proceedings-template Important Dates --------------- Submission deadline: 2019-05-20 Author notification: 2019-06-10 All deadlines are Anywhere on Earth (AoE), i.e. GMT/UTC-12:00 hour. Program Committee ----------------- Walter Binder, University of Lugano, Switzerland Walter Cazzola, Università degli Studi di Milano, Italy Shigeru Chiba, University of Tokyo, Japan Cynthia Disenfeld, University of Toronto, Canada Benoît Duhoux, Université catholique de Louvain, Belgium David H. Lorenz, Open University and Technion IIT, Israel Robert Hirschfeld, Hasso-Plattner-Institut (HPI), Germany Atsushi Igarashi, Kyoto University, Japan Tetsuo Kamina, Oita University, Japan Gary Leavens, University of Central Florida, United States Mariana Marasoiu, University of Cambridge, United Kingdom Hidehiko Masuhara, Tokyo Institute of Technology, Japan Roly Perera, Alan Turing Institute, United Kingdom Organizers ---------- David H. Lorenz, Open University and Technion IIT, Israel Robert Hirschfeld, Hasso-Plattner-Institut (HPI), Germany Atsushi Igarashi, Kyoto University, Japan Hidehiko Masuhara, Tokyo Institute of Technology, Japan

1 0

Timespan>>datesDo: - is this a bug?
by Chris Cunningham 11 May '19

11 May '19

So, this code: Date today asMonth datesDo: [:date| Transcript cr; show: date yyyymmdd] prints out each day in the month. That is what I'd expect. This code: |mth| mth := Date today asMonth. (mth start asDate to: mth end asDate) datesDo: [:date| Transcript cr; show: date yyyymmdd] does not print the last date. This has bitten me. If I add a nanosecond onto the end date (mth end asDate + 1) it does include the last date - but that is ugly. And dangerous if I have other code that carefully picks the following date start to work around this oddity. Thoughts? -cbc

3 3

Large arithmetic speed-up details
by Nicolas Cellier 11 May '19

11 May '19

I've opened a series of Smallissimo posts for the sake of documenting my recent Kernel changes - I should not have, it stole me some hours of sleep, but Tim gave me such a perfect pretext ;) I have more to write, but don't know if I can sustain, it's not paid work. I hope you'll enjoy! http://smallissimo.blogspot.com/2019/05/benchmarking-arithmetic-boost.html

3 2

The Inbox: Kernel-cmm.1228.mcz
by commits＠source.squeak.org 10 May '19

10 May '19

Chris Muller uploaded a new version of Kernel to project The Inbox: http://source.squeak.org/inbox/Kernel-cmm.1228.mcz ==================== Summary ==================== Name: Kernel-cmm.1228 Author: cmm Time: 7 May 2019, 6:36:01.955169 pm UUID: 2fad2a41-3aec-4e22-b9e8-cce50f7f6808 Ancestors: Kernel-nice.1227 Allow identification of instances of Boolean via #isBoolean. =============== Diff against Kernel-nice.1227 =============== Item was added: + ----- Method: Boolean>>isBoolean (in category 'testing') ----- + isBoolean + ^ true! Item was added: + ----- Method: Object>>isBoolean (in category 'testing') ----- + isBoolean + ^ false!

6 7

← Newer
1
...
8
9
10
11
12
13
14
15
16
Older →

Jump to page: