Boost logo

Boost :

From: Gennaro Prota (gennaro_prota_at_[hidden])
Date: 2003-02-04 10:07:35


On Tue, 4 Feb 2003 02:20:14 -0500, Daryle Walker <dwalker07_at_[hidden]>
wrote:

>I haven't been following Boost that much lately. Spent the past few
>days catching up.
>
>Some people have been discussing changes to the algorithm used by
>static_log2 lately.

Yes. Thanks for intervening. To be more precise, the issue is not
about the algorithm per se, but about the combination algorithm used +
its (compile-time) C++ implementation.

> Actually, I've forgotten why I used the
>implementation I did. I sometimes tend to be verbose in my code;
>hopefully compilers can optimize some of it out. Also, when you see an
>algorithm looking more complex than you think it should, be mindful
>that the code may be bigger to workaround some gotchas that the simpler
>alternative doesn't consider.

Yes, I asked also to see if this was the reason.

>The newer code I've seen on the list uses the same ideas as the current
>code, but there are enough differences that I have questions about.
>
>1. The current static_log2_helper_t uses three template arguments, the
>new code only uses two. I guess there's some merging of the Place and
>Index uses; can you explain further.

Er... I would like to. Unfortunately I haven't understood how the
current implementation works.

>2. The base case of the new code uses fully specialized
>static_log2_impl<1,0>, while the current code uses a partially
>specialized static_log2_helper_t<Val, Place, 1> (which requires
>workarounds for some compilers). One of the posts implied that the "1"
>in the first template argument is guaranteed in the usual
>circumstances. Can you explain further, including how to ensure that
>the usual circumstances occur.

Yes. I have attached the full code here. Basically the reason why,
when n=0, you always end up with x=1 relies on how you choose the
initial value of n and what preconditions holds at each recursion. The
proof is easy but maybe it's better going with an informal
explanation.

Let w be the width (number of value bits) of an unsigned long: then
choose_initial_n chooses the maximum power of two, say 'ni', such as:

   2**p = ni < w

For instance, with 32 bit unsigned longs, it chooses 16. This number
is the initial shift count if the value x of which you want to compute
the logarithm is >= 65536. Of course if x>=65536 this means that its
binary representation has at least one bit set in a position >=16.
Basically, the algorithm "constructs" the logarithm as sum of powers
of two, i.e. it acts as if you built the binary representation of the
logarithm itself. Suppose e.g that x = 192 = 128 + 64; in this case
the logarithm, 7, is constructed as 1+2+4. More precisely, you start
with n = 16, but continue without shifting x until you reach (by
repeatedly dividing n by two) n = 4. Note that the initial n _is_ a
power of two, so it is still a power of two at each recursion, except
the last one where it is zero. Now you have x>>4 >0, thus L>=4 and
thus

     L = 4 + some other non negative integer

Note that you shift x by a certain amount n only if you are sure that
that amount doesn't causes your left-most bit 1 to "go out" on the
right; this means that you never end up with x = 0. In other words:
x>=1 at each recursion. Now, could you end up with a number x
different from both 1 and 0? No, because whatever number x != 0 you
have at each recursion

  - it can't be >= 2**(value of n in the previous recursion step),
    otherwise it would have been shifted at that step. [well, except
    for the very first one, in which this precondition is enforced by
    choose_initial_n]

This means that when you reach n = 0 (which happens necessarily) your
x is greater than zero and smaller than 2**(1) = 2, i.e it is 1! :-)

To track down the behavior in the example above:

  log2(192) =

        4 + log2(192/16) = 4 + log2(12) // note that 12 < 2**4
        4 + 2 + log2(12/4) = 6 + log2(3) // " " 3 < 2**2
        4 + 2 + 1 + log2(3/2) = 7 + log2(1)
              

>3. One reason for the timing differences could be that the current code
>has an extra masking step that the new code doesn't have. Is the
>masking I'm doing really needed?

I'm sorry to not be helpful for this question, because I haven't dug
that much into the current implementation. Before doing any further
investigation, I asked here why it was chosen, but then Vesa Karvonen
proposed the algorithm above and I gave up looking at the old one.
BTW, note that the new code works even if unsigned long has padding
bits, without using std::numeric_limits. This is particularly
important for me because I wanted to propose a clean up for the
std::numeric_limits implementation we have for broken compilers
(boost/detail/limits.hpp). The idea to do the clean up is that members
such as digits and digits10 can be computed; for instance:

  digits = 1 + static_log2 <max_of<T> :: value> :: value;

Actually the above leads to another change I wanted to propose for the
Integer library: the current integer_traits<> already provides min and
max as integral constant expressions, but derives from numeric_limits
apparently for no reason. I propose to deprecate it and use a simple
template like:

  template <typename T> struct max_of { /* not defined */ };

which is specialized for each built-in integral type. In practice a
generic mapping of the macros in <climits>. There are other additions
I would like to propose too, so I've attached everything in the .zip
file. Please, consider that the code needs a little cleanup.

Genny.

begin 644 new - static_log2.hpp
M+R\@($)O;W-T(&EN=&5G97(O<W1A=&EC7VQO9S(N:'!P(&AE861E<B!F:6QE
M("`M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+R\-"@T*+R\@("A#
M*2!#;W!Y<FEG:'0_at_1&%R>6QE(%=A;&ME<B`R,#`Q+B`@4&5R;6ES<VEO;B!T
M;R!C;W!Y+"!U<V4L(&UO9&EF>2P@<V5L;"!A;F0-"B\O("!D:7-T<FEB=71E
M('1H:7,@<V]F='=A<F4@:7,@9W)A;G1E9"!P<F]V:61E9"!T:&ES(&-O<'ER
M:6=H="!N;W1I8V4_at_87!P96%R<R`-"B\O("!I;B!A;&P_at_8V]P:65S+B`@5&AI
M<R!S;V9T=V%R92!I<R!P<F]V:61E9"`B87,@:7,B('=I=&AO=70_at_97AP<F5S
M<R!O<@T*+R\@(&EM<&QI960@=V%R<F%N='DL(&%N9"!W:71H(&YO(&-L86EM
M(&%S('1O(&ET<R!S=6ET86)I;&ET>2!F;W(@86YY('!U<G!O<V4N(`T*#0HO
M+R`@4V5E(&AT='`Z+R]W=W<N8F]O<W0N;W)G(&9O<B!U<&1A=&5S+"!D;V-U
M;65N=&%T:6]N+"!A;F0@<F5V:7-I;VX@:&ES=&]R>2X@#0H-"B-I9FYD968@
M0D]/4U1?24Y414=%4E]35$%424-?3$]',E](4%`-"B-D969I;F4_at_0D]/4U1?
M24Y414=%4E]35$%424-?3$]',E](4%`-"@T*#0HC:6YC;'5D92`B8F]O<W0O
M8V]N9FEG+FAP<"(@+R\@9F]R($)/3U-47U-4051)0U]#3TY35$%.5`T*#0IN
M86UE<W!A8V4_at_8F]O<W0@>PT*("!N86UE<W!A8V4_at_9&5T86EL('L-"@T*#0H@
M("`@+R\@0VAO;W-E(&%N(&EN:71I86P@=F%L=64_at_9F]R('1H92!C;W)E(&EL
M;V<R(&%L9V]R:71H;2X-"B`@("`O+R!)9B!W92!C86QL($U!6"!T:&4@;6%X
M:6UU;2!V86QU92!F;W(@=6YS:6=N960@;&]N9W,@*%5,3TY'7TU!6"D-"B`@
M("`O+R!T:&%T(&EN:71I86P@=F%L=64@;B!I<R!T:&4@<&]W97(@;V8@='=O
M("AN/3)><"D@=&AA="!S871I<V9I97,-"B`@("`O+R!T:&4_at_9F]L;&]W:6YG
M(')E;&%T:6]N._at_T*("`@("\O#0H@("`@+R\@("`R7FX@/"!-05@@/#T@,EXH
M,FXI("T@,2`@(%L@;B`](#)><"!=("`@("@J*0T*("`@("\O(`T*("`@("\O
M($5X86UP;&4Z(&EF(&]N('EO=7(@<&QA=&9O<FT@=6YS:6=N960@;&]N9W,@
M:&%V92`T."!V86QU92!B:71S#0H@("`@+R\@("`@("`@("`@=&AE;B!N(#T@
M,S(@:7,@8VAO<V5N("AP/34I+@T*("`@("\O#0H@("`@+R\@3F]T92!T:&%T
M(&-H;V]S:6YG(&$@<&]W97(@;V8@='=O(&%S(&EN:71I86P@=F%L=64@<VEM
M<&QI9FEE<PT*("`@("\O('1H92!C;W)E(&%L9V]R:71H;2X_at_26X@<&%R=&EC
M=6QA<B!C:&]O<VEN9R!T:&4@<&]W97(@;V8@='=O#0H@("`@+R\@86-C;W)D
M:6YG('1O("@J*2!E;G-U<F5S('1H92!S=6ET86)I;&ET>2!O9B!T:&4_at_8V]R
M92!A;&=O<FET:&T-"B`@("`O+R!F;W(@86YY('=I9'1H(&]F('5N<VEG;F5D
M(&QO;F=S+@T*("`@("\O#0H-"B`@("!T96UP;&%T93QI;G0@;CX-"B`@("!S
M=')U8W0_at_8VAO;W-E7VEN:71I86Q?;B![#0H@("`@("`@(&5N=6T@>R!C(#T@
M(2_at_Q=6P\/&X\/&XI('T[#0H@("`@("`@($)/3U-47U-4051)0U]#3TY35$%.
M5"AI;G0L('9A;'5E(#T_at_8RIN("L_at_8VAO;W-E7VEN:71I86Q?;CPA8RIN*C(^
M.CIV86QU92D[#0H@("`@?3L-"@T*("`@('1E;7!L871E/#X-"B`@("!S=')U
M8W0_at_8VAO;W-E7VEN:71I86Q?;CPP/B![#0H@("`@("!"3T]35%]35$%424-?
M0T].4U1!3E0H:6YT+"!V86QU92`](#`I.PT*("`@('T[#0H-"@T*("`@('-T
M871I8R!C;VYS="!I;G0@:6YI=&EA;%]V86QU92`](&-H;V]S95]I;FET:6%L
M7VX\,38^.CIV86QU93L-"@T*#0H@("`@+R\@0V]R92!A;&=O<FET:&T-"B`@
M("`O+PT*("`@('1E;7!L871E/'5N<VEG;F5D(&QO;F<@>"P@:6YT(&X@/2!I
M;FET:6%L7W9A;'5E/@T*("`@('-T<G5C="!S=&%T:6-?;&]G,E]I;7!L('L-
M"B`@("`@("`@96YU;2![8VX@/2`H,75L/#QN(#P]('@I("H@;GT[#0H@("`@
M("`@($)/3U-47U-4051)0U]#3TY35$%.5"AI;G0L('9A;'5E(#T_at_8VX@*R`H
M<W1A=&EC7VQO9S)?:6UP;#PH>#X^8VXI+&XO,CXZ.G9A;'5E*2D[#0H@("`@
M?3L-"@T*("`@('1E;7!L871E/#X-"B`@("!S=')U8W0@<W1A=&EC7VQO9S)?
M:6UP;#PQ=6PL,#X@>PT*("`@("`@0D]/4U1?4U1!5$E#7T-/3E-404Y4*&EN
M="P@=F%L=64@/2`P*3L-"B`@("!].PT*("!]#0H-"B`@=&5M<&QA=&4\=6YS
M:6=N960@;&]N9R!X/@T*("!S=')U8W0@<W1A=&EC7VQO9S(@>PT*("`@($)/
M3U-47U-4051)0U]#3TY35$%.5"AI;G0L('9A;'5E(#T_at_9&5T86EL.CIS=&%T
M:6-?;&]G,E]I;7!L/'@^.CIV86QU92D[#0H@('T[#0H-"B`@=&5M<&QA=&4\
M/@T*("!S=')U8W0@<W1A=&EC7VQO9S(\,'5L/B![?3L-"GT-"@T*#0H-"B-E
7;F1I9B`O+R!I;F-L=61E(&=U87)D#0H\
`
end

begin 644 Additions.zip
M4$L#!!0````(`(J4+B[>7=3V+0,``&0)```8````9&5T86EL+W=C:&%R7VUI
M;E]M87_at_N:'!PM59;;]HP%'ZOU/]PUDHM]`(4UH=-[22@'2"U@("J3*H4N8E)
MO`4;V0X7J3]^QTX(E\*@TV8)D1R?Z_?Y^"2?/SS(YV$@)%3/SX$-1R$=4JZ)
M9H(KT`'1X`E^JF$DQ9AY%)ZK]7+'>6PT_at_7!O_E;NPY"X4BCKK2DTC4V5&%((
MV:LDDE$%0Z:,3Z%HH_at_YT3+F11'Z`?W2&P>:1K"L"-^[$#8C\!@$E'I60H3D_
M!Q4A0Q/?)'V=N\Y>6.URJ`3P-'I`QHS[6S/VZ(!QZF%(JDR%FH8AS$1D74T"
MBOE(L,$=#0P3EY1HU"<*T_*8THR[:#4;4<B_at_C&&Y6$CH90'1Q"QRQE'\.SPX
M9_at_..`:'2:G5[3IJ22<2IM]M.K>T4"X52X>JJB,IQ:OLI&]_<#2/DYNA5"*7S
MKN`#YN>"T>AH/7"SY52M/]R`N=D<8I11[K&!\9GDG(*42;/(PLG).W&YGS46
ML+3R9P:$P#"@A>'U+`:"AHI:740Y!@R15]K0#WHBYB=#T1&1B'<XNX#72,?Z
M(=6G"GY&J$Z4BH8)T5P_at_6&*0ND"RD_at_07A>!*9!G'J;0Z#^7F7=5QLK!CO2RJ
M>GM;<E']47M&2G8YV&:.0-:>2\5=]JOFF:4*[EM=8[S@`H6UYI,I:>'R9962
MCZS\6<P7&-RQ'6P7A.P7A8_at_KYAORD3VI+;Y)#DNM5G_at_OQ99[ZM8[/?.4G`3D
M9:DFY3-;4.;30M:M-9QN[\%IMSJ]K,%_at_500W4)A^+A2R6V!,`5A"#UV4V^V'
M^SW(WW=M"H/)?Y>45KIWNWG:<VT)$XRBZ>8(%LWY&]S>0LF*MN&;70OS_];B
M=-GSU13;;NF+]`8.B+(-K_at_BVO23<I^8F9MS<LXD;N`2L!QX;[2X.$9_at_P'0#'
M43:>#Z'9LNHC<:'5A?XN/=]U07!(R#3R]=U2;FHTZNW+IWZ\M[$G&LV>^=_8
M&7:O;*T7O?%7%!?_2/$_`3V]`=;1-V`4<U^N5_#XR/V0PI!<W/&P.`8J)0[5
MHXJ9;QBG2CC.EO=>5ZKX"O_at_Q0_!;@WAV8L0U#1EWAF2:3,?5D1<_VV(^-O>6
MC-%V/E?]B$B<0+\!4$L#!`H``````)%F1"X````````````````'````9&5T
M86EL+U!+`P04````"``TED$NYUGP%@<"``#T`P``#````&AA<U]S:6=N+FAP
M<+53P6[;,`R]!\@_$.DA2;O:;E<,0^H5Z`PL[6%)`!N]&DI,V0(<R9/D%-VP
M?Q]IN\F*'88=!OL_at_410?WWM4&(Y'80B5<+E3I8[O>-N%,JQK!\\5^@HM"`U*
M>RQIZ5\:A!T%+#86'6H/&DOAU0'A(.H670`KXQ%\)7Q7RE?*`?V%DA(M7Y#6
M[,&)%Z5+4)[/!$RX`2S>X$QH1]<1",8A&-EMDHL+<%[H0M_at_B.#8\2^:P1*V%
M-;"QQ_at_NXCJ+WXQ%_9TKJ`B5\7J_3+'^X3_/T<;G*'S:;?+G)*>\ZNHH^4!XE
M*8U_S>.*>E>W!<)D:XSSX<YHJ<J@:IH)'X?G\,58V+:J]I?,@<BX08A]4^.>
M5"#)C&;N^*U5I!R%QB,`\*9C::@/L34'#.`\'$A`!,1T&6R"-'C;Q5[IW,@C
MOD="$61"S,A:[!$R\M9YV^[\T6[XT0$.=-/L/GM,\F2]HM4JFQ&Q^EUO*7R"
M'B#.[A:+/A1#-+\=CW[>=HU@[?#_`,\@FUU>S1D/YO`;),G1VU7,^CI?TZ=D
MSH5)(]?@3HE:?4>0;`257`Q'S\I7G<(E:K2BA_at_-:QU9T:L,3CU=)T^R&_.3F
M8W2S@&D\A06TV_at_F)T`[3R&]ARL6G/*FFH7KL:G_SI$;\IP0QW[K[%R&D((U?
M^9^AIN?$[9VX]T9P_+3BC-<A*5MZ,./1+U!+`P04````"`!Z:T0N$@'T'E<$
M``#F"P``$0```&EN=&-O;G-T7VQO9S(N:'!PG59M;]LV$/Y>H/_AFGV1,M=.
MW`X8',=`ZP5I@"X.%@\;,*P"(U$2,8H42"JV4>2_[XZR)5EVTVR$@4C*<\\]
M]T9R-`+XJ+5U()3C&3<CZY_at_3<21U-A[F90DY9PDWD`K)`=X^OT:CUZ]>OQHA
M9S`/8:[+C1%9[N`79C9H_@>3_R#5^.SL?`APQTTAK!5:@=,0(W@`E>4#*'0B
M4GRQ7$I@*JD9$V&=$0^5X^!R8<'JU*V8X8#/F6&H/H'2Z$>1X(-'Q(U_I3$D
M#JPL.3,6:D*A@*$#1`EN4<^RS]JPG3"+[R>P$B[7E0.^+@VW%K39,A6E%(A#
M0Q*"TE&U1Z-GB"43!2`%1BD<NJB$8P]""K>!5!O$;J"L3*DM'\(N?_><0^Y<
M.1F-5JO5\(%*--0F\Q95F3#'[0`2'5<%5U0QK6JOAC\*GU.,QFFSJ2E_$*E*
M>`H?%XO[971SN[RZOOHMNE]^6-[,H\^+ZW'TZ>X.88_at_1BG\/5C.J6%8)AQ.O
M;11KE8J,.N8$,`"26;-LK>>+6WRZ79*M8_at_6W)<.*>%OX2A^A_=IIP<AM2FX)
M`;3HC>*HE!69PI1+K3)@)O.XBQX*6QK:A26KI&N`3SVG"7=,R,;3_A^,:)ZC
M5NPAA;3""2;AD<F*^TA=SK&/J&M(,[95I_at_U6OQBVYC<IK!!$'??KAS^]1<'6
MHJB*#L]>6!:"WS\O;J\CQ(<MD<N9ZTE0U*W$6.H5SI=.P:TT!.IR_*4,:P.+
M&;4I-GJ7B)Q*J5<"<VBX]%TT:0`M$F#\1<'4"Y]>XDLP5B&\A7/\SU_HG3Z5
M\#>A@]..U/;I:LUP1O@$1`K8FQM=&2C1(09=]*/.V2.']S]O8WO`D>DJV2X4
MK[SG=V,*/LZQ-_at_J"\O*G<'@D_at_EOMMPU,1$QEI(#9?K9HQ/>2:OU4'Z;,U[FM
M,-PH*)G!?JTD,RU]OQPM"8N1(O$83?D"KFR%S>E-NIL#&1XX;'EV>\=*)+C1
MZ-Y0V(,T=!1LYP6*"J?O@;>6M(/X_#/7PB5G"",IN+ME_,#5-QSMAI$75&D^
MI6E4L^U76KB?5_&V(CS:9C]2S0C2X_at_H'Y"O$6.DW`00'.\-DL_at_LF.`]#F$X5
M_D)XNNAP'-V'`I0S@`Z*5EWY2XA/%?QX(&SZ!K^?CF>3B<>%.Q^-LW[$+PAV
M>C8[%N].R%E+WO>"&VY]:D.!;+B/1!45(ZK;@0;CX@"Y<]O$V5=SA&K4!-P3
MT#;(_'B']M/Q3/%@/?`"::+W1!Y)89>&9O1(_F+B>5F[T(:V#N$4U`MZY_at_A?
MYU09M/U#[1/TA4Z#]6P6JW"@VIR&_ZN+#IC/*SGH==(S7=]TU[[SI_JE/M^I
MKM^Y[;6KAG=43=>S_TA!'+7_)O#]0W[=R<-A&KJAMT_?N(%`9[VXIO7]8#(Y
MR/VZOR'L*MD+YUG]T[-*8OW(]&E[![P>W_at_WOAWC,$D-[-_/1^GO3GA9_)^,*
M;\Z4]MWE+*N8P?OSOU!+`P04````"`!QF"XNT]&[':("``!5!P``"@```&UA
M>%]O9BYH<'"UE5%KVS`0Q]\+_0ZW]B5ILSC=V$O2!;*P)8'.#K5#QQ_at_8U98=
M_at_2,926Z;C7[WG63'<<:"V\$N!!OK]#_=[^YLQX$->0I%TE_G^>F)XY@_S-@#
M5:#7U"S"`\D*"B(!PK?`N*:I)!GH;4Z!*'RX?Q8)KC3A^BU]RB55B_at_E>:W:F
M79A1SHD4L)1"$W_at_W&+POE\]9PF.:P"?/\X/PZ^1;Z'T)Y\ME.%N&QFMP-?B`
M7NC".&WQ,FH\RHJ8PG64L0W3:GSP]"RFFK#,>8S61(8;QD-,TJ1_!@`F^?ZR
M[_>;&^Z%4-K!Y!*66L?F8B[%1FC,M%HQ/U1QA:9#N*>/1%IV!J9%AO<E\>OQ
M<&C1CH!I8`JBM5"4`XDB(6/&4ZM3FA96H`9=!P599%3U35!--WE&-*9MXG"R
MH1",06E91+H*";_`N0`N-)0H8[APX'E4'WI.LYQ*=(ZP2!BS`JYR&C&2L9_$
MA%15S:K%J@[^\O-T,;E9?)\$"\_M*%'(B(;F)#W30%UHLQ^G)^:RSV+<MJ/5
M*LD#!->-DXV1QRNMDC16MJ$?8,+3<.JY>.<&G;(R-/XSU'!8L\!A^FB9C)J2
MST<B_HLU3OD:P]Z@/!YB_at_X"B&Q:)#!NLM`NG;)(CY<8)R7J`G*D1N3)MU1T=
M]3:#UX/I?')KIK@[*L<S_at_3>[KNR4;%TO7+C![<+UD?"=]0^Z1U7+>=8]N&LJ
MGV-&++%'QP;W66KT[1QAHYN2J-Y^XG9S-KV\!/,BBXF,L2,EOB201;H]&EN5
MNF5B?C/^L0UK(;4Y1P_A^O/;H,6_\BP-H;2X8^'2G3K<>.YL#]I_at_6''UGT`4
M_`"%M=4+>-3[&F!6+^!2-#+9`5JU\ZFW-4"M#CEAZQ3VH_17!;MN6\OPW'T,
MT@(YG9[\!E!+`P04````"`!=E2XN>O]ZX!`"``"_!0``"@```&UI;E]O9BYH
M<'"M5&&+FT`0_1[(?YC:+TE(HVWIE\LUD(8V$:XJ43_at_H!=G3U2SHKKCK]8YR
M_[T[:A+3UO,H'0B1W??>SIN97=.$G/%0)(M#48Q'IHD_V+)[*D$=*&["/<DJ
M"B(!PA^!<473DF2@'@L*1.K%\UHDN%2$JS?TH2BIE$SPD^9D,X4MY9R4`KQ2
M*`+O+.M]L_V:)3RF"7QR73\(O]I.Z'X)=YX7;KT04=9;ZX-&:0CC=`"%:CS*
MJIC"=92QG"FYZJP9,56$9>:/Z$#*$+WGY`'-&P"`UA?>PE]<R!A%*7*AM)D:
MU]VY$T(J4]M.6-INCD>*YD5&E#X?:\1)3B%8_at_51E%:FVVO!3'S8#+A0TIF*8
MF?"T1/K9:&O1]SYO[/6-_6T=V*XSD:(J(QJB]AQ[,X6A^#X>X=\YK]^RN>Y(
MKC"UX6_at_E,9IV^('.;A-N7$=_.<&DJ1F-_Y"_NCIEKJ?J8^U_at_V9%\ZCOR'Z*3
MY?\(W;&9V;0(>IJC!R*;(S8AF:3(N*.1R/5M,BP#>SQ=]I-Q)&OR9K?>XX`C
M6-\->-4.R:2IM>.&MA/L;<?7%;^MP<&T7[89=36'VPM=RF.6/.=%LA0'L\G*
M[W)[&0=1*GP.T(6_VP=#A!;:A/8TA,\$3X_Z<.,ZVR.AGU+Q"Q]@/:=_`M=.
MYB\$MPF]#(P6CFFTU[VJ'[^_\EI$W2M\GHXO3UJ1,AZ/?@%02P,$%`````@`
M!Y]!+BMOV[0*`0``K0$```L```!P861D:6YG+FAP<(6046N#,!2%WP7_PZ5[
MT;)-U[W93K`6K"\J:]Y#:A(;T$0T;FQC_WU)74OWM'L)A)PO-^<D"*`GE`K9
MN$X0V`5>ZD/&I"2#@FI0FL`J#)]=Q_:=X)(R#MNR/"!<);M=7F1X7U4XJ[#%
MPE7X9###",G^P^P\6;<39;"I1TW-K1B,`ZX&&,4GP_H/T8I.Z/%*I/OD%6]S
M=,,LW_at_75I\=3WR]N3X]*C3JHE>2B^15M:];U+=%FM/[HF20=`Q2[SJB'J=:7
M;X$OBX*I.<P!)2A/<5H69E>@6;+EF0!1--N^AS?23_at_Q>KB:75E#<0SX\P-GE
M!L51=,;\M7WB>SV[,L:9I(+;F)<$S40&ZCH_4$L#!!0````(`&:5+BZ8/^O]
M/@$```P"```-````<')E8VES:6]N+FAP<(50P6K"0!2\!_(/@[TH%6/L3:W0
MAF*]F%!S#ZMYB0OQ;<ANBE+Z[]U-:BWTT(6%QYMAYLT$`>J&#E)+Q9-C7?M>
M$+B/833"FIA%HY`TR_at_C,IM,'W_.].UEP3_at_6>XWB79LG;2[39;>)M]IHDV3K)
M'&T:AJ$E6I9D^I_H-/E0M3EA<!+G3!7NE,'OM61S4*Q-5JER]@?=*Z5-8`F%
M++_!+D1RC0950#"L"I74P%QJFO]$38\$;D]["UC:7AH-:=!JTC`*#=F"-+'I
MN.^B:DF/06=G+;FTLA=H6;(=<M0B[Y9.9-(;&#K5E3"$I7-E<2*D*]_3IFD/
MYE8^/GP/]O5E[=*G=!-E4;RUTS8=MNPL*$>EN!SW5^`1(>[A"EEBV/>V3%>8
MSSMXA-NX\+W/A>NDZYHXEP5LF&M_92N:W/>^`%!+`P04````"`!#:40N:[C%
MK;@$``!W#P``#0```'!R;VUO=&EO;BYH<'#=5VUOVS80_AX@_^':`*N<I):;
M;`-F9P8ZKT@#=+:1:-B'91`8B;(UR*0F4_at_FRH/]]=WR195>N$VR?)B..)=X]
MY-T]?(X*0YA7<B5U+L7A01C2'P23'EQR(5_at_E:50S.!L,S@\/Z'.49R+E&?PT
MF]U$\?QZ]LLLNII-XX_S>7PYC\EP\&[P/1JB52[X?D/"%$E1IQQ>WTFI=)A(
MD>6+_K(L7].P8"NN2I9P2+EF>0%/]!37.:FKB_at_M=/()><BB8TJ`?).C'DBM@
M%8=:\10R6<%#LF15K$&*XM&&R46]@M*$SM.87.(\5?`$N=#X"WZ$=Z=0"Y4O
M!(XW#\].#P]@UU5(L;!FYRW?]=-O=_I^'KF0HBJ_9P5HOBH+ICEH"2M6`F?)
M$A`#;RG41&+@JI0BS<7"Q&N#:MPN<,%C4+JJ$XU^L98FQ!'@%(+?\PIL=5*:
M=NW5X7)A0Q]C9NB62H]/P*+1LK_NO97!-HP?>A&>2V8;AQZ]?#T=0,V"MA#I
MXY"<LZSB=F!$2*JB!R*R0?`-SHF#/?C=QO[':)=5;<VV<N7M[;?23.<)>AM0
M2#$>KG1`GEU5;;FX"1J7=M[1=X?SX8$/'<>GDJBX9!H>D'Q,"*EI;Z$'T96T
M`S+<2CO28R#N>,+(1<D5\7=5Y_at_6O%`2\O^C#(DG_at_K/_#=_WS'CS(NDAAR>XY
M;<^[@J^4`7C(]=*07]5WBO]5X\;'-1#_4YX4K+++D)F/T^X(SP#,*"7!EIW6
M9VH<'@^AK.\*S-*.RE[VY_V;_G%H-:>[?`2%Y7.,^DJ9G>$V!SL+[7#!AP.!
M\1Y]45ICU1AM<+@W\HO&_%6\Y%A`DT$45(2HLPR8VEDTZV=3W&TS'+IY1[N3
M\W_8`4T./W'M>@9Q;<G*DB/EA$DJJQ;U"DFI2*1ER9&0V'A._at_MYIXXYF`A3G
MQIZ20'2EWRCF==&DW"6IT3&RI!X(4:-HKG&IV";#%,8+T;K)V-9[$[V/KB;Q
M9#;%7],(*&.G8!J2RO_FN(1_at_3WD#B()![X2^P'Q&ZSG"L&D+K9Z1CH=#:EPX
MTK+UEDU`VRXF)QM-N6&6K<5G4ZNM\X`OTG,RAD%F3J[]:B)H6B/>,BR$.3+0
M0V5%CXX2)'FH/']RQ,("KUGPUFG$FB[^Y&///!]NXF_at_67TVC>'8=_SJ]N;J<
M?OB9[@,EZRKA)LP>=%RWVT08=UD]Z[KU^V$[%Q>M13P/_G9=3Q1/H_^^$,/A
M#EYNSO+4`?5OKQU05MR'74,[KRTH3Y,-6CK*[+MNB;'_S?7"7(7'P$6*Y$3>
M\B%^H^ZL\D1B6S_at_.&U7;QU`2:+/9]U+9ZNFS[1L%?OX,2UEI*]@OP=]P<^\O
M\,KI/`16(:<&Y/H*$2;Q;Y./[Z_CJ&<21)J09QEWKQGFD$."75;\/I>U<BKA
M7R_P:&2='%E(*2K."G3%$\J"TT+X`L\]KV#TMF=,\:NUP5V1\3RCU,8V=3.,
MU^<0SVUWYVGJ=V)+6O<SQ_:!H/'M/"VUVL&G-[>#-W#B_O=Z>V?PVKZ6=!++
M(Z1HGIG;S1QTZ!2^&19C?]#^\E7$(?JB>4G>CYL5DNDU<`L[E9A_at_O@5_5)NW
MWSW\\QO,!D@+\F^XBYI5>+[X!U!+`P04````"`!]E2XNT9/$7RL!``#V`0``
M"0```'=I9'1H+FAP<'U076O"0!!\/\A_&.R+TI*/]BU:I;6_at_OF@@!WT,9[*)
M!_$N))<6*?WOO6NJ6`I=.#AV9V9G)PCP+@MS\`]-X[$@<`_CY00K4DJT&DFK
MC<!]&#YXS&,WLE0%E7C>[5*>O6Y>^#I;)TFV2C('":,HLB"+D(K^!SDME==]
M01_at_U+>6RDUHY%Z/KR4%T62>KOX.]UIT)<JU*6?T,OZV_NF._at_2P@%J0Q5U,*<
M&HHOQZ7B2!`=+DNQ[PT&8:DJ2SS!K<1>FH%DZ-C4PA!F3DDY/I][K#-MGYLA
M/GQX#+:&DU/^Q#?+;+G;VM^68]PKIT@%:JVJ.[R)NB<\PKI9^8F?^O@%6`Q:
MKBXF9WP>QP/O%N-S+%?=!2+$"">3J<<^IRX-&Q>I0I9NS3FWJA=MX;$O4$L#
M!!0````(`"UK1"[3-CS=<@(``!\'```.````86Y?97AA;7!L92YC<'"55&%O
MTS`0_4RE_H=3D%C*I&WB8UJ*H.W$!T8GE_at_ZA%44F<1IKB1W9[KJ!^.^<XZ1)
MVK1LB936[^X]/]MW[O=>,QZFZXC"B`FE)279N-\`]5-.&8]%"V0B(YSE+2Q4
M.HIHC)AYM[B3D<=`Q&=)GCLMF/$:;@9R24.FF.![E`V+=+*'YB2*&%]U*"5$
M!8JM]H5R*3*AZRF:,<9U*+C202I6[SKBOP3NTCFFQ*R>L]\[/P<_P7"8$J58
MZ,!&R'LBQ9I'$`L)MY/34T_at_9OP<JI9#*,(QLC%L&G^;S&S^XNKF=(`2(,$Y+
M<#J[_+CXX@>7\V_!XNMT-EU,9M/`_W$]`WS\M_`>+I!$4T5?P#4,'K'8.-<T
MRU.BRZ/F)*/@C^%!L`ARB;L1F--W_Z<XZ/?^]'O&DU$QB_*+?T,+%EL*6"&>
M9]!"\PV8+RZ@*+'(]0=ELOT6R:%8:QB-P+DBCR!B<,S`-;PSX]0=#`QP_at_J_!
M;:D5ZQA[W_at_-)U]3&E_QDV*G*^#-4BTI]@>IU5<%6>%O0+8FC"M]-I7M(QP?'
M1>&WV67DH,)GHL#4_@?KH6J%'9%:H:&AV&\::,"^PK,INZO%.SAAF8QSEBDL
M!A?!@1WMDYZH_at_CN[23B;07XN>46V-=U-Y,+F=3FY\]&K77996>9G4!XMPK6H
M`_8J0!M:>'N<HAG*C*A1`SMZZ-KIW),EKUS^M;<$MA-DA'&W;I>ZQT9XM:1C
MM^J"1B!,B.P,;$PDT#967$+FD&F$G:7IBLIB,<JK]JG!+/,.*JM$2&UD.J.'
M\%3P54TJ#*WY<RUM,P^:VF8<=]><\GC"KM]7DNJUY'`Q+(_L'U!+`0(4`!0`
M```(`(J4+B[>7=3V+0,``&0)```8``````````$`(`"V_at_0````!D971A:6PO
M=V-H87)?;6EN7VUA>"YH<'!02P$"%``*``````"19D0N````````````````
M!P```````````!``_T%C`P``9&5T86EL+U!+`0(4`!0````(`#2602[G6?`6
M!P(``/0#```,``````````$`(`"V_at_8@#``!H87-?<VEG;BYH<'!02P$"%``4
M````"`!Z:T0N$@'T'E<$``#F"P``$0`````````!`"``MH&Y!0``:6YT8V]N
M<W1?;&]G,BYH<'!02P$"%``4````"`!QF"XNT]&[':("``!5!P``"@``````
M```!`"``MH$_"@``;6%X7V]F+FAP<%!+`0(4`!0````(`%V5+BYZ_WK@$`(`
M`+\%```*``````````$`(`"V_at_0D-``!M:6Y?;V8N:'!P4$L!`A0`%`````@`
M!Y]!+BMOV[0*`0``K0$```L``````````0`@`+:!00\``'!A9&1I;F<N:'!P
M4$L!`A0`%`````@`9I4N+I@_Z_T^`0``#`(```T``````````0`@`+:!=!``
M`'!R96-I<VEO;BYH<'!02P$"%``4````"`!#:40N:[C%K;@$``!W#P``#0``
M```````!`"``MH'=$0``<')O;6]T:6]N+FAP<%!+`0(4`!0````(`'V5+B[1
MD\1?*P$``/8!```)``````````$`(`"V@<`6``!W:61T:"YH<'!02P$"%``4
M````"``M:T0NTS8\W7("```?!P``#@`````````!`"``MH$2&```86Y?97AA
>;7!L92YC<'!02P4&``````L`"P"&`@``L!H`````
`
end


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk