* highest bit, statically determined @ 2012-09-29 17:34 Georg Bauhaus 2012-09-29 18:11 ` Pascal Obry ` (2 more replies) 0 siblings, 3 replies; 28+ messages in thread From: Georg Bauhaus @ 2012-09-29 17:34 UTC (permalink / raw) 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)))))))); ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-09-29 17:34 highest bit, statically determined Georg Bauhaus @ 2012-09-29 18:11 ` Pascal Obry 2012-09-29 18:59 ` Georg Bauhaus 2012-09-29 18:57 ` Bill Findlay 2012-09-30 15:39 ` Anatoly Chernyshev 2 siblings, 1 reply; 28+ messages in thread From: Pascal Obry @ 2012-09-29 18:11 UTC (permalink / raw) To: Georg Bauhaus 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 ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-09-29 18:11 ` Pascal Obry @ 2012-09-29 18:59 ` Georg Bauhaus 2012-09-29 19:18 ` Georg Bauhaus 0 siblings, 1 reply; 28+ messages in thread From: Georg Bauhaus @ 2012-09-29 18:59 UTC (permalink / raw) 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); ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-09-29 18:59 ` Georg Bauhaus @ 2012-09-29 19:18 ` Georg Bauhaus 0 siblings, 0 replies; 28+ messages in thread From: Georg Bauhaus @ 2012-09-29 19:18 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-09-29 17:34 highest bit, statically determined Georg Bauhaus 2012-09-29 18:11 ` Pascal Obry @ 2012-09-29 18:57 ` Bill Findlay 2012-09-29 19:16 ` Bill Findlay 2012-09-30 15:39 ` Anatoly Chernyshev 2 siblings, 1 reply; 28+ messages in thread From: Bill Findlay @ 2012-09-29 18:57 UTC (permalink / raw) 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; ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-09-29 18:57 ` Bill Findlay @ 2012-09-29 19:16 ` Bill Findlay 2012-09-29 21:36 ` Georg Bauhaus 2012-11-04 20:45 ` Yannick Duchêne (Hibou57) 0 siblings, 2 replies; 28+ messages in thread From: Bill Findlay @ 2012-09-29 19:16 UTC (permalink / raw) 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; ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-09-29 19:16 ` Bill Findlay @ 2012-09-29 21:36 ` Georg Bauhaus 2012-09-29 22:06 ` Georg Bauhaus ` (2 more replies) 2012-11-04 20:45 ` Yannick Duchêne (Hibou57) 1 sibling, 3 replies; 28+ messages in thread From: Georg Bauhaus @ 2012-09-29 21:36 UTC (permalink / raw) 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. ;-) ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-09-29 21:36 ` Georg Bauhaus @ 2012-09-29 22:06 ` Georg Bauhaus 2012-09-29 23:38 ` Bill Findlay 2012-09-30 15:01 ` Vadim Godunko 2 siblings, 0 replies; 28+ messages in thread From: Georg Bauhaus @ 2012-09-29 22:06 UTC (permalink / raw) 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.) ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-09-29 21:36 ` Georg Bauhaus 2012-09-29 22:06 ` Georg Bauhaus @ 2012-09-29 23:38 ` Bill Findlay 2012-09-30 15:01 ` Vadim Godunko 2 siblings, 0 replies; 28+ messages in thread From: Bill Findlay @ 2012-09-29 23:38 UTC (permalink / raw) 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; ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-09-29 21:36 ` Georg Bauhaus 2012-09-29 22:06 ` Georg Bauhaus 2012-09-29 23:38 ` Bill Findlay @ 2012-09-30 15:01 ` Vadim Godunko 2 siblings, 0 replies; 28+ messages in thread From: Vadim Godunko @ 2012-09-30 15:01 UTC (permalink / raw) 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; ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-09-29 19:16 ` Bill Findlay 2012-09-29 21:36 ` Georg Bauhaus @ 2012-11-04 20:45 ` Yannick Duchêne (Hibou57) 2012-11-04 22:00 ` Bill Findlay 1 sibling, 1 reply; 28+ messages in thread From: Yannick Duchêne (Hibou57) @ 2012-11-04 20:45 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-11-04 20:45 ` Yannick Duchêne (Hibou57) @ 2012-11-04 22:00 ` Bill Findlay 0 siblings, 0 replies; 28+ messages in thread From: Bill Findlay @ 2012-11-04 22:00 UTC (permalink / raw) 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; ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-09-29 17:34 highest bit, statically determined Georg Bauhaus 2012-09-29 18:11 ` Pascal Obry 2012-09-29 18:57 ` Bill Findlay @ 2012-09-30 15:39 ` Anatoly Chernyshev 2012-09-30 18:36 ` Shark8 2012-10-01 8:07 ` Georg Bauhaus 2 siblings, 2 replies; 28+ messages in thread From: Anatoly Chernyshev @ 2012-09-30 15:39 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-09-30 15:39 ` Anatoly Chernyshev @ 2012-09-30 18:36 ` Shark8 2012-10-01 8:07 ` Georg Bauhaus 1 sibling, 0 replies; 28+ messages in thread From: Shark8 @ 2012-09-30 18:36 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-09-30 15:39 ` Anatoly Chernyshev 2012-09-30 18:36 ` Shark8 @ 2012-10-01 8:07 ` Georg Bauhaus 2012-10-01 8:11 ` Georg Bauhaus 2012-10-01 8:52 ` Anatoly Chernyshev 1 sibling, 2 replies; 28+ messages in thread From: Georg Bauhaus @ 2012-10-01 8:07 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-10-01 8:07 ` Georg Bauhaus @ 2012-10-01 8:11 ` Georg Bauhaus 2012-10-01 8:52 ` Anatoly Chernyshev 1 sibling, 0 replies; 28+ messages in thread From: Georg Bauhaus @ 2012-10-01 8:11 UTC (permalink / raw) 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/ ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-10-01 8:07 ` Georg Bauhaus 2012-10-01 8:11 ` Georg Bauhaus @ 2012-10-01 8:52 ` Anatoly Chernyshev 2012-10-01 21:30 ` Georg Bauhaus 2012-10-04 10:01 ` kalvin.news 1 sibling, 2 replies; 28+ messages in thread From: Anatoly Chernyshev @ 2012-10-01 8:52 UTC (permalink / raw) > > 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; ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-10-01 8:52 ` Anatoly Chernyshev @ 2012-10-01 21:30 ` Georg Bauhaus 2012-10-01 22:55 ` Shark8 2012-10-02 11:03 ` Brian Drummond 2012-10-04 10:01 ` kalvin.news 1 sibling, 2 replies; 28+ messages in thread From: Georg Bauhaus @ 2012-10-01 21:30 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-10-01 21:30 ` Georg Bauhaus @ 2012-10-01 22:55 ` Shark8 2012-10-01 23:25 ` Georg Bauhaus 2012-10-02 11:03 ` Brian Drummond 1 sibling, 1 reply; 28+ messages in thread From: Shark8 @ 2012-10-01 22:55 UTC (permalink / raw) 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); ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-10-01 22:55 ` Shark8 @ 2012-10-01 23:25 ` Georg Bauhaus 0 siblings, 0 replies; 28+ messages in thread From: Georg Bauhaus @ 2012-10-01 23:25 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-10-01 21:30 ` Georg Bauhaus 2012-10-01 22:55 ` Shark8 @ 2012-10-02 11:03 ` Brian Drummond 2012-10-03 9:30 ` kalvink65 2012-10-04 8:25 ` Stephen Leake 1 sibling, 2 replies; 28+ messages in thread From: Brian Drummond @ 2012-10-02 11:03 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-10-02 11:03 ` Brian Drummond @ 2012-10-03 9:30 ` kalvink65 2012-10-03 18:54 ` Georg Bauhaus 2012-10-04 8:25 ` Stephen Leake 1 sibling, 1 reply; 28+ messages in thread From: kalvink65 @ 2012-10-03 9:30 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-10-03 9:30 ` kalvink65 @ 2012-10-03 18:54 ` Georg Bauhaus 2012-10-04 7:46 ` Georg Bauhaus 0 siblings, 1 reply; 28+ messages in thread From: Georg Bauhaus @ 2012-10-03 18:54 UTC (permalink / raw) <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. ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-10-03 18:54 ` Georg Bauhaus @ 2012-10-04 7:46 ` Georg Bauhaus 0 siblings, 0 replies; 28+ messages in thread From: Georg Bauhaus @ 2012-10-04 7:46 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-10-02 11:03 ` Brian Drummond 2012-10-03 9:30 ` kalvink65 @ 2012-10-04 8:25 ` Stephen Leake 1 sibling, 0 replies; 28+ messages in thread From: Stephen Leake @ 2012-10-04 8:25 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-10-01 8:52 ` Anatoly Chernyshev 2012-10-01 21:30 ` Georg Bauhaus @ 2012-10-04 10:01 ` kalvin.news 2012-10-05 7:50 ` Anatoly Chernyshev 1 sibling, 1 reply; 28+ messages in thread From: kalvin.news @ 2012-10-04 10:01 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-10-04 10:01 ` kalvin.news @ 2012-10-05 7:50 ` Anatoly Chernyshev 2012-10-05 8:38 ` Anatoly Chernyshev 0 siblings, 1 reply; 28+ messages in thread From: Anatoly Chernyshev @ 2012-10-05 7:50 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: highest bit, statically determined 2012-10-05 7:50 ` Anatoly Chernyshev @ 2012-10-05 8:38 ` Anatoly Chernyshev 0 siblings, 0 replies; 28+ messages in thread From: Anatoly Chernyshev @ 2012-10-05 8:38 UTC (permalink / raw) > 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; ^ permalink raw reply [flat|nested] 28+ messages in thread
end of thread, other threads:[~2012-11-04 22:00 UTC | newest] Thread overview: 28+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2012-09-29 17:34 highest bit, statically determined Georg Bauhaus 2012-09-29 18:11 ` Pascal Obry 2012-09-29 18:59 ` Georg Bauhaus 2012-09-29 19:18 ` Georg Bauhaus 2012-09-29 18:57 ` Bill Findlay 2012-09-29 19:16 ` Bill Findlay 2012-09-29 21:36 ` Georg Bauhaus 2012-09-29 22:06 ` Georg Bauhaus 2012-09-29 23:38 ` Bill Findlay 2012-09-30 15:01 ` Vadim Godunko 2012-11-04 20:45 ` Yannick Duchêne (Hibou57) 2012-11-04 22:00 ` Bill Findlay 2012-09-30 15:39 ` Anatoly Chernyshev 2012-09-30 18:36 ` Shark8 2012-10-01 8:07 ` Georg Bauhaus 2012-10-01 8:11 ` Georg Bauhaus 2012-10-01 8:52 ` Anatoly Chernyshev 2012-10-01 21:30 ` Georg Bauhaus 2012-10-01 22:55 ` Shark8 2012-10-01 23:25 ` Georg Bauhaus 2012-10-02 11:03 ` Brian Drummond 2012-10-03 9:30 ` kalvink65 2012-10-03 18:54 ` Georg Bauhaus 2012-10-04 7:46 ` Georg Bauhaus 2012-10-04 8:25 ` Stephen Leake 2012-10-04 10:01 ` kalvin.news 2012-10-05 7:50 ` Anatoly Chernyshev 2012-10-05 8:38 ` Anatoly Chernyshev
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox