HomeUser Control Panel (unavailable in archive)ForumsTutorialsArt GalleryResourcesMaps

Natural Logarithms

11-23-2008, 03:59 AM#1
BlinkBoy
I originally posted this in THW, now it will be here.

(Disclaimer: I'm not sure if someone has presented this method before, if he has please inform me, I just developed this today and I've been unable to check).

EDIT: I have checked and most of the other methods are different; some use binary, others borzan. The method which i found to use the same first rule that I apply, is pipedream's from wc3jass. Credits to him since he posted the idea first, :D.

Logarithm:

I scripted 5 functions for calculating the natural logarithm of a number, the first one is slower than the later, but it's more accurate.

Collapse JASS:
function Ln takes real a returns real
local real s = 1.0
local real sum = 0.0
local real g
local real e
local integer i = 10
loop
    exitwhen a < bj_E
    set a = a/bj_E
    set sum = sum + 1.
endloop
set e = (a-1.0)/10. //quite accurate for numbers < e
set g = s + e
loop
    exitwhen i <= 0 or a <= 1.0
    set i = i-1
    set sum = sum + (g-s)*(1./s + 8./(s+g) + 1./g)/6.
    set s = g
    set g = s + e
endloop
return sum
endfunction

// cubic, very good accurity for warcraft
function Ln takes real a returns real
local real sum = 0.0
loop
    exitwhen a < bj_E
    set a = a/bj_E
    set sum = sum + 1.
endloop
return sum + (a-1.)*(1. + 9./(2.+a) + 9./(1.+a*2.) + 1/a)/8.
endfunction

//Even faster! --parabollic, has a good accurity as well
function Ln takes real a returns real
local real sum = 0.0
loop
    exitwhen a < bj_E
    set a = a/bj_E
    set sum = sum + 1.
endloop
return sum + (a-1.)*(1. + 8./(1.+ a) + 1/a)/6.
endfunction

//Fourth, this one is quite a bit more accurate than the former 2, but it is a bit slower.

function Ln takes real a returns real
local real sum = 0.0
local real e = 1.284025417
loop
    exitwhen a < bj_E
    set a = a/bj_E
    set sum = sum + 1.
endloop
loop
    exitwhen a < e
    set a = a/e
    set sum = sum + .25
endloop
return sum + (a-1.)*(1. + 8./(1.+ a) + 1/a)/6. //and we apply simpson's :D
endfunction

//Added a Fifth, this one uses Taylor series instead.

function Ln takes real a returns real
local real sum = 0.0
local real e = 1.648721271
local real b
loop
    exitwhen a < bj_E
    set a = a/bj_E
    set sum = sum + 1.
endloop
if a >= e then
    set a = a/e
    set sum = sum + .5
endif
//Time to apply Taylor series of ln(1+x).
set e = 1.
set a = (a - 1.)
set b = a
loop
    exitwhen e > 5.
    set sum = sum + a/e
    set e = e + 1.
    set a = a*b*(-1.)
endloop
return sum
endfunction

function LogB takes real a, real base returns real
         return Ln(a)/Ln(base) //I would suggest that you save the nautral log of the base 
                                       //if you want to keep using it over and over.
endfunction

I'll explain a bit what's done.

The first part of the function takes care of calculating the integer part of the logarithm. We keep divinding our number by the base(e), until our number is smaller than e.

a good way to observe it is in this way:


As you see, we percieve the number as a multiplication. Now, why did we make this?(Here's where most of you get lost) Very simple, when calculating the definate integral of a function which we can't calculate through normal algebra, we must use the Simpson's method. Why I didn't use it directly? Simpson's rule is an approximation of the definite integral, the bigger be the distance between a and b, the biggger will be the accumulated error.

Some of you may remenber that the derivate of the natural logarithm is an hyperbole: Ln'(x) = 1/x (Ln(x)/dx = 1/x). 1/x is a function which is calculateable through linear algebra. Now knowing that, we can calculate the definate integral between 1 and the leaving value, which is < e, using Simpson's Rule.

I'm not going to be very specific on Simpson's rule, you can look at it in wikipedia or mathworld.

Now the Benchmarking and Statistics:



Here's anotther test with an smaller number:



It will be your decision to decide which function you'll use. I would suggest Third for fast usage, like for moving objects or places where you need it a lot. The first one should be used for things that do require a LOT of accurity, like armor calculation.
Attached Files
File type: w3mTestLog.w3m (38.6 KB)
11-23-2008, 10:24 AM#2
Captain Griffen
Quote:
locals are faster than globals so get your bj_e somewhere else

Benchmark proof? Plus, a constant global is faster than any local.

Actually this whole thing could do with benchmarks, and also more complete testing of accuracy, particularly against our log function already in the database.
11-23-2008, 06:22 PM#3
BlinkBoy
Quote:
Originally Posted by Captain Griffen
Benchmark proof? Plus, a constant global is faster than any local.

Actually this whole thing could do with benchmarks, and also more complete testing of accuracy, particularly against our log function already in the database.

ok, did the benchmarks and calculations. I notice that, in fact, you are right, Constant globals are a lil bit faster than locals. I replaced e by bj_E and added the benchmarking in comparison to Vexorian's Logarithm function.
11-23-2008, 07:26 PM#4
Rising_Dusk
Hah, yeah, that's more like it. Looks good to me, so I'll go ahead and approve this.