[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Scheme-reports] Strong win later reversed: Real numbers have imaginary part #e0

On Mon, Dec 24, 2012 at 7:51 AM, Mark H Weaver <mhw@x> wrote:
Alex Shinn <alexshinn@x> writes:

> On Sat, Dec 22, 2012 at 2:58 PM, Mark H Weaver <mhw@x> wrote:
>     Alex Shinn <alexshinn@x> writes:
>     > Exact arithmetic can run out of memory.
>     So can your proposed inexacts.  In order to avoid underflow and
>     overflow, the number of representable values cannot be finite,
>     because
>     there can be no maximum or minimum representable magnitude.
>      Therefore
>     the amount of memory needed to represent your numbers is
>     unbounded.  No
>     matter how clever your compression method is, that fact is
>     unavoidable.
> It's not a compression technique, and the amount of
> memory is in practice bounded by the limitations of
> computation.

What external representation will you use for these numbers?  For
example, even if you can efficiently handle something like this:

  (do ((i 10000000 (- i 1))
       (x 1e300 (expt x x)))
      ((zero? i) (/ x)))

What will you do if someone applies 'number->string' to the result?

It will use Conway's chained arrow notation, as mentioned
in my previous mail.

What you're describing here is just tetration:

  (tetrate 1e300 100000000)

which can be written using Knuth's arrow notation as


Note this value reduces to about


which we can see is larger than a Googleplex, but small
enough that we don't even need to bother with Conway's
notation, though in Chibi it may well be written out (after
taking the inverse):


Rules for promoting from one arrow (simple exponentiation),
to two arrows and beyond are non-trivial, and I'm still working
on a system to do this and maintain consistency with as
much accuracy as possible.  I may end up abandoning the
chained arrow notation in favor of simple power towers,
which would make arithmetic and comparisons much simpler
and still probably be impossible to overflow in practice.  By
adding an exponentiation you're just adding 1 to the tetration,
and you'll never practically be able to overflow a Scheme
bignum adding 1 at a time.  The only real reason to use
chained arrows is so that you can represent numbers on the
order of magnitude of Graham's number, but this is so large
as to be incomprehensible, and largely meaningless to perform
arithmetic on.

Being unable to ever overflow also depends on the primitives
provided.  Assuming expt is the most powerful operator, you
can build tetration on top of it but it's still a loop.  If we provide
tetration as a primitive efficiently manipulating
the internal representation, you can build bigger numbers
faster (but still not practically overflow).  However, if we
provide an n-ary hyper operator we can directly construct
chains, and then of course it's straightforward to construct
longer and longer chains until you run out of memory.

Anyway, this is way off-topic.  If you'd like to learn more I
recommend you start a thread on the chibi list, but this is
also a WIP branch which is on the back-burner at the moment.


Scheme-reports mailing list