# Log2 for BlitzMax

Tweet blitzmax code-archives algorithms
(Posted 1 year ago)

Compute fast ceil/floor of log base 2

Author: Pineapple

This is the output I get on for the example code running BlitzMax 1.50 on OSX Mavericks:

Ceil(Log2(x)) using doubles: 409 ms
Ceil(Log2(x)) using clog2(): 141 ms

Note that these functions will only work for positive integers.

``````'   --+-----------------------------------------------------------------------------------------+--
'     |   This code was originally written by Sophie Kirschner ([email protected])   |
'     | It is released as public domain. Please don't interpret that as liberty to claim credit |
'     |   that isn't yours, or to sell this code when it could otherwise be obtained for free   |
'     |                because that would be a really shitty thing of you to do.                |
'   --+-----------------------------------------------------------------------------------------+--

SuperStrict

' Example code
Rem
Local ms%,nms%
Local i%,x!,y%
Const log2!=0.69314718055994529
local cycles%=20000000

' Use a long sequence of random numbers of various powers to avoid apparent speedups due to consistent branching
local ral% = 1024
local ra%[ral]
for local i% = 0 until ra.length
local p% = rand(0,31)
ra[i] = abs( (1 shl p) + rand(0,\$ffff) )
next

' eat some cycles before going on with the important part
For i%=0 Until cycles
x=Ceil(Log(i)/log2)
Next

' test using doubles
ms=MilliSecs()
For i%=0 Until cycles
x=Ceil(Log( ra[i mod ral] )/log2)
Next
nms=MilliSecs()-ms
Print "Ceil(Log2(x)) using doubles: "+nms+" ms"

' test using clog2()
ms=MilliSecs()
For i%=0 Until cycles
y=clog2( ra[i mod ral] )
Next
nms=MilliSecs()-ms
Print "Ceil(Log2(x)) using clog2(): "+nms+" ms"
EndRem

Private
Global log2_array%[]=[  \$80000000,\$40000000,\$20000000,\$10000000,\$08000000,\$04000000,\$02000000,\$01000000, ..
\$00800000,\$00400000,\$00200000,\$00100000,\$00080000,\$00040000,\$00020000,\$00010000, ..
\$00008000,\$00004000,\$00002000,\$00001000,\$00000800,\$00000400,\$00000200,\$00000100, ..
\$00000080,\$00000040,\$00000020,\$00000010,\$00000008,\$00000004,\$00000002,\$00000001  ]
Public

Rem
bbdoc: Returns Ceil( Log2( x ) ) when x is a positive integer
about: Much faster than using floating point or double functions. Good for when you don't need to know the exact value.
EndRem
Function clog2%(x%)
If (x & log2_array[\$00]) Then Return (x<>log2_array[\$00])
If (x & log2_array[\$01]) Then Return \$01+(x<>log2_array[\$01])
If (x & log2_array[\$02]) Then Return \$02+(x<>log2_array[\$02])
If (x & log2_array[\$03]) Then Return \$03+(x<>log2_array[\$03])
If (x & log2_array[\$04]) Then Return \$04+(x<>log2_array[\$04])
If (x & log2_array[\$05]) Then Return \$05+(x<>log2_array[\$05])
If (x & log2_array[\$06]) Then Return \$06+(x<>log2_array[\$06])
If (x & log2_array[\$07]) Then Return \$07+(x<>log2_array[\$07])
If (x & log2_array[\$08]) Then Return \$08+(x<>log2_array[\$08])
If (x & log2_array[\$09]) Then Return \$09+(x<>log2_array[\$09])
If (x & log2_array[\$0A]) Then Return \$0A+(x<>log2_array[\$0A])
If (x & log2_array[\$0B]) Then Return \$0B+(x<>log2_array[\$0B])
If (x & log2_array[\$0C]) Then Return \$0C+(x<>log2_array[\$0C])
If (x & log2_array[\$0D]) Then Return \$0D+(x<>log2_array[\$0D])
If (x & log2_array[\$0E]) Then Return \$0E+(x<>log2_array[\$0E])
If (x & log2_array[\$0F]) Then Return \$0F+(x<>log2_array[\$0F])
If (x & log2_array[\$10]) Then Return \$10+(x<>log2_array[\$10])
If (x & log2_array[\$11]) Then Return \$11+(x<>log2_array[\$11])
If (x & log2_array[\$12]) Then Return \$12+(x<>log2_array[\$12])
If (x & log2_array[\$13]) Then Return \$13+(x<>log2_array[\$13])
If (x & log2_array[\$14]) Then Return \$14+(x<>log2_array[\$14])
If (x & log2_array[\$15]) Then Return \$15+(x<>log2_array[\$15])
If (x & log2_array[\$16]) Then Return \$16+(x<>log2_array[\$16])
If (x & log2_array[\$17]) Then Return \$17+(x<>log2_array[\$17])
If (x & log2_array[\$18]) Then Return \$18+(x<>log2_array[\$18])
If (x & log2_array[\$19]) Then Return \$19+(x<>log2_array[\$19])
If (x & log2_array[\$1A]) Then Return \$1A+(x<>log2_array[\$1A])
If (x & log2_array[\$1B]) Then Return \$1B+(x<>log2_array[\$1B])
If (x & log2_array[\$1C]) Then Return \$1C+(x<>log2_array[\$1C])
If (x & log2_array[\$1D]) Then Return \$1D+(x<>log2_array[\$1D])
If (x & log2_array[\$1E]) Then Return \$1E+(x<>log2_array[\$1E])
If (x & log2_array[\$1F]) Then Return \$1F+(x<>log2_array[\$1F])
End Function

Rem
bbdoc: Returns Floor( Log2( x ) ) when x is a positive integer
about: Much faster than using floating point or double functions. Good for when you don't need to know the exact value.
EndRem
Function flog2%(x%)
If (x & log2_array[\$00]) Then Return \$00
If (x & log2_array[\$01]) Then Return \$01
If (x & log2_array[\$02]) Then Return \$02
If (x & log2_array[\$03]) Then Return \$03
If (x & log2_array[\$04]) Then Return \$04
If (x & log2_array[\$05]) Then Return \$05
If (x & log2_array[\$06]) Then Return \$06
If (x & log2_array[\$07]) Then Return \$07
If (x & log2_array[\$08]) Then Return \$08
If (x & log2_array[\$09]) Then Return \$09
If (x & log2_array[\$0A]) Then Return \$0A
If (x & log2_array[\$0B]) Then Return \$0B
If (x & log2_array[\$0C]) Then Return \$0C
If (x & log2_array[\$0D]) Then Return \$0D
If (x & log2_array[\$0E]) Then Return \$0E
If (x & log2_array[\$0F]) Then Return \$0F
If (x & log2_array[\$10]) Then Return \$10
If (x & log2_array[\$11]) Then Return \$11
If (x & log2_array[\$12]) Then Return \$12
If (x & log2_array[\$13]) Then Return \$13
If (x & log2_array[\$14]) Then Return \$14
If (x & log2_array[\$15]) Then Return \$15
If (x & log2_array[\$16]) Then Return \$16
If (x & log2_array[\$17]) Then Return \$17
If (x & log2_array[\$18]) Then Return \$18
If (x & log2_array[\$19]) Then Return \$19
If (x & log2_array[\$1A]) Then Return \$1A
If (x & log2_array[\$1B]) Then Return \$1B
If (x & log2_array[\$1C]) Then Return \$1C
If (x & log2_array[\$1D]) Then Return \$1D
If (x & log2_array[\$1E]) Then Return \$1E
If (x & log2_array[\$1F]) Then Return \$1F
End Function``````