ruby picture

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
ruby picture
Comments Current voting
Using log identities to get things done faster is always better.


I agree with this change, but RCRs are more for changes in how Ruby itself works, rather than changes to how a method or two works. It would be better suited to posting on the ruby-core mailing list so that someone can patch it in.


Strongly opposed 0
Opposed 0
Neutral 0
In favor 4
Strongly advocate 5
ruby picture
If you have registered at RCRchive, you may now sign in below. If you have not registered, you may sign up for a username and password. Registering enables you to submit new RCRs, and vote and leave comments on existing RCRs.
Your username:
Your password:

ruby picture

Powered by .