What is BigDecimal, and Why Do I Care?
Ever wonder why Ruby's BigDecimal works?
Try this in your Ruby console:
0.1 + 0.2 == 0.3
# => falseThis isn’t a Ruby quirk. It’s a fundamental limitation of how computers represent decimal numbers using binary floating-point arithmetic. The problem affects every programming language that uses IEEE 754 floating-point numbers - which is nearly all of them.
In fact, you can find an exhaustive reference at the cleverly named https://0.30000000000000004.com/, from ABAP to zsh.
You’ve likely heard that you should use decimal data types instead of floating-point numbers for handling, say, currency values. (If you haven’t heard, you have now.)
Spoilers: in this article, we will discuss the implementation of BigDecimal gem - part of the Ruby standard library, and Ruby’s solution to this particular problem. We’ll do so by implementing progressively more complex versions of the algorithm, and we’ll eventually compare our results with BigDecimal itself. In truth, the algorithm behind BigDecimal is more familiar than you might guess - there’s a lot of special cases and optimizations, but we can get an intuitive feel for it pretty quickly.
Why Not Float?
Like most languages, Ruby’s Float type uses binary floating-point arithmetic. Also like most languages, Ruby Float types for any literal value that’s 1) numeric and 2) has a . in it.
Like so:
irb> 1.class
=> Integer
irb> 1.0.class
=> FloatThis can sometimes have confusing results; for example:
2 / 3
# => 0
2 / 3.0
# => 0.6666666666666666
2.0 / 3
# => 0.6666666666666666If you’ve ever seen someone write an seemingly unnecessary .0 in a numeric literal, it’s likely because they were trying to force a float division instead of an integer one. Of course, this isn’t the only way - any way you cast to a float works - but its likely the most common.
Anyway, while efficient, it cannot precisely represent many decimal fractions:
price = 10.0
tax_rate = 0.0825
total = price * tax_rate
# => 0.8250000000000001
# Rounding errors compound
(0.1 + 0.2) * 3
# => 0.9000000000000001For many purposes, this isn’t really a problem; a tiny error doesn’t effect many types of calculations. The big problem is expectations; people don’t expect binary rounding errors - they expect decimal rounding errors.
Fortunately, that’s just what BigDecimal provides.
BigDecimal provides arbitrary-precision decimal arithmetic. It represents numbers in decimal form with user-specified precision, eliminating floating-point rounding errors - like so: :
require 'bigdecimal'
price = BigDecimal("10.0")
tax_rate = BigDecimal("0.0825")
total = price * tax_rate
# => 0.825e0 (exactly 0.825)
# Comparisons work as expected
BigDecimal("0.1") + BigDecimal("0.2") == BigDecimal("0.3")
# => trueOf course, this leads to a logical question - one posed in the title of this article.
A Naive Approach
An naive solution might be storing the entire value as a decimal string. You could, indeed, use an algorithm similar to what children are taught to do in schoool - or perhaps what some of you do in your head, at least until you purchased a mobile phone and realized you could let your arithmetic skills (and quite possibly civilization) decline.
Specifically, something like this:
- First, line up the digits.
- Start looping through the rightmost digits.
- Add them together.
- If the result is greater than 10, subtract 10 and set carry to 1; if not, set carry to 0.
- Write the result to the output.
- Continue the loop, adding one whenever the carry bit is set.
- At the end of the loop, if the carry bit is set, add a leftmost one.
As noted, this is likely how you learned to do multiple digit arithmetic in school; there are other algorithms, such as for use with an abacus or for adding binary digits with logic gates, but this is a simple and familiar one.
Implemented in Ruby, that looks something like this:
class DecimalArithmetic
def initialize(value)
@value = value.to_s
end
def +(other)
other = DecimalArithmetic.new(other) unless other.is_a?(DecimalArithmetic)
a_str, b_str = normalize(@value, other.value)
result = []
carry = 0
(a_str.length - 1).downto(0) do |i|
digit_a = a_str[i] == '.' ? nil : a_str[i].to_i
digit_b = b_str[i] == '.' ? nil : b_str[i].to_i
if digit_a.nil?
result.unshift('.')
next
end
sum = digit_a + digit_b + carry
carry = sum / 10
result.unshift((sum % 10).to_s)
end
result.unshift(carry.to_s) if carry > 0
# Remove leading zeros (except before decimal or if it's the only digit)
while result.length > 1 && result.first == '0' && result[1] != '.'
result.shift
end
# Remove trailing zeros after decimal point
if result.include?('.')
while result.last == '0'
result.pop
end
# Remove decimal point if no fractional part remains
result.pop if result.last == '.'
end
result_str = result.join('')
DecimalArithmetic.new(result_str)
end
def to_s
@value
end
protected
attr_reader :value
private
def normalize(a, b)
a_parts = a.split('.')
b_parts = b.split('.')
a_int, a_dec = a_parts[0], a_parts[1] || ''
b_int, b_dec = b_parts[0], b_parts[1] || ''
max_int = [a_int.length, b_int.length].max
max_dec = [a_dec.length, b_dec.length].max
a_int = a_int.rjust(max_int, '0')
b_int = b_int.rjust(max_int, '0')
a_dec = a_dec.ljust(max_dec, '0')
b_dec = b_dec.ljust(max_dec, '0')
a_normalized = max_dec > 0 ? "#{a_int}.#{a_dec}" : a_int
b_normalized = max_dec > 0 ? "#{b_int}.#{b_dec}" : b_int
[a_normalized, b_normalized]
end
endNote that for demonstration purposes, this only implements the + operator - the code for the others is, as you no doubt imagine, more complex. (We also skipped handling negative numbers, validation, and a few other things, but this is already long enough as it is!)
Anyway, the first thing our code for the + operator does is call the normalize method. This ensures that the two strings are the same length by padding the beginning and end of the integer and decimal part of the shorter string; this is vital, because the rest of our code assumes that the Nth digit of string A is the same scale as the Nth digit of string B.
After that, our code proceeds straightforwardly, at least more or less. It loops through each digit, starting with the rightmost (i.e. smallest) digit. Much like you may have done as a child, it adds them together; it then divides the result by ten and carries that over to the next digit. You’ll note that, similar to our code earlier, this is / 10, not / 10.0; this means integer, not float, division; we could also do something like /10.0).floor, which does float division and then just rounds down, but that’s a bit more complex and not necessary.
The remainder is then used as the digit for this position.
As we go through the loop, when we encounter a ., we skip to the next digit. Since we have lined up the numbers using normalize, the . should occur on both numbers simultaneously.
Once we’ve looped through all the digits, we’re almost done. If we have a carry digit left, that means we need to add a leading 1; after that, we drop any unnecessary leading zeros or trailing zeros, join the digits together, and we’re good to go.
(As an aside, a particularly pedantic reader might note I have in this text and the code uses “digit” to refer to both numbers and the ’.’ marker, which is, technically, not a digit; hopefully you’ll forgive my lack of interest and repeatedly writing “digit and decimal place” everywhere.)
Lets take this class for a quick spin:
DecimalArithmetic.new('3.5') + 2
=> #<DecimalArithmetic:0x00007f4a780ba198 @value="5.5">Not terribly exciting, but it does work; you can try a variety of positive values and you should get the expected results.
One might wonder - what’s the performance look like?
Let’s find out:
require 'benchmark'
require 'bigdecimal'
require_relative 'decimalarthimetic'
values = [
["0.1", "0.2"],
["123.456", "789.012"],
["0.0001", "0.9999"]
]
iterations = 4096
puts "Decimal Arithmetic Benchmark - #{iterations} iterations"
puts "=" * 40
values.each do |a_str, b_str|
puts "#{a_str} + #{b_str}"
decimal_a = DecimalArithmetic.new(a_str)
decimal_b = DecimalArithmetic.new(b_str)
bigdecimal_a = BigDecimal(a_str)
bigdecimal_b = BigDecimal(b_str)
float_a = a_str.to_f
float_b = b_str.to_f
Benchmark.bm(15) do |x|
x.report("DecimalArithmetic") { iterations.times { decimal_a + decimal_b } }
x.report("BigDecimal") { iterations.times { bigdecimal_a + bigdecimal_b } }
x.report("Float") { iterations.times { float_a + float_b } }
end
puts
endRunning our script, we get this result:
Decimal Arithmetic Benchmark - 4096 iterations
========================================
0.1 + 0.2
user system total real
DecimalArithmetic 0.019192 0.000888 0.020080 ( 0.020264)
BigDecimal 0.000839 0.000000 0.000839 ( 0.000843)
Float 0.000101 0.000000 0.000101 ( 0.000101)
123.456 + 789.012
user system total real
DecimalArithmetic 0.028990 0.000010 0.029000 ( 0.029080)
BigDecimal 0.000831 0.000000 0.000831 ( 0.000834)
Float 0.000098 0.000000 0.000098 ( 0.000097)
0.0001 + 0.9999
user system total real
DecimalArithmetic 0.028436 0.000000 0.028436 ( 0.028531)
BigDecimal 0.001098 0.000000 0.001098 ( 0.001101)
Float 0.000102 0.000000 0.000102 ( 0.000102)
Your exact numbers will vary, of course, but we can observe a few things here; firstly, that our DecimalArithmetic approach is very, very slow - in the first test, 24 times slower than BigDecimal and 200 times slower than Float. Of course, BigDecimal is still slower than Float - 8.3x slower or so - but dramatically faster than our String-based implementation.
The reason for that, of course, is that this is not, in fact, how BigDecimal works - as you likely already surmised.
Biggish Decimals
BigDecimal doesn’t work with strings - thats not a particularly fast algorithm - it works with arrays of numbers.
Note, though, that for performance reasons, BigDecimal doesn’t work with arrays of base 10 numbers - instead, it works with arrays of base 10000 or base 1000000000 numbers, depending on whether you are on a 32-bit or 64-bit system. Both of these numbers, though, are powers of 10 - and they fit neatly within a 32 bit or a 64 bit integer.
This means we can use CPU native integer arithmetic on each “chunk” of digits - 10000 or 1000000000 - and get significant performance increases.
Now, the actual source code of BigDecimal is largely in C and is quite optimized - which is great for performance, of course, but a somewhat tough read. For the sake of discussion, lets “re-implement” a simplified version of BigDecimal - call it BiggishDecimal.
As with the DecimalArithmetic class before, we will make some adjustments to keep it short: we’ll only implement addition, we’ll stick with base-10000, we’ll ignore sign, and so on.
Lets take a look at the class:
class BiggishDecimal
DECIMAL_PLACES = 50
BASE = 10000
BASE_DIGITS = 4
def initialize(value)
@value = value.to_s
@mantissa, @exponent = parse_number(@value)
end
def +(other)
other = BiggishDecimal.new(other) unless other.is_a?(BiggishDecimal)
result_mantissa, result_exponent = add_magnitudes(@mantissa, @exponent, other.mantissa, other.exponent)
BiggishDecimal.from_parts(result_mantissa, result_exponent)
end
def to_s
return "0" if @mantissa.all?(&:zero?)
# Convert mantissa array to individual digit array
digits = []
@mantissa.reverse.each do |segment|
# Extract digits from segment using integer arithmetic
temp_digits = []
s = segment
BASE_DIGITS.times do
temp_digits.unshift(s % 10)
s /= 10
end
digits.concat(temp_digits)
end
# Remove leading zeros
while digits.length > 1 && digits.first == 0
digits.shift
end
# Calculate decimal position
decimal_pos = digits.length + @exponent * BASE_DIGITS
# Build result string based on decimal position
if decimal_pos <= 0
# Number is 0.00...digits
result_parts = ["0.", "0" * (-decimal_pos)]
digits.each { |d| result_parts << d.to_s }
elsif decimal_pos >= digits.length
# Number is digits followed by zeros
digits.each { |d| result_parts = (result_parts || []) << d.to_s }
result_parts << "0" * (decimal_pos - digits.length)
else
# Number has decimal point in the middle
result_parts = []
digits[0...decimal_pos].each { |d| result_parts << d.to_s }
result_parts << "."
digits[decimal_pos..-1].each { |d| result_parts << d.to_s }
end
result = result_parts.join
# Clean up trailing zeros and decimal point
if result.include?('.')
result = result.sub(/0+$/, '')
result = result.sub(/\.$/, '')
end
result.empty? ? "0" : result
end
protected
attr_reader :mantissa, :exponent
def self.from_parts(mantissa, exponent)
instance = allocate
instance.instance_variable_set(:@mantissa, mantissa)
instance.instance_variable_set(:@exponent, exponent)
instance
end
private
def parse_number(str)
# Split on decimal point
if str.include?('.')
parts = str.split('.')
integer_str = parts[0] || "0"
fractional_str = parts[1] || ""
else
integer_str = str
fractional_str = ""
end
# Convert strings to digit arrays immediately
integer_digits = integer_str.chars.map(&:to_i)
fractional_digits = fractional_str.chars.map(&:to_i)
# Remove leading zeros from integer part
while integer_digits.length > 1 && integer_digits.first == 0
integer_digits.shift
end
# Pad fractional digits on the right to make divisible by BASE_DIGITS
if fractional_digits.length > 0
frac_padding = (BASE_DIGITS - (fractional_digits.length % BASE_DIGITS)) % BASE_DIGITS
fractional_digits += [0] * frac_padding
end
# Combine digit arrays
all_digits = integer_digits + fractional_digits
# Pad on the left to make divisible by BASE_DIGITS
padding = (BASE_DIGITS - (all_digits.length % BASE_DIGITS)) % BASE_DIGITS
all_digits = [0] * padding + all_digits
# Build mantissa from right to left by grouping digits into BASE segments
mantissa = []
i = all_digits.length - BASE_DIGITS
while i >= 0
segment = 0
BASE_DIGITS.times do |j|
segment = segment * 10 + all_digits[i + j]
end
mantissa << segment
i -= BASE_DIGITS
end
# Calculate exponent based on number of fractional segments
fractional_segments = fractional_digits.length / BASE_DIGITS
exponent = -fractional_segments
# Remove trailing zeros from mantissa (high-order zeros)
while mantissa.length > 1 && mantissa.last == 0
mantissa.pop
end
[mantissa, exponent]
end
def add_magnitudes(left_mantissa, left_exponent, right_mantissa, right_exponent)
aligned_left, aligned_right, common_exponent = align_operands(
left_mantissa, left_exponent,
right_mantissa, right_exponent
)
result_mantissa = []
carry = 0
max_length = [aligned_left.length, aligned_right.length].max
max_length.times do |i|
left_digit = aligned_left[i] || 0
right_digit = aligned_right[i] || 0
sum = left_digit + right_digit + carry
result_mantissa << (sum % BASE)
carry = sum / BASE
end
if carry > 0
result_mantissa << carry
end
[result_mantissa, common_exponent]
end
def align_operands(left_mantissa, left_exponent, right_mantissa, right_exponent)
if left_exponent < right_exponent
padding = [0] * (right_exponent - left_exponent)
[padding + left_mantissa, right_mantissa, right_exponent]
elsif right_exponent < left_exponent
padding = [0] * (left_exponent - right_exponent)
[left_mantissa, padding + right_mantissa, left_exponent]
else
[left_mantissa, right_mantissa, left_exponent]
end
end
endLets take it for a quick spin:
(BiggishDecimal.new('3.0') + BiggishDecimal.new('0.5')).to_s
=> "3.5"Fundamentally, this actually works similar to our DecimalArithmetic script - pad the two numbers until all the digits line up, loop through them, add and carry, and then reassemble.
There’s a slight wrinkle with the “align_operands” function: we’re not storing the whole number in the array. We’re also storing number as exponent and mantissa - in other words, the exponent is the amount of columns to shift our entire number left or right by, and the mantissa is what remains. Therefore, our alignment function needs to take into account both the mantissa and the exponent.
It does this by first comparing the exponents - if one side is 10000 bigger, it creates an array with the smaller size padded with zeros to fit the larger one. If they have the same exponent, it just passes them through.
After that, our loop is pretty similar to the DecimalArithmetic:
max_length.times do |i|
left_digit = aligned_left[i] || 0
right_digit = aligned_right[i] || 0
sum = left_digit + right_digit + carry
result_mantissa << (sum % BASE)
carry = sum / BASE
endTake a look at the following code from BigDecimal.c:
while (a_pos > 0) {
c->frac[--c_pos] = a->frac[--a_pos] + carry;
if (c->frac[c_pos] >= BASE) {
c->frac[c_pos] -= BASE;
carry = 1;
}
else {
carry = 0;
}
}
if (c_pos) c->frac[c_pos - 1] += carry;
goto Exit;
Look familar? The syntax is different - Ruby doesn’t even have a pre-decrement operator, which frankly I count as a feature - but the idea of looping, adding, carrying any leftovers, remains.
Of course, BigDecimal has a lot more features and special cases then we’ve shown here; it supports variable precision and a lot more operators than we’ve shown - but it’s also not mystical or impossible to understand.