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

1e300^^10000000

Note this value reduces to about

1e2.7e3010302

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

1/1e300->1e7->2

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.

Alex