This is mainly about my BigDecimal implementation in JavaScript.
One of the things I found out while writing that script is that multiplication provided correct values only when the number of digits in each part was no greater than 7. 7 digits * 7 digits = 14 digits, perfectly. 8 digits * 8 digits = problems. (With sixteen digits in a number value, you get funny results.)
So, I specifically coded BigDecimal not to store any final results in sections more than 7 digits. The gist of the mathematical operation was:
for (a = 0; a < this.digitArray.length; a++) {
for (b = 0; b < rightSide.digitArray.length; b++) {
response.digitArray[a + b + offset] += this.digitArray[a] * rightSide.digitArray[b]
}
}
Well, in revisiting the concept, I realized this afternoon that I didn't have to be quite that tight. If you have:
p = a + b, where a = n * 10^7 and b = some other n (< 10^7)
and also q = c + d, where c and d have corresponding values, then:
p * q = (a + b) * (c + d)
Breaking this down, it becomes:
p * q = (n_a * n_c) * 10^14 + ((n_a * n_d) + (n_b * n_c)) * 10^7 + (n_b * n_d)
(n_a * n_c) simply gets shifted one section to the left, so we don't have to worry about that. What should I do with the other three values, which could easily total over 10^14 anyway?
Well, there's no need to directly set a section's value, is there? Why not have a special function handle that, and when it detects a condition that would lead to an out-of-bounds value, handle it? That would eliminate the need for after-the-fact carrying operations.
for (a = 0; a < this.digitArray.length; a++) {
for (b = 0; b < rightSide.digitArray.length; b++) {
var this_1stHalf = Math.floor(this.digitArray[a] / 10000000);
var this_2ndHalf = this.digitArray[a] % 10000000;
var right_1stHalf = Math.floor(rightSide.digitArray[a] / 10000000);
var right_2ndHalf = rightSide.digitArray[a] % 10000000;
// addValue does our carry operations
response.addValue(a + b + offset - 1, this_1stHalf * right_1stHalf);
response.addValue(a + b + offset, this_1stHalf * right_2ndHalf * 10000000);
response.addValue(a + b + offset, this_2ndHalf * right_1stHalf * 10000000);
response.addValue(a + b + offset, this_2ndHalf * right_2ndHalf);
}
}
With that done, I could safely double the length of digits back up to 14, and thus double the number of digits the script could handle.
As an afterthought: with the integral types D provides, I don't have to do Math.floor() operations.
Oh, and that bitrot happens bit in the title? Well, I took one look at the coding style of the BigDecimal.js script as I posted it, and I could only stare in amazed horror. It works, but there's no way I'd write it that way now...
Posted by WeirdAl at September 27, 2004 2:23 PM