The Trunk: Kernel-nice.1111.mcz

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

The Trunk: Kernel-nice.1111.mcz

commits-2
Nicolas Cellier uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-nice.1111.mcz

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

Name: Kernel-nice.1111
Author: nice
Time: 14 August 2017, 12:02:46.695166 am
UUID: 280f8152-036b-48e1-b3f3-038fa2611ea7
Ancestors: Kernel-tpr.1110

Avoid costly and useless LargeInteger arithmetics when evaluating:
(2009/2000) raisedTo: (3958333/100000)

These large integer operations were helping to find the nearest Float approximation to the #nthRoot: but
1) they do not scale when the radical increases,
2) we then spoil the accuracy by raising the root to an Integer power naively and inacurately.

Instead, if the result is inexact, fall back to a ln/exp formulation which is a few ulp off but at least fast.

=============== Diff against Kernel-tpr.1110 ===============

Item was changed:
  ----- Method: Fraction>>nthRoot: (in category 'mathematical functions') -----
  nthRoot: aPositiveInteger
  "Answer the nth root of the receiver."
 
+ | guess |
+ guess := (numerator nthRootTruncated: aPositiveInteger) / (denominator nthRootTruncated: aPositiveInteger).
+ (guess raisedTo: aPositiveInteger) = self ifTrue: [^guess].
+ "There is no exact nth root, so answer a Float approximation"
+ ^(self abs ln / aPositiveInteger) exp * self sign!
- | d n |
- n := numerator nthRoot: aPositiveInteger.
- d := denominator nthRoot: aPositiveInteger.
- "The #sqrt method in integer will only answer a Float if there's no exact square root.
- So, we need a float anyway."
- (n isInfinite or: [ d isInfinite ]) ifTrue: [
- ^self asFloat nthRoot: aPositiveInteger ].
- ^n / d!

Item was added:
+ ----- Method: Fraction>>raisedToFraction: (in category 'mathematical functions') -----
+ raisedToFraction: aFraction
+ | root |
+ root := (self numerator nthRootTruncated: aFraction denominator) / (self denominator nthRootTruncated: aFraction denominator).
+ (root raisedToInteger: aFraction denominator) = self ifTrue: [^root raisedToInteger: aFraction numerator].
+ ^super raisedToFraction: aFraction!

Item was added:
+ ----- Method: Integer>>raisedToFraction: (in category 'mathematical functions') -----
+ raisedToFraction: aFraction
+ | root |
+ root := self nthRootTruncated: aFraction denominator.
+ (root raisedToInteger: aFraction denominator) = self ifTrue: [^root raisedToInteger: aFraction numerator].
+ ^super raisedToFraction: aFraction!

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 raisedToFraction: aNumber].
- ^ (self nthRoot: aNumber denominator) raisedToInteger: aNumber numerator ].
  self negative ifTrue: [
  ^ ArithmeticError signal: 'Negative numbers can''t be raised to float powers.' ].
  aNumber isZero 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
  ifTrue: [^ (ZeroDivide dividend: 1) signal]
  ifFalse: [^ self]].
  ^ (aNumber * self ln) exp "Otherwise use logarithms"!

Item was added:
+ ----- Method: Number>>raisedToFraction: (in category 'mathematical functions') -----
+ raisedToFraction: aFraction
+ self isZero
+ ifTrue:
+ [aFraction negative ifTrue: [^ (ZeroDivide dividend: 1) signal].
+ ^self].
+ self negative ifFalse: [^(self ln * aFraction) exp].
+ aFraction denominator even
+ ifTrue: [^ ArithmeticError signal: 'nth root only defined for positive Integer n.'].
+ ^(self negated ln * aFraction) exp negated!

Item was added:
+ ----- Method: ScaledDecimal>>raisedToFraction: (in category 'mathematical functions') -----
+ raisedToFraction: aFraction
+ | result |
+ result := self asFraction raisedToFraction: aFraction.
+ ^result isFloat
+ ifTrue: [result]
+ ifFalse: [result asScaledDecimal: scale]!


cbc
Reply | Threaded
Open this post in threaded view
|

Re: The Trunk: Kernel-nice.1111.mcz

cbc
I would just like to say that I really enjoy reading your math related changes. I usually learn something new - but always get a enjoy the opportunity to think about these things in a different light. 

Thanks,
cbc 

On Aug 13, 2017 3:03 PM, <[hidden email]> wrote:
Nicolas Cellier uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-nice.1111.mcz

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

Name: Kernel-nice.1111
Author: nice
Time: 14 August 2017, 12:02:46.695166 am
UUID: 280f8152-036b-48e1-b3f3-038fa2611ea7
Ancestors: Kernel-tpr.1110

Avoid costly and useless LargeInteger arithmetics when evaluating:
(2009/2000) raisedTo: (3958333/100000)

These large integer operations were helping to find the nearest Float approximation to the #nthRoot: but
1) they do not scale when the radical increases,
2) we then spoil the accuracy by raising the root to an Integer power naively and inacurately.

Instead, if the result is inexact, fall back to a ln/exp formulation which is a few ulp off but at least fast.

=============== Diff against Kernel-tpr.1110 ===============

Item was changed:
  ----- Method: Fraction>>nthRoot: (in category 'mathematical functions') -----
  nthRoot: aPositiveInteger
        "Answer the nth root of the receiver."

+       | guess |
+       guess := (numerator nthRootTruncated: aPositiveInteger) / (denominator nthRootTruncated: aPositiveInteger).
+       (guess raisedTo: aPositiveInteger) = self ifTrue: [^guess].
+       "There is no exact nth root, so answer a Float approximation"
+       ^(self abs ln / aPositiveInteger) exp * self sign!
-       | d n |
-       n := numerator nthRoot: aPositiveInteger.
-       d := denominator nthRoot: aPositiveInteger.
-       "The #sqrt method in integer will only answer a Float if there's no exact square root.
-       So, we need a float anyway."
-       (n isInfinite or: [ d isInfinite ]) ifTrue: [
-               ^self asFloat nthRoot: aPositiveInteger ].
-       ^n / d!

Item was added:
+ ----- Method: Fraction>>raisedToFraction: (in category 'mathematical functions') -----
+ raisedToFraction: aFraction
+       | root |
+       root := (self numerator nthRootTruncated: aFraction denominator) / (self denominator nthRootTruncated: aFraction denominator).
+       (root raisedToInteger: aFraction denominator) = self ifTrue: [^root raisedToInteger: aFraction numerator].
+       ^super raisedToFraction: aFraction!

Item was added:
+ ----- Method: Integer>>raisedToFraction: (in category 'mathematical functions') -----
+ raisedToFraction: aFraction
+       | root |
+       root := self nthRootTruncated: aFraction denominator.
+       (root raisedToInteger: aFraction denominator) = self ifTrue: [^root raisedToInteger: aFraction numerator].
+       ^super raisedToFraction: aFraction!

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 raisedToFraction: aNumber].
-               ^ (self nthRoot: aNumber denominator) raisedToInteger: aNumber numerator ].
        self negative ifTrue: [
                ^ ArithmeticError signal: 'Negative numbers can''t be raised to float powers.' ].
        aNumber isZero 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
                        ifTrue: [^ (ZeroDivide dividend: 1) signal]
                        ifFalse: [^ self]].
        ^ (aNumber * self ln) exp               "Otherwise use logarithms"!

Item was added:
+ ----- Method: Number>>raisedToFraction: (in category 'mathematical functions') -----
+ raisedToFraction: aFraction
+       self isZero
+               ifTrue:
+                       [aFraction negative ifTrue: [^ (ZeroDivide dividend: 1) signal].
+                       ^self].
+       self negative ifFalse: [^(self ln * aFraction) exp].
+       aFraction denominator even
+               ifTrue: [^ ArithmeticError signal: 'nth root only defined for positive Integer n.'].
+       ^(self negated ln * aFraction) exp negated!

Item was added:
+ ----- Method: ScaledDecimal>>raisedToFraction: (in category 'mathematical functions') -----
+ raisedToFraction: aFraction
+       | result |
+       result := self asFraction raisedToFraction: aFraction.
+       ^result isFloat
+               ifTrue: [result]
+               ifFalse: [result asScaledDecimal: scale]!




Reply | Threaded
Open this post in threaded view
|

Re: The Trunk: Kernel-nice.1111.mcz

Nicolas Cellier
Thanks Chris,
It's not very noble and beautiful math, but very applied and finally accessible.
Floating point is trade off and only trade off, so it leave place for arts and crafts, a domain where human still have added value if sufficiently patient ;)

2017-08-15 5:59 GMT+02:00 Chris Cunningham <[hidden email]>:
I would just like to say that I really enjoy reading your math related changes. I usually learn something new - but always get a enjoy the opportunity to think about these things in a different light. 

Thanks,
cbc 

On Aug 13, 2017 3:03 PM, <[hidden email]> wrote:
Nicolas Cellier uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-nice.1111.mcz

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

Name: Kernel-nice.1111
Author: nice
Time: 14 August 2017, 12:02:46.695166 am
UUID: 280f8152-036b-48e1-b3f3-038fa2611ea7
Ancestors: Kernel-tpr.1110

Avoid costly and useless LargeInteger arithmetics when evaluating:
(2009/2000) raisedTo: (3958333/100000)

These large integer operations were helping to find the nearest Float approximation to the #nthRoot: but
1) they do not scale when the radical increases,
2) we then spoil the accuracy by raising the root to an Integer power naively and inacurately.

Instead, if the result is inexact, fall back to a ln/exp formulation which is a few ulp off but at least fast.

=============== Diff against Kernel-tpr.1110 ===============

Item was changed:
  ----- Method: Fraction>>nthRoot: (in category 'mathematical functions') -----
  nthRoot: aPositiveInteger
        "Answer the nth root of the receiver."

+       | guess |
+       guess := (numerator nthRootTruncated: aPositiveInteger) / (denominator nthRootTruncated: aPositiveInteger).
+       (guess raisedTo: aPositiveInteger) = self ifTrue: [^guess].
+       "There is no exact nth root, so answer a Float approximation"
+       ^(self abs ln / aPositiveInteger) exp * self sign!
-       | d n |
-       n := numerator nthRoot: aPositiveInteger.
-       d := denominator nthRoot: aPositiveInteger.
-       "The #sqrt method in integer will only answer a Float if there's no exact square root.
-       So, we need a float anyway."
-       (n isInfinite or: [ d isInfinite ]) ifTrue: [
-               ^self asFloat nthRoot: aPositiveInteger ].
-       ^n / d!

Item was added:
+ ----- Method: Fraction>>raisedToFraction: (in category 'mathematical functions') -----
+ raisedToFraction: aFraction
+       | root |
+       root := (self numerator nthRootTruncated: aFraction denominator) / (self denominator nthRootTruncated: aFraction denominator).
+       (root raisedToInteger: aFraction denominator) = self ifTrue: [^root raisedToInteger: aFraction numerator].
+       ^super raisedToFraction: aFraction!

Item was added:
+ ----- Method: Integer>>raisedToFraction: (in category 'mathematical functions') -----
+ raisedToFraction: aFraction
+       | root |
+       root := self nthRootTruncated: aFraction denominator.
+       (root raisedToInteger: aFraction denominator) = self ifTrue: [^root raisedToInteger: aFraction numerator].
+       ^super raisedToFraction: aFraction!

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 raisedToFraction: aNumber].
-               ^ (self nthRoot: aNumber denominator) raisedToInteger: aNumber numerator ].
        self negative ifTrue: [
                ^ ArithmeticError signal: 'Negative numbers can''t be raised to float powers.' ].
        aNumber isZero 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
                        ifTrue: [^ (ZeroDivide dividend: 1) signal]
                        ifFalse: [^ self]].
        ^ (aNumber * self ln) exp               "Otherwise use logarithms"!

Item was added:
+ ----- Method: Number>>raisedToFraction: (in category 'mathematical functions') -----
+ raisedToFraction: aFraction
+       self isZero
+               ifTrue:
+                       [aFraction negative ifTrue: [^ (ZeroDivide dividend: 1) signal].
+                       ^self].
+       self negative ifFalse: [^(self ln * aFraction) exp].
+       aFraction denominator even
+               ifTrue: [^ ArithmeticError signal: 'nth root only defined for positive Integer n.'].
+       ^(self negated ln * aFraction) exp negated!

Item was added:
+ ----- Method: ScaledDecimal>>raisedToFraction: (in category 'mathematical functions') -----
+ raisedToFraction: aFraction
+       | result |
+       result := self asFraction raisedToFraction: aFraction.
+       ^result isFloat
+               ifTrue: [result]
+               ifFalse: [result asScaledDecimal: scale]!