Runtime: Standardized Rational object

[Thaina]

This issue was ported from https://github.com/dotnet/csharplang/issues/553

Lately in csharplang whenever we talk about struct feature. Rational struct often came up as an example

And so I think that Rational actually useful. Normally approximate number with float. 3 * (1 / 3f) is not became what we would expect. Floating point error need to be handled everywhere since we program in C

Most of the time we care about precision than the range of number. If we could naturally use Rational in code it could make a lot of sense in many calculation logic

And instead of always making Rational on our own then overriding all operators just about conversion between each number type. I think it could be useful enough to have it built in

```C#
struct Rational64 { public int Number,Divider; }
struct Rational128 { public long Number,Divider; }

// Both will have long list of overload operator and implicit operator

Rational64 f = 3; // implicit operator for int. Became Rational64(3,1)

Rational64 f3 = 1 / f; // operator / will flip Number and Divider
var three = 9 * f3; // 9 * 1 / 3 became Rational64(9,3). Should it always find LCM or just did it only when overflow?

### ps

We actually could handle internal value like this

```C#
struct Rational64
{
    uint divider;
    public int Number;
    public uint Divider { get => divider + 1; set => divider = value - 1 }

    public double Value { get => Number / (double)Divider; }
}

With this we will always handle negative only in number. And zeromemory will be 0 / 1

ps2

Should we also add Irrational and Algebraic object too?

```C#
struct Irrational64 // Actually just 1 order of power for polynomial calculation
{
public Rational64 Value;
public Rational64 Power;
}

struct Irrational128
{
public Rational128 Value;
public Rational128 Power;
}

class Algebraic128 // The real Irrational
{
public Rational128 Value = 0 / 1R;
public Algebraic Power = null; // Unlike Irrational, can contain chain of power

public static implicit operator double(Algebraic128 value) => Math.Pow((double)Value,Power ?? 1);

}
```

I think most of calculation we use in graphics and physics simulation could be use Irrational128 in general

ps3

From csharplang repo I was propose this feature to have literal syntax. And there are suggestion that it should at least make the object itself pass corefx first

[svick]

My comments:

1. I find it confusing that Rational64 uses 32-bit integers. Are both Rational types actually needed? Maybe having only Rational128 (renamed to just Rational) would be enough?
2. Would a type that can actually represent any rational number (i.e. one using BigIntegers for numerator and denominator) be useful?
3. I think that Irrational is not a great name, since it can't represent irrational numbers like π.
4. Are the Irrational and Algebraic types actually useful? For example, as far as I can tell, they can't even represent values like √2 + √3.

[Thaina]

@svick Thanks

1 - I just thinking that for fraction value. We use int more than long in general. 1/3 for example. epsilon being 1 / int.MaxValue might be enough. But well, I agree it confusing so maybe LongRational ?

2 - There are BigRational proposed dotnet/runtime#14853. But in most case I want to deal with number by valuetype. At least Rational with int64

3 - I have research it and think that it's true. That struct should be named Algebraic and that algebraic struct should be named with other word (Have seen it called closed form function)
But for PI I normally call it Transcendental separated from normal irrational

4 - You are right. That expression would need more work to do. I would thinking more about it
But still with Irrational struct. We could make any expression easily with array of those numbers and extensions method

[svick]

We could make any expression easily with array of those numbers and extensions method

How? Are you saying the array would represent sum of all its elements? Then how would you express ?

And I still don't see what is the actual use case for such numbers. If there is one, I would expect it to be very specialized, so it doesn't belong in corefx.

[Thaina]

@svick is easy one

It could became

Which is

[mellinoe]

I have seen Rational types used in libraries before, but they are usually very niche (for example), and in my opinion aren't very interesting for us to include in the BCL. There are all sorts of different specialized mathematical types we could potentially include, but we only want to include things that are generally or universally useful. I feel that this would be better served by a third-party library for the time being.

[Thaina]

@mellinoe I think it's niche because we actually not included in BCL

All of financial and statistics application or even graphics and physics simulation could replace most floating point in the code into rational if it was standard library

But because it not standard no one would likely risk downloading additional library for their crucial job so it still neglect even it make calculation more accurate. They need to bear with float because float is standard

This is somehow dilemma. I think it need to start somewhere to make it being general

But I think Rational number is universally useful

[mellinoe]

@mellinoe I think it's niche because we actually not included in BCL

All of financial and statistics application or even graphics and physics simulation could replace most floating point in the code into rational if it was standard library

Certainly, that is always a possibility. However, this isn't just a niche type in C#/.NET. I'm not really aware of any graphics or physics libraries which represent data in this way, even in other languages. IMO, it's also more than just being inconvenient or poorly-supported in libraries. GPU's fundamentally don't understand this data format. Real-time physics simulation libraries still predominantly use 32-bit floats for speed, even though 64-bit floats would be essentially a drop-in replacement. A rational structure wouldn't be.

I'm not saying that this wouldn't be a useful type, I'm just not sure that it is universal enough for inclusion in the BCL, at least not yet. I agree with @tannergooding's suggestion in the other issue that this would be great to build as a standalone NuGet package before consideration for the BCL.

[Thaina]

@mellinoe As I said it hardly compared because both float32 and float64 was standardize into bcl. You don't need to rely on nuget

Actually it was ingrained into literal f and d. It so fast to just code it without even using. Not to mention there are Math and other library about it that support float and double from the core

It like C# that even it better than Java, it still struggle to raise the popularity than Java. Because Java was born before

I bet if float and double was excluded into nuget package it would be the same popularity as nowaday

We might gone too far now. floating point was being standard for so long even before GPU itself. And in the old day computer was limit by many cap, a floating point that can represent widely range of number would be more useful to support it than rational number

But nowaday we have ram in GB unit. I think we should start solving bug 3 * (1 / 3) != 1 in the system

[tannergooding]

@Thaina. I don't think you'll ever see float drop away as the primary representation for values. As @mellinoe points out, there are no major real-time libraries that use anything other than float, primarily because they care more about speed then they do precision. When you are manipulating 2073600 pixels (that's 1920x1080) 60 times each second (and it could be more with 4k resolution and higher refresh rates, which are becoming more common) to provide a smooth but realistic enough experience, you want speed and that is something that raw integer math can't handle (even when representing a rational number using a numerator/denominator pair).

The primary reason that integer math doesn't work is because there isn't hardware to support it. Graphics cards are essentially tens or hundreds (sometimes thousands) of compute units designed specifically to crunch floating point numbers. Even on the CPU, floating point throughput can be higher than integer throughput, because the pipeline has been specifically designed to handle it and to handle it seperately from normal integer operations. For example, the Intel Haswell, Broadwell, and Skylake processors can retire a maximum of 32 single precision operations per cycle (when doing two 8-wide FMA instructions).

Now, you appear to be wanting to solve some of the common and well known problems that arise from floating-point arithmetic and many of these are already solved (and standardized). The primary issue with binary floating-point arithmetic is that some numbers are not exact.

For example, the following program:
```C#
var value = 0.0;

for (int i = 0; i <= 10; i++)
{
Console.WriteLine($"{value:G17}");
value += 0.1;
}

Produces:

0
0.10000000000000001
0.20000000000000001
0.30000000000000004
0.40000000000000002
0.5
0.59999999999999998
0.69999999999999996
0.79999999999999993
0.89999999999999991
0.99999999999999989

This issue, however, only exits in "binary" based floating-point arithmetic. IEEE also defines "decimal" based arithmetic which does not suffer from most of these problems (I don't think our `System.Decimal` type is IEEE compliant, but it follows the same principle).

For example, the following program:
```C#
var value = 0.0m;

for (int i = 0; i <= 10; i++)
{
    Console.WriteLine($"{value}");
    value += 0.1m;
}

Produces:

0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1

Applications which require more precise results (such as financial applications) will use the decimal based arithmetic over float/double (which are binary based arithmetic). The program takes longer to run, but will give the more precise results that they need.

Decimal based arithmetic does still have some shortcomings. For example, 1/3 is represented as 0.3333333333333333333333333333 and multiplying 1/3 * 3 ends up with 0.9999999999999999999999999999 rather than 1.0. However, the number of digits that Decimal supports is enough that most applications can account for these small errors by rounding. As an example, a financial application doesn't need 29 trailing digits, they really only need about 4, and rounding 1/3 * 3 will give 1.0 and allow their arithmetic to remain correct.

Then there are applications which require even more precise results (such as scientific applications that are performing data modelling or making extremely precise measurements). For the cases where even decimal doesn't meet their needs, they will end up rolling their own (or using some existing library) that does take care of their needs so that they can precisely compute/model all numbers (rational numbers, irrational numbers, complex numbers, trascedental numbers, etc...).

[HalosGhost]

I would like to add my voice to support this proposal. Rationals are actually incredibly useful for a wide variety of applications (for example, doing arithmetic with currency in a manner that is guaranteed to be accurate). In many cases where people use IEEE754 floats, rationals can be dramatically better.

I would like to suggest a few things though.

First of all, just a stylistic thing, can we please use the terms Numerator and Denominator instead of Number and Divider (which are not standard terms)?

Second, a normalize method will be necessary to simplify a rational to its normal form. This may signal the need for two Rational types at least (one which enforces normalization after each operation) and one which does not. I'm not sure which I would prefer, though I suspect we might want to have the routine always called in operator=.

Third, in an attempt to avoid adding a whole class of exceptions and silly behavior, the fields should really be Numerator and DenominatorLessOne (i.e., treat 0 in the denominator as 1). This actually allows for a wider value range, and eliminates the possibility of divide-by-zero errors. Keeping that property private and exposing a more user-friendly Denominator property is not a problem so long as the constructor does some sane validation.

Fourth, if it is preferred, a rational type can reasonably be defined as an encoding of a single integer as having two parts (and a separate field to track where the separator is). A byte is more than large enough to store where the separation is for a 128-bit total precision rational. This allows for a flexible precision in a Rational type along with reducing the total size required for the type. This does, however complicate the implementation quite a bit which may be something we'd all like to avoid.

I can provide an example Rational class if people would find that useful.

[joshfree]

Just a quick note that there's a rudimentary Rational class from the old bcl codeplex site @ https://github.com/MicrosoftArchive/bcl/blob/master/Libraries/BigRational/BigRationalLibrary/BigRational.cs

@HalosGhost if you're passionate about working on a prototype or example Rational type for .NET Core, a repo for the experiment to happen in could be https://github.com/dotnet/corefxlab

However I do think Rational isn't really suitable for many basic scenarios (that are better supported by existing decimal or double types); the folks that do need a Rational type are likely working on advanced mathematical modeling / simulations / solvers - and have domain specific requirements that would need to be met in order for the type to be usable by them.

/cc @eerhardt

[carlyman77]

Excuse me for being a year+ late, but was anything decided on a big rational? Nearly all these threads I read seem to die off and not lead anywhere. Thanks in advance! @HalosGhost @joshfree

[HalosGhost]

@carlyman77, I have a functional prototype lying around, but I got stuck on deciding how to handle canonicalization. Namely, whether or not a Rational should automatically canonicalize anytime you do anything with it, or if it should instead only be canonicalized during comparisons. there's not necessarily a down-side to the latter, and it saves a fair bit of computational power.

Thoughts?

[carlyman77]

That's a good question. I think during comparison sounds reasonable. (Thanks for responding to me btw, it sounds like you are way in front of where I am - considering writing my own rational.)

There are use cases where accuracy is far more important than performance (my physics project for example), although as @joshfree points out these use cases might be limited (read: not commercial).

[erjicles]

@carlyman77, I have a functional prototype lying around, but I got stuck on deciding how to handle canonicalization. Namely, whether or not a Rational should automatically canonicalize anytime you do anything with it, or if it should instead only be canonicalized during comparisons. there's not necessarily a down-side to the latter, and it saves a fair bit of computational power.

Thoughts?

Just my 2 cents. Every project where I've needed this has required the canonical form, so I'd lean towards always canonicalizing (and maybe for fun, you could also keep the original raw BigInteger numerator and denominator values as separate properties).

Another option is to provide a global static flag that determines the canonicalization behavior. Default it to always canonicalize, but the user can set it to false so that it only canonicalizes when required or explicitly requested.

[erjicles]

PS - If you do implement this, please implement it as BigRational (based on BigInteger) rather than the other integer types. Rationals that don't have arbitrary precision quickly become useless, as most applications that would use them require perfect precision, and most calculations involving them create large numerators and denominators that exceed the precision of the non-BigInteger types.

[Thaina]

Even though I request this feature myself but for such times I have a new idea already but it still not solid

I now think we should not have a struct for rational. Instead we should have class for Number and it's exponent. Represent rational with negative exponent, Then we could represent the number by the array of product

2/3 is [2^1,3^-1] for example and so sqrt(2) is [2^[2^-1]]

Not sure is better or worse

[erjicles]

Even though I request this feature myself but for such times I have a new idea already but it still not solid

I now think we should not have a struct for rational. Instead we should have class for Number and it's exponent. Represent rational with negative exponent, Then we could represent the number by the array of product

2/3 is [2^1,3^-1] for example and so sqrt(2) is [2^[2^-1]]

Not sure is better or worse

I can see use cases for this, but I also see many use cases for a standardized arbitrary-precision rational structure. I don't necessarily see it as either/or. For me personally, a rational object would be more useful, but I could see this being useful in some cases too.

[tannergooding]

If you do implement this, please implement it as BigRational (based on BigInteger) rather than the other integer types

If implemented, a BigRational type would have to be based on BigInteger (given the name). A separate Rational type might be a viable alternative for known small use cases.

Another option is to provide a global static flag that determines the canonicalization behavior. Default it to always canonicalize, but the user can set it to false so that it only canonicalizes when required or explicitly requested.

I don't like the idea of a global flag as they are tricky and can easily introduce bugs. I'd rather instead say that we follow what IEEE 754 does for its decimal types, which is canonical results by default (except for a few operations, such as abs, negate, and copySign, which operate on "bit strings") or that we return non-canonical results by default and require the user to explicitly call a Canonicalize method when they deem that having one is important.

[erjicles]

If you do implement this, please implement it as BigRational (based on BigInteger) rather than the other integer types

If implemented, a BigRational type would have to be based on BigInteger (given the name). A separate Rational type might be a viable alternative for known small use cases.

Indeed. Since the thread is called "Standardized Rational object" and much of the discussion left the nature of the proposed standardized rational object ambiguous, I just wanted to state explicitly that I think an arbitrary-precision BigRational type would be the most useful implementation (though I can see utility for other Rational types in some scenarios).

Another option is to provide a global static flag that determines the canonicalization behavior. Default it to always canonicalize, but the user can set it to false so that it only canonicalizes when required or explicitly requested.

I don't like the idea of a global flag as they are tricky and can easily introduce bugs. I'd rather instead say that we follow what IEEE 754 does for its decimal types, which is canonical results by default (except for a few operations, such as abs, negate, and copySign, which operate on "bit strings") or that we return non-canonical results by default and require the user to explicitly call a Canonicalize method when they deem that having one is important.

Totally fair. I'd lean toward canonical results by default because the canonical form is needed for most uses. At the very least, I would cache the canonical form once computed so that you wouldn't need to calculate it more than once for any given BigRational variable.

[tannergooding]

The next step here would be for someone to propose the public surface area of the Rational or BigRational type (both should realistically be the same public surface area, just replacing one with the other). At a base level, this would involve the following:

• Constructors
• Comparison Operators (==, !=, <, >, <=, >=)
• Comparison Interfaces (IEquatable, IComparable)
• Formatting/Parsing Methods (ToString, Parse, TryParse)
• Unary Operators (+, -, ++, --)
• Binary Operators (+, -, *, /, %)

Other operators (such as ^, &, |, <<, and >>) would likely need to be discussed, but I don't think there is a reasonable implementation. Implicit/explicit conversions for the integer and floating-point primitives would likely need to be discussed (and decided if those or constructors are better).

After that is done, we can likely have a discussion around class vs struct and the proposed API can then be taken forward to API review. The API review process is detailed here: https://github.com/dotnet/runtime/blob/master/docs/project/api-review-process.md, with a "good example" listed under step 1. Not all parts from the good example area required, but providing some basic rationale and the proposed API section are good minimums as they help centralize the proposal and avoid needing to help scrolling around the tracking issue.

[carlyman77]

Happy to start looking into the shape that the type would take (assuming my 1 year old cuts me a bit of slack in the coming days).

FWIW, I prefer the name Rational over BigRational. The initial design I was thinking of working towards was using bit strings until I found a better way to do it.

Edit: invites incoming for collaborators, please ping me if you're keen.