On Mon, Dec 24, 2012 at 7:51 AM, Mark H Weaver <[email protected]> wrote:
> Alex Shinn <[email protected]> writes: > > > On Sat, Dec 22, 2012 at 2:58 PM, Mark H Weaver <[email protected]> wrote: > > > > Alex Shinn <[email protected]> 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
_______________________________________________ Scheme-reports mailing list [email protected] http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports
