Irrational numbers

Hello monks,

as far as I know there is no such thing as an irrational number in computing. And by this I mean: a number that has an infinite number of non repeating decimals. Or in other words, a number that is real, but that is not rational.

I think it's a bit frustrating. Computers should have a more accurate representation of real numbers. Even in a programming language as awesome as perl6, pi for instance is still defined with a decimal approximation:

my constant pi = 3.14159_26535_89793_238e0;

Honnestly, I would have expected a bit more than that from perl6.

I'm not sure it would be useful but I don't care much. It would be cool and that's what matters to me :) And what's cool but apparently useless often appears to be quite useful eventually, so it's worth considering doing it even if we don't see any immediate use for it. Anyway I'd like to discuss how I imagine it could be done.

Definition

In maths, one way of defining a real number is to define it as the limit of a sequence of rational numbers. If this sequence is constant above a certain rank or if the limit is actually a rational number, then the number is rational. Otherwise, it is said to be irrational.

Infinite sequences are not hard to define in computing, providing you feel comfortable with the notion of closures or lazy lists. Therefore a way of defining a real number would be to use exactly this: a lazy list or a closure, just as in this Rosetta Code task, where irrationals such as pi or sqrt(2) are defined with continued fractions (which are a particular case of infinite lists of rationals)

Here is an other example, also from Rosetta Code:

sub zeta($s) { [\+] map -> \n { 1 / n**$s }, 1..* }
say zeta(2)[1000];
[download]

Here we define the zeta function as a function returning a lazy list, and we display the thousandth term of the list returned by the call of zeta with two as an argument.

Any infinite list would do, providing that it converges. You can use a Taylor-series for instance.

You can even imagine using non converging sequences. Who knows, maybe it could be useful. They could appear in the middle of a calculus and then disappear in the end. Kind of like whith imaginary numbers. But that's an other story.

Arithmetic

It seems to me that arithmetic should not be too difficult to define. For instance, the addition operator would be a function that takes two lazy lists and returns a lazy list whose terms are the sum of the terms of the lazy lits. In Perl6, I'd write it like this:

sub infix:<+>(Irrational $x, Irrational $y) {
    Irrational.new: gather while True {
        (state $n)++;
        take $x[$n] + $y[$n];
    }
}
[download]

Couldn't it be as simple as that?

Equivalence and order relations

That might be the thoughest problem.

There is no simple way for a computer to tell if two infinite lists are equals. Unless of course it can make a deduction from an analytic definition of the terms. But in the general case, the computer just can't inspect all the terms one at a time because if the two lists are actually equals, then the computer will need the eternity to reach a conclusion.

So just as arithmetic operators on irrationals would return a lazy list of rational numbers, a equivalence relation operator on irrationals would return a lazy list of booleans. Like in real life, when you ask something to someone but you're not sure about his answer:

- Do you think that's true ?
- Yes, it's true.
- You're really sure?
- Hang on, let me check again.  Yes, it's true.
- Really, really sure?

And so on.

A naďve implementation would thus be:

sub infix:<==>(Irrational $x, Irrational $y) {
    while True {
        (state $n)++;
        return $x[$n] == $y[$n];
    }
}
[download]

Unfortunately, there are several reasons why this could not be convenient. But that would be a start.

Conclusion

I told you how I think irrational numbers could be implemented in Perl or Perl6. I won't say more, and I'll just read what you think of it. I really think it would be cool if we could just have a "Real" number type that would fill all use cases.

One possible application would be for programs that have to deal with very wild ranges of values, without loss of any precision. The example I have in mind is programs such as the Kerbal Space Program:

The unique necessities of the game, which has to correctly handle distances in a range of at least 13 orders of magnitude and velocities in the order of kilometers per second, have required a number of workarounds to avoid numerical stability issues. Fixing all the known bugs of this nature took multiple updates over a period of months.

I know this game is not open source and it's not written in Perl, but someone might be willing to write something similar.

Update: small example

Here is a toy example module where I define addition, multiplication and display up to an arbitrary precision. Then I define one, the exponential and arctangent functions, and then I compute and display two, three, e, e+one, e*e and pi.

package Real;

# the accuracy number below is only for display.
# It does not affect the (infinite) precision of the numbers.
our $accuracy = 1e-3;

use overload '+' => sub {
    my ($a, $b) = map { $_->() } my ($x, $y) = @_;
    bless sub { sub { $a->() + $b->() } }, ref $x;
},
'*' => sub {
    my ($a, $b) = map { $_->() } my ($x, $y) = @_;
    bless sub { sub { $a->() * $b->() } }, ref $x;
},
q{""} => sub {
    my $x = shift->();
    my $a = $x->();
    my $b;
    while (abs($a - ($b = $x->())) > $accuracy) {
        $a = $b;
    }
    return "$b (ą$accuracy)";
},
;

1;

package Test;
my $one = bless sub { sub {1} }, 'Real';
sub Exp {
    my $x = shift;
    bless sub {
        # Here I use floating points for convenience
        # but obviously I should use only rationals.
        my ($s, $p, $n) = (1, 1, 1);
        sub { $s += $p *= $x / $n++ }
    }, 'Real';
}
sub Arctan {
    my $x = shift;
    bless sub {
        # same remark here about the use of floating points
        my ($s, $p, $n) = (0, 1, -1);
        sub { $s += (-1)**++$n * ($p *= $x) / (2*$n + 1) }
    }, 'Real';
}

print $one, "\n";
print my $two = $one + $one, "\n";
print my $three = $two + $one, "\n";
print my $e = Exp(1), "\n";
print $e + $one, "\n";
print $e * $e, "\n";
print ($three + $one) * Arctan(1);
[download]

Comment on Irrational numbers Select or Download Code

Replies are listed 'Best First'.
Re: Irrational numbers by tobyink (Canon) on Dec 17, 2012 at 21:05 UTC
Certain irrational numbers have a compact but useful representation; for example the square-root of two can be represented as `bless(\'2 ** 0.5', 'Surd')`. A suitably smart implementation of the `Surd` class could figure out that root-2 times 3-root-2 equals 6 without resorting to floating point arithmetic. The problem with π is that it's not just irrational; it's transcendental. There's no convenient, accurate representation of it. You've just got to store an approximation as a float or string or whatever, and it will only be accurate to a certain number of decimal places. `perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'`	[reply] [d/l] [select]
Re^2: Irrational numbers by grondilu (Friar) on Dec 17, 2012 at 22:20 UTC
I'm afraid you missed the point I was trying to make. Pi could be represented as a lazy yet infinite list of rationals converging towards pi. So could any irrational numbers, including those who are transcendental. Representing real numbers seems like a very natural use case of lazy lists.	[reply]
Re^3: Irrational numbers by tobyink (Canon) on Dec 18, 2012 at 08:35 UTC
Let's say you want pi to a million digits. Using a lazy list populated by the Machin's formula will take you several hours of calculation. But a hard-coded decimal representation of a million digits will take less than a megabyte of memory/disk space, even if inefficiently stored as one digit per byte and can be retrieved virtually instantly. In practice, there's little reason to need that sort of precision. A 64-bit float has about 20 decimal digits of precision, which is enough to calculate the circumference of the Earth to less than a hair's breadth. Apparently 61 digits of pi is enough to calculate the circumference of the observable universe to within one Planck length. In practice, floats are simply good enough for most purposes. `perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'`	[reply]
Re: Irrational numbers by BrowserUk (Patriarch) on Dec 18, 2012 at 00:29 UTC
One possible application would be for programs that have to deal with very wild ranges of values, without loss of any precision. The example I have in mind is programs such as the Kerbal Space Program: The KSP simulation fudges the calculations around the N-body problem in order to ensure that the simulation can be run at a pace that makes the game play possible. Performing those calculations using your lazy lists would be so slow that it would make the game impossible to play. And there is one reason why no one uses such representations. Another is: how would you ever decide when to stop calling for more digits... Floating point reals are used to calculate real trajectories; like those that took men to the moon and the Voyager missions on their grand tour passed Jupiter, Saturn, Uranus and Neptune; and to allow the Deep Space Network to still find them and receive their signals after 35 years and 10 billion miles. Seems good enough to me. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. RIP Neil Armstrong	[reply]
Re^2: Irrational numbers by grondilu (Friar) on Dec 18, 2012 at 01:27 UTC
It might indeed have a big cost in performance, though it's not so obvious. When adding two real numbers, there would be no computation whatsoever until an actual approximation of the result is requested. It could require lots of memory though, since there is a creation of a new closure (with all its context) for each arithmetic operation. Ť Another is: how would you ever decide when to stop calling for more digits... ť This really is not an issue. It's like entering a drugstore and complaining about how there is too much choice. Accuracy would only affect numerical comparison and approximations. You can use a fixed value if you want. It depends on what you want to do with your numbers. The important thing is that it won't affect the way the calculations are done. Or in other words, it won't affect the result, only the way you show it. Say you have a spaceship in a circular orbit around the sun with about an hundred thousands of millions of meters radius. That's about 150e9 meters. And you want to compute the position to a precision of the millimiter, because you worry about space debris for instance, or because you need to do some very advanced docking, or whatever). That would involve using angles as small as 6e-15 radians. So you'll need about 15 decimals of pi for you calculations. You wouldn't have to worry about that with an exact definition of pi. You would just make the calculations, and request a result with a millimeter precision. At no point you would have to worry about changing the definition of pi.	[reply]
Re^3: Irrational numbers by BrowserUk (Patriarch) on Dec 18, 2012 at 10:13 UTC
Say you have a spaceship in a circular orbit around the sun ... and request a result with a millimeter precision. Sorry, but your misunderstandings are legion. It would be impossible to pre-calculate such an encounter, regardless of the precision of the calculations. The gravitational field of the Sun is neither uniform nor constant; and we do not yet have, and never will have, an accurate mapping of it; nor any way to produce one. For a start, in order to produce such a map, it would be necessary to have an identifiable reference point or line, but the Sun's surface and its interior rotate at different speeds; and the surface rotates at different speeds relative to latitude, with the poles rotating almost 50% faster than the equator. The surface is constantly changing so there is no way to denote a fixed reference point. In addition, solar radiation has a profound affect upon small craft in orbit around the Sun; and it is entirely unpredictable. These, and many other factors, are why all long distance space flights have in-transit correction burns built into them. Not to correct for inaccuracies in precalculations; but rather to correct for the unknowable and unpredictable affects of gravitational perturbations and variable solar pressures. And that is why all docking maneuvers in space require either manual corrections or programmed, active corrections using vehicle to vehicle sensing during final approach. The polite assessment of your idea is that it is a solution looking for a problem to solve. If implemented, it would at best be, an unnecessary drain on computing resources; at worst, completely pointless. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. RIP Neil Armstrong	[reply]
Re^4: Irrational numbers by grondilu (Friar) on Dec 18, 2012 at 12:27 UTC
Re^5: Irrational numbers by BrowserUk (Patriarch) on Dec 18, 2012 at 13:18 UTC
Some notes below your chosen depth have not been shown here
Re^3: Irrational numbers by tobyink (Canon) on Dec 18, 2012 at 10:20 UTC
A 64 bit float already gives you almost 20 significant figures; which should be sufficient for this use case. Besides which, the metre itself is defined with reference to the speed of light, which has not been measured to a precision of anywhere near 20 significant figures. `perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'`	[reply]
Re^3: Irrational numbers by Anonymous Monk on Dec 18, 2012 at 15:05 UTC
It might indeed have a big cost in performance, though it's not so obvious. You are competing against something that the hardware can do in as little as one cpu cycle. No matter what you do, it will have a huge performance penalty, percentage wise.	[reply]
Re^4: Irrational numbers by BrowserUk (Patriarch) on Dec 18, 2012 at 16:04 UTC
Re: Irrational numbers by syphilis (Archbishop) on Dec 18, 2012 at 03:01 UTC
Computers should have a more accurate representation of real numbers Interesting idea - and well worth raising. Perhaps related (but also a little different) is Interval Arithmetic. Just set your precision, do your calculations, and you end up with an upper and lower bound (for the given precision/inputs) - within which the exact value lies. I've played with a C library, and a perl extension (that I wrote) that wraps that C library .... but only played. Cheers, Rob	[reply]
Re^2: Irrational numbers by grondilu (Friar) on Dec 18, 2012 at 12:03 UTC
I would almost certainly need that. To display the result up to a certain accuracy, I assumed in the code above that the distance between two consecutive terms gets smaller and smaller. It's always possible to find a subsequence with such a property so we can define all reals as such. I'm not sure this property is conserved with the arithmetic operations as defined above. So I would need a rigorous way of dealing with the sum or product of terms whose precision is known up to a given accuracy. So: thanks, that'll be useful if I ever want to implement this thing for real.	[reply]


"be consistent"
	PerlMonks