- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers

# Splitting Numeric to separate Sum from Product

Thu, 2011-09-08, 04:22

The scala.math.Numeric typeclass defines addition and multiplication

operations together in one non-separable interface. There are

reasonably common situations where an addition operation can be

defined without a multiplication operator for "Number-like" data:

- (Mathematical) vectors of the same dimension can be added, but not

in general multiplied to produce another vector.

- Multiplication of matrices of the same dimension is not always defined.

Would there be any problem in factoring out two super-trait

typeclasses above Numeric, enabling addition and multiplication to be

defined separately?

I for one would find this useful. For example, one could define

TraversableOnce.{sum, product} in terms of their more specific

operations, and sum a collection of vectors component-wise.

-Ben

Thu, 2011-09-08, 16:27

#2
Re: Splitting Numeric to separate Sum from Product

Numeric doesn't support division or modulus, but scala also defines the traits scala.math.Fractional for division (implicit instances for Double, BigDecimal, etc.) and scala.math.Integral for integer division and modulus (implicit instances for Int, BigInt, etc.).

I think Numeric's main motivation was to unify the handling of basic numeric types (like BigDecimal, double, float, int, long, char, etc.) vs. modeling the algebraic structure of any type. It's design is nice and simple as you can easily add rationals into the mix or what-have-you. However, I think trying to expand it to vectors, strings, etc. probably better belongs in a separate library that tries to more accurately model algebraic structures. Numeric (and Fractional and Integral) is simple enough to be understandable by most people (vs. monoids, rings, fields, etc), while still providing a good amount of flexibility.

I mean, although you could create a simple Monoid supertrait of Numeric to handle your Vector case (and Strings, eg), chances are you are going to want to do a lot more with your vectors than just sum them. You'd probably want an entire library dedicated to dealing with them.

Moreover, matrices and vectors have the problem that their dimension is an integral part of what operations are defined. So even defining something as simple as Vector addition requires runtime checks with a Numeric-like Monoid trait. Since scala's Numeric instances seem to be wholly against runtime exceptions (eg. implicitly[Fractional[Double]].div(1, 0) gives infinity, rather than an exception), I'm not sure if Vectors would mix well.

On Thu, Sep 8, 2011 at 9:20 AM, Erik Osheim <erik [at] plastic-idolatry [dot] com> wrote:

I think Numeric's main motivation was to unify the handling of basic numeric types (like BigDecimal, double, float, int, long, char, etc.) vs. modeling the algebraic structure of any type. It's design is nice and simple as you can easily add rationals into the mix or what-have-you. However, I think trying to expand it to vectors, strings, etc. probably better belongs in a separate library that tries to more accurately model algebraic structures. Numeric (and Fractional and Integral) is simple enough to be understandable by most people (vs. monoids, rings, fields, etc), while still providing a good amount of flexibility.

I mean, although you could create a simple Monoid supertrait of Numeric to handle your Vector case (and Strings, eg), chances are you are going to want to do a lot more with your vectors than just sum them. You'd probably want an entire library dedicated to dealing with them.

Moreover, matrices and vectors have the problem that their dimension is an integral part of what operations are defined. So even defining something as simple as Vector addition requires runtime checks with a Numeric-like Monoid trait. Since scala's Numeric instances seem to be wholly against runtime exceptions (eg. implicitly[Fractional[Double]].div(1, 0) gives infinity, rather than an exception), I'm not sure if Vectors would mix well.

On Thu, Sep 8, 2011 at 9:20 AM, Erik Osheim <erik [at] plastic-idolatry [dot] com> wrote:

On Thu, Sep 08, 2011 at 01:22:20PM +1000, Ben Hutchison wrote:

> Would there be any problem in factoring out two super-trait

> typeclasses above Numeric, enabling addition and multiplication to be

> defined separately?

Hi Ben,

I became interested in improving scala.math.Numeric around November

2010 when I started trying to use it.

The problems I ran into with scala.math.Numeric related to:

* lack of speed

* lack of division/modulus

* lack of useful conversions

I have addressed these concerns as well as I can in an alternate

Numeric library (and compiler plugin) which are located on Github here:

https://github.com/azavea/numeric.

If you're interested in trying out your idea feel free to fork that

repo, make your changes, test them, and send me a pull request. When

doing so you should try to make sure that you are maintaining the

existing performance numbers (which I've worked very hard to get). :)

Ultimately, we may need a situation where we have both minimal type

classes relating to algebraic properties of different types (e.g.

groups, rings, fields, etc) as well as a type for essentially

"abstracting over everything you can you do with the AnyVal number

types". My use case is closer to the latter, but many people will also

want the former. Right now I don't think scala.math.Numeric addresses

either need very well.

I am not sure what the road map is for improving

com.scala.math.Numeric. Substantial changes to it will probably break

binary compatibility, so there is some reluctance to do that. It's also

true that since very few people seem to use Numeric currently there

isn't a lot of demand for these changes. Hopefully these kinds of

discussions and work on alternate implementations will generate more

interest.

Thu, 2011-09-08, 17:27

#3
Re: Splitting Numeric to separate Sum from Product

On Thu, Sep 08, 2011 at 11:26:17AM -0400, Tom Switzer wrote:

> Numeric doesn't support division or modulus, but scala also defines the

> traits scala.math.Fractional for division (implicit instances for Double,

> BigDecimal, etc.) and scala.math.Integral for integer division and modulus

> (implicit instances for Int, BigInt, etc.).

But when trying to abstract an algorithm across Int/Double the lack of

any concept that something like division is defined on both is

crippling. This is *especially* true given that both Int and Double

define the / operator, so in practice your code for those cases will be

*identical*. I haven't met anyone who's tried to use Numeric for

anything serious and hasn't hit this problem.

I haven't talked to anyone who *needed* the Fractional/Integral

distinction (re division) whereas I myself (and most others who've used

Numeric) have had to give up because of the lack of division. To be

specific, my work involves processing large rasters of numbers

(integral or fractional). Not being able to write a function once that

will work with Int and Double is a deal-breaker.

Do you have a specific reason for *not* wanting division defined on

Numeric. I can understand wanting to have Integral/Fractional type

classes to limit which types can be used, but I can't understand

wanting to cripple Numeric.

> I think Numeric's main motivation was to unify the handling of basic numeric

> types (like BigDecimal, double, float, int, long, char, etc.)

> vs. modeling the algebraic structure of any type. It's design is nice and

> simple as you can easily add rationals into the mix or what-have-you.

> However, I think trying to expand it to vectors, strings, etc. probably

> better belongs in a separate library that tries to more accurately model

> algebraic structures. Numeric (and Fractional and Integral) is simple enough

> to be understandable by most people (vs. monoids, rings, fields, etc), while

> still providing a good amount of flexibility.

I agree that having a separate library for algebraic structures makes

sense. I don't agree that the current design is nice or simple, unless

you:

1. Already understand type classes

2. Don't need division

3. Don't want to be able to mix literals and generic types

4. Don't mind things being slow

My sense from your reply is that you feel like the current Numeric

trait in Scala is "fine" which I strongly disagree with. I do agree

that with Vectors, Matrices, etc. you will have all sorts of additional

concerns that will probably merit their own library (like Scalala or

similar).

Thu, 2011-09-08, 18:17

#4
Re: Splitting Numeric to separate Sum from Product

Well, you have met at least one person (me). The main thing is that while double and int both define a "division" operator, they are not the same thing, and I honestly haven't run into the case where I wouldn't want to separate the 2 (though I assume you and I are working on fairly different projects).

I actually like the separation of Numeric and Fractional (keep in mind, Fractional inherits from Numeric). I use it these extensively in a geometry library I developed and its nice that when you see a function that only requires Numeric, as you know your answers will be exact with BigDecimal or Ints. When you see a Fractional requirement, you know you need to use Rational numbers to achieve an exact result. You could also use Double or BigDecimal, but then the results are not guaranteed to be exact. Since all my geometric objects are abstracted over the number type, being able to know what operations you can apply to them is nice.

In this library, many predicates and orderings can be defined using only addition & multiplication. For instance, I define an intersection ordering for pairs of lines. This ordering doesn't require division, but this would not be immediately obvious to someone seeing this for the first time, since finding and reporting the intersection DOES require division (unless you are using homogeneous coordinates). Having only a Numeric implicit required is a reassurance to a user of the library, since it means the ordering is correctly defined and exact for lines using Int, BigInt or BigDecimal (this wouldn't be the case if division were used).

The separation is also necessary for ints (I think), as integer division (in Scala) is not real division. I wouldn't want someone thinking they could use an Int when it will give an unknown/incorrect (as opposed to inaccurate) result. And, as noted above, it is nice to be able to see the wide range of operations available to you if you use Int (or BigInt), which may not always be obvious.

I actually like the separation of Numeric and Fractional (keep in mind, Fractional inherits from Numeric). I use it these extensively in a geometry library I developed and its nice that when you see a function that only requires Numeric, as you know your answers will be exact with BigDecimal or Ints. When you see a Fractional requirement, you know you need to use Rational numbers to achieve an exact result. You could also use Double or BigDecimal, but then the results are not guaranteed to be exact. Since all my geometric objects are abstracted over the number type, being able to know what operations you can apply to them is nice.

In this library, many predicates and orderings can be defined using only addition & multiplication. For instance, I define an intersection ordering for pairs of lines. This ordering doesn't require division, but this would not be immediately obvious to someone seeing this for the first time, since finding and reporting the intersection DOES require division (unless you are using homogeneous coordinates). Having only a Numeric implicit required is a reassurance to a user of the library, since it means the ordering is correctly defined and exact for lines using Int, BigInt or BigDecimal (this wouldn't be the case if division were used).

The separation is also necessary for ints (I think), as integer division (in Scala) is not real division. I wouldn't want someone thinking they could use an Int when it will give an unknown/incorrect (as opposed to inaccurate) result. And, as noted above, it is nice to be able to see the wide range of operations available to you if you use Int (or BigInt), which may not always be obvious.

Thu, 2011-09-08, 19:47

#5
Re: Splitting Numeric to separate Sum from Product

Hi Tom,

Thanks for your thoughtful reply and description of your use case. I'm

sorry if I came off as hostile but I couldn't tell if you actually

needed the current Numeric behavior or were just playing devil's

advocate.

First of all, is your library online? I have been working on my own

classes for complex and rational numbers and would love to see what

you've come up with. And please feel free to give me feedback on my own

Numeric project.

It does sound like our cases are different. In one of my cases, I am

dealing with large (e.g. 100M cells) grid of numbers (could be 64-bit

floating point, 32-bit integer, whatever) which represents some kind of

geographical data (e.g. elevation data, soil type, etc). I want to be

able to write operations which work no matter what the underlying data

type is, without having to convert the underlying data type, or

duplicate code.

Operations on this data might include division, for instance when

converting units, rescaling or normalizing data. In these cases,

maintaining exact precision is usually less important since the data is

usually already aggregated/sampled. Instead we are very focused on

performance, since we need to be able to do this processing at

"web-appropriate speeds".

Floor division and true division definitely are different operations,

but I think even the fact that we use the same operator symbol for both

shows that we consider them somewhat analogous. While abstracting

across integral/fractional types may be inappropriate in some contexts,

do you think it's *always* inappropriate and should be forbidden?

I strongly believe there needs to be some way to do this in Scala (as

there is in most dynamically typed languages, e.g. Clojure, Python,

Ruby, etc). Java completely lacks this ability and I think it is a

feather in Scala's cap that it is possible.

I wonder if there isn't a way to achieve the kind of "numeric precision

tracking" which you're doing in a better way, rather than using the

(current) properties of Fractional and Numeric? This could involve

creating additional type classes which group the types according

to which operations they can use while maintaining precision.

I suggest this because everyone has different ideas of how much

precision they need. In my case, I'm willing to be limited to the

precision of the underlying data type. In finance, I think most people

don't need to use Rational (because they don't need infinite precision

on fractions like 1/3, but only as much as they need) and are willing

to consider division on BigDecimal "precise enough". In your case, you

don't want to lose *any* precision. I don't think we can settle this

issue just one way, because everyone has their own requirements.

Thu, 2011-09-08, 20:17

#6
Re: Splitting Numeric to separate Sum from Product

Hi,

I pretty much have the same problems as everyone wit Numeric here.

An example hereis the work to optimize Range/NumericRange Numeric where

Numeric has largely prevented me on making the "sum" method run in < 1ms

instead of > 35s for "1 to Int.MaxValue".

The bad thing is, that I can't start requiring Integral or Fractional

without breaking the API, which just provides me with a Numeric.

So I pretty much agree that we need a better types dealing with numbers.

Maybe it is possible to get additional people interested in that topic

(e. g. people from Scalala) on the same table, so see if there is common

ground which the standard libraries can provide to help interoperability

between different projects.

Seeing what Anti-XML does Scala devs generally seem to be willing to

break the ABI if people can demonstrate measurable and meaningful

benefits, so maybe there is a chance to get this into 2.11 if a workable

solution is available _before_ 2.10 ships?

Thanks and bye!

Simon

Fri, 2011-09-09, 01:37

#7
Re: Splitting Numeric to separate Sum from Product

On Fri, Sep 9, 2011 at 1:26 AM, Tom Switzer wrote:

> Numeric (and Fractional and Integral) is simple enough

> to be understandable by most people (vs. monoids, rings, fields, etc), while

> still providing a good amount of flexibility.

Actually, the problem is precisely that Numeric is not simple enough.

I don't think its about adding "algebraic structure" or "monoids" into

the library. Rather, simply splitting the methods already there into

smaller, more focused units. I suspect that it can be done while

maintaining backwards compatibility.

Numeric defines Addition and Multiplication in one interface. Thats

unnecessary coupling: considering TraversableOnce.{sum, product}

(presently the main application/motivation of Numeric in the library),

sum requires you to pass a definition of multiplication, even though

it never uses it. Similarly, product requires Addition even though

it's never used.

chances are you are going to want

> to do a lot more with your vectors than just sum them. You'd probably want

> an entire library dedicated to dealing with them.

Indeed. Anyone can create such a library if they wish, using their

preferred design. But how and where will it integrate with the

standard library? The touchpoints may likely include sum and product,

and it makes sense for the standard lib to require the minimal

required interface from the provider of Numeric-like operations.

> Moreover, matrices and vectors have the problem that their dimension is an

> integral part of what operations are defined. So even defining something as

> simple as Vector addition requires runtime checks with a Numeric-like Monoid

> trait. Since scala's Numeric instances seem to be wholly against runtime

> exceptions (eg. implicitly[Fractional[Double]].div(1, 0) gives infinity,

> rather than an exception), I'm not sure if Vectors would mix well.

A counter example, from Stanford PPL's Delite project, which

currently has several EPFL Scala team members working on/around it. It

would seem that they see value in numeric operations over Vectors &

Matrices:

https://github.com/stanford-ppl/Delite/blob/develop/dsls/optiml/src/ppl/...

-Ben

PS Delite's Arith numeric typeclass also demonstrates the diversity

around how to handle the division operator, having chosen a different

approach to the standard library.

Fri, 2011-09-09, 02:07

#8
Re: Splitting Numeric to separate Sum from Product

Hi,

> Numeric defines Addition and Multiplication in one interface. Thats

> unnecessary coupling: considering TraversableOnce.{sum, product}

> (presently the main application/motivation of Numeric in the library),

> sum requires you to pass a definition of multiplication, even though

> it never uses it. Similarly, product requires Addition even though

> it's never used.

>

Please god, no!

In some cases you need not only multiplication but also division to have

a reasonable fast algorithm.

In the particular case it is a difference between O(1) and a runtime of

less than one ms or O(n) and completely useless runtimes of minutes for

large collections for sum.

Have a look at the mail I wrote a few hours ago, where I excatly

described that problem.

Thanks and bye,

Simon

Fri, 2011-09-09, 02:27

#9
Re: Splitting Numeric to separate Sum from Product

> The problems I ran into with scala.math.Numeric related to:

>

> * lack of speed

> * lack of division/modulus

> * lack of useful conversions

>

> I have addressed these concerns as well as I can in an alternate

> Numeric library (and compiler plugin) which are located on Github here:

> https://github.com/azavea/numeric.

>

> If you're interested in trying out your idea feel free to fork that

> repo, make your changes, test them, and send me a pull request.

I like your approach, ie outlining the present shortcomings of Numeric

and developing specific proposals for improvement. I'll try to

collaborate with you on this.

I share some of your concerns with the present Numeric abstractions

and have some others that are complimentary to your own:

* One is the non-separability of Sum and Product ops, as mentioned here.

* The other is around stuff the present API doesn't include that I

find essential for doing alot of math: trig, exponential, random

numbers, indications of precision/error bounding. Theres a question

around how to make this available for those who need it, without

imposing on those who dont?

I don't have the time to detail the latter issue in full at present,

but I'll try to write it up in the next day or so.

-Ben

-Ben

Fri, 2011-09-09, 02:37

#10
Re: Splitting Numeric to separate Sum from Product

On Fri, Sep 09, 2011 at 11:09:03AM +1000, Ben Hutchison wrote:

> * One is the non-separability of Sum and Product ops, as mentioned here.

Agreed. To be clear, I don't mind creating new traits for those (and

even implementing Numeric in terms of them) as long as Numeric can

continue to perform well.

In fact, given that complex numbers don't have a total ordering, the

current Numeric design (which has Numeric[A] implementing Ordered[A])

doesn't work so well for Complex numbers either. You can always fake

it, but that isn't fantastic, nor are runtime exceptions (the approach

that Python takes). So I think it does make sense to try to create type

classes that express exactly what we want/need.

> * The other is around stuff the present API doesn't include that I

> find essential for doing alot of math: trig, exponential, random

> numbers, indications of precision/error bounding. Theres a question

> around how to make this available for those who need it, without

> imposing on those who dont?

I've thought about this also. It would be good to be able to support

all useful math operations in the type class rather than requiring

conversions to Double (which may produce bad results when dealing with

very large and/or very precise types). I may try to do this soon, since

it's relatively easy (as long as the underlying types have

implementations).

Questions around floating point errors, precision bounding, etc are a

bit more thorny. I don't think it will be possible to solve those

without (potentially) expensive run-time checks and conversions, which

are a deal-breaker for me. I almost imagine using some kind of boxed

data type to do this, which could wrap the operations and detect

errors/precision changes.

It's worth strategizing about, at any rate.

Fri, 2011-09-09, 02:57

#11
Re: Splitting Numeric to separate Sum from Product

Perhaps a trade-off could be to create a few new traits. Something more like,

trait Monoid[A] { def zero: A def add(x: A, y: A): A}

trait Ring[A] extends Monoid[A] { def one: A def sub(x: A, y: A): A def mul(x: A, y: A): A}

trait Numeric[A] extends Ring[A] { def div(x: A, y: A): A}

trait Fractional[A] extends Ring[A] {

On Thu, Sep 8, 2011 at 8:30 PM, Ben Hutchison <brhutchison [at] gmail [dot] com> wrote:

I didn't mean to imply that you shouldn't able to do arithmetic over vectors or matrices (it obviously makes sense), but more that I wasn't entirely sure if there was a reason why Numeric seems to eschew runtime exceptions.

Yep. I prefer Numeric's approach, but clearly several opinions in the conversation take "Arith"'s side.

trait Monoid[A] { def zero: A def add(x: A, y: A): A}

trait Ring[A] extends Monoid[A] { def one: A def sub(x: A, y: A): A def mul(x: A, y: A): A}

trait Numeric[A] extends Ring[A] { def div(x: A, y: A): A}

trait Fractional[A] extends Ring[A] {

On Thu, Sep 8, 2011 at 8:30 PM, Ben Hutchison <brhutchison [at] gmail [dot] com> wrote:

On Fri, Sep 9, 2011 at 1:26 AM, Tom Switzer <thomas [dot] switzer [at] gmail [dot] com> wrote:

> Numeric (and Fractional and Integral) is simple enough

> to be understandable by most people (vs. monoids, rings, fields, etc), while

> still providing a good amount of flexibility.

Actually, the problem is precisely that Numeric is not simple enough.

I don't think its about adding "algebraic structure" or "monoids" into

the library. Rather, simply splitting the methods already there into

smaller, more focused units. I suspect that it can be done while

maintaining backwards compatibility.

Numeric defines Addition and Multiplication in one interface. Thats

unnecessary coupling: considering TraversableOnce.{sum, product}

(presently the main application/motivation of Numeric in the library),

sum requires you to pass a definition of multiplication, even though

it never uses it. Similarly, product requires Addition even though

it's never used.

chances are you are going to want

> to do a lot more with your vectors than just sum them. You'd probably want

> an entire library dedicated to dealing with them.

Indeed. Anyone can create such a library if they wish, using their

preferred design. But how and where will it integrate with the

standard library? The touchpoints may likely include sum and product,

and it makes sense for the standard lib to require the minimal

required interface from the provider of Numeric-like operations.

> Moreover, matrices and vectors have the problem that their dimension is an

> integral part of what operations are defined. So even defining something as

> simple as Vector addition requires runtime checks with a Numeric-like Monoid

> trait. Since scala's Numeric instances seem to be wholly against runtime

> exceptions (eg. implicitly[Fractional[Double]].div(1, 0) gives infinity,

> rather than an exception), I'm not sure if Vectors would mix well.

A counter example, from Stanford PPL's Delite project, which

currently has several EPFL Scala team members working on/around it. It

would seem that they see value in numeric operations over Vectors &

Matrices:

https://github.com/stanford-ppl/Delite/blob/develop/dsls/optiml/src/ppl/dsl/optiml/capabilities/Arith.scala#L94

I didn't mean to imply that you shouldn't able to do arithmetic over vectors or matrices (it obviously makes sense), but more that I wasn't entirely sure if there was a reason why Numeric seems to eschew runtime exceptions.

-Ben

PS Delite's Arith numeric typeclass also demonstrates the diversity

around how to handle the division operator, having chosen a different

approach to the standard library.

Yep. I prefer Numeric's approach, but clearly several opinions in the conversation take "Arith"'s side.

Fri, 2011-09-09, 03:07

#12
Re: Splitting Numeric to separate Sum from Product

Whoops, accidently sent that while typing... Again:

trait Monoid[A] { def zero: A def add(x: A, y: A): A}

trait Ring[A] extends Monoid[A] { def one: A def sub(x: A, y: A): A def mul(x: A, y: A): A}

trait Numeric[A] extends Ring[A] { def div(x: A, y: A): A}

type Fractional = Numeric

trait Integral[A] extends Ring[A] { def quot(x: A, y: A): A def rem(x: A, y: A): A}

Now, implement implicit objects as before, but mixin Numeric AND Integral for Int as well. Now people can use Numeric for division, Integral if they want to specify integer-style division, and I can use Ring to indicate that division will not be used.

trait Monoid[A] { def zero: A def add(x: A, y: A): A}

trait Ring[A] extends Monoid[A] { def one: A def sub(x: A, y: A): A def mul(x: A, y: A): A}

trait Numeric[A] extends Ring[A] { def div(x: A, y: A): A}

type Fractional = Numeric

trait Integral[A] extends Ring[A] { def quot(x: A, y: A): A def rem(x: A, y: A): A}

Now, implement implicit objects as before, but mixin Numeric AND Integral for Int as well. Now people can use Numeric for division, Integral if they want to specify integer-style division, and I can use Ring to indicate that division will not be used.

Fri, 2011-09-09, 03:27

#13
Re: Splitting Numeric to separate Sum from Product

I cannot see how whether an addition goes through Numeric or not can change the complexity from O(1) to O(n). Certainly wrapping an object for each addition/multiplication has performance penalties, but this would only change the constant factor. I have seen some people here looking for nice ways to get around Scala type classes' need to wrap an object for each call for a while. I'm not sure if anything has come of this though.

It would be nice if we could somehow get the compiler to go from "num.mkNumericOps(a).+(b)" to "num.plus(a, b)".

On Thu, Sep 8, 2011 at 8:59 PM, Simon Ochsenreither <simon [at] ochsenreither [dot] de> wrote:

It would be nice if we could somehow get the compiler to go from "num.mkNumericOps(a).+(b)" to "num.plus(a, b)".

On Thu, Sep 8, 2011 at 8:59 PM, Simon Ochsenreither <simon [at] ochsenreither [dot] de> wrote:

Please god, no!

In some cases you need not only multiplication but also division to have a reasonable fast algorithm.

In the particular case it is a difference between O(1) and a runtime of less than one ms or O(n) and completely useless runtimes of minutes for large collections for sum.

Have a look at the mail I wrote a few hours ago, where I excatly described that problem.

Thanks and bye,

Simon

Fri, 2011-09-09, 03:57

#14
Re: Splitting Numeric to separate Sum from Product

On Thu, Sep 08, 2011 at 10:12:56PM -0400, Tom Switzer wrote:

> I cannot see how whether an addition goes through Numeric or not can change

> the complexity from O(1) to O(n).

I think Simon is just referring to the fact that if you don't have

division you can't use something like (n * (n + 1)) / 2 to sum a

NumericRange, so instead you must manually add all the entries up by

hand.

> It would be nice if we could somehow get the compiler to go from

> "num.mkNumericOps(a).+(b)" to "num.plus(a, b)".

Agreed.

Coincidentally, my projects has an optional compiler plugin which does

exactly this. :)

Fri, 2011-09-09, 04:07

#15
Re: Splitting Numeric to separate Sum from Product

On Thu, Sep 8, 2011 at 10:12 PM, Tom Switzer <thomas [dot] switzer [at] gmail [dot] com> wrote:

I cannot see how whether an addition goes through Numeric or not can change the complexity from O(1) to O(n). Certainly wrapping an object for each addition/multiplication has performance penalties, but this would only change the constant factor.

Indeed. But when the constant factor is 40, you start to get worried. (Or you start to think that you should be programming in Python or Groovy.)

On Thu, Sep 8, 2011 at 8:59 PM, Simon Ochsenreither <simon [at] ochsenreither [dot] de> wrote:In some cases you need not only multiplication but also division to have a reasonable fast algorithm.

In the particular case it is a difference between O(1) and a runtime of less than one ms or O(n) and completely useless runtimes of minutes for large collections for sum.

You're either running out of memory or the JVM is optimizing away your code entirely if you are going from ms to minutes. If the JVM can turn your nominally O(n) operation into an O(1) one, so can you. Otherwise it's not more than a factor of 100 or so in the very worst cases (double-boxed vs. primitive on every operation) unless you are really stressing the memory system.

--Rex

Fri, 2011-09-09, 04:17

#16
Re: Splitting Numeric to separate Sum from Product

Let us also not repeat the mistakes of haskell, by splitting Monoid into a Semigroup first. Please :)

On 09/09/2011 11:53 AM, "Tom Switzer" <thomas [dot] switzer [at] gmail [dot] com> wrote:> Perhaps a trade-off could be to create a few new traits. Something more

> like,

>

> trait Monoid[A] {

> def zero: A

> def add(x: A, y: A): A

> }

>

> trait Ring[A] extends Monoid[A] {

> def one: A

> def sub(x: A, y: A): A

> def mul(x: A, y: A): A

> }

>

> trait Numeric[A] extends Ring[A] {

> def div(x: A, y: A): A

> }

>

> trait Fractional[A] extends Ring[A] {

>

>

> On Thu, Sep 8, 2011 at 8:30 PM, Ben Hutchison <brhutchison [at] gmail [dot] com> wrote:

>

>> On Fri, Sep 9, 2011 at 1:26 AM, Tom Switzer <thomas [dot] switzer [at] gmail [dot] com>

>> wrote:

>> > Numeric (and Fractional and Integral) is simple enough

>> > to be understandable by most people (vs. monoids, rings, fields, etc),

>> while

>> > still providing a good amount of flexibility.

>>

>> Actually, the problem is precisely that Numeric is not simple enough.

>> I don't think its about adding "algebraic structure" or "monoids" into

>> the library. Rather, simply splitting the methods already there into

>> smaller, more focused units. I suspect that it can be done while

>> maintaining backwards compatibility.

>>

>> Numeric defines Addition and Multiplication in one interface. Thats

>> unnecessary coupling: considering TraversableOnce.{sum, product}

>> (presently the main application/motivation of Numeric in the library),

>> sum requires you to pass a definition of multiplication, even though

>> it never uses it. Similarly, product requires Addition even though

>> it's never used.

>>

>>

>> chances are you are going to want

>> > to do a lot more with your vectors than just sum them. You'd probably

>> want

>> > an entire library dedicated to dealing with them.

>>

>> Indeed. Anyone can create such a library if they wish, using their

>> preferred design. But how and where will it integrate with the

>> standard library? The touchpoints may likely include sum and product,

>> and it makes sense for the standard lib to require the minimal

>> required interface from the provider of Numeric-like operations.

>>

>> > Moreover, matrices and vectors have the problem that their dimension is

>> an

>> > integral part of what operations are defined. So even defining something

>> as

>> > simple as Vector addition requires runtime checks with a Numeric-like

>> Monoid

>> > trait. Since scala's Numeric instances seem to be wholly against runtime

>> > exceptions (eg. implicitly[Fractional[Double]].div(1, 0) gives infinity,

>> > rather than an exception), I'm not sure if Vectors would mix well.

>>

>> A counter example, from Stanford PPL's Delite project, which

>> currently has several EPFL Scala team members working on/around it. It

>> would seem that they see value in numeric operations over Vectors &

>> Matrices:

>>

>>

>> https://github.com/stanford-ppl/Delite/blob/develop/dsls/optiml/src/ppl/dsl/optiml/capabilities/Arith.scala#L94

>>

>>

> I didn't mean to imply that you shouldn't able to do arithmetic over vectors

> or matrices (it obviously makes sense), but more that I wasn't entirely sure

> if there was a reason why Numeric seems to eschew runtime exceptions.

>

>

>> -Ben

>>

>> PS Delite's Arith numeric typeclass also demonstrates the diversity

>> around how to handle the division operator, having chosen a different

>> approach to the standard library.

>>

>

> Yep. I prefer Numeric's approach, but clearly several opinions in the

> conversation take "Arith"'s side.

Fri, 2011-09-09, 06:17

#17
Re: Splitting Numeric to separate Sum from Product

Over the past 18 months I have done some analysis and prototyping

around handling the variable numerical precision of a Numeric

abstraction, that I hope to write up and add to the thread when time

permits (hopefully tonight). But first, I just want to get off my

chest why for me, Numeric & friends are really worth caring about and

getting right.

Good, usable abstraction over numbers is /rare/ in current

programming/software technology. The majority of present day languages

and frameworks couple against concrete numeric representations, for

example int, single/double floating point, or BigDecimal. I believe it

would be something of a landmark, a /substantial/ advance in software

practice, if Scala offered a numeric abstraction of sufficient quality

and practicality that it enjoyed widespread use. For me, that's a

potentially achievable goal worth working towards, with big ongoing

payoffs over many years to come.

We already have 3 JVM formats that approximate real numbers with

varying cost/accuracy tradeoffs: 32 bit float, 64 bit double, and

BigDecimal. Cameron Purdy's recent talk on future JVM evolution

anticipates several more, including 128bit floats and decimals

[http://i.cmpnet.com/ddj/images/mediacenter/jvmlanguagesummit/2011_Purdy_JVM_Language_Summit.pdf].

So even restricted to real numbers, of varying precision, there's no

shortage of formats to abstract over. We just need to get the

abstraction mechanism right.

As I see it, the stakes in this game are: get Numeric right, and Scala

will have achieved something rare, special and lasting (not to deny it

already has in many other ways). Get it wrong, and we're Yet Another

Language that didn't quite manage to the slay the numeric-abstraction

dragon, and we'll have to wait a decade for the next chance to come

along.

-Ben

On Fri, Sep 9, 2011 at 11:21 AM, Erik Osheim wrote:

> On Fri, Sep 09, 2011 at 11:09:03AM +1000, Ben Hutchison wrote:

>> * One is the non-separability of Sum and Product ops, as mentioned here.

>

> Agreed. To be clear, I don't mind creating new traits for those (and

> even implementing Numeric in terms of them) as long as Numeric can

> continue to perform well.

>

> In fact, given that complex numbers don't have a total ordering, the

> current Numeric design (which has Numeric[A] implementing Ordered[A])

> doesn't work so well for Complex numbers either. You can always fake

> it, but that isn't fantastic, nor are runtime exceptions (the approach

> that Python takes). So I think it does make sense to try to create type

> classes that express exactly what we want/need.

>

>> * The other is around stuff the present API doesn't include that I

>> find essential for doing alot of math: trig, exponential, random

>> numbers, indications of precision/error bounding. Theres a question

>> around how to make this available for those who need it, without

>> imposing on those who dont?

>

> I've thought about this also. It would be good to be able to support

> all useful math operations in the type class rather than requiring

> conversions to Double (which may produce bad results when dealing with

> very large and/or very precise types). I may try to do this soon, since

> it's relatively easy (as long as the underlying types have

> implementations).

>

> Questions around floating point errors, precision bounding, etc are a

> bit more thorny. I don't think it will be possible to solve those

> without (potentially) expensive run-time checks and conversions, which

> are a deal-breaker for me. I almost imagine using some kind of boxed

> data type to do this, which could wrap the operations and detect

> errors/precision changes.

>

> It's worth strategizing about, at any rate.

>

Fri, 2011-09-09, 12:37

#18
Re: Splitting Numeric to separate Sum from Product

On Fri, Sep 9, 2011 at 11:21 AM, Erik Osheim wrote:

> Questions around floating point errors, precision bounding, etc are a

> bit more thorny.

Here's my thinking on how precision interacts with numeric-abstraction:

An implementation of Numeric, or likely some subtype like Fractional

or a hypothetical "Real" trait, knows about the accuracy of the

underlying numeric data it operates on. It needs to expose this

information to allow:

1. Estimating and bounding the error in a computation. While error

analysis is a complex area and is algorithm dependent, it clearly

depends significantly upon the amount of precision in the numeric data

used.

2. A reasonable implementation of equality (or perhaps more correctly

for real numbers, approximate equality). When testing numerical

computations, its important to be able to know if two real number

values are sufficiently close to be considered equal. True, exact

equality at bit level is rarely useful for floating point

computations. How close two values need be is a function of the

expected error in the computation.

An approach that I have had some success with in a prototype Real

numeric trait is to signal precision via a relative error threshold.

Values closer, in relative not absolute terms, than the threshold

should be considered equal; the imprecision of the number format means

that lesser differences might simply be errors. For Double, I use a

value of one millionth as my threshold.

trait Real[T] extends Fractional[T] {

...

/** Hint as to the accuracy of this numeric representation.

* This is the relative error threshold below which two Real values

should be considered (approximately) equal

* (ie approxEq is defined in terms of this).

*/

def RelativeError: T

}

-Ben

Fri, 2011-09-09, 13:47

#19
Re: Splitting Numeric to separate Sum from Product

Hi,

Please have a look at the specific case I mentioned: https://github.com/scala/scala/pull/83

This is a real verified case. The VM doesn't optimize the code in any way.

For some collections where start/end/step is given (Range and friends) it is possible to compute the result of the sum method without traversing the whole collection.

I'm pretty sure that no VM on this planet can optimize "add every element of this collection together O(n)" to "invent a better algorithm to solve the problem in O(1)".

Thanks and bye

In some cases you need not only multiplication but also division to have a reasonable fast algorithm.

In the particular case it is a difference between O(1) and a runtime of less than one ms or O(n) and completely useless runtimes of minutes for large collections for sum.

You're either running out of memory or the JVM is optimizing away your code entirely if you are going from ms to minutes. If the JVM can turn your nominally O(n) operation into an O(1) one, so can you. Otherwise it's not more than a factor of 100 or so in the very worst cases (double-boxed vs. primitive on every operation) unless you are really stressing the memory system.

Please have a look at the specific case I mentioned: https://github.com/scala/scala/pull/83

This is a real verified case. The VM doesn't optimize the code in any way.

For some collections where start/end/step is given (Range and friends) it is possible to compute the result of the sum method without traversing the whole collection.

I'm pretty sure that no VM on this planet can optimize "add every element of this collection together O(n)" to "invent a better algorithm to solve the problem in O(1)".

Thanks and bye

Fri, 2011-09-09, 16:37

#20
Re: Splitting Numeric to separate Sum from Product

Hi Ben,

I am not an expert in numerical analysis, error propagation, etc. so

please take my response with the requisite dosage of salt.

On Fri, Sep 09, 2011 at 09:24:00PM +1000, Ben Hutchison wrote:

> An approach that I have had some success with in a prototype Real

> numeric trait is to signal precision via a relative error threshold.

> Values closer, in relative not absolute terms, than the threshold

> should be considered equal; the imprecision of the number format means

> that lesser differences might simply be errors. For Double, I use a

> value of one millionth as my threshold.

>

> trait Real[T] extends Fractional[T] {

> ...

> /** Hint as to the accuracy of this numeric representation.

> * This is the relative error threshold below which two Real values

> should be considered (approximately) equal

> * (ie approxEq is defined in terms of this).

> */

> def RelativeError: T

> }

So I guess you plan is to create an instance of Real[T] with the type

and error you care about?

implicit object RealDoubleWithMillionthThreshold extends Real[Double] {

def relativeError = 0.000001

}

I worry that this approach would either be cumbersome or cause

unforeseen problems when you need to deal with two (or more) different

epsilons in a single algorithm. It seems like it tries to hard the part

about numerical analysis that people often want to concentrate on.

I'm not sure that these are real concerns, but I'm not that they are

not either.

A different approach I can imagine would be something like this:

case class Epsilon[T:Fractional](error:T) {

def compareWithError(a:T, b:T) = {

val delta = a - b

if (delta.abs < error) 0 else delta.signum

}

}

class ApproximateReal[T:Fractional](val value:T, val epsilon:T) {

def +(rhs:ApproximateReal[T]) = {

val v = this.value + rhs.value

val e = max(this.epsilon, rhs.epsilon)

new ApproximateReal(v, e)

}

...

def cmp(rhs:ApproximateReal[T]) = {

val e = min(this.epsilon, rhs.epsilon)

e.compareWithError(this.value, rhs.value)

}

...

}

object ApproximateReal {

def apply[T:Fractional](v:T)(implicit e:Epsilon[T]) = new ApproximateReal(v, e)

def apply[T:Fractional](v:T, e:T) = new ApproximateReal(v, e)

...

}

This approach introduces boxing (which will certainly impact

performance) but makes it easy to manage many different epsilons, and

potentially recalculate them in useful ways.

Finally, I could imagine using your method but introducing some kind of

syntax-seeming construct to make it easier to provide the correct

implicit epsilon, e.g.:

val result = withError(0.000001) {

// do all the calculations in here

}

I am reluctant to try to demonstrate writing withError until I've

looked more closely at it though.

One final though: the problems of trying to compute and track errors

(round off and truncation) and precision extend just beyond the

problems of testing numeric equality with floating-point numbers. It is

worth considering other cases too, e.g. BigDecimal, rational numbers,

etc.

Fri, 2011-09-09, 21:37

#21
Re: Splitting Numeric to separate Sum from Product

On Thu, Sep 8, 2011 at 6:16 PM, Erik Osheim <erik [at] plastic-idolatry [dot] com> wrote:

For what its worth. A better improvement would be to remove /(x:Int):Int entirely. On the whole this "feature" has probably caused significantly more costs to the world than value.

I've never seen code using integer division where it didn't just seem like an interesting hack. Somewhat like n << 1 instead of n * 2. Sure it works, but in no way does it signal any useful intent.

The times I've seen it used accidentally is quite numerous though, round(sum(qty)/sum(samples)) for example. The worst thing with this kind of bug is that it isn't directly obvious in the output. More often than not (in my experience) this kind of bug is discovered by by coincidence during random code inspections rather than by the users relying on the wrong figures to base their decisions on.

Yeah sure TDD, discipline, education and all that will remove this problem too, but keep in mind that Scala is now starting to take steps into the wonderful world of ERP development. A world where most developers have no clue about floating points, number precisions or other "geeky"-details. It is no coincidence that Java tries very, very, hard not to be scary. (Which it fails miserably at by the way, COBOL is a much better language in key aspects such as IO and database-integartion)

While on the topic one might also consider removing float and double in their base-2 version from the Prelude and instead expose base-10 versions[1] by default. If you care enough about fp-performance to need base-2 floats you also know enough to able to use a specialised library for it. I don't know how to do this and still interoperate with Java though...

[1] http://en.wikipedia.org/wiki/Decimal_floating_point

BR,

John

But when trying to abstract an algorithm across Int/Double the lack of

any concept that something like division is defined on both is

crippling. This is *especially* true given that both Int and Double

define the / operator, so in practice your code for those cases will be

*identical*. I haven't met anyone who's tried to use Numeric for

anything serious and hasn't hit this problem.

For what its worth. A better improvement would be to remove /(x:Int):Int entirely. On the whole this "feature" has probably caused significantly more costs to the world than value.

I've never seen code using integer division where it didn't just seem like an interesting hack. Somewhat like n << 1 instead of n * 2. Sure it works, but in no way does it signal any useful intent.

The times I've seen it used accidentally is quite numerous though, round(sum(qty)/sum(samples)) for example. The worst thing with this kind of bug is that it isn't directly obvious in the output. More often than not (in my experience) this kind of bug is discovered by by coincidence during random code inspections rather than by the users relying on the wrong figures to base their decisions on.

Yeah sure TDD, discipline, education and all that will remove this problem too, but keep in mind that Scala is now starting to take steps into the wonderful world of ERP development. A world where most developers have no clue about floating points, number precisions or other "geeky"-details. It is no coincidence that Java tries very, very, hard not to be scary. (Which it fails miserably at by the way, COBOL is a much better language in key aspects such as IO and database-integartion)

While on the topic one might also consider removing float and double in their base-2 version from the Prelude and instead expose base-10 versions[1] by default. If you care enough about fp-performance to need base-2 floats you also know enough to able to use a specialised library for it. I don't know how to do this and still interoperate with Java though...

[1] http://en.wikipedia.org/wiki/Decimal_floating_point

BR,

John

Fri, 2011-09-09, 22:17

#22
Re: Splitting Numeric to separate Sum from Product

On Fri, Sep 09, 2011 at 10:22:23PM +0200, John Nilsson wrote:

> The times I've seen it used accidentally is quite numerous though,

> round(sum(qty)/sum(samples)) for example. The worst thing with this kind of

> bug is that it isn't directly obvious in the output. More often than not (in

> my experience) this kind of bug is discovered by by coincidence during

> random code inspections rather than by the users relying on the wrong

> figures to base their decisions on.

If this is a big concern of yours then you'd probably want to go the

way Python has and have two division operators: floor division and true

division. Then you can define things so that / uses true division (even

with integral types) and always yields a fractional result. Then people

will also be able to use floor division (mapped to some other operator)

to recover the whole quotient (the way division on integers currently

works).

This type of feature would probably require support for a better

numeric tower in the compiler, and would make the current type class

strategy harder (since Integral[A] would need to define which

Fractional[B] you end up with after doing true division). But I would

be excited to work on something like this.

I don't consider removing integer division to be a useful way to

resolve this issue.

> While on the topic one might also consider removing float and double in

> their base-2 version from the Prelude and instead expose base-10 versions[1]

> by default. If you care enough about fp-performance to need base-2 floats

> you also know enough to able to use a specialised library for it. I don't

> know how to do this and still interoperate with Java though...

This isn't realistic. While it would be nice to have base-10 floating

point types available, it shouldn't force the removal of the base-2

versions. Changing the definition of Float and Double would break

backward compatibility, force a large change to the language spec, and

complicate/destroy Java interop on primitive types.

It seems like you are saying that we need to cripple integral types and

slow down the fractional types in order to satisfy "enterprise

programmers," even though these same souls are already working with

Java and C#, both of which have these exact same issues. Am I

misunderstanding?

Sat, 2011-09-10, 02:47

#23
Re: Splitting Numeric to separate Sum from Product

On Fri, Sep 9, 2011 at 11:07 PM, Erik Osheim <erik [at] plastic-idolatry [dot] com> wrote:

Compare it to null vs Option[T], yes you are constructing and boxing your values which have a performance impact. But in the end the common case is "fast enough" to warrant its use.

I'm not convinced that you have to "cripple" anything or make scientific computing impossible to achieve this though. Btw. there are chips out there that have hardware implementation of the decimal floats, would the feature be readily available in mainstream languages I'm sure Intel and AMD would include it it into their chips.

BR,

John

If this is a big concern of yours then you'd probably want to go theOr possible just return a reminder with the floor.

way Python has and have two division operators: floor division and true

division.

I don't consider removing integer division to be a useful way toRemove/rename I'm not suggesting making the operation unavailable, just to make it harder to accidentally use it.

resolve this issue.

It seems like you are saying that we need to cripple integral types andNo you understand me correct. Yes they are struggling with these issues in Java and C#, and Scala are in many way positioning it self as an improvement over the current mainstream languages. I'm just proposing that it could be even more of an improvement.

slow down the fractional types in order to satisfy "enterprise

programmers," even though these same souls are already working with

Java and C#, both of which have these exact same issues. Am I

misunderstanding?

Compare it to null vs Option[T], yes you are constructing and boxing your values which have a performance impact. But in the end the common case is "fast enough" to warrant its use.

I'm not convinced that you have to "cripple" anything or make scientific computing impossible to achieve this though. Btw. there are chips out there that have hardware implementation of the decimal floats, would the feature be readily available in mainstream languages I'm sure Intel and AMD would include it it into their chips.

BR,

John

Sun, 2011-09-11, 07:47

#24
Re: Splitting Numeric to separate Sum from Product

Erik,

After examining your code sketches, Im fairly sure there's been a

miscommunication of my numerical precision proposal, such that our

thinking may be solving different problems.

Let's start at the beginning: why do we abstract over numbers? We want

to write code that does maths, and be able to vary the type of numbers

we use, from one application to the next, or from one run to the next.

For example, we might have a rendering library, that can run in 32 bit

applications on mobile devices, but 64 bits in a server-deployed app.

Or, a differential equation solver that we can run at 32bit in

prototyping mode, but switch to 256 bits when we need ultra-accuracy,

eg planning a spacecraft trajectory.

The point is, in any given app or context, there is typically only one

Numeric instance present. We choose our number format and stick with

it. The application designer (ie consumer of Numeric) has some

"accuracy/error management strategy" (which will often be to do

nothing, but might be some error measure or interval) but for that

strategy to be credible, they need one crucial piece of information

from the provider of the Numeric instance in use: "how accurate is the

underlying Numeric representation?"

That is the piece of information I was trying to expose (indirectly)

via the RelativeError member of the Numeric instance. But in further

consideration, it seems better to model the parameters of the

representation as literally as possible.

Most non-integer numbers in use to day are floating point. What we

call "floating point" use a base2 digits, while what are called

"decimal numbers" use base 10 digits, but in both cases the points

"float". Ive called the proposed trait below Real, but Im not 100%

comfortable with that name. Maybe FloatingPoint[T] is actually

better..

//Proposal Version 2

trait Real[T] extends Fractional[T] {

//the number base used _internally_ by the representation

def Base //ie an enum: Base2 || Base10

//the number of significant digits in the internal base. Ie binary

digits for base 2.

def SignificantDigits: Int

//enum of rounding mode strategies, similar to BigDecimal's

def RoundingMode

}

For example:

- Scala type Double has 53 significant binary digits, is Base2, and

uses Round Half to Even Rounding Mode.

- C# decimal has 28 significant decimal digits, is Base 10, and uses

Round Half to Even Rounding Mode

- java.util.BigDecimal same as C# decimal, but with possibly unlimited

significant digits. (how best to represent "unlimited' in an API?

Option[Int]?)

From these "building blocks" we can derive many useful attributes:

- Exactness: can the number format represent decimal numbers exactly?

Yes, if base10, no otherwise.

- How many significant decimal digits are there? (ie 15-16 for Double,

being log2(53))

- A RelativeError value can be derived from the SignificantDigits &

Exactness along with knowledge of our application's computational

behaviour & demands.

-Ben

PS In thinking about numeric abstraction design, I'll observe that

java.util.BigDecimal makes for an excellent case study: Because it

represents floating point decimals of variable precision, it has had

to contend with many of the relevant issues.

On Sat, Sep 10, 2011 at 1:31 AM, Erik Osheim wrote:

> On Fri, Sep 09, 2011 at 09:24:00PM +1000, Ben Hutchison wrote:

>> An approach that I have had some success with in a prototype Real

>> numeric trait is to signal precision via a relative error threshold.

>> Values closer, in relative not absolute terms, than the threshold

>> should be considered equal; the imprecision of the number format means

>> that lesser differences might simply be errors. For Double, I use a

>> value of one millionth as my threshold.

>>

>> trait Real[T] extends Fractional[T] {

>> ...

>> /** Hint as to the accuracy of this numeric representation.

>> * This is the relative error threshold below which two Real values

>> should be considered (approximately) equal

>> * (ie approxEq is defined in terms of this).

>> */

>> def RelativeError: T

>> }

>

> So I guess you plan is to create an instance of Real[T] with the type

> and error you care about?

>

> implicit object RealDoubleWithMillionthThreshold extends Real[Double] {

> def relativeError = 0.000001

> }

>

> I worry that this approach would either be cumbersome or cause

> unforeseen problems when you need to deal with two (or more) different

> epsilons in a single algorithm. It seems like it tries to hard the part

> about numerical analysis that people often want to concentrate on.

>

> I'm not sure that these are real concerns, but I'm not that they are

> not either.

>

> A different approach I can imagine would be something like this:

>

> case class Epsilon[T:Fractional](error:T) {

> def compareWithError(a:T, b:T) = {

> val delta = a - b

> if (delta.abs < error) 0 else delta.signum

> }

> }

>

> class ApproximateReal[T:Fractional](val value:T, val epsilon:T) {

> def +(rhs:ApproximateReal[T]) = {

> val v = this.value + rhs.value

> val e = max(this.epsilon, rhs.epsilon)

> new ApproximateReal(v, e)

> }

> ...

> def cmp(rhs:ApproximateReal[T]) = {

> val e = min(this.epsilon, rhs.epsilon)

> e.compareWithError(this.value, rhs.value)

> }

> ...

> }

>

> object ApproximateReal {

> def apply[T:Fractional](v:T)(implicit e:Epsilon[T]) = new ApproximateReal(v, e)

> def apply[T:Fractional](v:T, e:T) = new ApproximateReal(v, e)

> ...

> }

>

> This approach introduces boxing (which will certainly impact

> performance) but makes it easy to manage many different epsilons, and

> potentially recalculate them in useful ways.

>

> Finally, I could imagine using your method but introducing some kind of

> syntax-seeming construct to make it easier to provide the correct

> implicit epsilon, e.g.:

>

> val result = withError(0.000001) {

> // do all the calculations in here

> }

>

> I am reluctant to try to demonstrate writing withError until I've

> looked more closely at it though.

>

> One final though: the problems of trying to compute and track errors

> (round off and truncation) and precision extend just beyond the

> problems of testing numeric equality with floating-point numbers. It is

> worth considering other cases too, e.g. BigDecimal, rational numbers,

> etc.

>

Sun, 2011-09-11, 08:37

#25
Re: Splitting Numeric to separate Sum from Product

On Sep 11, 2011, at 08:44 , Ben Hutchison wrote:

> [snip]

> - java.util.BigDecimal same as C# decimal, but with possibly unlimited

> significant digits. (how best to represent "unlimited' in an API?

> Option[Int]?)

>

Considering that the underlying BigInteger will start failing at 2^31 bits, I’d say “unlimited” is quite easily expressible in this case ;-) The general point being that unlimited numeric precision cannot be available on a finite computer.

Regards,

Roland Kuhn

Typesafe – Enterprise-Grade Scala from the Experts

twitter: @rolandkuhn

Mon, 2011-09-12, 03:07

#26
Re: Splitting Numeric to separate Sum from Product

On 09/11/2011 02:44 AM, Ben Hutchison wrote:

> ... but switch to 256 bits when we need ultra-accuracy,

> eg planning a spacecraft trajectory.

I wasn't planning on adding anything to this thread, but I have worked

on systems that created plans for satellites, and we used plain old

doubles -- in .NET no less. To be honest we wouldn't have wanted an

ultra-precise numeric library. The reality that your model will never be

perfectly accurate, so you build buffers around your limits so you don't

need to worry about such imprecisions.

But one thing that would be really useful in a numeric library is an

easy (e.g. hard to ignore) way to incorporate tolerances in comparisons.

We didn't care so much about the precision of our answers so much that

our calculations did not exceed limits, and we always compared our

answers against the limits using tolerances. Or at least we should have,

and not checking against a tolerance (because it was easy to ignore) was

a large source of hard-to-find and harder-to-replicate bugs.

ARKBAN

P.S.: I am now fortunate to be using Scala professionally instead of .NET.

Mon, 2011-09-12, 03:47

#27
Re: Splitting Numeric to separate Sum from Product

On Mon, Sep 12, 2011 at 12:01 PM, ARKBAN wrote:

>

> On 09/11/2011 02:44 AM, Ben Hutchison wrote:

>>

>> ... but switch to 256 bits when we need ultra-accuracy,

>> eg planning a spacecraft trajectory.

>

> I wasn't planning on adding anything to this thread, but I have worked on

> systems that created plans for satellites, and we used plain old doubles --

> in .NET no less. To be honest we wouldn't have wanted an ultra-precise

> numeric library.

OK, its a data point. But we cannot conclude that because you didn't

use them in your project, precision above 64 bits is not needed. 128

bit floats are listed in the JVM's future wish list I linked to

earlier, which I'd claim indicates more than one party has been

wanting them.

Regardless of the case, or lack of, for 128+ bit floats, numeric

abstraction is useful for abstracting across the 32/64 bit divide.

> But one thing that would be really useful in a numeric library is an easy

> (e.g. hard to ignore) way to incorporate tolerances in comparisons.

I fully agree tolerances are important and use them myself. However,

its important to distinguish attributes that properly belong /on/ the

numeric abstraction from those that can be built /on top of/ the

abstraction.

I suspect error tracking (eg a +- error value, interval arithmetic)

techniques can be constructed on top of a numeric abstraction; you may

or may not take the numeric precision into account in that layer.

-Ben

We

> didn't care so much about the precision of our answers so much that our

> calculations did not exceed limits, and we always compared our answers

> against the limits using tolerances. Or at least we should have, and not

> checking against a tolerance (because it was easy to ignore) was a large

> source of hard-to-find and harder-to-replicate bugs.

>

> ARKBAN

>

> P.S.: I am now fortunate to be using Scala professionally instead of .NET.

>

Mon, 2011-09-12, 04:57

#28
Re: Splitting Numeric to separate Sum from Product

On Sun, Sep 11, 2011 at 7:01 PM, ARKBAN wrote:

> But one thing that would be really useful in a numeric library is an easy

> (e.g. hard to ignore) way to incorporate tolerances in comparisons. We

> didn't care so much about the precision of our answers so much that our

> calculations did not exceed limits, and we always compared our answers

> against the limits using tolerances. Or at least we should have, and not

> checking against a tolerance (because it was easy to ignore) was a large

> source of hard-to-find and harder-to-replicate bugs.

Sort of a tangent, but it's underappreciated and you can embed it:

http://futureboy.us/frinkdocs/#IntervalArithmetic

In the below, PLT is "possibly less than" and CLT "certainly less than".

velocity = new interval[50, 55] mph

[2794/125 (exactly 22.352), 15367/625 (exactly 24.5872)] m s^-1 (velocity)

time = new interval[4.0, 4.4] seconds

[4.0, 4.4] s (time)

velocity / time

[5.0799999999999999998, 6.1468] m s^-2 (acceleration)

(velocity / time) PLT 5.08 m/s^2

true

(velocity / time) CLT 5.08 m/s^2

false

(velocity / time) PLT 5.07 m/s^2

false

Mon, 2011-09-12, 11:27

#29
Re: Splitting Numeric to separate Sum from Product

On Mon, Sep 12, 2011 at 1:47 PM, Paul Phillips wrote:

> Sort of a tangent, but it's underappreciated and you can embed it:

>

> http://futureboy.us/frinkdocs/#IntervalArithmetic

>

From a quick review of interval operators

[http://en.wikipedia.org/wiki/Interval_arithmetic], it seems that a

sensible Numeric typeclass could be defined for intervals, built atop

any Numeric definition for the interval endpoints. That looks like the

"easy" way to include error bounds into computations that Arkan

wanted, without having to touch the computational code itself.

-Ben

> In the below, PLT is "possibly less than" and CLT "certainly less than".

>

> velocity = new interval[50, 55] mph

> [2794/125 (exactly 22.352), 15367/625 (exactly 24.5872)] m s^-1 (velocity)

> time = new interval[4.0, 4.4] seconds

> [4.0, 4.4] s (time)

> velocity / time

> [5.0799999999999999998, 6.1468] m s^-2 (acceleration)

> (velocity / time) PLT 5.08 m/s^2

> true

> (velocity / time) CLT 5.08 m/s^2

> false

> (velocity / time) PLT 5.07 m/s^2

> false

>

Mon, 2011-09-12, 12:57

#30
Re: Splitting Numeric to separate Sum from Product

On Fri, Sep 9, 2011 at 11:53 AM, Tom Switzer wrote:

> Perhaps a trade-off could be to create a few new traits. Something more

> like,

> trait Monoid[A] {

> def zero: A

> def add(x: A, y: A): A

> }

>

> trait Ring[A] extends Monoid[A] {

> def one: A

> def sub(x: A, y: A): A

> def mul(x: A, y: A): A

> }

> trait Numeric[A] extends Ring[A] {

> def div(x: A, y: A): A

> }

A beautiful and liberating aspect of switching from an OO- centric to

a Typeclass- centric "default worldview" is that you no longer need to

inherit from something to be that something. You don't need to inherit

from Number to be a number, and you dont need to inherit from Monoid

to be a monoid. Sum and Product are monoids, and they don't need the

consent of the core library:

implicit def sum2Monoid[A](sum: Sum[A]) = new Monoid[A] {

def zero = sum.zero

def add(x: A, y: A) = sum.add(x, y)

}

Another limitation of inheritance is that it's essentially a global

declaration. The trait hierarchy sketched above states that Numeric is

always interpreted as a Monoid via addition/zero. But

multiplication/one is an equally valid way to interpret Numeric as a

Monoid. And to represent that via inheritance requires that Numeric

inherits from Monoid twice simultaneously with differing

implementations: a contortion not even Scala will allow!

-Ben

>

> On Thu, Sep 8, 2011 at 8:30 PM, Ben Hutchison wrote:

>>

>> On Fri, Sep 9, 2011 at 1:26 AM, Tom Switzer

>> wrote:

>> > Numeric (and Fractional and Integral) is simple enough

>> > to be understandable by most people (vs. monoids, rings, fields, etc),

>> > while

>> > still providing a good amount of flexibility.

>>

>> Actually, the problem is precisely that Numeric is not simple enough.

>> I don't think its about adding "algebraic structure" or "monoids" into

>> the library. Rather, simply splitting the methods already there into

>> smaller, more focused units. I suspect that it can be done while

>> maintaining backwards compatibility.

>>

>> Numeric defines Addition and Multiplication in one interface. Thats

>> unnecessary coupling: considering TraversableOnce.{sum, product}

>> (presently the main application/motivation of Numeric in the library),

>> sum requires you to pass a definition of multiplication, even though

>> it never uses it. Similarly, product requires Addition even though

>> it's never used.

>>

>>

>> chances are you are going to want

>> > to do a lot more with your vectors than just sum them. You'd probably

>> > want

>> > an entire library dedicated to dealing with them.

>>

>> Indeed. Anyone can create such a library if they wish, using their

>> preferred design. But how and where will it integrate with the

>> standard library? The touchpoints may likely include sum and product,

>> and it makes sense for the standard lib to require the minimal

>> required interface from the provider of Numeric-like operations.

>>

>> > Moreover, matrices and vectors have the problem that their dimension is

>> > an

>> > integral part of what operations are defined. So even defining something

>> > as

>> > simple as Vector addition requires runtime checks with a Numeric-like

>> > Monoid

>> > trait. Since scala's Numeric instances seem to be wholly against runtime

>> > exceptions (eg. implicitly[Fractional[Double]].div(1, 0) gives infinity,

>> > rather than an exception), I'm not sure if Vectors would mix well.

>>

>> A counter example, from Stanford PPL's Delite project, which

>> currently has several EPFL Scala team members working on/around it. It

>> would seem that they see value in numeric operations over Vectors &

>> Matrices:

>>

>>

>> https://github.com/stanford-ppl/Delite/blob/develop/dsls/optiml/src/ppl/...

>>

>

> I didn't mean to imply that you shouldn't able to do arithmetic over vectors

> or matrices (it obviously makes sense), but more that I wasn't entirely sure

> if there was a reason why Numeric seems to eschew runtime exceptions.

>

>>

>> -Ben

>>

>> PS Delite's Arith numeric typeclass also demonstrates the diversity

>> around how to handle the division operator, having chosen a different

>> approach to the standard library.

>

> Yep. I prefer Numeric's approach, but clearly several opinions in the

> conversation take "Arith"'s side.

Mon, 2011-09-12, 14:07

#31
Re: Splitting Numeric to separate Sum from Product

I completely agree its a single data point, I never meant to imply

otherwise. I know for fact that there are other spacecraft systems where

higher precision is needed.

ARKBAN

On 9/11/11 10:42 PM, Ben Hutchison wrote:

> On Mon, Sep 12, 2011 at 12:01 PM, ARKBAN wrote:

>> On 09/11/2011 02:44 AM, Ben Hutchison wrote:

>>> ... but switch to 256 bits when we need ultra-accuracy,

>>> eg planning a spacecraft trajectory.

>> I wasn't planning on adding anything to this thread, but I have worked on

>> systems that created plans for satellites, and we used plain old doubles --

>> in .NET no less. To be honest we wouldn't have wanted an ultra-precise

>> numeric library.

> OK, its a data point. But we cannot conclude that because you didn't

> use them in your project, precision above 64 bits is not needed. 128

> bit floats are listed in the JVM's future wish list I linked to

> earlier, which I'd claim indicates more than one party has been

> wanting them.

>

> Regardless of the case, or lack of, for 128+ bit floats, numeric

> abstraction is useful for abstracting across the 32/64 bit divide.

>

>> But one thing that would be really useful in a numeric library is an easy

>> (e.g. hard to ignore) way to incorporate tolerances in comparisons.

> I fully agree tolerances are important and use them myself. However,

> its important to distinguish attributes that properly belong /on/ the

> numeric abstraction from those that can be built /on top of/ the

> abstraction.

>

> I suspect error tracking (eg a +- error value, interval arithmetic)

> techniques can be constructed on top of a numeric abstraction; you may

> or may not take the numeric precision into account in that layer.

>

> -Ben

>

> We

>> didn't care so much about the precision of our answers so much that our

>> calculations did not exceed limits, and we always compared our answers

>> against the limits using tolerances. Or at least we should have, and not

>> checking against a tolerance (because it was easy to ignore) was a large

>> source of hard-to-find and harder-to-replicate bugs.

>>

>> ARKBAN

>>

>> P.S.: I am now fortunate to be using Scala professionally instead of .NET.

>>

Mon, 2011-09-12, 15:37

#32
Re: Splitting Numeric to separate Sum from Product

On Fri, Sep 9, 2011 at 17:22, John Nilsson wrote:

>

> I've never seen code using integer division where it didn't just seem like

> an interesting hack. Somewhat like n << 1 instead of n * 2. Sure it works,

> but in no way does it signal any useful intent.

It depends on what you do. I've never written code using any kind of

floating point, except to produce statistics (and, these, mostly

benchmarks -- ie, not production code). Well, maybe "never" is going

too far, but I honestly can't recall any such instance.

Integer division? It is everywhere. How many full pages are needed to

display n items, m items per page? n / m. Total number of pages is (n

+ m - 1) / m.

The same problem under different disguises appear over and over:

memory allocation, scheduling, compression, etc.

Sure, scientific computing of all sorts use floating point.

> While on the topic one might also consider removing float and double in

> their base-2 version from the Prelude and instead expose base-10 versions[1]

> by default. If you care enough about fp-performance to need base-2 floats

> you also know enough to able to use a specialised library for it. I don't

> know how to do this and still interoperate with Java though...

What? I can't think of a single use for base-10 floating point

*except* to represent money. That would be like BCD all over again --

which was hardware supported, and then discarded because of its

uselessness.

If you want to represent money, there's a type for you: BigDecimal.

Accurate decimal fractions, no overflows, no underflows.

Mon, 2011-09-12, 22:27

#33
Re: Splitting Numeric to separate Sum from Product

On Mon, Sep 12, 2011 at 4:30 PM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:

Why not just floor(n/m) ? or val (times, rest) = n / m, basically any way of expressing the intent that cant be mistaken for a bug.

Money is one use case yes, but there are other. It's just my experience that it's the most common use case, I have no clue what the actual statistics are though.

So for the sake of arguments I'm suggesting that val a = 4.2 would be interpreted as val a = BigDecimal("4.2") and not val a = Float.valueOf(4.2)

BR,

John

Integer division? It is everywhere. How many full pages are needed to

display n items, m items per page? n / m. Total number of pages is (n

+ m - 1) / m.

Why not just floor(n/m) ? or val (times, rest) = n / m, basically any way of expressing the intent that cant be mistaken for a bug.

What? I can't think of a single use for base-10 floating pointAny use case where you expect a clueless business user to enter a fraction you'd want a representation with the same rounding errors as they are used to.

*except* to represent money. That would be like BCD all over again --

which was hardware supported, and then discarded because of its

uselessness.

Money is one use case yes, but there are other. It's just my experience that it's the most common use case, I have no clue what the actual statistics are though.

If you want to represent money, there's a type for you: BigDecimal.I think BigDecimal is perfect for the task. But I can see how some people might think it could be a performance problem.

Accurate decimal fractions, no overflows, no underflows.

So for the sake of arguments I'm suggesting that val a = 4.2 would be interpreted as val a = BigDecimal("4.2") and not val a = Float.valueOf(4.2)

BR,

John

Tue, 2011-09-13, 00:07

#34
Re: Splitting Numeric to separate Sum from Product

On Tue, Sep 13, 2011 at 7:19 AM, John Nilsson wrote:

> On Mon, Sep 12, 2011 at 4:30 PM, Daniel Sobral wrote:

>> What? I can't think of a single use for base-10 floating point

>> *except* to represent money. That would be like BCD all over again --

>> which was hardware supported, and then discarded because of its

>> uselessness.

>

> Any use case where you expect a clueless business user to enter a fraction

> you'd want a representation with the same rounding errors as they are used

> to.

>

> Money is one use case yes, but there are other. It's just my experience that

> it's the most common use case, I have no clue what the actual statistics are

> though.

Im favoring John's argument here. Base 2 floats are a legacy of the

need to do math the most efficient way possible. They put the

computers convenience ahead of the humans. But many users do not see

10-100x performance difference as an issue: the recent tendency to

treating Java and Ruby as interchangeable tech options is an example

of this.

Other than money itself, a common decimal use case is fractional

"factors" and "thresholds" used in business rules, eg:

- The proportional amount a price is discounted in a sale

- The number of loyalty points accrued per month in a scheme

- The maximum distance a customer can live from a store to receive free delivery

Money related, yes, because business is about money, but not just money itself.

Lets turn it around: how is representing our base 10 number system in

base 2 a "sensible default"?

The most likely way this could make it into Scala, IMO, is for the

future JVM to add an intrinsic decimal type, and then Java/Scala etc

add a decimal literal syntax.

-Ben

Tue, 2011-09-13, 00:47

#35
Re: Splitting Numeric to separate Sum from Product

On Mon, Sep 12, 2011 at 18:19, John Nilsson wrote:

> On Mon, Sep 12, 2011 at 4:30 PM, Daniel Sobral wrote:

>>

>> Integer division? It is everywhere. How many full pages are needed to

>> display n items, m items per page? n / m. Total number of pages is (n

>> + m - 1) / m.

>

> Why not just floor(n/m) ? or val (times, rest) = n / m, basically any way

> of expressing the intent that cant be mistaken for a bug.

Look, you have an outlook. To you, division means fractions, and

that's that. To people like me, division is integer division. There's

no bug or mistaken intent, because there's nothing using floating

points at all. To *use* floating points, on the other hand, now *that*

may cause bugs! Floating points have no place in a discrete world,

arrays don't have an index 4.2. To introduce floating points there at

all means having to constantly guard against fraction. Miss a floor

here, and add two numbers, and you might end up with the wrong result.

Personally, I think type widening is a mistake. Get rid of it, and

you'll *never* have the problems you mention, because the instant you

try to feed that number to something expecting a double (or BigInt),

it will blow.

>> What? I can't think of a single use for base-10 floating point

>> *except* to represent money. That would be like BCD all over again --

>> which was hardware supported, and then discarded because of its

>> uselessness.

>

> Any use case where you expect a clueless business user to enter a fraction

> you'd want a representation with the same rounding errors as they are used

> to.

>

> Money is one use case yes, but there are other. It's just my experience that

> it's the most common use case, I have no clue what the actual statistics are

> though.

And how many applications do you think handle money? The compiler sure

doesn't, nor does the kernel. I've worked telecom for ten years, and

while there certainly were applications handling money there, none of

mine did. They all dealt in nice integers -- the only time a

non-integer was passed to it, it was handled simply as a string to be

fed to the output.

There's a huge world of integer-using applications. It might not be

_your_ world, but it is there.

> I think BigDecimal is perfect for the task. But I can see how some people

> might think it could be a performance problem.

> So for the sake of arguments I'm suggesting that val a = 4.2 would be

> interpreted as val a = BigDecimal("4.2") and not val a = Float.valueOf(4.2)

Personally, it's almost what I'd prefer. I think the ideal would be

BigInt, properly optimized to work as a Double as long as it doesn't

overflow/underflow. If hardware supported decimal point, then I'd go

with BigDecimal, but I'd never forge ahead in the hopes that hardware

will catch up. Not unless I'm Microsoft or Oracle, at least.

Tue, 2011-09-13, 00:57

#36
Re: Splitting Numeric to separate Sum from Product

Just as an example, grepping for Double on the compiler yield 55

instances. All of them seem related to compiling doubles, too. Float

and Short have 41 instances, which I assume are _all_ related to

compiling them. In contrast, Byte, of all things, have 124 instances,

and Int has 1216. In the library, which has to provide floating point

support, these numbers are 360, 298, 229 and 2340.

On Mon, Sep 12, 2011 at 20:40, Daniel Sobral wrote:

> On Mon, Sep 12, 2011 at 18:19, John Nilsson wrote:

>> On Mon, Sep 12, 2011 at 4:30 PM, Daniel Sobral wrote:

>>>

>>> Integer division? It is everywhere. How many full pages are needed to

>>> display n items, m items per page? n / m. Total number of pages is (n

>>> + m - 1) / m.

>>

>> Why not just floor(n/m) ? or val (times, rest) = n / m, basically any way

>> of expressing the intent that cant be mistaken for a bug.

>

> Look, you have an outlook. To you, division means fractions, and

> that's that. To people like me, division is integer division. There's

> no bug or mistaken intent, because there's nothing using floating

> points at all. To *use* floating points, on the other hand, now *that*

> may cause bugs! Floating points have no place in a discrete world,

> arrays don't have an index 4.2. To introduce floating points there at

> all means having to constantly guard against fraction. Miss a floor

> here, and add two numbers, and you might end up with the wrong result.

>

> Personally, I think type widening is a mistake. Get rid of it, and

> you'll *never* have the problems you mention, because the instant you

> try to feed that number to something expecting a double (or BigInt),

> it will blow.

>

>>> What? I can't think of a single use for base-10 floating point

>>> *except* to represent money. That would be like BCD all over again --

>>> which was hardware supported, and then discarded because of its

>>> uselessness.

>>

>> Any use case where you expect a clueless business user to enter a fraction

>> you'd want a representation with the same rounding errors as they are used

>> to.

>>

>> Money is one use case yes, but there are other. It's just my experience that

>> it's the most common use case, I have no clue what the actual statistics are

>> though.

>

> And how many applications do you think handle money? The compiler sure

> doesn't, nor does the kernel. I've worked telecom for ten years, and

> while there certainly were applications handling money there, none of

> mine did. They all dealt in nice integers -- the only time a

> non-integer was passed to it, it was handled simply as a string to be

> fed to the output.

>

> There's a huge world of integer-using applications. It might not be

> _your_ world, but it is there.

>

>> I think BigDecimal is perfect for the task. But I can see how some people

>> might think it could be a performance problem.

>> So for the sake of arguments I'm suggesting that val a = 4.2 would be

>> interpreted as val a = BigDecimal("4.2") and not val a = Float.valueOf(4.2)

>

> Personally, it's almost what I'd prefer. I think the ideal would be

> BigInt, properly optimized to work as a Double as long as it doesn't

> overflow/underflow. If hardware supported decimal point, then I'd go

> with BigDecimal, but I'd never forge ahead in the hopes that hardware

> will catch up. Not unless I'm Microsoft or Oracle, at least.

>

> --

> Daniel C. Sobral

>

> I travel to the future all the time.

>

Tue, 2011-09-13, 07:47

#37
Re: Splitting Numeric to separate Sum from Product

My outlook isnt based on what I think. Its based on what I think the person who wrote the code thought. Lile I said I see this little gem from time to time: Math.round(int1/int2) ...

In my second example I didn't mean to imply converting things to a float btw.

val (times, re) = i1/i2

or another symbol like

val times = i1/!i2

still integer division.

BR

John

Sent from my phone

Den 13 sep 2011 01:40 skrev "Daniel Sobral" <dcsobral [at] gmail [dot] com>:> On Mon, Sep 12, 2011 at 18:19, John Nilsson <john [at] milsson [dot] nu> wrote:

>> On Mon, Sep 12, 2011 at 4:30 PM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:

>>>

>>> Integer division? It is everywhere. How many full pages are needed to

>>> display n items, m items per page? n / m. Total number of pages is (n

>>> + m - 1) / m.

>>

>> Why not just floor(n/m) ? or val (times, rest) = n / m, basically any way

>> of expressing the intent that cant be mistaken for a bug.

>

> Look, you have an outlook. To you, division means fractions, and

> that's that. To people like me, division is integer division. There's

> no bug or mistaken intent, because there's nothing using floating

> points at all. To *use* floating points, on the other hand, now *that*

> may cause bugs! Floating points have no place in a discrete world,

> arrays don't have an index 4.2. To introduce floating points there at

> all means having to constantly guard against fraction. Miss a floor

> here, and add two numbers, and you might end up with the wrong result.

>

> Personally, I think type widening is a mistake. Get rid of it, and

> you'll *never* have the problems you mention, because the instant you

> try to feed that number to something expecting a double (or BigInt),

> it will blow.

>

>>> What? I can't think of a single use for base-10 floating point

>>> *except* to represent money. That would be like BCD all over again --

>>> which was hardware supported, and then discarded because of its

>>> uselessness.

>>

>> Any use case where you expect a clueless business user to enter a fraction

>> you'd want a representation with the same rounding errors as they are used

>> to.

>>

>> Money is one use case yes, but there are other. It's just my experience that

>> it's the most common use case, I have no clue what the actual statistics are

>> though.

>

> And how many applications do you think handle money? The compiler sure

> doesn't, nor does the kernel. I've worked telecom for ten years, and

> while there certainly were applications handling money there, none of

> mine did. They all dealt in nice integers -- the only time a

> non-integer was passed to it, it was handled simply as a string to be

> fed to the output.

>

> There's a huge world of integer-using applications. It might not be

> _your_ world, but it is there.

>

>> I think BigDecimal is perfect for the task. But I can see how some people

>> might think it could be a performance problem.

>> So for the sake of arguments I'm suggesting that val a = 4.2 would be

>> interpreted as val a = BigDecimal("4.2") and not val a = Float.valueOf(4.2)

>

> Personally, it's almost what I'd prefer. I think the ideal would be

> BigInt, properly optimized to work as a Double as long as it doesn't

> overflow/underflow. If hardware supported decimal point, then I'd go

> with BigDecimal, but I'd never forge ahead in the hopes that hardware

> will catch up. Not unless I'm Microsoft or Oracle, at least.

>

> --

> Daniel C. Sobral

>

> I travel to the future all the time.

Tue, 2011-09-13, 17:17

#38
Re: Splitting Numeric to separate Sum from Product

On Thu, Sep 8, 2011 at 23:12, Tom Switzer wrote:

> I cannot see how whether an addition goes through Numeric or not can change

> the complexity from O(1) to O(n). Certainly wrapping an object for each

> addition/multiplication has performance penalties, but this would only

> change the constant factor. I have seen some people here looking for nice

> ways to get around Scala type classes' need to wrap an object for each call

> for a while. I'm not sure if anything has come of this though.

> It would be nice if we could somehow get the compiler to go from

> "num.mkNumericOps(a).+(b)" to "num.plus(a, b)".

You mean like this?

scala> import scala.math.Numeric.Implicits._

import scala.math.Numeric.Implicits._

scala> def f[T: Numeric](a: T, b: T) = a + b

f: [T](a: T, b: T)(implicit evidence$1: Numeric[T])T

Tue, 2011-09-13, 17:27

#39
Re: Splitting Numeric to separate Sum from Product

On Mon, Sep 12, 2011 at 3:19 PM, John Nilsson <john [at] milsson [dot] nu> wrote:

I'd prefer if integer division returned a Rational, which would give a type safe and accurate way of handling the result. From there it can be either converted back to an integer or to a double depending on your requirements. It would also make '5 / 2 * 2' equivalent to '5 * 2 / 2' --

Derek Williams

On Mon, Sep 12, 2011 at 4:30 PM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:Integer division? It is everywhere. How many full pages are needed to

display n items, m items per page? n / m. Total number of pages is (n

+ m - 1) / m.

Why not just floor(n/m) ? or val (times, rest) = n / m, basically any way of expressing the intent that cant be mistaken for a bug.

I'd prefer if integer division returned a Rational, which would give a type safe and accurate way of handling the result. From there it can be either converted back to an integer or to a double depending on your requirements. It would also make '5 / 2 * 2' equivalent to '5 * 2 / 2' --

Derek Williams

Tue, 2011-09-13, 17:27

#40
Re: Splitting Numeric to separate Sum from Product

On Tue, Sep 13, 2011 at 01:08:58PM -0300, Daniel Sobral wrote:

> You mean like this?

>

> scala> import scala.math.Numeric.Implicits._

> import scala.math.Numeric.Implicits._

>

> scala> def f[T: Numeric](a: T, b: T) = a + b

> f: [T](a: T, b: T)(implicit evidence$1: Numeric[T])T

If you examine the parse tree of this you'll see that this is actually:

def f[T](a:T, b:T)(implicit ev:Numeric[T]):T = new ev.Ops(a).+(b)

What Tom was talking about was removing the object construction that

the new nv.Ops(a) does to get directly to the underlying Numeric.plus:

def f[T](a:T, b:T)(implicit ev:Numeric[T]):T = num.add(a, b)

This transformation isn't safe to do in general, because Ops'

constructor might do something important. In this case though it is a

perfectly safe optimization (as it is for most type classes).

This is one of the root motivations of Josh Suereth's proposals related

to optimizing abstract decorators and type classes, AFAIK.

Tue, 2011-09-13, 17:47

#41
Re: Splitting Numeric to separate Sum from Product

On Tue, Sep 13, 2011 at 03:40, John Nilsson wrote:

> My outlook isnt based on what I think. Its based on what I think the person

> who wrote the code thought. Lile I said I see this little gem from time to

> time: Math.round(int1/int2) ...

>

> In my second example I didn't mean to imply converting things to a float

> btw.

>

> val (times, re) = i1/i2

> or another symbol like

> val times = i1/!i2

> still integer division.

IIRC, integer division in Pascal was "div". I have no problems with that.

>

> BR

> John

>

> Sent from my phone

>

> Den 13 sep 2011 01:40 skrev "Daniel Sobral" :

>> On Mon, Sep 12, 2011 at 18:19, John Nilsson wrote:

>>> On Mon, Sep 12, 2011 at 4:30 PM, Daniel Sobral

>>> wrote:

>>>>

>>>> Integer division? It is everywhere. How many full pages are needed to

>>>> display n items, m items per page? n / m. Total number of pages is (n

>>>> + m - 1) / m.

>>>

>>> Why not just floor(n/m) ? or val (times, rest) = n / m, basically any

>>> way

>>> of expressing the intent that cant be mistaken for a bug.

>>

>> Look, you have an outlook. To you, division means fractions, and

>> that's that. To people like me, division is integer division. There's

>> no bug or mistaken intent, because there's nothing using floating

>> points at all. To *use* floating points, on the other hand, now *that*

>> may cause bugs! Floating points have no place in a discrete world,

>> arrays don't have an index 4.2. To introduce floating points there at

>> all means having to constantly guard against fraction. Miss a floor

>> here, and add two numbers, and you might end up with the wrong result.

>>

>> Personally, I think type widening is a mistake. Get rid of it, and

>> you'll *never* have the problems you mention, because the instant you

>> try to feed that number to something expecting a double (or BigInt),

>> it will blow.

>>

>>>> What? I can't think of a single use for base-10 floating point

>>>> *except* to represent money. That would be like BCD all over again --

>>>> which was hardware supported, and then discarded because of its

>>>> uselessness.

>>>

>>> Any use case where you expect a clueless business user to enter a

>>> fraction

>>> you'd want a representation with the same rounding errors as they are

>>> used

>>> to.

>>>

>>> Money is one use case yes, but there are other. It's just my experience

>>> that

>>> it's the most common use case, I have no clue what the actual statistics

>>> are

>>> though.

>>

>> And how many applications do you think handle money? The compiler sure

>> doesn't, nor does the kernel. I've worked telecom for ten years, and

>> while there certainly were applications handling money there, none of

>> mine did. They all dealt in nice integers -- the only time a

>> non-integer was passed to it, it was handled simply as a string to be

>> fed to the output.

>>

>> There's a huge world of integer-using applications. It might not be

>> _your_ world, but it is there.

>>

>>> I think BigDecimal is perfect for the task. But I can see how some people

>>> might think it could be a performance problem.

>>> So for the sake of arguments I'm suggesting that val a = 4.2 would be

>>> interpreted as val a = BigDecimal("4.2") and not val a =

>>> Float.valueOf(4.2)

>>

>> Personally, it's almost what I'd prefer. I think the ideal would be

>> BigInt, properly optimized to work as a Double as long as it doesn't

>> overflow/underflow. If hardware supported decimal point, then I'd go

>> with BigDecimal, but I'd never forge ahead in the hopes that hardware

>> will catch up. Not unless I'm Microsoft or Oracle, at least.

>>

>> --

>> Daniel C. Sobral

>>

>> I travel to the future all the time.

>

Tue, 2011-09-13, 19:07

#42
Re: Splitting Numeric to separate Sum from Product

There are two errors in my previous email:

1. When I wrote "new nv.Ops(a)" I meant "new ev.Ops(a)"

2. When I wrote "num.add(a, b)" I meant "num.plus(a, b)"

Hopefully the underlying meaning was not lost.

Tue, 2011-09-13, 19:27

#43
Re: Splitting Numeric to separate Sum from Product

On Tue, Sep 13, 2011 at 10:21:33AM -0600, Derek Williams wrote:

> I'd prefer if integer division returned a Rational, which would give a type

> safe and accurate way of handling the result. From there it can be either

> converted back to an integer or to a double depending on your

> requirements. It would also make '5 / 2 * 2' equivalent to '5 * 2 / 2'

Boy has this thread gone beyond the original scope!

Python 3's division operator does return rational results from integral

arguments. It's certainly a valid strategy. That said...

A good way to move forward would be for people who have particular

needs or desires to build their own libraries/code which they can then

promote. I'm definitely interested in discussing "standard"

implementations of other numeric types and I'm happy to try to make the

Numeric implementation I manage interop with these other libraries as

well as possible. But I don't think Numeric is the place to build them.

As for a type class hierarchy for Semigroup, Monoid, Ring, Fractional,

and Integral: I want to help out, and am willing to incorporate it my

Numeric implementation as long as it doesn't impact performance.

For those who want to take a more radical track, the right thing to do

is probably to create some kind of abstract Number class (with multiple

subclasses wrapping different numeric classes) that could track

precision, handle promotion, etc. While this would end up being slower,

I think you could create a really powerful and expressive numeric tower

this way.

I'm not sure how someone would go about lobbying for changes like

Int/Int -> Double, but I am pretty sure that discussions about Numeric

are the wrong place for it. :)

Tue, 2011-09-13, 19:37

#44
Re: Splitting Numeric to separate Sum from Product

On Tue, Sep 13, 2011 at 12:11 PM, Erik Osheim <erik [at] plastic-idolatry [dot] com> wrote:

To bring my comment back on topic, if we had more granular type classes we could have something like:

trait Divide[T, R] { def div(a: T, b: T): R }

object IntDivide extends Divide[Int, Int] { def div(a: Int, b: Int): Int = ...}

object IntDivideToRational extends Divide[Int, Rational] { def div(a: Int, b: Int): Rational = ...}

object IntDivideToDouble extends Divide[Int, Double] { def div(a: Int, b: Int): Double = ... }

--

Derek Williams

I'm not sure how someone would go about lobbying for changes likeInt/Int -> Double, but I am pretty sure that discussions about Numeric

are the wrong place for it. :)

To bring my comment back on topic, if we had more granular type classes we could have something like:

trait Divide[T, R] { def div(a: T, b: T): R }

object IntDivide extends Divide[Int, Int] { def div(a: Int, b: Int): Int = ...}

object IntDivideToRational extends Divide[Int, Rational] { def div(a: Int, b: Int): Rational = ...}

object IntDivideToDouble extends Divide[Int, Double] { def div(a: Int, b: Int): Double = ... }

--

Derek Williams

Tue, 2011-09-13, 20:27

#45
Re: Splitting Numeric to separate Sum from Product

Afaik, some languages use +, -, *, / for integer operations and +., -.,

*., /. for floating point.

Might not work with the current syntax rules in Scala, though...

> IIRC, integer division in Pascal was "div". I have no problems with that.

>

Tue, 2011-09-13, 20:37

#46
Re: Splitting Numeric to separate Sum from Product

The logical split is `div` for integer division and `/` for floating-point division, plus the introduction of a `Rational` type. The problem is that it would require some tweaking of the current precedence rules, and some dev time that's currently in very high demand...

On 13 September 2011 20:18, Simon Ochsenreither <simon [at] ochsenreither [dot] de> wrote:

--

Kevin Wright

mail: kevin [dot] wright [at] scalatechnology [dot] com

gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com quora: http://www.quora.com/Kevin-Wrightgoogle+: http://gplus.to/thecoda

kev [dot] lee [dot] wright [at] gmail [dot] com twitter: @thecoda

vibe / skype: kev.lee.wrightsteam: kev_lee_wright

"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra

On 13 September 2011 20:18, Simon Ochsenreither <simon [at] ochsenreither [dot] de> wrote:

Afaik, some languages use +, -, *, / for integer operations and +., -., *., /. for floating point.

Might not work with the current syntax rules in Scala, though...

IIRC, integer division in Pascal was "div". I have no problems with that.

--

Kevin Wright

mail: kevin [dot] wright [at] scalatechnology [dot] com

gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com quora: http://www.quora.com/Kevin-Wrightgoogle+: http://gplus.to/thecoda

kev [dot] lee [dot] wright [at] gmail [dot] com twitter: @thecoda

vibe / skype: kev.lee.wrightsteam: kev_lee_wright

"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra

Tue, 2011-09-13, 21:07

#47
Re: Splitting Numeric to separate Sum from Product

On Tue, Sep 13, 2011 at 08:35:30PM +0100, Kevin Wright wrote:

> The logical split is `div` for integer division and `/` for floating-point

> division, plus the introduction of a `Rational` type. The problem is that

> it would require some tweaking of the current precedence rules, and some dev

> time that's currently in very high demand...

I that it would be nice to have a Rational type, although there are

still details to work out. E.g. Is it Rationa[T] or Rational? And if

the latter which underlying type is used? BigInt? Long?

I'd really prefer something involving / instead of `div`, especially

given that I doubt the precedence rules are up for modification/debate

any time soon. Python's // is probably out due to being a comment in

Scala, and Ocaml's /. wouldn't work either.

But maybe something similar? /~ and /$ both spring to mind (and would

have the correct precedence already). While normally inventing

operators is in bad taste, in this case I think there is historical

precedent to doing so, especially if it were going to become part of

the core library.

Tue, 2011-09-13, 21:37

#48
Re: Splitting Numeric to separate Sum from Product

When I made my Rational type I chose BigInt simply because, if you are going out of the way to use Rational instead of Double, you probably care enough about precision (over speed) to want BigInt. Also, I felt that Rationals should be able to be constructed from any Double (or BigDecimal) without loss of precision.

I think a Rational[T] type may not be the best choice; if the choice to use Long was REALLY wanted, I'd think it make more sense to have 2 classes: Rational (Long) and BigRational (BigInt).

Tom

On Tue, Sep 13, 2011 at 3:58 PM, Erik Osheim <erik [at] plastic-idolatry [dot] com> wrote:

I think a Rational[T] type may not be the best choice; if the choice to use Long was REALLY wanted, I'd think it make more sense to have 2 classes: Rational (Long) and BigRational (BigInt).

Tom

On Tue, Sep 13, 2011 at 3:58 PM, Erik Osheim <erik [at] plastic-idolatry [dot] com> wrote:

On Tue, Sep 13, 2011 at 08:35:30PM +0100, Kevin Wright wrote:

> The logical split is `div` for integer division and `/` for floating-point

> division, plus the introduction of a `Rational` type. The problem is that

> it would require some tweaking of the current precedence rules, and some dev

> time that's currently in very high demand...

I that it would be nice to have a Rational type, although there are

still details to work out. E.g. Is it Rationa[T] or Rational? And if

the latter which underlying type is used? BigInt? Long?

I'd really prefer something involving / instead of `div`, especially

given that I doubt the precedence rules are up for modification/debate

any time soon. Python's // is probably out due to being a comment in

Scala, and Ocaml's /. wouldn't work either.

But maybe something similar? /~ and /$ both spring to mind (and would

have the correct precedence already). While normally inventing

operators is in bad taste, in this case I think there is historical

precedent to doing so, especially if it were going to become part of

the core library.

Tue, 2011-09-13, 21:47

#49
Re: Splitting Numeric to separate Sum from Product

On Tue, Sep 13, 2011 at 04:26:38PM -0400, Tom Switzer wrote:

> When I made my Rational type I chose BigInt simply because, if you are going

> out of the way to use Rational instead of Double, you probably care enough

> about precision (over speed) to want BigInt. Also, I felt that Rationals

> should be able to be constructed from any Double (or BigDecimal) without

> loss of precision.

Assuming Rational is "opt-in" I totally agree with you that it makes

sense to have the most precision possible. If we were to make 3 / 4 ->

Rational then I'm not sure that's such a great assumption anymore. I

think it's hard to appreciate the performance impact this would have

without doing a lot of profiling of existing Scala codebases first.

Then again maybe I'm just too concerned with performance.

> I think a Rational[T] type may not be the best choice; if the choice to use

> Long was REALLY wanted, I'd think it make more sense to have 2 classes:

> Rational (Long) and BigRational (BigInt).

You are probably right. There aren't many Ts which could satisfy

Rational[T] so maybe it's better not to act like there are.

Tue, 2011-09-13, 22:07

#50
Re: Splitting Numeric to separate Sum from Product

On 13 September 2011 21:26, Tom Switzer <thomas [dot] switzer [at] gmail [dot] com> wrote:

When I made my Rational type I chose BigInt simply because, if you are going out of the way to use Rational instead of Double, you probably care enough about precision (over speed) to want BigInt. Also, I felt that Rationals should be able to be constructed from any Double (or BigDecimal) without loss of precision.

I think a Rational[T] type may not be the best choice; if the choice to use Long was REALLY wanted, I'd think it make more sense to have 2 classes: Rational (Long) and BigRational (BigInt).

Tom

+1 on Rational / BigRational, it fits in nicely with existing conventions.

I'd like to see Rational[T] as an abstract parent of IntRational, LongRational and BigRational, which gives the benefits of specialisation in the first two cases. There's certainly an argument to be made for wanting accuracy without sacrificing too much performance, though care would have to be taken in cases where an operation on xRational would cause the numerator or denominator to overflow.

On Tue, Sep 13, 2011 at 3:58 PM, Erik Osheim <erik [at] plastic-idolatry [dot] com> wrote:

On Tue, Sep 13, 2011 at 08:35:30PM +0100, Kevin Wright wrote:

> The logical split is `div` for integer division and `/` for floating-point

> division, plus the introduction of a `Rational` type. The problem is that

> it would require some tweaking of the current precedence rules, and some dev

> time that's currently in very high demand...

I that it would be nice to have a Rational type, although there are

still details to work out. E.g. Is it Rationa[T] or Rational? And if

the latter which underlying type is used? BigInt? Long?

I'd really prefer something involving / instead of `div`, especially

given that I doubt the precedence rules are up for modification/debate

any time soon. Python's // is probably out due to being a comment in

Scala, and Ocaml's /. wouldn't work either.

But maybe something similar? /~ and /$ both spring to mind (and would

have the correct precedence already). While normally inventing

operators is in bad taste, in this case I think there is historical

precedent to doing so, especially if it were going to become part of

the core library.

On Thu, Sep 08, 2011 at 01:22:20PM +1000, Ben Hutchison wrote:

> Would there be any problem in factoring out two super-trait

> typeclasses above Numeric, enabling addition and multiplication to be

> defined separately?

Hi Ben,

I became interested in improving scala.math.Numeric around November

2010 when I started trying to use it.

The problems I ran into with scala.math.Numeric related to:

* lack of speed

* lack of division/modulus

* lack of useful conversions

I have addressed these concerns as well as I can in an alternate

Numeric library (and compiler plugin) which are located on Github here:

https://github.com/azavea/numeric.

If you're interested in trying out your idea feel free to fork that

repo, make your changes, test them, and send me a pull request. When

doing so you should try to make sure that you are maintaining the

existing performance numbers (which I've worked very hard to get). :)

Ultimately, we may need a situation where we have both minimal type

classes relating to algebraic properties of different types (e.g.

groups, rings, fields, etc) as well as a type for essentially

"abstracting over everything you can you do with the AnyVal number

types". My use case is closer to the latter, but many people will also

want the former. Right now I don't think scala.math.Numeric addresses

either need very well.

I am not sure what the road map is for improving

com.scala.math.Numeric. Substantial changes to it will probably break

binary compatibility, so there is some reluctance to do that. It's also

true that since very few people seem to use Numeric currently there

isn't a lot of demand for these changes. Hopefully these kinds of

discussions and work on alternate implementations will generate more

interest.