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

Mistrel · Post by **Mistrel** » Wed Aug 08, 2007 9:29 pm

Here is some example code. Be sure to compile without the debugger.

I recieved 2.594 seconds for ^2 and 0.172 seconds for n*n.

Code: Select all

Structure ptcoord
	x.f
	y.f
	z.f
EndStructure

Procedure.f RndNeg(num)
    n=Random(1)
    i=Random(num)
    If n=1
        i=i*-1
    EndIf
    ProcedureReturn i
EndProcedure

Procedure.f Dist3d(x1.f,y1.f,z1.f,x2.f,y2.f,z2.f)
	ProcedureReturn Sqr(Pow((x2.f-x1.f),2)+Pow((y2.f-y1.f),2)+Pow((z2.f-z1.f),2))
EndProcedure

Procedure.f Dist3d_2(x1.f,y1.f,z1.f,x2.f,y2.f,z2.f)
	xd.f=(x2.f-x1.f)
	yd.f=(y2.f-y1.f)
	zd.f=(z2.f-z1.f)
	dist.f=Sqr(xd.f*xd.f+yd.f*yd.f+zd.f*zd.f)
	ProcedureReturn dist.f
EndProcedure

;50,000 points * 60 fps * 1 seconds
point_count.q=50000*60*1

Dim a.ptcoord(point_count)
time.f

For i=1 To point_count
	a(i)\x=RndNeg(5000)/(Random(10)+1)
	a(i)\y=RndNeg(5000)/(Random(10)+1)
	a(i)\z=RndNeg(5000)/(Random(10)+1)
Next i

A_point.ptcoord
A_point\x=RndNeg(5000)/(Random(10)+1)
A_point\y=RndNeg(5000)/(Random(10)+1)
A_point\z=RndNeg(5000)/(Random(10)+1)

output.s="Considering "+Str(point_count)+" points"+Chr(10)+Chr(13)+Chr(10)+Chr(13)

start.f=ElapsedMilliseconds() 
For i=1 To point_count
newdist.f=Dist3d(A_point\x,A_point\y,A_point\z,a(i)\x,a(i)\y,a(i)\z)
If newdist.f<closest.f Or closest.f=0
	closest.f=newdist.f
EndIf
If newdist.f>farthest.f Or farthest.f=0
	farthest.f=newdist.f
EndIf
Next i
time.f=(ElapsedMilliseconds()-start.f)/1000

output.s+"Euclidean distance (^2):"+Chr(10)+Chr(13)
output.s+"The closest point is "+StrF(closest.f)+Chr(10)+Chr(13)
output.s+"The farthest point is "+StrF(farthest.f)+Chr(10)+Chr(13)
output.s+"Completed in "+StrF(time.f)+" seconds."+Chr(10)+Chr(13)+Chr(10)+Chr(13)

start.f=ElapsedMilliseconds() 
For i=1 To point_count
newdist.f=Dist3d_2(A_point\x,A_point\y,A_point\z,a(i)\x,a(i)\y,a(i)\z)
If newdist.f<closest.f Or closest.f=0
	closest.f=newdist.f
EndIf
If newdist.f>farthest.f Or farthest.f=0
	farthest.f=newdist.f
EndIf
Next i
time.f=(ElapsedMilliseconds()-start.f)/1000

output.s+"Euclidean distance (n*n):"+Chr(10)+Chr(13)
output.s+"The closest point is "+StrF(closest.f)+Chr(10)+Chr(13)
output.s+"The farthest point is "+StrF(farthest.f)+Chr(10)+Chr(13)
output.s+"Completed in "+StrF(time.f)+" seconds."+Chr(10)+Chr(13)+Chr(10)+Chr(13)

MessageRequester("",output.s)

Kaeru Gaman · Post by **Kaeru Gaman** » Wed Aug 08, 2007 9:47 pm

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

sic

for x² or x³, use simple mult.

for 2^n, use bitshift.

Pow() is optimised for floats, for things like 3.14152965^2.718281828459

pdwyer · Post by **pdwyer** » Thu Aug 09, 2007 12:32 am

Might be just me but I believe that these sorts of things should be in the docs. I don't think you should need to trip over a perf issue before realising that it's there.

Not a big deal perhaps, but I'm one of those people who read the docs and hope to find lists of caveats... (like the right shifting of signed vars etc)

Kaeru Gaman · Post by **Kaeru Gaman** » Thu Aug 09, 2007 12:53 am

(dont get "caveats")

seriously, every programmer who ever was concerned with performance issues,
should know that a simple mult is way faster than calling a float-function...

it's "optimizing for beginers"....

sure, some tutorials for this issue would be helpful,
but PB is not necessarily a platform for teaching every rookie every trick...

not mentioning such things in the documentation (docu, not "omnipotential tips&tricks summary") is not a problem.

PS:
sorry I should've known not to post that explicit, because some people seem to have problems with telling the facts...
but it's late at night, and I love to speak my mind...

Mistrel · Post by **Mistrel** » Thu Aug 09, 2007 1:03 am

Well, to a certain extent it is in the documentation. The help for Pow() does identity that it will cast your variables to a float. I wouldn't have ever expected that.

seriously, every programmer who ever was concerned with performance issues,
should know that a simple mult is way faster than calling a float-function...

I don't appreciate that statement. Sometimes it's the simple things that get you and you don't know until you ask.

Kaeru Gaman · Post by **Kaeru Gaman** » Thu Aug 09, 2007 1:33 am

well, sorry to you personally.

I didn't mean to insult you.

but as a programmer, some "should know that a simple mult is way faster than calling a float-function"
should be plainly clear.

for me personally it never was about a question, it was a clear fact always, no matter in wich language I program.

Mistrel · Post by **Mistrel** » Thu Aug 09, 2007 2:33 am

But as a programmer, some "should know that a simple mult is way faster than calling a float-function"
should be plainly clear.

Would you explain to me in detail about why this is?

If I were casting an int to a float for the calculation and then back to an int I could understand but in this case I'm not.

What is Pow() actually doing with my data?

pdwyer · Post by **pdwyer** » Thu Aug 09, 2007 2:59 am

Docs just say:

Pow()

Syntax

Result.f = Pow(Number.f, Power.f)
Description

Returns the Number^Power.
Supported OS

Windows, Linux, MacOS X

I suppose yes you are right, it does say ".f" and so there is some reading you can do between the lines.

My point is that most of the docs are like this, with little in the way of detailed explanation. A nice thing to add would be:

"As this is optimised for floating point opperations performance critical apps not requiring floating point arithmatic should avoid this function"

I'm sure lots of PB'er will disagree and say "I'd prefer if PB staff spent more time on the compiler than the docs" etc, I've fallen off my seat from people saying on the forums that they think the PB docs are "wonderful" so I'll just accept this as a quirk on my part.

IMHO, the text above is not a "Doc" it's a tooltip

Demivec · Post by **Demivec** » Thu Aug 09, 2007 4:06 am

pdwyer wrote:I suppose yes you are right, it does say ".f" and so there is some reading you can do between the lines.

My point is that most of the docs are like this, with little in the way of detailed explanation.

I'm sure lots of PB'er will disagree and say "I'd prefer if PB staff spent more time on the compiler than the docs" etc, I've fallen off my seat from people saying on the forums that they think the PB docs are "wonderful" so I'll just accept this as a quirk on my part.

I agree that the documentation needs some improvements both on use and side-effects of using certain functions.

I had a similiar discussion regarding Labels in a DataSection here: http://www.purebasic.fr/english/viewtop ... atasection

In reference to the link I know that much of the documentation wasn't originally written in english. That's wondeful, but what can be done to improve the translation?

The part that I would raise with pdwyer is regarding

Kaeru Gaman wrote:seriously, every programmer who ever was concerned with performance issues,
should know that a simple mult is way faster than calling a float-function...

it's "optimizing for beginers"....

sure, some tutorials for this issue would be helpful,
but PB is not necessarily a platform for teaching every rookie every trick...

not mentioning such things in the documentation (docu, not "omnipotential tips&tricks summary") is not a problem.

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

The thought makes reason stare.

So if it is understood that Help files are not for Experts only, but for Beginners as well, it would be well to include inportant side-effects ( and caveats) that are both beneficial and harmful. This is one of the reasons that the Help file includes sample code and alerts you that some of the documentation is for Advanced Users (and requires a deeper understanding for its proper use).

Perhaps it would be helpful to make a collective entry relating to some of these issues. I don't think anyone will be harmed by having documentation that is more informative or Helpful (Experts typically just scan it anyways because they allready know what they're looking for.

).

Having a way to submit ideas for documentation improvements would definately be helpful.

pdwyer · Post by **pdwyer** » Thu Aug 09, 2007 4:37 am

Submit them to Kale and get them into a 2nd edition of that Purebasic book!

That's for beginners!

Mistrel · Post by **Mistrel** » Thu Aug 09, 2007 4:54 am

pdwyer wrote:Submit them to Kale and get them into a 2nd edition of that Purebasic book!

That's for beginners!

That would be pretty cool but I don't think it would be applicable to any section other than an appendix. There's no point in explaining the inner workings of how something works to a beginner.

As much as I agree with your intentions, I don't think these kinds of problems would even be appropriate for Kale's book.

pdwyer · Post by **pdwyer** » Thu Aug 09, 2007 4:59 am

Mistrel wrote: As much as I agree with your intentions, I don't think these kinds of problems would even be appropriate for Kale's book.

True, they belong in the help file under "POW()"

Helle · Post by **Helle** » Thu Aug 09, 2007 6:29 am

POW is not a direct FPU-Instruction like ADD, SUB, MUL or DIV; POW is "hand-making" by the programmer like:

Code: Select all

Global Bas.d=3.14152965
Global Exp.d=2.718281828459
Global Res.d

  !fld qword[v_Exp]            
  !fld qword[v_Bas]
  !fyl2x
  !fld st0
  !frndint
  !fsub st1,st0
  !fxch st1
  !f2xm1
  !fld1
  !faddp st1,st0
  !fscale
  !fstp st1             ;for stack!
  !fstp qword[v_Res]

MessageRequester("Pow",StrD(Res))

More instructions -> low speed.

Gruss
Helle

DarkDragon · Post by **DarkDragon** » Thu Aug 09, 2007 8:06 am

I had to write my own Pow a few days ago for a curve plotter for mobile phones. I always test my codes with PureBasic (faster Debugging than Java) and then convert it.

Code: Select all

Declare.d MyPow(base.d, exponent.d)
Declare.d Root(Val.d, Exp.l)

Procedure.d Root(Val.d, Exp.l)
  Define Result.d = $FFFFFF
  Define Power.d = 0.0

  Repeat
    Power = MyPow(Result, Exp)
    If Power > Val + 0.00001
      Result * 0.5
    ElseIf Power < Val - 0.00001
      Result * 1.5
    Else
      Break
    EndIf
  ForEver

  ProcedureReturn Result
EndProcedure

Procedure.d Logarithm10(Value.d)
  Define start.d  = (Len(Str(Value)) - 1)
  Define Result.d = start
  Define Power.d = 0.0
  Define Tollerance.d = Pow(10, start - 4)
  
  If Result = 0.0
    Result = 1.0
  EndIf
  
  time = ElapsedMilliseconds()
  Repeat
    Power = Pow(10, Result)
    If Power > Value + Tollerance
      Result * 0.5
    ElseIf Power < Value - Tollerance
      Result * 1.5
    Else
      Break
    EndIf
  Until ElapsedMilliseconds() - time > 1000

  ProcedureReturn Result
EndProcedure

Procedure.d MyPow(base.d, exponent.d)
  Protected result.d

  If base = 0.0
    ProcedureReturn 0.0
  ElseIf exponent >= 1.0
    While exponent >= 1.0
      If result = 0.0
        result = base
      Else
        result * base
      EndIf

      exponent - 1.0
    Wend

    If exponent > 0.0
      result * (Root(base, Int(1.0 / exponent)))
    EndIf
  ElseIf exponent > 0.0
    result = (Root(base, Int(1.0 / exponent)))
  Else
    result = 1.0 / MyPow(base, Abs(exponent))
  EndIf

  ProcedureReturn result
EndProcedure

Debug Pow(10.0, -2.5)
Debug MyPow(10.0, -2.5)

Debug Log10(1000)
Debug Logarithm10(1000)

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.

Psychophanta · Post by **Psychophanta** » Thu Aug 09, 2007 11:25 am

DarkDragon wrote: 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?