n*n 1500% times faster than Pow(n,2)?

[DarkDragon]

If you know how to optimize the logarithm10 function (without Assembler) MUCH(That means that it will work pretty fast with high numbers on a 300MHz PC or such), please tell me.

Can not use Log10() instead? or i miss the objective of your function?

Please read before posting:

I had to write my own Pow a few days ago for a curve plotter for mobile phones.

You won't have log10 on mobile phones. You have to write such functions yourself. A mobile phone is nearly similar to a 300 MHz PC.

[Psychophanta]

Ok Daniel, i see
Like a PC at 300MHz? And there are not any Log() (at any base) function in mobile phones? It is strange.

[DarkDragon]

Ok Daniel, i see
Like a PC at 300MHz? And there are not any Log() (at any base) function in mobile phones? It is strange.

The speed on mobiles is like on a 300MHz pc, so I need it to run fast on such a pc (I thought you know PCs better than mobiles, so I compared the mobile speed to a pc speed so you can work on the problem). But on mobiles and other minimal embedded systems you won't see a ready to use log function.

Even on today's pcs you wouldn't see a ready to use log function if you would write your programs in assembler (See Helle's posting).

I need a speed increase of about 100-200% in my methods. I already precalculated some things (Like value + tolerance and value - tolerance and so on) but it's not enough.

[Kaeru Gaman]

@Mistrel

I hope Helle's explanation made it clear.

sure, such things are to learn by the way you learn programming.

if you are programming for some time, maybe in different languages,
then such issues will be absolutely immanent for you.
once you understood how a computer works,
you can assume the performance by looking at the command and it's description a lot of times.

I admit, for me this all is somehow obvious, because I learned programming back in a time when it was a sacrilege to use a division by 2 instead a bitshift.

not each and every trick needs to be told in a documentation.

and mind you, now that you have discovered it yourself, you will never forget it and you will always have a look on performance issues.
so, it made you a better programmer that it was not told in the doc.

__________________________________

This kind of thinking makes a Help file unnecessary. It assumes that Help files are for Experts. Since when do Experts need Help?

well, there is a broad range between "beginner" and "expert"...
"experts" also need a documentation, because only few can keep in mind every command and it's syntax of a bunch of languages.

I agree to you that a little chapter to explain "Performance Issues" would be a nice idea, but I doubt many would read it.

there a still people getting big eyes when they are told SpritePixelCollision is slow,
although it's explicitly told in the documentation of this command.

[Derek]

How accurate do you need it, I ask because according to wikipedia there is a rough way of working it out.

Code: Select all

a.f=1850
Debug Log10(a.f)
For n=1 To 11
a=Sqr(a)
Next
a-1
a*889
Debug a

Very fast but not as accurate as yours.

[DarkDragon]

How accurate do you need it, I ask because according to wikipedia there is a rough way of working it out.

Code: Select all

a.f=1850
Debug Log10(a.f)
For n=1 To 11
a=Sqr(a)
Next
a-1
a*889
Debug a

Very fast but not as accurate as yours.

Thanks, but it should be a bit more accurate. 3 numbers behind the dot should be enough. I will use your method until there's one which is a bit more accurate.

[Derek]

What is the range of numbers that you are needing the log of or is it going to be upto the user to supply a number? Might be able to tweak the routine if there is a range.

[DarkDragon]

What is the range of numbers that you are needing the log of or is it going to be upto the user to supply a number? Might be able to tweak the routine if there is a range.

It's up to the user, I'm sorry. But can you try making the most precise you can do? I think the users will understand that it can't be more accurate.

[Derek]

Well I've tried but so far the program is getting so complicated that it is becoming too long winded to be usable.

What I have come up with is that you need to change the multiplier depending on the number that you want the log of, see table..

log10 of .1 needs multiplier of 889.935181
1000 = 887.935913
1e6 = 886.438477
....
....
1e48 = 865.650940

but trying to find a relationship between the input and multiplier is the hard part. Will keep trying.

[Kaeru Gaman]

an idea....

Log2 would be a simple thing in binary, with bitshift and stuff...

how 'bout finding a relation from log2 to log10?

[dioxin]

how 'bout finding a relation from log2 to log10?

You convert from the log of any base to the log of any other base with a single multiply.

Code: Select all

LOG10(x) = LOG2(x)*LOG10(2)
         = LOG2(x)*0.30103

Paul.

[dioxin]

Mistrel,
it's no surprise that POW() takes longer. It's nothing to do with floats and non-floats, it's because the general way to calculate x^y is:
answer= EXP(y*log(x)).

Both EXP and LOG are complex functions and take many cpu clock cycles to calculate.
If y is a small integer then it's quicker to do repeated multiplies than to use POW().



DarkDragon,
for a quicker LOG10 you need to know to do a number of steps.

First, as you're using LOGs and floats it's likely you have numbers stored in floating point format. This will be some representation of the number as:

Code: Select all

sign * Mantisssa  * 2^exponent

For LOGs, sign must be positive.

Use the identity:

Code: Select all

LOG(Mantisssa  * 2^exponent) = LOG(Mantisssa) + exponent*LOG(2)

LOG(2) is a constant so the term exponent*LOG(2) becomes a simple multiply.

LOG(Mantisssa) is still a LOG function but is now guaranteed to have a mantissa between 0.5 and 1.0 which will converge rapidly using one of the common sequences. e.g. this one converges in 4 steps to a value with an error of around 0.0001.

(image from http://en.wikipedia.org/wiki/Logarithm )


So the result of Natural LOG(x) can be done in around 10 add/subtracts, 6 multiplies and 6 divides.
If you know it converges if small number of iterations then the divides can be converted to muliplies by constants to speed things up further.

You then convert the LOGe(x) to LOG10(x) with one more multiply as in the post above.

Paul.

[Mistrel]

It's no surprise that POW() takes longer. It's nothing to do with floats and non-floats, it's because the general way to calculate x^y is:
answer= EXP(y*log(x)).

Thank you! That's all I wanted to know.

[citystate]

EXP is the opposite function to LOG - EXP(n) is the equivalent to e^n

[Mistrel]

Can Exp() be done in PB without using Pow()? It would seem a little redundant otherwise.