Author: Gerd Isenberg
Date: 02:08:59 06/14/04
Go up one level in this thread
On June 13, 2004 at 19:26:43, Gerd Isenberg wrote:
>On June 13, 2004 at 10:26:55, Gerd Isenberg wrote:
>
>>On June 13, 2004 at 09:52:57, Gerd Isenberg wrote:
>>
>>>
>>>
>>> 1 0x00000001 4-bit deBruijn found
>>> 2 0x00000002 8-bit deBruijn found
>>> 16 0x00000010 16-bit deBruijn found
>>> 2048 0x00000800 32-bit deBruijn found
>>>67108864 0x04000000 64-bit deBruijn found
>>>
>>
>>Funny, seems in general for N-bit de Bruijn sequences, where N is power of two,
>>the number of N-bit de Bruijn sequences is a power of two too:
>>
>> # N-bit deBruijn := 2**(N/2 - log2(N))
>>
>>Excuse my digressions ;-)
>
>Sorry, after some more brain storming again on that tocip, i came to the
>conclusion that this formula is only the half truth. There is one valid way to
>shift/rotate the odd set left, to get exactly an even set with log2(N)-1 leading
>zeros (minimum needed for wrap), instead the odd set with log2(N) leading binary
>zeros.
>
>0011(0) - 0,1,3,2
>0110(0) - 1,3,2,0
>-----^ the wrapped zero
>
>therefore my next guess:
>
> # N-bit deBruijn := 2**(N/2 - log2(N) + 1)
>
>0x03f08c5392f756cd is reserved by Gian Carlo's BitScan!
>If anybody else uses this constant with the associated table and an unique byte,
>short or int sequence, it may be considerd as Deep Sjeng clone!
>There are 2**27 - 1 others ;-)
>
>Gerd
I did some Google-Group seach and found:
Betrifft:Re: Cycle problem
View: Complete Thread
Original Format
Newsgroups:sci.math
Datum:1997/10/15
...
These are called De Bruijn sequences. For m bits there are 2^{2^{m-1}-m}
of them. See chapter 8 in Van Lint & Wilson, A Course in Combinatorics,
Cambridge UP, 1992.
.....
This formula 2^{2^{m-1}-m} with m = log2(N) is identical with "my" empirical
determined initial one:
# N-bit deBruijn := 2**(N/2 - log2(N))
I wonder why the shifted even ones with m-1 leading zeros are not considered as
"real" De Bruijn sequences.
Gerd
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.