Arithmetics

[=?ISO-8859-2?Q?Milan_=C8erm=E1k?=]

Hi all,
I'm about to write an arithmetics object library. It should contain
classes like ShortInteger (for 32-bit longs), Double and Float as
standard numeric type wrappers and LongInteger (really long numbers, not
only 64-bit) and Fraction (to express high precission).
All these classes may inherit from abstract class Number.

I got stuck on following point. I'm not sure how to implement basic
arithmetic operations. What the result type should be? (I don't mean
method return type, but specific operation result type, ie. 1.0 + 1.0 =
<double> 2.0.)

And one more question. If I put the code into a library, it be possible
to extend it? For example some one may want to implement Complex.

Any ideas?
Thanks,
Milan Cermak (Czech Republic)

 

[Phlip]

[cross-posted to a newsgroup that had a discussion about this exact issue
recently]

I'm about to write an arithmetics object library. It should contain
classes like ShortInteger (for 32-bit longs), Double and Float as
standard numeric type wrappers and LongInteger (really long numbers, not
only 64-bit) and Fraction (to express high precission).
All these classes may inherit from abstract class Number.

Why?

If they inherit, what virtual method do they override?

If you mean that clients of Number can accept a Number & and use it, without
knowing what derived type it is, can you show an example of what you want
such a client to look like?

I got stuck on following point. I'm not sure how to implement basic
arithmetic operations. What the result type should be? (I don't mean
method return type, but specific operation result type, ie. 1.0 + 1.0 =
<double> 2.0.)

Double + Double = Fraction, because the result could overflow Double's
range.

Assuming a Fraction is two LongIntegers - a numerator and denominator -
hence it can store any rational.

Now, how to store any irrational?

And one more question. If I put the code into a library, it be possible
to extend it? For example some one may want to implement Complex.

What ultimate problem are you trying to solve? Is the problem "I don't have
an arithmetics object library"?

If you want to solve math problems, which ones? If you try to write a
library that "could" solve any of them (including the ones that have no
numbers), you will only get stuck.

 

[Victor Bazarov]

I'm about to write an arithmetics object library. It should contain
classes like ShortInteger (for 32-bit longs), Double and Float as
standard numeric type wrappers and LongInteger (really long numbers, not
only 64-bit) and Fraction (to express high precission).

(a) Why do you name it 'ShortInteger' when it's apparently long?
(b) Why do you think you need wrappers for double and float?

All these classes may inherit from abstract class Number.
Why?

I got stuck on following point. I'm not sure how to implement basic
arithmetic operations. What the result type should be? (I don't mean
method return type, but specific operation result type, ie. 1.0 + 1.0 =
<double> 2.0.)

Each type should have its own addition operator and the result could
be the same type. You could, of course, go the C++ way and define
some kind of _promotion_ rules, e.g. ShortInteger can be promoted to
Fraction when added to Fraction, or to LongInteger when added to it.

And one more question. If I put the code into a library, it be possible
to extend it? For example some one may want to implement Complex.

If you satisfy the requirements the standard library imposes on the
type for which std::complex is instantiated, you could forego that

Any ideas?

Start working already.

V

 

[=?ISO-8859-2?Q?Milan_=C8erm=E1k?=]

Victor Bazarov napsal(a):

(a) Why do you name it 'ShortInteger' when it's apparently long?

The name doesn't matter. But there should be one class for integers that
could be handled by processor directly and one for others.

(b) Why do you think you need wrappers for double and float?

I want to pack them into collections with other objects. (I mean one
collection containing different kinds of objects.) Maybe one wrapper for
floating point number could be enough.

Why?

Wouldn't it be nice? May be, it will help with some implementation
issues. Furthermore client can use a Number doesn't care about it's type.

Each type should have its own addition operator and the result could
be the same type.

You could, of course, go the C++ way and define
some kind of _promotion_ rules, e.g. ShortInteger can be promoted to
Fraction when added to Fraction, or to LongInteger when added to it.

This is the way I like. But it doesn't satisfy the extensibility issue.
When I introduce new kind of Number, I need to add new promotion rule
and execution method to all other classes. This may not be possible when
I want to extend an already compiled library.

If you satisfy the requirements the standard library imposes on the
type for which std::complex is instantiated, you could forego that
'Complex' type and instead use std::complex<yourtypehere>...

It may not be Complex but Matrix or whatever.

The reason I'm asking is that I thought about this for 3+ months, but
not found any way to satisfy extesibility issue. Sometimes I think I
want too much from the poor C++ language.

Milan Cermak

 

[=?ISO-8859-2?Q?Milan_=C8erm=E1k?=]

Phlip napsal(a):

[cross-posted to a newsgroup that had a discussion about this exact issue
recently]

I'm about to write an arithmetics object library. It should contain
classes like ShortInteger (for 32-bit longs), Double and Float as
standard numeric type wrappers and LongInteger (really long numbers, not
only 64-bit) and Fraction (to express high precission).
All these classes may inherit from abstract class Number.

Why?

If they inherit, what virtual method do they override?

I thought that operators will be implemented by Number class. These will
be promotion rules (just as Victor pointed out).

If you mean that clients of Number can accept a Number & and use it, without
knowing what derived type it is, can you show an example of what you want
such a client to look like?

This is not a point. I'd like to pack numbers into heterogenous
collections (containing different kinds of objects). But I don't want to
bother client with conversions to basic type and back to object.
That's why I want arithmetics on objects.

Double + Double = Fraction, because the result could overflow Double's
range.

Could be but I don't think so. Double + Double = Double with precission
loss. Or may be more complex type with separated mantissa and exponent.

Thanks,
Milan Cermak

 

[lilburne]

Victor Bazarov napsal(a):



Wouldn't it be nice? May be, it will help with some implementation
issues. Furthermore client can use a Number doesn't care about it's type.

I suspect that most code that uses Number will break in the
face of equality. With floating point values the comparison
a == b is usually suspect.

It may not be Complex but Matrix or whatever.

Is a matrix a number? Multiplication is not commulative for
Matrices.

 

[Pete Becker]

I suspect that most code that uses Number will break in the
face of equality. With floating point values the comparison
a == b is usually suspect.

It's quite well defined and it's exact. The place where naive users run
into trouble is in computing the values that they are comparing.

 

[Avner Ben]

The classical solutions for this problem involves the bridge pattern and
likely either double dispatch or algebraic hierarchy. There is much
literature on the subject you may wish to consult before proceeding on
your own, for example by Coplien.

Avner.

 

[Makhno]

Sometimes I think I want too much from the poor C++ language.

"Poor language"? C++ is perhaps the richest, most flexible of all languages
out there. A user has the ability to write high-level, abstract code, and if
necessary, dive down as deep as required for performance/compatibility
purposes. And it can all be done neatly as well (though sadly, seldom is...)

 

[lilburne]

It's quite well defined and it's exact. The place where naive users run
into trouble is in computing the values that they are comparing.

Which for a computer program is a bit of a bitch.

Perhaps he can make operator== virtual and use an 'eps'
within the comparisons using floats or doubles, but what
should that 'eps' be?

 

[lbpf]

I got stuck on following point. I'm not sure how to implement basic

arithmetic operations. What the result type should be? (I don't mean
method return type, but specific operation result type, ie. 1.0 + 1.0 =
<double> 2.0.)

Personally, I'd have it return the greater of the two types on which
the operation is performed (i.e. integer 1 + double 2= double 3).

 

[=?iso-8859-1?Q?Andr=E9_P=F6nitz?=]

Hi all,
I'm about to write an arithmetics object library. It should contain
classes like ShortInteger (for 32-bit longs), Double and Float as
standard numeric type wrappers and LongInteger (really long numbers, not
only 64-bit) and Fraction (to express high precission).

Why don't you simply use an existing library?

All these classes may inherit from abstract class Number.

Why?

Arithmetic library usually spend a great deal of effort on making
operations as fast as possible. Calling random virtual functions
does not help much there...

Andre'

 

[Pete Becker]

Which for a computer program is a bit of a bitch.

Well, it's difficult, and most programmers don't know enough about it to
get it right. Worse, most programmers don't know that they don't know
enough about it. So they throw in techniques like approximate
comparisons, which hide small errors and produce results more like what
they expect.

Perhaps he can make operator== virtual and use an 'eps'
within the comparisons using floats or doubles, but what
should that 'eps' be?

It depends on what you're trying to compute. Writing accurate, fast
floating point code is a specialized field. Hacking around with guesses
about epsilons can sometimes pave over minor errors, but by itself it
doesn't make the computation more robust.

int f()
{
int i = 1/3;
return i * 3;
}

If someone asked you why f() returns 0 instead of 1, would you tell them
that they should use an epsilon to test for equality?

 

[Thomas Matthews]

Hi all,
I'm about to write an arithmetics object library. It should contain
classes like ShortInteger (for 32-bit longs), Double and Float as
standard numeric type wrappers and LongInteger (really long numbers, not
only 64-bit) and Fraction (to express high precission).
All these classes may inherit from abstract class Number.

I got stuck on following point. I'm not sure how to implement basic
arithmetic operations. What the result type should be? (I don't mean
method return type, but specific operation result type, ie. 1.0 + 1.0 =
<double> 2.0.)

And one more question. If I put the code into a library, it be possible
to extend it? For example some one may want to implement Complex.

Any ideas?
Thanks,
Milan Cermak (Czech Republic)

1. I suggest you review existing libraries. If you want people
to use your library, you must provide them with something
the other libraries don't.
Gnu GMP library
Open SSL Big Number library.

2. In cryptography, numbers consisting of 512, 1024 and 2048 bits
are common. The users of cryptography algorithms would
appreciate high speed numeric algorithms.

3. Don't reinvent the wheel. I you need a library, see what's
available first.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book
http://www.sgi.com/tech/stl -- Standard Template Library

 

[=?ISO-8859-2?Q?Milan_=C8erm=E1k?=]

Makhno napsal(a):

"Poor language"? C++ is perhaps the richest, most flexible of all languages
out there. A user has the ability to write high-level, abstract code, and if
necessary, dive down as deep as required for performance/compatibility
purposes. And it can all be done neatly as well (though sadly, seldom is...)

As I wrote peaces of code, I wished C++ to have virtual static methods,
runtime object type identification (not only RTTI, I want the class to
be answered as a result to do 'new' on it). If I inherit the class, it
would be nice for me to call newly introduced child methods from parent.

In this case I want syntactical construction that allows me to extend
class stored in another module. (Something like "protocol" in Objective-C.)

 

[=?ISO-8859-2?Q?Milan_=C8erm=E1k?=]

André Pönitz napsal(a):

Why don't you simply use an existing library?

'Cause the arithmetics is not only one goal. I invent the library as a
basic programing instrument. It knows (heterogenous) collections,
streams, string (8-bit for now, but I plan to use UCS-2), thread,
semaphore and more.
One of the basic supposition is that all classes inherit from one common
class (the only way to implement heterogenous collections).

If you ask why I don't use STL, I answer: It blows up my mind. I don't
understand it, and think it's written wrong way.

Why?

Arithmetic library usually spend a great deal of effort on making
operations as fast as possible. Calling random virtual functions
does not help much there...

I don't want to implement any specific arithmetic algorithm, just
numbers and basic operations on them (addition, subtraction, division,
multiplication and so).
May be I'm reinventing the wheel as Thomas Matthews said, but others
wheels seem to have sharp angles to me.

Milan Cermak

 

[Phlip]

As I wrote peaces of code, I wished C++ to have virtual static methods,

Why? 'virtual' means based on an actual object's type. If you have no actual
object,

runtime object type identification (not only RTTI, I want the class to
be answered as a result to do 'new' on it). If I inherit the class, it
would be nice for me to call newly introduced child methods from parent.

You are asking for a dynamically typed language where classes are themselves
objects. Try Ruby.

In this case I want syntactical construction that allows me to extend
class stored in another module.

Read /Modern C++ Design/ by Andrei Alexandrescu, and get into traits,
policies, etc.

You could also try Euphoria, a math enabling language.

(Something like "protocol" in Objective-C.)

If you can stand the sight of two different languages crammed together.

 

[lilburne]

Well, it's difficult, and most programmers don't know enough about it to
get it right. Worse, most programmers don't know that they don't know
enough about it. So they throw in techniques like approximate
comparisons, which hide small errors and produce results more like what
they expect.




It depends on what you're trying to compute. Writing accurate, fast
floating point code is a specialized field. Hacking around with guesses
about epsilons can sometimes pave over minor errors, but by itself it
doesn't make the computation more robust.

Yes writing computationally stable fp code requires a great deal of
experience, which is why we give that sort of stuff to people with
experience.

That being said no one should think that:

fast_line_surface_intersection() == old_line_surface_intersection();

even though the expression has always been true in the tests you have run.

On something like the above there will usually be a tolerance involved,
its no good calculating the point of intersection to e-100 if the user
is only interested in a result to within e-4. Then if you are going to
use that point of intersection in some other calculation you already
have an inbuilt inaccuracy to start with. The subsequent calculation may
well be very accurate but any precision loss is going to accumulate.

For our systems we can maintain e-10, which is sufficient given that
user equipment can only maintain e-5.

int f()
{
int i = 1/3;
return i * 3;
}

If someone asked you why f() returns 0 instead of 1, would you tell them
that they should use an epsilon to test for equality?

Would you?

 

[Pete Becker]

Would you?

Evading the question doesn't aid your credibility.

 

[puppet_sock]

If I inherit the class, it
would be nice for me to call newly introduced child methods from parent.

It would be a gross violation of object oriented design. The parent
should not know about new methods in the child. In fact, the parent
should not know about the child at all.
Socks