# Thread: Nearest Power of 2 quickly

1. ## Nearest Power of 2 quickly

For my Tile Splicer I need a routine to calculate the nearest power of 2 for the output image. I know that the following code will work just fine, but it seems that their really should be a faster way (btw: I know that a shift is better then a *, but the optimizer takes care of it in this case).

[pascal] if frmGenerate.SizePower2 then
begin
p2 := 2;
while p2 < imgOut.Width do
p2 := p2 * 2;
imgOut.Width := p2;
p2 := 2;
while p2 < imgOut.Height do
p2 := p2 * 2;
imgOut.Height := p2;
end;[/pascal]

I know this is a simple, stupid question, but I've been stuck for a bit trying to find a better way

2. ## Nearest Power of 2 quickly

Have you tried using a pre-calculated table?

You can make it start at 2 and run up to whatever the highest size would be then you'd simply only have to run through the array until you find a size that fits.

3. ## Re: Nearest Power of 2 quickly

This is a typical situation where some assembler can be usefull. Of course, always {\$ifdef} the assembler code and put a Pascal version in the {\$else} part to not hurt portabilty.

[pascal]
if frmGenerate.SizePower2 then
begin
w:=imgout.width;
h:=imgout.height;
asm
mov ebx,w
bsr ecx,ebx
mov ebx,1
inc ecx
shl ebx,ecx
mov w,ebx

mov ebx,h
bsr ecx,ebx
mov ebx,1
inc ecx
shl ebx,ecx
mov h,ebx
end;
end;
[/pascal]

4. ## Nearest Power of 2 quickly

Here's an alternative code I've been distributing in Asphyre package:

Code:
```function NextPowerOfTwo&#40;Value&#58; Integer&#41;&#58; Integer;
begin
Result&#58;= 1;
asm
xor ecx, ecx
bsr ecx, Value
inc ecx
shl Result, cl
end;
end;```
Code:
```function CeilPowerOfTwo&#40;Value&#58; Integer&#41;&#58; Integer;
asm
mov ecx, eax
xor eax, eax
dec ecx
bsr ecx, ecx
cmovz ecx, eax
setnz al
inc eax
shl eax, cl
end;```

5. ## Nearest Power of 2 quickly

OH for crying out loud Here are two no-assembly, portable algorythms i use, first one i came up with, it's based on idea of second algorythm, which is from wikipedia (or the other way round).

Code:
```if &#40;number and &#40;number - 1&#41; <> 0&#41; // FAST POT CHECK

trunc&#40;power&#40;2, trunc&#40;Log2&#40;number&#41;&#41;&#41;&#41;; // MAKE NUMBER A POT, ROUND UP```

6. ## Nearest Power of 2 quickly

:shock: :shock: Do you have any idea how slow a trunc is?

No, for speed you need to do it with integer logic. This is a way how you can do it in Pascal:

dec(v);
v:=v or (v shr 1) or (v shr 2) or (v shr 4) or (v shr 8 ) or (v shr 16);
inc(v);

... but even this one is slower than the assembler one. The ancient art proves itself usefull once more!

7. ## Nearest Power of 2 quickly

Originally Posted by dmantione
:shock: :shock: Do you have any idea how slow a trunc is?
why would trunc be slow? it executes on the FPU, right?

8. ## Nearest Power of 2 quickly

Originally Posted by Delfi
Originally Posted by dmantione
:shock: :shock: Do you have any idea how slow a trunc is?
why would trunc be slow? it executes on the FPU, right?
This is the trunc implementation in FPC

[pascal]
{\$define FPC_SYSTEM_HAS_TRUNC}
function fpc_trunc_real(d : ValReal) : int64;assembler;compilerproc;
var
oldcw,
newcw : word;
res : int64;
asm
fnstcw oldcw
fwait
movw oldcw,%cx
orw \$0x0f00,%cx
movw %cx,newcw
fldcw newcw
fldt d
fistpq res
fwait
movl res,%eax
movl res+4,%edx
fldcw oldcw
end;
[/pascal]

Note all the hackery with the FPU control word, necessary to make the FPU truncate instead of round. Tinkering with the fpucw is terribly expensive.

Never mind.

10. ## Nearest Power of 2 quickly

I cant think of any situation where a power of 2 calculation is not fast enough...

You normally use this when loading textures in which case the disk access is going to slow it down no matter what. I know jdarling didnt ask for the fastest thing out there, but it's a classic example of the 90% - 10% optimisation mantra:

90% of the code you write will be executed once or twice
the other 10% will be executed very many more times (thousands of times per second?)

And to optimize code that falls into the first 90% is a waste of time. You need to figure out if this code really falls into that last 10% before you start worrying that the trunc() procedure is not fast enough

Just for luck, this is how I implemented it.. using the suggested lookup-table.

Code:
```const
Pow2&#58; array&#91;0..12&#93; of integer = &#40;2,4,8,16,32,64,128,256,512,1024,2048,4096,8192&#41;;

Function GetNextPow2&#40;Wid&#58; integer&#41;&#58; integer;
var I&#58; integer;
begin
Result &#58;= Wid;

for I &#58;= 1 to 12 do
begin
If Pow2&#91;I&#93; >= Wid then
begin
Result &#58;= Pow2&#91;I-1&#93;;
exit;
end;
end;

end;

Function GetPrevPow2&#40;Wid&#58; integer&#41;&#58; integer;
var I&#58; integer;
begin
Result &#58;= Wid;

for I &#58;= 12 downto 1 do
begin
If Pow2&#91;I&#93; <= Wid then
begin
Result &#58;= Pow2&#91;I-1&#93;;
exit;
end;
end;

end;```

Page 1 of 4 123 ... Last

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•
Comodo SSL