I'll maintain that it is a binary search within each power of 16. Consider that the higher half of the possible numbers in the range will be found on the first test, half the remainder on the second test, half the remainder on the third test etc.
Sounds like a binary search to me.
You are right that the search tree could be more even ala:
This is the evenly balanced search tree providing an answer in 5 comparisons for all cases.
Like I said there are many ways to arrange the search tree depending on how well you know the input numbers and how finicky you want to be.
If the input numbers are uniformly distributed over 0 - 2^30 then the best tree would be:
That gives a lower average number of comparisons but the worst case is of course much higher.
On the timings - My testing is with Blitz2D since I don't have Blitz3D and I thought that they would be closer for basic calculations like this than BlitzMax.
Given the difference between your latest figures and mine perhaps they are more different than I thought.
Performance testing always seems to degrade into comparing the machines and language versions rather than finding out anything general and reliable about how to code for efficiency. In almost all cases I've found that Blitz performance is fantastic for the projects that I have.
Now with fast Alpha, 2D image rotation and other drawing speed improvements in BlitzMax everything is really good.
Sounds like a binary search to me.
You are right that the search tree could be more even ala:
Function NextPowerV4:Int(n:Int) If n <= $8000 If n <= $80 If n <= $8 If n <= $2 If n <= $1 Return $1 Else Return $2 EndIf Else If n <= $4 Return $4 Else Return $8 EndIf EndIf Else If n <= $20 If n <= $10 Return $10 Else Return $20 EndIf Else If n <= $40 Return $40 Else Return $80 EndIf EndIf EndIf Else If n <= $800 If n <= $200 If n <= $100 Return $100 Else Return $200 EndIf Else If n <= $400 Return $400 Else Return $800 EndIf EndIf Else If n <= $2000 If n <= $1000 Return $1000 Else Return $2000 EndIf Else If n <= $4000 Return $4000 Else Return $8000 EndIf EndIf EndIf EndIf Else If n <= $8000000 If n <= $80000 If n <= $20000 If n <= $10000 Return $10000 Else Return $20000 EndIf Else If n <= $40000 Return $40000 Else Return $80000 EndIf EndIf Else If n <= $200000 If n <= $100000 Return $100000 Else Return $200000 EndIf Else If n <= $400000 Return $400000 Else Return $800000 EndIf EndIf EndIf Else If n <= $8000000 If n <= $2000000 If n <= $1000000 Return $1000000 Else Return $2000000 EndIf Else If n <= $4000000 Return $4000000 Else Return $8000000 EndIf EndIf Else If n <= $20000000 If n <= $10000000 Return $10000000 Else Return $20000000 EndIf Else If n <= $40000000 Return $40000000 Else Throw "Value too big" EndIf EndIf EndIf EndIf EndIf End Function
This is the evenly balanced search tree providing an answer in 5 comparisons for all cases.
Like I said there are many ways to arrange the search tree depending on how well you know the input numbers and how finicky you want to be.
If the input numbers are uniformly distributed over 0 - 2^30 then the best tree would be:
Function NextPowerV5:Int(n:Int) If n > $40000000 Throw "Value too big" ElseIf n > $20000000 Return $40000000 ElseIf n > $10000000 Return $20000000 ElseIf n > $8000000 Return $10000000 ElseIf n > $4000000 Return $8000000 ElseIf n > $2000000 Return $4000000 ElseIf n > $1000000 Return $2000000 ElseIf n > $800000 Return $1000000 ElseIf n > $400000 Return $800000 ElseIf n > $200000 Return $400000 ElseIf n > $100000 Return $200000 ElseIf n > $80000 Return $100000 ElseIf n > $40000 Return $80000 ElseIf n > $20000 Return $40000 ElseIf n > $10000 Return $20000 ElseIf n > $8000 Return $10000 ElseIf n > $4000 Return $8000 ElseIf n > $2000 Return $4000 ElseIf n > $1000 Return $2000 ElseIf n > $800 Return $1000 ElseIf n > $400 Return $800 ElseIf n > $200 Return $400 ElseIf n > $100 Return $200 ElseIf n > $80 Return $100 ElseIf n > $40 Return $80 ElseIf n > $20 Return $40 ElseIf n > $10 Return $20 ElseIf n > $8 Return $10 ElseIf n > $4 Return $8 ElseIf n > $2 Return $4 ElseIf n > $1 Return $2 ElseIf n > $0 Return $1 Else Throw "Value too low" EndIf End Function
That gives a lower average number of comparisons but the worst case is of course much higher.
On the timings - My testing is with Blitz2D since I don't have Blitz3D and I thought that they would be closer for basic calculations like this than BlitzMax.
Given the difference between your latest figures and mine perhaps they are more different than I thought.
Performance testing always seems to degrade into comparing the machines and language versions rather than finding out anything general and reliable about how to code for efficiency. In almost all cases I've found that Blitz performance is fantastic for the projects that I have.
Now with fast Alpha, 2D image rotation and other drawing speed improvements in BlitzMax everything is really good.