perlmeditation
grondilu
<p>Hello monks,</p>
<p>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.</p>
<p>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:</p>
<code>my constant pi = 3.14159_26535_89793_238e0;</code>
<p>Honnestly, I would have expected a bit more than that from perl6.</p>
<p>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.</p>
<h2>Definition</h2>
<p>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.</p>
<p>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 <a href=http://rosettacode.org/wiki/Continued_fractions>this Rosetta Code task</a>, where irrationals such as pi or sqrt(2) are defined with continued fractions (which are a particular case of infinite lists of rationals)</p>
<p>Here is an other example, also <a href=http://rosettacode.org/wiki/Sum_of_a_series>from Rosetta Code</a>:</p>
<code>sub zeta($s) { [\+] map -> \n { 1 / n**$s }, 1..* }
say zeta(2)[1000];</code>
<p>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.</p>
<p>Any infinite list would do, providing that it converges. You can use a Taylor-series for instance.</p>
<p>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.</p>
<h2>Arithmetic</h2>
<p>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:</p>
<code>sub infix:<+>(Irrational $x, Irrational $y) {
Irrational.new: gather while True {
(state $n)++;
take $x[$n] + $y[$n];
}
}</code>
<p>Couldn't it be as simple as that?</p>
<h2>Equivalence and order relations</h2>
<p>That might be the thoughest problem.</p>
<p>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.</p>
<p>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:</p>
<pre>
- 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?
</pre>
<p>And so on.</p>
<p>A naïve implementation would thus be:</p>
<code>sub infix:<==>(Irrational $x, Irrational $y) {
while True {
(state $n)++;
return $x[$n] == $y[$n];
}
}</code>
<p>Unfortunately, there are several reasons why this could not be convenient. But that would be a start.</p>
<h2>Conclusion</h2>
<p>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.</p>
<p>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 <a href=http://en.wikipedia.org/wiki/Kerbal_Space_Program>Kerbal Space Program</a>:</p>
<blockquote>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.</blockquote>
<p>I know this game is not open source and it's not written in Perl, but someone might be willing to write something similar.</p>
<h2>Update: small example</h2>
<p>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.</p>
<code>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);
</code>