1

We can not store a decimal in infinite precision, but there may be some way to represent them just like we represent infinite lists in haskell.

The first idea came to me is to represent a decimal number via something similar to Codata, so that for any given natural number k, we can calculate the decimal number precise to k digits.

But there is some obvious problem, think about the number a = 0.333... and b = 0.666... , if we plus them together, we got ans = 0.999... (a sequence of digits) , but we can never tell whether a + b == 1 in this case.

What I want is, to define the decimal number somehow, so that it support the +, -, *, /, >, == operations, and no matter what +, -, *, / operation we applied to these decimal numbers, we get new decimal numbers, which we can calculate them precise to k digits given any natural number k.

I'm wondering: is there any idea which may work this out?

luochen1990
  • 3,689
  • 1
  • 22
  • 37
  • 1
    Have you seen http://hackage.haskell.org/package/cyclotomic? – jkeuhlen Feb 22 '17 at 18:38
  • 3
    I'm not sure your requirements are well-defined. It's possible `Rational` is what you're looking for; it supports all those operations without losing precision (you won't be able to construct an irrational number with them) – jberryman Feb 22 '17 at 18:55
  • 2
    More generally, you can never do "x == y" because no matter how many digits you calculate you can never be sure that the next one won't differ. The practical solution seems to be to have families of numbers so that programmers can pick the one they want. – Paul Johnson Feb 22 '17 at 19:30
  • @PaulJohnson I think the OP's reasoning is to (for example) store numbers as two lists of digits before and after the `.`. Then, if either of the lists is finite, `==` won't diverge. I agree with the spirit of your comment though. I would even add that "families" should be designed to be closed under a set of (not imprecise) operations. `Rational` is closed over the operations in `Fractional`, for example. – Alec Feb 22 '17 at 19:38
  • 1
    @Alec Unfortunately, `==` can still diverge even if only one list is infinite. For example, `1 = 0.9999...` should never return `False` (and ideally would return `True`, but not with the obvious infinite list of digits approach). `Rational` is fine if you expect both lists to be finite (or repeating). – Daniel Wagner Feb 22 '17 at 19:39
  • @Alec: While I'm not up on category theory, the term "codata" suggests a potentially infinite representation. However I agree about the need for these families to be closed over at least Num, and possibly Fractional. I seem to recall reading about a family of transcendental numbers closed over Num that is based on the square root of 2, which would be a good example if only I could find it. – Paul Johnson Feb 22 '17 at 19:41

1 Answers1

6

Haskell offers Rational, Cyclotomic, and CReal for doing exact arithmetic.

CReal, the computable reals, comes about as close as it's possible to come to representing real numbers on a machine; just about any stupid real number you can think up and describe can be stuffed into a CReal. The tradeoff of being able to represent so many things is that your power of observation is severely limited. Checking for equality, checking whether one is bigger than another, even knowing for sure what the first digit should be are technically undecidable problems; though the package provided on Hackage provides approximation algorithms for all of these observations.

Cyclotomic can represent a much smaller chunk of the reals, and can represent a fair chunk of the complex numbers, all while retaining exact computation, and supports many more observations in a decidable way. Much of the stuff you want to do can be done with cyclotomic numbers.

Rational represents all the numbers that can be written as fractions. This is a significantly smaller chunk of the reals than CReal or Cyclotomic: square roots (and other roots) are pretty much out, trigonometric functions are pretty much out, pi and e are out, etc. But the observations are correspondingly more efficient than for CReal and Cyclotomic, so they are sometimes just the ticket.

...of course, if efficiency matters, Double is going to blow all of these out of the water with today's hardware. Choose your poison carefully!

Daniel Wagner
  • 145,880
  • 9
  • 220
  • 380
  • 1
    Where (i.e. in which Hackage package) is this `CReal` type which represents [computable reals](https://en.wikipedia.org/wiki/Computable_number)? Perhaps you meant ['constructive'](https://hackage.haskell.org/package/numbers-3000.2.0.1/docs/Data-Number-CReal.html#t:CReal)? (Great answer, I am just genuinely curious if there is a well-known Haskell implementation of computable reals which I've managed to not know about all this time...) – user2407038 Feb 23 '17 at 01:02
  • @user2407038 As far as I know, "constructive reals" is a synonym for "computable reals". – Daniel Wagner Feb 23 '17 at 01:06
  • My understanding is that 'constructive' reals have the property "knowing for sure what the first digit should be [is] technically undecidable" (as you stated in the answer) at least for an arbitrary constructive real, but 'computable' reals have the property "we can calculate them precise to k digits given any natural number k." (as stated in the OP). Constructive reals represent the actual set of reals, whereas computable reals are only a (dense) subset of the reals. These two are different, but I am uncertain to which of them the `data CReal = CR (Int -> Integer)` corresponds. – user2407038 Feb 23 '17 at 01:13
  • @user2407038 The definition of computable reals at the Wikipedia link you provide does not appear to agree with what you say. (Beware the misleading informal definition given at the top -- go straight to the formal definition!) It merely says that given an error bound we can find a rational within that bound of the true answer. This is not enough to choose the first digit correctly: consider the function that takes an error bound e and returns `0.5-e/2`. This represents the number `0.5`, but there is no error bound we can run this function on to decide whether the first digit should be 4 or 5. – Daniel Wagner Feb 23 '17 at 01:25
  • If we have a computable real `a`, to discover its `k`th digit, is it not enough to compute the rational `r` approximating it to within `10^(-k-1)`? e.g. we pick `e = 0.001` and then the approximation is `0.4995`. The actual value is `0.4995 +- 0.001` which is between `0.4994` and `0.4996`. – user2407038 Feb 23 '17 at 02:44
  • @user2407038 No, `0.4995 +- 0.001` is between `0.4985` and `0.5005`. – Daniel Wagner Feb 23 '17 at 02:46
  • Oops (arithmetic is hard...) thanks for the discussion, looks like I've got some gaps to fill in my understanding. (I leave my silly comments for the posterity of future readers) – user2407038 Feb 23 '17 at 05:44