My integers in Ruby (MRI) refuse to overflow. I've noticed the class change from fixnum to bignum but I'm wondering how this is modeled and what sort of process ruby uses to perform arithmetic on these massive integers. I've seen this behaviour in SCHEME as well as other environments.
I ask because I'd like to implement something similar in a C program and would like to know how bignum + bignum reduces to primitive operations.
Any pointers?
Erlang does this as well. You can take a look at the source code (in C) in the erl_interface module.
Basically, it boils down to long-addition/multiplication/division/subtraction. There are a lot of optimizations that can be done from there (duh), so rolling your own isn't really recommended. I'd recommend checking out the GMP (gnu multi-precision) project, which static or dynamic links into your app. It's not hard to use, but there's a few C++ and other wrappers for it that let you work with it more simply. If you're doing floating point stuff, get MPFR, which handles rounding properly.
Python also does this.
Basically, instead of treating a number as a string of bits that naturally fits the hardware architecture, (32 bits for instance) it treats a number as a string of 32-bit digits, then implements all the arithmetic operations to handle carries from one 32-bit digit to another. That also involves allocating additional 32 bit digits as the number grows longer. This is easier than it seems.
For instance, 99 * 99 is less that 100 * 100 which is 10,000, therefore one might assume that multiplying two 2-digit numbers will produce a result no longer than 4 digits. Same thing applies when each digit is a 32-bit word.
You might want to try implementing this in Ruby, just for fun, using some type that allows fixed binary quantities. I believe the FixNum class would work.
Look at section 20.6 in the Numerical Recipes for C book: http://www.nrbook.com/a/bookcpdf.php
It's a great implementation of arbitrary precision math. If you wanted to get fancy you'd make a C++ class that overloads the operators and then implements these functions. Or you can just call them directly.