Factor.js and Rational.js
Non-integer number handling in JavaScript is...somewhat fuzzy. And not in the cute critter kind of way. Some implementations of JS use a variation on IEEE-7541; the standard seems to be that a minimum of 64 bits are used to represent the number2.
Like all floating point systems, inaccuracies quickly creep in — especially when you are trying to produce accurate, human readable answers. One of my projects, which I first implemented in JavaScript as a well known client-side browser language, had to output numbers that were both human readable3 and accurate. This problem was compounded by the fact that the scaling of the numbers was not known in advance: in some case, the numbers might not need a higher resolution than one sixth, but it others, the user would need to be able to differentiate and understand values to the nearest thousand or so.
What all these numbers did in common was that they were rational numbers4, so storing them as such seemed like the logical thing to do.
However, you can quickly run into problems with just storing two integers and performing operations on them, as those integers themselves have a tendency to overflow. When I was working on this originally, I had little time6, and less experience with JavaScript as I have now, so I just left it there
Shortly after the release of Noggle, I began work on a mathematical version of the game, provisionally called ‘Moggle’. The scoring is based on the number of prime factors that a number has, so I had to write a fast, dynamic factorisation library in JavaScript. By making the design to use memory freely, this became a simple task — whenever a pair of factors are found, merge their factor tree.
For the result to be useful in other contexts, however, not only do we need a list of prime factors, but how many times they occur to be collected. This then allows us to concisely represent any integer.
factors.get: function(n)
{
if (n in factors.vals)
return factors.vals[n];
var lim = Math.floor(Math.sqrt(n));
for (i = 2; i <= lim; ++i)
{
if (n % i === 0)
{
factors.vals[n] = factors.merge(factors.get(i), factors.get(n / i));
return factors.vals[n];
}
}
// Create information for a prime
factors.vals[n] = {}; factors.vals[n][n] = 1;
return factors.vals[n];
}
The code iterates over the integers less than or equal to the numbers square root7, and checks if that number is a factor. The other factors functions, such as merge, can be seen in Factors.js over on my GitHub account. The code for prime numbers looks slightly ungainly: Because JavaScript, like many other scripting languages, has mixed associative and indexed arrays. Here, an associative array using numeric indexes is used to map from prime factors to the number of times they occur.
And now, we come back to the rational number problem. I remembered this whilst working on Factor.js, and so changed my objective to create Rational.js which creates a pretty fully featured rational “class”. Numbers are stores as a thruple8 of sign, numerator, and denominator. Each operation then calls the simplify function before returning, which reduces the chance of any integer overflow.
Rational instances9 can be created from a number10
of different string (and, therefore, numerical) formats. You can specify as an
integer ratio, such as -2/3, or a decimal string,
such as 2.364.
For reasons known to only myself when putting this together, decimal approximation is done by the method of creating and then resolving a continued fraction, rather than doing a decimal shift to the left, and having 10n as the denominator. The code is however, configured to only make an approximation to a string in the case where it does not quickly resolve, which will, some of the time perform corrections for dodgy rounding.
This method is not very memory efficient when compared to the more traditional methods of performing a cancellation of a rational number, such as using Euclid's algorithm, which only requires a single variable for storage, rather than a tree of all factors. It's also slower in most cases to perform the array comparisons and merges required by the Factor.js code. However, it remembers the results, and can reuse it. This reduces the time any repeated calculations will take, which is an advantage in some processing situations.
- 1 ↑ http://msdn.microsoft.com/en-us/library/ie/7wkd9z69(v=vs.94).aspx
- 2 ↑ http://www.hunlock.com/blogs/The_Complete_Javascript_Number_Reference
- 3 ↑ i.e. not 0.6 + 0.1 = 0.699999999873
- 4 ↑ For those who don't remember their mathematics lessons, rational numbers are numbers which can be represented as the ratio of two integers5.
-
5
↑
Note that not all values that are taken to be the ratio of two
integers is necessarily a rational number: infinity is not rational, but it
is often given that
.
- 6 ↑ Exams! :O
- 7 ↑ If the number is not prime, at least one factor must be in this range
- 8 ↑ That's totally a valid term for a 3-tuple, right?
- 9 ↑ A phrase which I one day hope to apply to humans, perhaps?
- 10 ↑ Two is a number