 # RCR 322: Use log identities to improve BigMath::log performance

Submitted by leonardr (Mon Oct 24 15:33:41 UTC 2005)

## Abstract

BigMath::log is very slow. It can be made much faster, without sacrificing precision, by decomposing large numbers into small numbers and exploiting log identities.

## Problem

The current implementation of BigMath::log is very slow for numbers greater than about 10, because its performance is a function of the magnitude of the number.

## Proposal

BigDecimal stores numbers in a scientific notation-like format, and BigDecimal#split already exists to turn x*10^y into [(sign), x, 10, y].

From the identity log(x*y) == log(x) + log(y) it follows that log(x*10^y) == log(x) + log(10^y). It also follows that log(10^y) == log(10) * y. Therefore, log(x*10^y) == log(x) + (log(10) * y).

This means the log of an arbitrarily large scientific-notation number can be calculated by taking the log of the fraction and the log of the power, both of which are very small by BigDecimal standards. Since BigDecimal addition and multiplication don't lose precision, the result is as precise as taking the log of the number without decomposing it.

A simple reimplementation of BigDecimal#log will use the existing implementation for small numbers, and decompose large numbers into their component parts.

## Analysis

The standard library should offer efficient implementations of algorithms so that users don't have to write the efficient implementations themselves. This implementation greatly improves performance by extending the existing implementation in a way both intuitive and mathematically sound.

## Implementation

``` require 'bigdecimal'
require 'bigdecimal/math'
require 'bigdecimal/util'
module BigMath
alias :_log :log
def log(x, prec)
raise ArgumentError, "Zero or  negative argument for log" if x <= 0 ||  prec <= 0
return _log(x, prec) if x <= 10
return x if x.infinite? || x.nan?
sign, fraction, power, exponent =  x.split
fraction = BigDecimal(".#{fraction}")
power = power.to_s.to_d
_log(fraction, prec) + (_log(power,  prec) * exponent)
end
end```   