From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=0.4 required=5.0 tests=BAYES_00,FORGED_MUA_MOZILLA
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Thread: a07f3367d7,7e15102eb14c0020
X-Google-Attributes: gida07f3367d7,public,usenet
X-Google-NewGroupId: yes
X-Google-Language: ENGLISH,ASCII-7-bit
Received: by 10.66.80.98 with SMTP id q2mr1678864pax.33.1349940040756;
        Thu, 11 Oct 2012 00:20:40 -0700 (PDT)
Path: 
 jt13ni2543pbb.1!nntp.google.com!npeer03.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!border3.nntp.dca.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!news.glorb.com!newsfeed1.swip.net!newsfeed.arcor.de!newsspool1.arcor-online.net!news.arcor.de.POSTED!not-for-mail
Date: Thu, 04 Oct 2012 09:46:16 +0200
From: Georg Bauhaus <rm.dash-bauhaus@futureapps.de>
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.7;
 rv:15.0) Gecko/20120907 Thunderbird/15.0.1
MIME-Version: 1.0
Newsgroups: comp.lang.ada
Subject: Re: highest bit, statically determined
References: <cd5ac9f5-ebd4-4c1a-8fee-478dd2680a43@googlegroups.com>
 <441830536370982493.692537rm-host.bauhaus-maps.arcor.de@news.arcor.de>
In-Reply-To: 
 <441830536370982493.692537rm-host.bauhaus-maps.arcor.de@news.arcor.de>
Message-ID: <506d3ec6$0$9524$9b4e6d93@newsspool1.arcor-online.net>
Organization: Arcor
NNTP-Posting-Date: 04 Oct 2012 09:46:14 CEST
NNTP-Posting-Host: 88f4b729.newsspool1.arcor-online.net
X-Trace: 
 DXC==Z3EZAeoF\VYI9]OHn9o5^ic==]BZ:af^4Fo<]lROoRQnkgeX?EC@@PUSa^hhA5AYZPCY\c7>ejVXZEoXj9QACFSO;Qj6`9JEO_
X-Complaints-To: usenet-abuse@arcor.de
X-Received-Bytes: 1964
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Date: 2012-10-04T09:46:14+02:00
List-Id: <comp.lang.ada>

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