Find the nearest power of two

[Mistrel]

I found this snippet while reading and article and thought it could be useful.

Code: Select all

1 << (int)(ceil(log2(given)))

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.

[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

[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.

[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.

[Trond]

Right.

[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.

[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.

[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