Page 1 of 1
Find the nearest power of two
Posted: Mon Jan 11, 2010 10:00 am
by Mistrel
I found this snippet while reading and article and thought it could be useful.
For example, it can be used for texturing on hardware that does not support arbitrary texture sizes.
How can this be converted to PB? I see Log and Log10 but not Log2.
Re: Find the nearest power of two
Posted: Mon Jan 11, 2010 11:24 am
by Foz
Code: Select all
Procedure GetNearestTwo(Value, Mode)
ProcedureReturn 1 << Int(Round(Log(Value) / Log(2), Mode))
EndProcedure
Debug "next two up"
For i = 1 To 25
Debug Str(i) + " " + Str(GetNearestTwo(i, #PB_Round_Up))
Next
Debug ""
Debug "nearest two"
For i = 1 To 25
Debug Str(i) + " " + Str(GetNearestTwo(i, #PB_Round_Nearest))
Next
btw, Wikipedia search for Log2 was the source
Re: Find the nearest power of two
Posted: Mon Jan 11, 2010 12:56 pm
by Trond
It's so much faster with inline assembly:
Code: Select all
Procedure GetNearestTwo(Value, Mode)
ProcedureReturn 1 << Int(Round(Log(Value) / Log(2), Mode))
EndProcedure
Procedure Nearest2pow(Value)
!mov ecx, [p.v_Value]
!dec ecx
!bsr ecx, ecx
!mov eax, 1
!add ecx, 1
!shl eax, cl
ProcedureReturn
EndProcedure
#Tries = 10000000
Dim results(#Tries, 1)
time = ElapsedMilliseconds()
For U = 0 To #Tries
results(u, 0) = GetNearestTwo(u, #PB_Round_Up)
Next
MessageRequester("", Str(ElapsedMilliseconds()-time))
time = ElapsedMilliseconds()
For U = 0 To #Tries
results(u, 1) = Nearest2pow(u)
Next
MessageRequester("", Str(ElapsedMilliseconds()-time))
By the way, 1 is not really a power of two, as the other procedure seems to think.
Re: Find the nearest power of two
Posted: Mon Jan 11, 2010 1:44 pm
by srod
By the way, 1 is not really a power of two, as the other procedure seems to think.
Now sure what you mean by that Trond? 2^0 = 1 and thus 1 is indeed a power of 2.
Re: Find the nearest power of two
Posted: Mon Jan 11, 2010 2:17 pm
by Trond
Right.
Re: Find the nearest power of two
Posted: Mon Jan 11, 2010 2:33 pm
by luis
Interesting !
Another way almost as fast as the asm could be this (no use of log, only or and shifts, found on GameDev forum):
Code: Select all
Procedure GetNextPowerOfTwo( x )
x & $ffffffff -1
x | x >> 1
x | x >> 2
x | x >> 4
x | x >> 8
x | x >> 16
ProcedureReturn x & $ffffffff + 1
EndProcedure
The firts two results for 0 and 1 can be debatable, depending on the intended usage, but the others seems ok ...
EDIT: renamed to GetNextPowerOfTwo() because this one only find the NEXT one, not the nearest one... like the one in ASM if I'm not mistaken.
So the one from Foz seems more useful to me.
Re: Find the nearest power of two
Posted: Tue Jan 12, 2010 12:00 am
by skywalk
Holy Moly!
I use this function in VB6 to set the number of samples for an AD converter.
It is not in a critical time path, meaning, it's not sent in a loop like the test case above.
But, I was curious, and just the arithmetic bit shifting trick is 12 times faster than my VB6 routine.
VB6 doesn't have bitwise operations per se. VB.NET does, but I am not going there.
So, another reason for me to keep trying to assimilate this tool into my code base.
Re: Find the nearest power of two
Posted: Wed Feb 24, 2010 8:45 pm
by Booger
Yet another that I use in loading texture sheets on old cards.
Code: Select all
Procedure NEXTPOWEROF2(number.l)
EnableASM
Protected RetVal.l = 1;
XOR ecx , ecx
BSR ecx , Number
INC ecx
SHL RetVal , cl
DisableASM
ProcedureReturn RetVal.l
EndProcedure