highest bit, statically determined

highest bit, statically determined

[Georg Bauhaus]

Is there a shorter/better way of having the compiler
find the highest bit = 1 in a static numeric constant?

If N is such a constant, e.g. Some_Type'Last where
Some_Type'Size = 8 and its bound are static, then

    Highest_Bit_In_Octet : constant :=
      Natural'Max
      (8 * Boolean'Pos (N / 2**7 > 0),
       Natural'Max
       (7 * Boolean'Pos (N / 2**6 > 0),
        Natural'Max
        (6 * Boolean'Pos (N / 2**5 > 0),
         Natural'Max
         (5 * Boolean'Pos (N / 2**4 > 0),
          Natural'Max
          (4 * Boolean'Pos (N / 2**3 > 0),
           Natural'Max
           (3 * Boolean'Pos (N / 2**2 > 0),
            Natural'Max
            (2 * Boolean'Pos (N / 2**1 > 0),
             Natural'Max
             (1 * Boolean'Pos (N / 2**0 > 0), 0))))))));

Re: highest bit, statically determined

[Pascal Obry]

Georg,

> Is there a shorter/better way of having the compiler
> find the highest bit = 1 in a static numeric constant?
> 
> If N is such a constant, e.g. Some_Type'Last where
> Some_Type'Size = 8 and its bound are static, then
> 
>    Highest_Bit_In_Octet : constant :=
>      Natural'Max
>      (8 * Boolean'Pos (N / 2**7 > 0),
>       Natural'Max
>       (7 * Boolean'Pos (N / 2**6 > 0),
>        Natural'Max
>        (6 * Boolean'Pos (N / 2**5 > 0),
>         Natural'Max
>         (5 * Boolean'Pos (N / 2**4 > 0),
>          Natural'Max
>          (4 * Boolean'Pos (N / 2**3 > 0),
>           Natural'Max
>           (3 * Boolean'Pos (N / 2**2 > 0),
>            Natural'Max
>            (2 * Boolean'Pos (N / 2**1 > 0),
>             Natural'Max
>             (1 * Boolean'Pos (N / 2**0 > 0), 0))))))));

if N > 128 then
   return 8;
elsif N > 64
   return 7;
elsif ...

elsif N > 0 then
   return 1;
end if;

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|    http://www.obry.net  -  http://v2p.fr.eu.org
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver keys.gnupg.net --recv-key F949BD3B

Re: highest bit, statically determined

[Georg Bauhaus]

On 29.09.12 20:11, Pascal Obry wrote:

>>     Highest_Bit_In_Octet : constant :=
>>       Natural'Max
>>       (8 * Boolean'Pos (N / 2**7 > 0),
...
>>            (3 * Boolean'Pos (N / 2**2 > 0),
>>             Natural'Max
>>             (2 * Boolean'Pos (N / 2**1 > 0),
>>              Natural'Max
>>              (1 * Boolean'Pos (N / 2**0 > 0), 0))))))));
>
> if N > 128 then
>     return 8;
> elsif N > 64
>     return 7;
> elsif ...
>
> elsif N > 0 then
>     return 1;
> end if;
>


The N > 2**X part is good, thanks for the answer that removed
a fair bit of fog. But the "return X" indicates that the solution
cannot be static, or can it?

There might be an expression in Ada 2012 that does it. Alas,
I cannot use Ada 2012 yet---which I should have mentioned!

    Highest_Bit_In_Octet_2012 : constant :=
      (if N > 2**7 then 8
      elsif N > 2**6 then 7
      elsif N > 2**5 then 6
      elsif N > 2**4 then 5
      elsif N > 2**3 then 4
      elsif N > 2**2 then 3
      elsif N > 2**1 then 2
      elsif N > 2**0 then 1
      else 0);
      

Re: highest bit, statically determined

[Georg Bauhaus]

On 29.09.12 20:59, Georg Bauhaus wrote:

>     Highest_Bit_In_Octet_2012 : constant :=
>       (if N > 2**7 then 8

Or N >= 2**7, really.

Re: highest bit, statically determined

[Bill Findlay]

On 29/09/2012 18:34, in article
50673111$0$9505$9b4e6d93@newsspool1.arcor-online.net, "Georg Bauhaus"
<rm.dash-bauhaus@futureapps.de> wrote:

> Is there a shorter/better way of having the compiler
> find the highest bit = 1 in a static numeric constant?
> 
> If N is such a constant, e.g. Some_Type'Last where
> Some_Type'Size = 8 and its bound are static, then
> 
>     Highest_Bit_In_Octet : constant :=
>       Natural'Max
>       (8 * Boolean'Pos (N / 2**7 > 0),
>        Natural'Max
>        (7 * Boolean'Pos (N / 2**6 > 0),
>         Natural'Max
>         (6 * Boolean'Pos (N / 2**5 > 0),
>          Natural'Max
>          (5 * Boolean'Pos (N / 2**4 > 0),
>           Natural'Max
>           (4 * Boolean'Pos (N / 2**3 > 0),
>            Natural'Max
>            (3 * Boolean'Pos (N / 2**2 > 0),
>             Natural'Max
>             (2 * Boolean'Pos (N / 2**1 > 0),
>              Natural'Max
>              (1 * Boolean'Pos (N / 2**0 > 0), 0))))))));

In my experience that sort of code, applied in non-static cases, is less
efficient than one would hope, and more obvious code works faster.

Something like the following can be readily extended to greater operand
widths:

   function first_1_bit (y : octet)
   return Natural is
      x : octet;
      r : Natural;
   begin
      if y = 0 then return 0; end if;

      if (y / 16) /= 0 then
         r := 4; x := y / 16;
      else
         r := 0; x := y;
      end if;

      if (x / 4) /= 0 then
         r := r + 2; x := x / 4;
      end if;

      if (x / 2) /= 0 then
         r := r + 1;
      end if;

      return r + 1;
   end first_1_bit;

It looks fairly inline-able, and foldable for a static value of y.

-- 
Bill Findlay
with blueyonder.co.uk;
use  surname & forename;

Re: highest bit, statically determined

[Bill Findlay]

On 29/09/2012 19:57, in article CC8D0314.1E2CC%yaldnif.w@blueyonder.co.uk,
"Bill Findlay" <yaldnif.w@blueyonder.co.uk> wrote:

> On 29/09/2012 18:34, in article
> 50673111$0$9505$9b4e6d93@newsspool1.arcor-online.net, "Georg Bauhaus"
> <rm.dash-bauhaus@futureapps.de> wrote:
> 
>> Is there a shorter/better way of having the compiler
>> find the highest bit = 1 in a static numeric constant?
>> 
>> If N is such a constant, e.g. Some_Type'Last where
>> Some_Type'Size = 8 and its bound are static, then
>> 
>>     Highest_Bit_In_Octet : constant :=
>>       Natural'Max
>>       (8 * Boolean'Pos (N / 2**7 > 0),
>>        Natural'Max
>>        (7 * Boolean'Pos (N / 2**6 > 0),
>>         Natural'Max
>>         (6 * Boolean'Pos (N / 2**5 > 0),
>>          Natural'Max
>>          (5 * Boolean'Pos (N / 2**4 > 0),
>>           Natural'Max
>>           (4 * Boolean'Pos (N / 2**3 > 0),
>>            Natural'Max
>>            (3 * Boolean'Pos (N / 2**2 > 0),
>>             Natural'Max
>>             (2 * Boolean'Pos (N / 2**1 > 0),
>>              Natural'Max
>>              (1 * Boolean'Pos (N / 2**0 > 0), 0))))))));
> 
> In my experience that sort of code, applied in non-static cases, is less
> efficient than one would hope, and more obvious code works faster.
> 
> Something like the following can be readily extended to greater operand
> widths:
> 
>    function first_1_bit (y : octet)
>    return Natural is
>       x : octet;
>       r : Natural;
>    begin
>       if y = 0 then return 0; end if;
> 
>       if (y / 16) /= 0 then
>          r := 4; x := y / 16;
>       else
>          r := 0; x := y;
>       end if;
> 
>       if (x / 4) /= 0 then
>          r := r + 2; x := x / 4;
>       end if;
> 
>       if (x / 2) /= 0 then
>          r := r + 1;
>       end if;
> 
>       return r + 1;
>    end first_1_bit;
> 
> It looks fairly inline-able, and foldable for a static value of y.

I can now confirm that with GNAT GPL 2012 at -O3 it does inline and fold,
but I now see that you want the result to be static as well as the operand,
and this does not achieve that.

-- 
Bill Findlay
with blueyonder.co.uk;
use  surname & forename;

Re: highest bit, statically determined

[Georg Bauhaus]

On 29.09.12 21:16, Bill Findlay wrote:

functionfirst_1_bit

:-)

> I can now confirm that with GNAT GPL 2012 at -O3 it does inline and fold,
> but I now see that you want the result to be static as well as the operand,
> and this does not achieve that.

Daringly, I have tried to steal the idea and try a comparison (out of
curiosity, not for the static thing). GCC performs simple tail call
elimination (explaining the Shift parameter)!

    function First_1_Bit_A (y : octet; Shift : Integer := 0)  return Natural is
    begin
       if y >= 2**4  then
          if y >= 2**6 then
             return Shift + 7 + Boolean'Pos (y >= 2**7);
          else
             return Shift + 5 + Boolean'Pos (y >= 2**5);
          end if;
       else
          if Y = 0 then
             return 0;
          else
             return First_1_Bit_A (y * 2**4, Shift => -4);
          end if;
       end if;
    end First_1_Bit_A;

Don't know if that's as readily adaptable to other word sizes, but it might
make the functionist happier. ;-)

Re: highest bit, statically determined

[Georg Bauhaus]

On 29.09.12 23:36, Georg Bauhaus wrote:
> On 29.09.12 21:16, Bill Findlay wrote:
>
> function first_1_bit

>     function First_1_Bit_A (y : octet; Shift : Integer := 0)  return Natural is

first_1_bit is better by between 30% and 40% speed here.

Inlining can mean that the program runs about 4x as fast,
for each of the two functions.

(But, with GNAT, the deprecated -gnatN has *no* effect in the
case of first_1_bit_a.
Best options: -O2 -funroll-loops -gnatp -gnatn.)

Re: highest bit, statically determined

[Bill Findlay]

On 29/09/2012 22:36, in article
506769fb$0$6580$9b4e6d93@newsspool3.arcor-online.net, "Georg Bauhaus"
<rm.dash-bauhaus@futureapps.de> wrote:

> On 29.09.12 21:16, Bill Findlay wrote:
> 
> functionfirst_1_bit
> 
> :-)
> 
>> I can now confirm that with GNAT GPL 2012 at -O3 it does inline and fold,
>> but I now see that you want the result to be static as well as the operand,
>> and this does not achieve that.
> 
> Daringly, I have tried to steal the idea and try a comparison (out of
> curiosity, not for the static thing). GCC performs simple tail call
> elimination (explaining the Shift parameter)!
> 
>     function First_1_Bit_A (y : octet; Shift : Integer := 0)  return Natural
> is
>     begin
>        if y >= 2**4  then
>           if y >= 2**6 then
>              return Shift + 7 + Boolean'Pos (y >= 2**7);
>           else
>              return Shift + 5 + Boolean'Pos (y >= 2**5);
>           end if;
>        else
>           if Y = 0 then
>              return 0;
>           else
>              return First_1_Bit_A (y * 2**4, Shift => -4);
>           end if;
>        end if;
>     end First_1_Bit_A;

These bogus parameters, used to pretend that data is not intrinsically
variable, are as objectionable as using goto statements to synthesize while
loops, IMNSHO.

> Don't know if that's as readily adaptable to other word sizes, but it might
> make the functionist happier. ;-)

Fortunately, I have no interest in keeping functionists (or the adherents of
any other religion) happy. 8-)

-- 
Bill Findlay
with blueyonder.co.uk;
use  surname & forename;

Re: highest bit, statically determined

[Vadim Godunko]

On Sunday, September 30, 2012 1:37:00 AM UTC+4, Georg Bauhaus wrote:
> 
> Daringly, I have tried to steal the idea and try a comparison (out of
> curiosity, not for the static thing). GCC performs simple tail call
> elimination (explaining the Shift parameter)!
> 
If you don't need static function, you can use following function (GCC can precompute its result for static value):

with Interfaces.C; use Interfaces.C;

function Bit (X : Unsigned) return Unsigned;
pragma Inline (Bit);

function Bit (X : Unsigned) return Unsigned is

   function CLZ (X : Unsigned) return Unsigned;
   pragma Import (Intrinsic, CLZ, "__builtin_clz");

begin
   if X = 0 then
      --  XXX Return what you want.

      return 0;

   else
      return Unsigned'Size - CLZ (X);
   end if;
end Bit;

Re: highest bit, statically determined

[Yannick Duchêne (Hibou57)]

Le Sat, 29 Sep 2012 21:16:01 +0200, Bill Findlay  
<yaldnif.w@blueyonder.co.uk> a écrit:

>
> On 29/09/2012 19:57, in article  
> CC8D0314.1E2CC%yaldnif.w@blueyonder.co.uk,
> "Bill Findlay" <yaldnif.w@blueyonder.co.uk> wrote:
>
>> On 29/09/2012 18:34, in article
>> 50673111$0$9505$9b4e6d93@newsspool1.arcor-online.net, "Georg Bauhaus"
>> <rm.dash-bauhaus@futureapps.de> wrote:
>>
>>> Is there a shorter/better way of having the compiler
>>> find the highest bit = 1 in a static numeric constant?
>>>
>>> If N is such a constant, e.g. Some_Type'Last where
>>> Some_Type'Size = 8 and its bound are static, then
>>>
>>>     Highest_Bit_In_Octet : constant :=
>>>       Natural'Max
>>>       (8 * Boolean'Pos (N / 2**7 > 0),
>>>        Natural'Max
>>>        (7 * Boolean'Pos (N / 2**6 > 0),
>>>         Natural'Max
>>>         (6 * Boolean'Pos (N / 2**5 > 0),
>>>          Natural'Max
>>>          (5 * Boolean'Pos (N / 2**4 > 0),
>>>           Natural'Max
>>>           (4 * Boolean'Pos (N / 2**3 > 0),
>>>            Natural'Max
>>>            (3 * Boolean'Pos (N / 2**2 > 0),
>>>             Natural'Max
>>>             (2 * Boolean'Pos (N / 2**1 > 0),
>>>              Natural'Max
>>>              (1 * Boolean'Pos (N / 2**0 > 0), 0))))))));
>>
>> In my experience that sort of code, applied in non-static cases, is less
>> efficient than one would hope, and more obvious code works faster.
>>
>> Something like the following can be readily extended to greater operand
>> widths:
>>
>>    function first_1_bit (y : octet)
>>    return Natural is
>>       x : octet;
>>       r : Natural;
>>    begin
>>       if y = 0 then return 0; end if;
>>
>>       if (y / 16) /= 0 then
>>          r := 4; x := y / 16;
>>       else
>>          r := 0; x := y;
>>       end if;
>>
>>       if (x / 4) /= 0 then
>>          r := r + 2; x := x / 4;
>>       end if;
>>
>>       if (x / 2) /= 0 then
>>          r := r + 1;
>>       end if;
>>
>>       return r + 1;
>>    end first_1_bit;
>>
>> It looks fairly inline-able, and foldable for a static value of y.
>
> I can now confirm that with GNAT GPL 2012 at -O3 it does inline and fold,
> but I now see that you want the result to be static as well as the  
> operand,
> and this does not achieve that.
>

What means folding in this context?


-- 
“Syntactic sugar causes cancer of the semi-colons.” [1]
“Structured Programming supports the law of the excluded muddle.” [1]
[1]: Epigrams on Programming — Alan J. — P. Yale University

Re: highest bit, statically determined

[Bill Findlay]

On 04/11/2012 20:45, in article op.wm9nx2i3ule2fv@cardamome, "Yannick
Duch�ne   (Hibou57)" <yannick_duchene@yahoo.fr> wrote:

> Le Sat, 29 Sep 2012 21:16:01 +0200, Bill Findlay
> <yaldnif.w@blueyonder.co.uk> a �crit:
> 
>> 
>> On 29/09/2012 19:57, in article
>> CC8D0314.1E2CC%yaldnif.w@blueyonder.co.uk,
>> "Bill Findlay" <yaldnif.w@blueyonder.co.uk> wrote:
>> 
>>> On 29/09/2012 18:34, in article
>>> 50673111$0$9505$9b4e6d93@newsspool1.arcor-online.net, "Georg Bauhaus"
>>> <rm.dash-bauhaus@futureapps.de> wrote:
>>> 
>>>> Is there a shorter/better way of having the compiler
>>>> find the highest bit = 1 in a static numeric constant?
>>>> 
>>>> If N is such a constant, e.g. Some_Type'Last where
>>>> Some_Type'Size = 8 and its bound are static, then
>>>> 
>>>>     Highest_Bit_In_Octet : constant :=
>>>>       Natural'Max
>>>>       (8 * Boolean'Pos (N / 2**7 > 0),
>>>>        Natural'Max
>>>>        (7 * Boolean'Pos (N / 2**6 > 0),
>>>>         Natural'Max
>>>>         (6 * Boolean'Pos (N / 2**5 > 0),
>>>>          Natural'Max
>>>>          (5 * Boolean'Pos (N / 2**4 > 0),
>>>>           Natural'Max
>>>>           (4 * Boolean'Pos (N / 2**3 > 0),
>>>>            Natural'Max
>>>>            (3 * Boolean'Pos (N / 2**2 > 0),
>>>>             Natural'Max
>>>>             (2 * Boolean'Pos (N / 2**1 > 0),
>>>>              Natural'Max
>>>>              (1 * Boolean'Pos (N / 2**0 > 0), 0))))))));
>>> 
>>> In my experience that sort of code, applied in non-static cases, is less
>>> efficient than one would hope, and more obvious code works faster.
>>> 
>>> Something like the following can be readily extended to greater operand
>>> widths:
>>> 
>>>    function first_1_bit (y : octet)
>>>    return Natural is
>>>       x : octet;
>>>       r : Natural;
>>>    begin
>>>       if y = 0 then return 0; end if;
>>> 
>>>       if (y / 16) /= 0 then
>>>          r := 4; x := y / 16;
>>>       else
>>>          r := 0; x := y;
>>>       end if;
>>> 
>>>       if (x / 4) /= 0 then
>>>          r := r + 2; x := x / 4;
>>>       end if;
>>> 
>>>       if (x / 2) /= 0 then
>>>          r := r + 1;
>>>       end if;
>>> 
>>>       return r + 1;
>>>    end first_1_bit;
>>> 
>>> It looks fairly inline-able, and foldable for a static value of y.
>> 
>> I can now confirm that with GNAT GPL 2012 at -O3 it does inline and fold,
>> but I now see that you want the result to be static as well as the
>> operand,
>> and this does not achieve that.
>> 
> 
> What means folding in this context?

Compile-time evaluation, so that the end result is a compile-time known
(I do not say static, as that is a term of art in Ada) value.

-- 
Bill Findlay
with blueyonder.co.uk;
use  surname & forename;

Re: highest bit, statically determined

[Anatoly Chernyshev]

Ouch...
with ada.numerics.elementary_functions;
use ada.numerics.elementary_functions;
Highest_Bit_In_Octet:=natural(float'truncation(log(float(N),2.0)));

I didn't check it for speed though. Pros that it doesn't depend on the size.

Re: highest bit, statically determined

[Shark8]

On Sunday, September 30, 2012 9:39:41 AM UTC-6, Anatoly Chernyshev wrote:
> 
> with ada.numerics.elementary_functions;
> use ada.numerics.elementary_functions;
> Highest_Bit_In_Octet:=natural(float'truncation(log(float(N),2.0)));
> 
> I didn't check it for speed though. Pros that it doesn't depend on the size.

Nice!
Sometimes we get a little too caught-up in the problem-minutia we forget what the problem's really about. -- That, and some of these attributes aren't used enough to put them in the forefront of your mind when you hit a problem that can use them nicely.

Re: highest bit, statically determined

[Georg Bauhaus]

On 30.09.12 17:39, Anatoly Chernyshev wrote:
> Ouch...
> with ada.numerics.elementary_functions;
> use ada.numerics.elementary_functions;
> Highest_Bit_In_Octet:=natural(float'truncation(log(float(N),2.0)));
>
> I didn't check it for speed though. Pros that it doesn't depend on the size.

I did. And this time I had the program actually call the randomizing
Initialize I had written for the test data. .-/ Results have changed
in favor of the recursive first_1_bit_a. The test is running on a laptop,
so it likely says little about results on a microcontroller.

x an array of 12_000 octets, 10_000 iterations for each test.

First row : Count(f(x_{k}) = f(x_{k + 1})),
second row : time in seconds

    68580000 2.635991000    -- f is first_1_bit
    68580000 2.036651000    -- f is first_1_bit_a
    68580000 27.735934000   -- f is first_1_bit_log

with inline expansion:

    68580000 1.687923000
    68580000 1.447859000
    68580000 24.481472000

Slightly faster in both cases when translation suppresses checks,
the integer versions more than the FPT version.

Re: highest bit, statically determined

[Georg Bauhaus]

On 01.10.12 10:07, Georg Bauhaus wrote:

> First row : Count(f(x_{k}) = f(x_{k + 1})),
> second row : time in seconds
%s/row/column/

Re: highest bit, statically determined

[Anatoly Chernyshev]

> 
>     68580000 1.687923000
> 
>     68580000 1.447859000
> 
>     68580000 24.481472000

Yes, that could be expected. Here's the draft lightning-fast version:

procedure xx is
last_bit_a: array(0..255) of natural:=(0|1=>0,2|3=>1,4..7=>2, 8..15=>3, 16..31=>4,32..63=>5, 64..127=>6, 128..255=>7);
N:natural;
begin
...
Highest_Bit_In_Octet:=last_bit_a(N);
...
end xx;

Re: highest bit, statically determined

[Georg Bauhaus]

On 01.10.12 10:52, Anatoly Chernyshev wrote:
> (0|1=>0,2|3=>1,4..7=>2, 8..15=>3, 16..31=>4,32..63=>5, 64..127=>6, 128..255=>7);

    68580000 2.653934000
    68580000 2.021029000
    68580000 27.702262000
    68580000 1.173348000   -- first_1_bit_table

I guess the approaches can be used together for larger N-tets.

Re: highest bit, statically determined

[Shark8]

I wouldn't be surprised if you could make it faster by making it a constant.
Refactor something  like:

Type Light_Vector is array(0..255) of natural;
last_bit_a: Constant Light_Vector:=
(0|1=>0, 2|3=>1, 4..7=>2, 8..15=>3, 16..31=>4, 32..63=>5, 64..127=>6, 128..255=>7);

Re: highest bit, statically determined

[Georg Bauhaus]

On 02.10.12 00:55, Shark8 wrote:
> I wouldn't be surprised if you could make it faster by making it a constant.

It is a constant. Making it variable does not make a difference, though.

Re: highest bit, statically determined

[Brian Drummond]

On Mon, 01 Oct 2012 23:30:24 +0200, Georg Bauhaus wrote:

> On 01.10.12 10:52, Anatoly Chernyshev wrote:
>> (0|1=>0,2|3=>1,4..7=>2, 8..15=>3, 16..31=>4,32..63=>5, 64..127=>6,
>> 128..255=>7);
> 
>     68580000 2.653934000 68580000 2.021029000 68580000 27.702262000
>     68580000 1.173348000   -- first_1_bit_table
> 
> I guess the approaches can be used together for larger N-tets.

Just for completeness,

function first_bit_case(N:Octet) return natural is 
begin 
   case N is
      when 0       => return 0;
      when 1       => return 1;
      when 2..3    => return 2;
      when 4..7    => return 3;
      when 8..15   => return 4;
      when 16..31  => return 5;
      when 32..63  => return 6;
      when 64..127 => return 7;
      when others  => return 8;
   end case;
end first_bit_case;

Here (on an Atom netbook) it measures about the same as the equivalent if 
chain; faster than the recursive versions but slower than the table.

         --Z := Z + first_1_bit_ifchain(Data(i)); -- real 0m3.208s
         --Z := Z + first_bit_table(Data(i));	-- real	0m1.971s
         --Z := Z + first_1_bit(Data(i));	-- real	0m4.672s
         --Z := Z + First_1_Bit_A(Data(i));	-- real	0m3.937s
         Z := Z + first_bit_case(Data(i));	-- real	0m3.272s

The Ada-2012 case expression was no faster.

- Brian

Re: highest bit, statically determined

[kalvink65]

How about binary search algorithm with constant execution time:

Binary_Search_Highest_Bit_In_Octet_2012 : constant :=
      (if N > (2**4)-1 then -- determine upper or lower nibble
          -- upper nibble
          if N > (2**6)-1
            -- bits 7 and 6
            if N > (2**7)-1 then
                7
            else
                6
          else
            -- bits 5 and 4
            if N > (2**5)-1 then
                5
            else
                4
       else
          -- lower nibble
          if N > (2**2)-1 then
            -- bits 3 and 2
            if N > (2**3)-1 then
                3
            else
                2
          else
            -- bits 1 and 0
            if N > (2**1)-1 then
                1
            else
                0);

Disclaimer: I am not an Ada programmer, so this might not compile, but describes the idea anyway.

- Kalvin

Re: highest bit, statically determined

[Georg Bauhaus]

<kalvink65@gmail.com> wrote:
> How about binary search algorithm with constant execution time:
> 
> Binary_Search_Highest_Bit_In_Octet_2012 : constant :=
>       (if N > (2**4)-1 then -- determine upper or lower nibble
>           -- upper nibble
>           if N > (2**6)-1
>             -- bits 7 and 6
>             if N > (2**7)-1 then
>                 

Isn't this about the same as the recursive one?
(It uses Boolean'Pos around the third if.)

Also, I don't think its complexity is constant, since the number
of conditionals depends on the position of the first 1 bit.
That dependence is gone with the table.

Relative performance might depend on whether shift
and jump is more expensive than another branch of
conditionals. I'm guessing.

Re: highest bit, statically determined

[Georg Bauhaus]

On 03.10.12 20:54, Georg Bauhaus wrote:
> <kalvink65@gmail.com> wrote:
>> How about binary search algorithm with constant execution time:
>>
>> Binary_Search_Highest_Bit_In_Octet_2012 : constant :=
>>        (if N > (2**4)-1 then -- determine upper or lower nibble
>>            -- upper nibble
>>            if N > (2**6)-1
>>              -- bits 7 and 6
>>              if N > (2**7)-1 then
>>
>
> Isn't this about the same as the recursive one?
> (It uses Boolean'Pos around the third if.)

> Also, I don't think its complexity is constant,

Ouch. I have thought again, it has constant execution time.
For the recursive one, the above one, and the one using a table,
respectively, I get, in seconds:

1.62, 1.57, 0.95

Re: highest bit, statically determined

[Stephen Leake]

Brian Drummond <brian@shapes.demon.co.uk> writes:

> On Mon, 01 Oct 2012 23:30:24 +0200, Georg Bauhaus wrote:
>
>> On 01.10.12 10:52, Anatoly Chernyshev wrote:
>>> (0|1=>0,2|3=>1,4..7=>2, 8..15=>3, 16..31=>4,32..63=>5, 64..127=>6,
>>> 128..255=>7);
>> 
>>     68580000 2.653934000 68580000 2.021029000 68580000 27.702262000
>>     68580000 1.173348000   -- first_1_bit_table
>> 
>> I guess the approaches can be used together for larger N-tets.
>
> Just for completeness,
>
> function first_bit_case(N:Octet) return natural is 
> begin 
>    case N is
>       when 0       => return 0;
>       when 1       => return 1;
>       when 2..3    => return 2;
>       when 4..7    => return 3;
>       when 8..15   => return 4;
>       when 16..31  => return 5;
>       when 32..63  => return 6;
>       when 64..127 => return 7;
>       when others  => return 8;
>    end case;
> end first_bit_case;

Even better; binary search if/then/else instead of a linear case
statement; that cuts the number of compares significantly, especially
for larger word sizes.

-- 
-- Stephe

Re: highest bit, statically determined

[kalvin.news]

maanantai, 1. lokakuuta 2012 11.52.43 UTC+3 Anatoly Chernyshev kirjoitti:
> > 
> 
> >     68580000 1.687923000
> 
> > 
> 
> >     68580000 1.447859000
> 
> > 
> 
> >     68580000 24.481472000
> 
> 
> 
> Yes, that could be expected. Here's the draft lightning-fast version:
> 
> 
> 
> procedure xx is
> 
> last_bit_a: array(0..255) of natural:=(0|1=>0,2|3=>1,4..7=>2, 8..15=>3, 16..31=>4,32..63=>5, 64..127=>6, 128..255=>7);
> 
> N:natural;
> 
> begin
> 
> ...
> 
> Highest_Bit_In_Octet:=last_bit_a(N);
> 
> ...
> 
> end xx;

This can be optimised for improved size so that we create a lookup table only for a nibble values (0..15), and divide the handling into two parts according to whether the higher nibble is zero or non-zero. The end result would be a slighter slower execution speed but less code space. And this method can easily be extended to larger data sizes, too.

- Kalvin

Re: highest bit, statically determined

[Anatoly Chernyshev]

On Thursday, October 4, 2012 2:01:50 PM UTC+4, kalvi...@gmail.com wrote:
> maanantai, 1. lokakuuta 2012 11.52.43 UTC+3 Anatoly Chernyshev kirjoitti:
> 
> > > 
> 
> > 
> 
> > >     68580000 1.687923000
> 
> > 
> 
> > > 
> 
> > 
> 
> > >     68580000 1.447859000
> 
> > 
> 
> > > 
> 
> > 
> 
> > >     68580000 24.481472000
> 
> > 
> 
> > 
> 
> > 
> 
> > Yes, that could be expected. Here's the draft lightning-fast version:
> 
> > 
> 
> > 
> 
> > 
> 
> > procedure xx is
> 
> > 
> 
> > last_bit_a: array(0..255) of natural:=(0|1=>0,2|3=>1,4..7=>2, 8..15=>3, 16..31=>4,32..63=>5, 64..127=>6, 128..255=>7);
> 
> > 
> 
> > N:natural;
> 
> > 
> 
> > begin
> 
> > 
> 
> > ...
> 
> > 
> 
> > Highest_Bit_In_Octet:=last_bit_a(N);
> 
> > 
> 
> > ...
> 
> > 
> 
> > end xx;
> 
> 
> 
> This can be optimised for improved size so that we create a lookup table only for a nibble values (0..15), and divide the handling into two parts according to whether the higher nibble is zero or non-zero. The end result would be a slighter slower execution speed but less code space. And this method can easily be extended to larger data sizes, too.
> 
> 
> 
> - Kalvin

If you play with the memory optimization (I'm not very good at it), the array above will be made of 3 bit integers (0 to 7), which occupy lousy 3*256/8= 96 bytes of memory. Laughable by today's standards. Even if you go for long_long_long..._integers, the table will be quite small.

Re: highest bit, statically determined

[Anatoly Chernyshev]

> If you play with the memory optimization (I'm not very good at it), the array above will be made of 3 bit integers (0 to 7), which occupy lousy 3*256/8= 96 bytes of memory. Laughable by today's standards. Even if you go for long_long_long..._integers, the table will be quite small.

Here we go:

with Text_IO;
use Text_IO;
procedure xx is
type smallint is range 0..7;
type smallint_a is array(0..255) of smallint;
for smallint_a'Component_Size use 3;
last_bit_a: smallint_a:=(0|1=>0,2|3=>1,4..7=>2, 8..15=>3, 16..31=>4,32..63=>5, 64..127=>6, 128..255=>7);
begin
put_line (integer'Image (smallint_a'size/8));
end xx;