Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??

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];

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]; } }

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]; } }

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);

In reply to Irrational numbers by grondilu

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others making s'mores by the fire in the courtyard of the Monastery: (10)
    As of 2014-07-28 11:51 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      My favorite superfluous repetitious redundant duplicative phrase is:









      Results (196 votes), past polls