8 Replies - 3848 Views - Last Post: 30 December 2012 - 04:07 AM Rate Topic: -----

#1 BloodyInari  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 106
  • Joined: 16-November 09

Question On Optimizing Logarithm

Posted 22 December 2012 - 09:39 PM

Not really a question per se on any problems I have with my code but more so on how to get a more accurate calculation in shorter order of time. Effectively speaking, I wish to have my method correctly calculate out to "X" decimal places for the output value but in less time than the baseline process.

The method I'm currently using works just dandy but requires an upper bound of roughly 100-1000 elements in the series calculation to be approximately within 10 decimal places of accuracy. The question I have is would altering/changing the expression used for a converging series (i.e. rather than 2^k, say 10^k ?) give a "quicker" way of approaching the same output value but in shorter iterations and how?

The code in question:
def logN(val, base):
    #logarithm of base 'N'

        list_series = []
        inc, integer, partial_sum = 0, 0, 0
        bound = 1000
        val = float(val)
        
        while val >= base:
            integer += 1
            val /= base
        partial = val

        while inc < bound:
            
            partial *= partial
            
            if partial >= base:
                list_series.append(1)
                partial /= base  
            elif partial < base:
                list_series.append(0)
            inc += 1

        for var in range(len(list_series)):
            
            expr = ((list_series[var])/2.0)**(var+1)
            partial_sum = expr + partial_sum

        log_val = integer + partial_sum
        return log_val



Is This A Good Question/Topic? 0
  • +

Replies To: Question On Optimizing Logarithm

#2 alexr1090  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 44
  • View blog
  • Posts: 124
  • Joined: 08-May 11

Re: Question On Optimizing Logarithm

Posted 24 December 2012 - 08:06 PM

gmpy is good with this.
Was This Post Helpful? 1
  • +
  • -

#3 sepp2k  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2087
  • Posts: 3,174
  • Joined: 21-June 11

Re: Question On Optimizing Logarithm

Posted 25 December 2012 - 05:21 AM

View Postalexr1090, on 25 December 2012 - 04:06 AM, said:

gmpy is good with this.


I did not get the impression that the OP wanted to work with higher precision numbers. I also did not get the idea that he was looking for library functions that he could just call because, if he were, he could have just used math.log.
Was This Post Helpful? 1
  • +
  • -

#4 BloodyInari  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 106
  • Joined: 16-November 09

Re: Question On Optimizing Logarithm

Posted 27 December 2012 - 03:45 PM

View Postsepp2k, on 25 December 2012 - 06:21 AM, said:

View Postalexr1090, on 25 December 2012 - 04:06 AM, said:

gmpy is good with this.


I did not get the impression that the OP wanted to work with higher precision numbers. I also did not get the idea that he was looking for library functions that he could just call because, if he were, he could have just used math.log.


I looked into gmpy but no, its not really what I'm looking for with regards to my post. However, to be a bit more clear, I am trying to bugger anyone concerning the implementation of my expression, seeing as it could be written better in such a way that a more accurate output is given in less steps

bound = 1000
expr = ((numerator[var])/2.0)**(var+1)



The form that I'm using is from a reference to a strict mathematical expression for a logarithm that reduces the value within the logarithm function by the base value until it gives a value less or equal than the value of the base, thus giving the most significant integer of the "logged" value.
The expression then goes for an "infinite" looping operation that closer approximates the trailing decimal by squaring the leftover and seeing whether it is less than or equal to being divisible by the base. Depending upon the whether it is or is not, an output is given to be 1 or 0, respectively.
From there it recurses until the upper bound is met (ideally infinity) and then the function runs a summation drawing from the designated numerator list (being 0 or 1) and divides by a rising power of 2 for each successive numerator.

Generally speaking, this summation operation is/should be the most simplistic but therefore the most intensive calculation case possible, thus taking the most time as it is the slowest method of approximation.

        while increment < bound:
            
            partial *= partial
            
            if partial >= base:
                numerator.append(1)
                partial /= base  
            elif partial < base:
                numerator.append(0)
            increment += 1

        for var in range(len(numerator)):
            
            expr = ((numerator[var])/2.0)**(var+1)
            partial_sum = expr + partial_sum

        log_val = integer + partial_sum

        return log_val



I've been fiddling around since my OP, and the conclusion I've come to is that a higher order base would be more effective but at the cost of having to be more definitive with regards to the if-then statement block that appends to the numerator list by using a set of integers from [0,9] instead of [0,1]; i.e. power being 'n', set includes [0,n-1].
It appears, like as before, I must raise the partial value by a power of 'n', determine how "often" it can be reduced by an order of base, append, and then run summation to output "logged" value.

sepp2k, you are correct in your assumption concerning the utilization of libraries (completely useless for what I'm playing around with), although I'm a bit confused as to what you meant by "work with higher precision numbers".

This post has been edited by BloodyInari: 27 December 2012 - 03:48 PM

Was This Post Helpful? 0
  • +
  • -

#5 sepp2k  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2087
  • Posts: 3,174
  • Joined: 21-June 11

Re: Question On Optimizing Logarithm

Posted 27 December 2012 - 04:41 PM

View PostBloodyInari, on 27 December 2012 - 11:45 PM, said:

I'm a bit confused as to what you meant by "work with higher precision numbers".


I meant that I did not get the impression that you intended to work with anything but regular Python floating point numbers - as opposed to the high-precision numeric types offered by the gmpy library.
Was This Post Helpful? 0
  • +
  • -

#6 andrewsw  Icon User is online

  • Fire giant boob nipple gun!
  • member icon

Reputation: 3180
  • View blog
  • Posts: 10,653
  • Joined: 12-December 12

Re: Question On Optimizing Logarithm

Posted 27 December 2012 - 06:42 PM

I suggest a couple of minor changes:

    if partial >= base:
        numerator.append(1)
        partial /= base  
    else: # no need for elif
        numerator.append(0)
    increment += 1
    
len_num = len(numerator) # take this evaluation out of the loop
for var in range(len_num):


For the 2nd suggestion, maybe Python is clever enough not to re-evaluate len() for each iteration(?), assuming it is able to determine that the length with not change. Edited: I believe Python only evaluates the end condition once anyway.

Actually, you are iterating a list, so more efficient would be:

for var, val in enumerate(numerator):
    expr = (val / 2.0)**(var + 1)

I apologise if you are already aware of these points.

This post has been edited by andrewsw: 27 December 2012 - 06:58 PM

Was This Post Helpful? 0
  • +
  • -

#7 sepp2k  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2087
  • Posts: 3,174
  • Joined: 21-June 11

Re: Question On Optimizing Logarithm

Posted 27 December 2012 - 06:57 PM

View Postandrewsw, on 28 December 2012 - 02:42 AM, said:

For the 2nd suggestion, maybe Python is clever enough not to re-evaluate len() for each iteration(?), assuming it is able to determine that the length with not change.


This has nothing to do with cleverness or being able to determine that the length does not change. Function arguments are evaluated exactly once before the function is called. This is the same in Python as it is in any other strict language. So even if it wanted to range wouldn't be able to cause its argument to be evaluated more than once.
Was This Post Helpful? 0
  • +
  • -

#8 BloodyInari  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 106
  • Joined: 16-November 09

Re: Question On Optimizing Logarithm

Posted 29 December 2012 - 11:21 PM

View Postsepp2k, on 27 December 2012 - 05:41 PM, said:

View PostBloodyInari, on 27 December 2012 - 11:45 PM, said:

I'm a bit confused as to what you meant by "work with higher precision numbers".


I meant that I did not get the impression that you intended to work with anything but regular Python floating point numbers - as opposed to the high-precision numeric types offered by the gmpy library.


You are correct. Alright, I see it's just what I thought you might have been referring to.


View Postandrewsw, on 27 December 2012 - 07:42 PM, said:

I suggest a couple of minor changes:

    if partial >= base:
        numerator.append(1)
        partial /= base  
    else: # no need for elif
        numerator.append(0)
    increment += 1
    
len_num = len(numerator) # take this evaluation out of the loop
for var in range(len_num):


For the 2nd suggestion, maybe Python is clever enough not to re-evaluate len() for each iteration(?), assuming it is able to determine that the length with not change. Edited: I believe Python only evaluates the end condition once anyway.

Actually, you are iterating a list, so more efficient would be:

for var, val in enumerate(numerator):
    expr = (val / 2.0)**(var + 1)

I apologise if you are already aware of these points.


The "superfluous" elif statement is technically redundant, like you said, but I've tinkered a bit more since and made some improvements with regards to my second comment concerning the summation expression. The results of my tinkering mean I require a more defined set of rules for all the "new" integers (0-9) that act as the numerator when the expression is computed; i.e. a more explicit if-then-else-if-then statement block for each integer in may potentially register and store to the numerator list. A moot point by now but anyhow...
Also, just a force of habit for evaluating lists. My bad. :whistling:

I'm not overly familiar with enumerate() but I'll mess with that more and see what I get, thanks.

This post has been edited by BloodyInari: 29 December 2012 - 11:27 PM

Was This Post Helpful? 0
  • +
  • -

#9 BloodyInari  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 106
  • Joined: 16-November 09

Re: Question On Optimizing Logarithm

Posted 30 December 2012 - 04:07 AM

Alrighty, the expression procedure has been overhauled nicely by replacing the rather redundant and roundabout process. I think I'm done with this topic unless there may be something more to add?

old code:
        while incr < bound:
            
            partial *= partial
            if partial >= base:
                self.list_series.append(1)
                partial /= base  
            else:
                self.list_series.append(0)
            incr += 1

        for var in range(len(self.list_series)):
            
            expr = ((self.list_series[var])/2.0)**(var+1)
            partial_sum = expr + partial_sum

        log_val = integer + partial_sum
        return log_val



new(er) code: utilizing a raised order of 10 instead, of which directly gives each decimal place in sequential order; therefore, the degree of precision is now defined by the upper bound of the computation process and with the added bonus that no if-statements are necessary for determining the proper stored integer for each corresponding decimal place.
        while incr < bound:
            
            partial = (partial**10)
            count = 0
            while partial >= base:
                partial /= base
                count += 1
            self.list_series.append(count)
            incr += 1

        for var in range(len(self.list_series)):
            
            expr = ((self.list_series[var])/(10.0**(var+1)))
            partial_sum = expr + partial_sum

        log_val = integer + partial_sum
        return log_val


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1