Speeding up array processing

[AndyG]

I start programming (not as a profession) 35 years ago, using an PC1401 Sharp calculator with 3534 BYTES (yes Bytes) RAM for BASIC-Programs. Fortunately, this machine is programmable with machinecode (not Assembler, "assembling" the code is to be made by Brain1.0 )

BASIC for User-interaction, ASM for speed...

Today i like to speedup some calculations with ASM, and i still have the habit to optimize and "count clockticks".

1 hour ago, czardas said:

My first version was capable of up to 27 bits, but I estimate it would have taken about 6 hours

I have measured a full "rotation" of a 32-Bit number in ASM takes about 100 clockticks, including "deleting not uniques", and the precalculation of bitcount and so on...

32 Bit is equal to 4,3e9 (numbers), lets say a Computer has 2Ghz, which is 2e9 clockticks per second. 

So the calculation of all 32 Bit numbers should take: 100 clockticks * 4.3e9 / 2e9 clockticks / second = 215 seconds 

The "array" is a bytearray, the "numbers" are represented by their index. AutoIt can only allocate 1GIG of RAM, which reduces the maximum number to 30 bit which should take 60seconds for the calculation. The using of SIMD and SSE could speed up the calculation by 2 , we are at 30 Seconds for 30Bit. (I dont think that multithreading is worth the time)

On CPU, so far, so good.

My experience with OpenCl shows, that with a good to parallelize algorithm, a GPU could make the calculation in some milliseconds. Normally it takes more time to transfer the data ( all "numbers") from RAM to the GPU and get back the result, than do the whole calculation.

I will try both ways.....

Edited August 13, 2016 by AndyG

[AndyG]

4 minutes ago, Melba23 said:

(although it is still lamentably slow when compared to ones you and czardas have been posting).

I would not say it is lamentably slow. Comparing to the OP´s script is is very fast. I think, he (the OP) would be very proud if he could write such a beautiful piece of code! 

[Melba23]

AndyG,

Thanks for the compliment - looking at your code, I return it with interest.

M23

[czardas]

40 minutes ago, AndyG said:

I will try both ways

I hope to see the results. I'm learning a lot from this.

[AndyG]

With the help of AssembleIt(), the runtime of ASM-code to calculate all 14Bit  numbers  takes something around 1 (one) millisecond. Unoptimized code, "oldschool" ASM...no SSE/SIMD. 

A 27Bit calculation takes 30 Seconds,

20Bit calculation takes 80 milliseconds with 52487 "unique" numbers. Time to fill an AutoIt-Array from dllstruct(bytearray) takes some seconds...._arrayunique() is overloaded too. I must write the unique numbers/bitstrings  into memory as an ASCII-string, so that this string can be read via dllstructgetdata(). That should be fast enough, 1-2ms i think...

The script uses ASM code mixed with AutoIt-variables, i prefer this method to develop quick´n´dirty ,  A "standalone"-code could be created by AssembleIt() if necessary.

//EDIT if you take a look at my code, you can see that i use my debugger 

AssembleIt2_64.zip

expandcollapse popup

#include <Array.au3>           ;aligncomment=30
#include <assembleit2_64.au3>
#AutoIt3Wrapper_UseX64=n



$bits = 20
$ar = 2 ^ ($bits) - 1          ;all numbers


;the "array", every byte is 0 (valid number) or set to 1 by the code to "delete" it
$bytestruct = DllStructCreate("byte[" & $ar + 1 & "]")
$ptr = DllStructGetPtr($bytestruct) ;pointer to the data


$msb = 2 ^ ($bits - 1)         ;msb
$mask = 2 ^ $bits - 1          ;mask


#cs PhotoMarker
    use32


    mov edi, $ptr              ;pointer to the bytestruct
    mov ebx,-1                 ;start: for $i=1 to $ar step 2

    label1:
    add ebx,2                  ;...step 2
    cmp ebx,$ar
    jae Label_end              ;if all numbers calculated, exit
    cmp dword[edi+ebx],1       ;If $a[$i] = 0 Then
    je label1                  ;if not, next $i

    ;bitcount calculation
    ;we shift left, until the carryflag is set to 1
    mov edx,ebx                ;save $i
    xor eax,eax                ;=0, number of shifts
    clc                        ;clear carry-flag CF
    bitcount:                  ;loop until CF=1
    inc eax                    ;shiftcounter+=1
    shl edx,1                  ;shift left...
    ;~      _asmdbg_()
    jnc bitcount               ;jump if not carry
    dec eax                    ;shiftcount-=1,
    sub eax,32                 ;we need bitcount
    neg eax                    ;=bitcount

    ;$t = BitShift($i, $bitcount - $bits) ;shift to the left border
    mov edx,ebx
    mov ecx,$bits
    sub ecx,eax
    shl edx,cl

    ;~      _asmdbg_()
    mov byte[edi+edx],1        ;delete rotated number, $a[$t] = 1

    ;now, lets rotate
    xor esi,esi                ;$x=0
    Label2:                    ;for $x=1 to $bitcount
    ;~     _asmdbg_()
    inc esi                    ;$x+=1
    cmp esi,eax                ;is bitcount reached?
    ja label1                  ;if above, next number

    cmp edx,$msb               ;If $t > $msb Then ;only if msb =1
    jl Label3                  ;jump if less
    mov byte[edi+edx],1        ;delete rotated number, $a[$t] = 1

    ;~      _asmdbg_()
    shl edx,1                  ;$t=$t*2
    sub edx,$mask              ;$t=$t-$mask

    cmp edx,ebx                ;If $t > $i Then $a[$t] = 1
    jle Label2                 ;jump if less or equal
    mov byte[edi+edx],1        ;delete rotated number, $a[$t] = 1
    ;~      _asmdbg_()
    jmp Label2                 ;next $x
    Label3:
    shl edx,1                  ;$t=$t*2
    ;~     _asmdbg_()
    jmp Label2                 ;next $x


    Label_end:                 ;exit

    mov eax,ebx


    ret                        ;eax is returned
#ce


$timer = TimerInit()

$ret = _AssembleIt2("uint", "PhotoMarker")

ConsoleWrite("! time=" & TimerDiff($timer) & "ms" & @CRLF)

ConsoleWrite("wait for filling the array..." & @CRLF)

Dim $a[$ar + 1]

For $i = 2 To $ar Step 2       ;all odd numbers (dllstruct is 1-based but memory is 0-based)
    If DllStructGetData($bytestruct, 1, $i) = 0 Then $a[$i - 1] = $i - 1 ;only if not "deleted"=1
Next

;~ _ArrayDisplay($a)

ConsoleWrite("wait for ArrayUnique()..." & @CRLF)

$r = _ArrayUnique($a)

ConsoleWrite($bits & "bits :  " & UBound($r) & " uniques were found" & @CRLF)

Dim $c[UBound($r) + 1][2]

ConsoleWrite("wait for ArrayDisplay()..." & @CRLF)
For $i = 1 To UBound($r) - 1
    $c[$i][0] = $r[$i]
    $c[$i][1] = Dec2Bin($r[$i])
Next


$z = _ArrayDisplay($c)

Func Dec2Bin($D)
    Return (BitShift($D, 1) ? Dec2Bin(BitShift($D, 1)) : "") & BitAND($D, 1) ;
EndFunc                        ;==>Dec2Bin

 

Edited August 14, 2016 by AndyG

[czardas]

@AndyG That Assembly code runs blindingly fast.

I had another go to see what improvements I could make in my own code (pure AutoIt). There were a few improvements to be made. After trying everything I could think of, I still wasn't getting the same speed as your version in post #55. I couldn't figure out why there was such a difference until all of a sudden it dawned on me. You write the time taken before calling _ArrayUnique(). That doesn't make for a fair comparison: the job was unfinished.  

Although you don't really need to call _ArrayUnique(). 

~ 110 milliseconds without any formatting [2 GB RAM].

expandcollapse popup

#include <Array.au3>

Local $iBits = 14

Local $aArray, $iTimer
$iTimer = TimerInit()
$aArray = BitLoopPermute($iBits)

ConsoleWrite(TimerDiff($iTimer) / 1000 & " seconds" & @LF)
ConsoleWrite(UBound($aArray) & " variants" & @LF)

_ArrayDisplay($aArray)

Func BitLoopPermute($iBinLen) ; limit = 24 bits
    $iBinLen = Int($iBinLen)
    If $iBinLen < 1 Then Return SetError(1) ; lowest loop size = 1
    If $iBinLen > 24 Then Return SetError(2) ; to remain within array size limits

    Local $iBound = 2^$iBinLen, $aArray[$iBound]
    For $i = 1 To 2^($iBinLen -1) Step 2
        $aArray[$i] = $i
    Next

    Local $iInversion, $iCount = 1
    For $i = 1 To 2^($iBinLen -1) Step 2
        If $aArray[$i] Then
            $iInversion = $i
            Do
                $iInversion = FirstInversion($iInversion, $iBinLen)
                If $iInversion > $i Then $aArray[$iInversion] = ''
            Until $iInversion = $i ; recursion either due to symmetry or a complete cycle
            $aArray[$iCount] = $i
            $iCount += 1
        EndIf
    Next

    $aArray[0] = 0
    $aArray[$iCount] = $iBound -1
    ReDim $aArray[$iCount +1]

    Return $aArray
EndFunc ;==> BitLoopPermute

Func FirstInversion($iInteger, $iLoopSize) ; skips all even numbers
    Local $iPosition = Floor(Log($iInteger) / Log(2)) ; the position of the first set bit [AndyG]
    $iInteger -= 2^($iPosition) ; remove MSB
    Return BitShift($iInteger, $iPosition -$iLoopSize) +1 ; shift the bits right [+1 MSB becomes the LSB]
EndFunc ;==> FirstInversion

Func DecToBase($iInt, $iBase) ; for bases 2 to 9
    Local $iRem, $sRet = ''
    While $iInt > $iBase -1
        $iRem = Mod($iInt, $iBase)
        $sRet = $iRem & $sRet
        $iInt = Int(($iInt - $iRem) /$iBase)
    WEnd
    Return $iInt & $sRet
EndFunc ;==> DecToBase

~ 180 milliseconds with formatted binary strings [2 GB RAM].

Func BitLoopPermute($iBinLen) ; limit = 24 bits
    $iBinLen = Int($iBinLen)
    If $iBinLen < 1 Then Return SetError(1) ; lowest loop size = 1
    If $iBinLen > 24 Then Return SetError(2) ; to remain within array size limits

    Local $iBound = 2^$iBinLen, $aArray[$iBound]
    For $i = 1 To 2^($iBinLen -1) Step 2
        $aArray[$i] = $i
    Next

    Local $iInversion, $iCount = 1, $sZeros = StringRight('000000000000000000000000', $iBinLen)
    For $i = 1 To 2^($iBinLen -1) Step 2
        If $aArray[$i] Then
            $iInversion = $i
            Do
                $iInversion = FirstInversion($iInversion, $iBinLen)
                If $iInversion > $i Then $aArray[$iInversion] = ''
            Until $iInversion = $i ; recursion either due to symmetry or a complete cycle
            $aArray[$iCount] = StringRight($sZeros & DecToBase($i, 2), $iBinLen)
            $iCount += 1
        EndIf
    Next

    $aArray[0] = $sZeros
    $aArray[$iCount] = DecToBase($iBound -1, 2)
    ReDim $aArray[$iCount +1]

    Return $aArray
EndFunc ;==> BitLoopPermute

 

Edited August 14, 2016 by czardas
Optimized FirstInversion() code

[AndyG]

1 hour ago, czardas said:

You write the time taken before calling _ArrayUnique().

this is, because there is absolutely no need to use ArrayUnique. What is the intention to use ArrayUnique? There is NO other justification to use it than "lazyness".

Because every "valid" unique number is already known long before the ArrayUnique is called!

instead of 

For $i = 1 To $ar Step 2            ;all odd numbers
    If $a[$i] = 0 Then              ;only if not deleted
        $bitcount = Floor(Log($i) / Log(2)) + 1 ;number of bits of the actual number
        blaaaahhhh
    endif
next

you could write:

dim $valids[$ar]
$validcounter=0

For $i = 1 To $ar Step 2            ;all odd numbers
    If $a[$i] = 0 Then              ;only if not deleted
        ;we definitely caught a "valid" number
        $validcounter=$validcounter+1
        $valids[$validcounter]=$i
        
        ;all the rest is only to delete numbers GREATER than the valid one we had caught
        $bitcount = Floor(Log($i) / Log(2)) + 1 ;number of bits of the actual number
        blaaaahhhh
    endif
next

 

//EDIT if you are a "hardcore" Programmer, you could use the $a-array to store all the valids...uniques...

For $i = 1 To $ar Step 2            ;all odd numbers
    If $a[$i] = 0 Then              ;only if not deleted
        $a[$validcounter]=$i
        $validcounter=$validcounter+1
        
        $bitcount = Floor(Log($i) / Log(2)) + 1 ;number of bits of the actual number
        blahhh
    endif
next    

redim $a[$validcounter]  ;only valids

 

Edited August 14, 2016 by AndyG

[czardas]

I'm not going to test it: I'll take your word for it. I don't need it to run faster because 12 bits in 30 ms is all I need. 

I think we've just about exhausted what can be done here, unless someone else has something interesting to add. You never know!

Edited August 14, 2016 by czardas

[AndyG]

another doublepost

No "Arrayunique", only stringfunctions needed

expandcollapse popup

#include <Array.au3>           ;aligncomment=30
#include <assembleit2_64.au3>
#AutoIt3Wrapper_UseX64=n



$bits = 15
$ar = 2 ^ ($bits) - 1          ;all numbers


;the "array", every byte is 0 (valid number) or set to 1 by the code to "delete" it
$bytestruct = DllStructCreate("byte[" & $ar + 1 & "]")
$asciistruct = DllStructCreate("char[" & $bits * $ar & "]")

$ptr_bytestruct = DllStructGetPtr($bytestruct) ;pointer to the data
$ptr_asciistruct = DllStructGetPtr($asciistruct) ;pointer to the string

$msb = 2 ^ ($bits - 1)         ;msb
$mask = 2 ^ $bits - 1          ;mask


#cs PhotoMarker
    use32

    mov edi,$ptr_asciistruct   ;our "string"pointer

    mov esi, $ptr_bytestruct   ;pointer to the bytestruct
    mov ebx,-1                 ;start: for $i=1 to $ar step 2

    label1:
    add ebx,2                  ;...step 2
    cmp ebx,$ar
    jae Label_end              ;if all numbers calculated, exit
    cmp byte[esi+ebx],1        ;If $a[$i] = 0 Then
    je label1                  ;if not, next $i

    ;we caught an unique number, write it into the string
    ;we use a char-array to store the ascii-string
    ;ebx is now the "integer" to convert, edi the adress of the next "letter"

    ;Convert 32Bit-integer into ascii-"number" at EDI
    ;************************************************************
    ;wird dieser Bereich auskommentiert, wird ein String aus nullen und einsen zurückgegeben 0=keine Prim 1=Prim
    ;dann können mit den AutoIt-Stringbefehlen die Primzahlen und deren Anzahl ausgelesen werden
    push   ebx                 ;alle benötigten Register sichern
    push   edx
    mov eax, ebx               ;Zahl laden
    mov ebx, 10                ; Divisor
    xor ecx, ecx               ;ECX=0 (Anzahl der Ziffern)
    Schleife_1:
    xor edx, edx
    div ebx                    ; EDX:EAX / EBX = EAX Rest EDX
    push dx                    ; LIFO
    add cl,1                   ; ADD soll schneller sein als INC
    or  eax, eax               ; AX = 0?
    jnz Schleife_1             ; nein: nochmal
    Schleife_2:
    pop ax                     ; gepushte Ziffern zurückholen
    or al, 00110000b           ; Umwandlung in ASCII
    stosb                      ; Nur AL nach [EDI] (EDI ist ein Zeiger auf den String)
    loop Schleife_2            ; bis keine Ziffern mehr da sind
    mov byte [edi],0Dh         ;CR  CarriageReturn, man könnte auch ein Komma (ascii=2C) einsetzen, dazu noch ein nullbyte als EndOfString
    add edi,1                  ;ein Byte weiter
    pop   edx
    pop   ebx                  ;Register wiederherstellen
    ;************************************************************Ende Ziffer aus Register




    ;bitcount calculation
    ;we shift left, until the carryflag is set to 1
    mov edx,ebx                ;save $i
    xor eax,eax                ;=0, number of shifts
    clc                        ;clear carry-flag CF
    bitcount:                  ;loop until CF=1
    inc eax                    ;shiftcounter+=1
    shl edx,1                  ;shift left...
    ;~      _asmdbg_()
    jnc bitcount               ;jump if not carry
    dec eax                    ;shiftcount-=1,
    sub eax,32                 ;we need bitcount
    neg eax                    ;=bitcount

    ;$t = BitShift($i, $bitcount - $bits) ;shift to the left border
    mov edx,ebx
    mov ecx,$bits
    sub ecx,eax
    shl edx,cl

    ;~      _asmdbg_()
    mov byte[esi+edx],1        ;delete rotated number, $a[$t] = 1

    ;now, lets rotate
    xor ecx,ecx                ;$x=0
    Label2:                    ;for $x=1 to $bitcount
    ;~     _asmdbg_()
    inc ecx                    ;$x+=1
    cmp ecx,eax                ;is bitcount reached?
    ja label1                  ;if above, next number

    cmp edx,$msb               ;If $t > $msb Then ;only if msb =1
    jl Label3                  ;jump if less
    mov byte[esi+edx],1        ;delete rotated number, $a[$t] = 1

    ;~      _asmdbg_()
    shl edx,1                  ;$t=$t*2
    sub edx,$mask              ;$t=$t-$mask

    cmp edx,ebx                ;If $t > $i Then $a[$t] = 1
    jle Label2                 ;jump if less or equal
    mov byte[esi+edx],1        ;delete rotated number, $a[$t] = 1
    ;~      _asmdbg_()
    jmp Label2                 ;next $x
    Label3:
    shl edx,1                  ;$t=$t*2
    ;~     _asmdbg_()
    jmp Label2                 ;next $x


    Label_end:                 ;calculation is done, now we have to build the ascii-list


    ret                        ;eax is returned
#ce


$timer = TimerInit()

$ret = _AssembleIt2("uint", "PhotoMarker") ;calculate the valid numbers
$string = DllStructGetData($asciistruct, 1) ; we get the string

ConsoleWrite("! time=" & TimerDiff($timer) & "ms" & @CRLF)

;no good idea to "show" this long string via msgbox
;MsgBox(262144, 'Debug line ~' & @ScriptLineNumber, 'Selection:' & @CRLF & '$string' & @CRLF & @CRLF & 'Return:' & @CRLF & $string) ;### Debug MSGBOX

;we better write it into a file
$filename = "valid_numbers_up_to_" & $ar & ".dat"
FileDelete($filename)
FileWrite($filename, $string)
ShellExecute($filename)



ConsoleWrite("wait for filling the array..." & @CRLF)

StringReplace($string, @CR, @CR) ;count uniques
$uniques = @extended
ConsoleWrite($bits & "bits :  " & $uniques & " uniques were found" & @CRLF)

$r = StringSplit($string, @CR) ;into an array^^

Dim $c[UBound($r) + 1][2]

ConsoleWrite("wait for ArrayDisplay()..." & @CRLF)
For $i = 1 To UBound($r) - 1
    $c[$i][0] = $r[$i]
    $c[$i][1] = Dec2Bin($r[$i])
Next


$z = _ArrayDisplay($c)

Func Dec2Bin($D)
    Return (BitShift($D, 1) ? Dec2Bin(BitShift($D, 1)) : "") & BitAND($D, 1) ;
EndFunc                        ;==>Dec2Bin

next one is the "standalone"-version....

[czardas]

@AndyG A small detail: your last version is missing the final value for 15 bits = 32767. You are also not counting zero as a variant, although I don't remember that being part of the request.

[AndyG]

last "evolution"...

20 bits takes only some (milli)seconds to calculate. The most time goes by "showing" the calculated numbers (which is not needed i think!)

expandcollapse popup

#include <Array.au3>                                   ;aligncomment=30
;~ #include <assembleit2_64.au3>
#AutoIt3Wrapper_UseX64=n



$bits = 20
ConsoleWrite("#Bits = " & $bits & @CRLF)
$ar = 2 ^ ($bits) - 1                                  ;all numbers

;the "array", every byte is 0 (valid number) or set to 1 by the code to "delete" it
$bytestruct = DllStructCreate("byte[" & $ar + 1 & "]")
$asciistruct = DllStructCreate("char[" & $bits * $ar & "]") ;should be enough...

$ptr_bytestruct = DllStructGetPtr($bytestruct)         ;pointer to the data
$ptr_asciistruct = DllStructGetPtr($asciistruct)       ;pointer to the string

$msb = 2 ^ ($bits - 1)                                 ;msb
$mask = 2 ^ $bits - 1                                  ;mask


$timer = TimerInit()

;~ $asm_code = _AssembleIt2("retBinary", "PhotoMarker")
Local $asm_code = "0x8B7C24048B742408BBFFFFFFFF83C3023B5C240C7770803C1E0174F1535289D8BB0A00000031C931D2F7F3665280C10109C075F366580C30AAE2F9C6070D83C7015A5B89DA31C0F840D1E273FB4883E820F7D889DA8B4C241829C1D3E2C604160131C94139C177A53B5424147C14C6041601D1E22B54241039DA7EE7C6041601EBE1D1E2EBDD89D8C3"
Local $asm_struct = DllStructCreate("byte[" & StringLen($asm_code) / 2 - 1 & "]") ;speicher für asm-code bereitstellen...
DllStructSetData($asm_struct, 1, $asm_code)            ;...und mit code beschreiben


DllCallAddress("none:cdecl", DllStructGetPtr($asm_struct), "ptr", $ptr_asciistruct, "ptr", $ptr_bytestruct, "uint", $ar, "uint", $mask,"uint",$msb,"uint",$bits);$ret = _AssembleIt2("uint", "PhotoMarker", "ptr", $ptr_asciistruct, "ptr", $ptr_bytestruct, "uint", $ar, "uint", $mask) ;calculate the valid numbers
$string = DllStructGetData($asciistruct, 1)            ; we get the string

ConsoleWrite("! time=" & Int(TimerDiff($timer)) & "ms  since start calculating the numbers and write them into a string" & @CRLF)

;no good idea to "show" this long string via msgbox
;MsgBox(262144, 'Debug line ~' & @ScriptLineNumber, 'Selection:' & @CRLF & '$string' & @CRLF & @CRLF & 'Return:' & @CRLF & $string) ;### Debug MSGBOX

;we better write it into a file
$filename = "valid_numbers_up_to_" & $ar & ".dat"
FileDelete($filename)
FileWrite($filename, $string)
ShellExecute($filename)

ConsoleWrite("! time=" & Int(TimerDiff($timer)) & "ms  since start including writing/showing the file" & @CRLF)


ConsoleWrite("wait for StringSplit()..." & @CRLF)

StringReplace($string, @CR, @CR) ;count uniques
$uniques = @extended
ConsoleWrite($bits & "bits :  " & $uniques & " uniques were found" & @CRLF)

$r = StringSplit($string, @CR) ;into an array^^

ConsoleWrite("! time=" & Int(TimerDiff($timer)) & "ms  since start including stringsplit the string, wait for filling the array" & @CRLF)

Dim $c[UBound($r)][2]
For $i = 1 To UBound($r) - 1
    $c[$i][0] = $r[$i]
    $c[$i][1] = Dec2Bin($r[$i])
Next

ConsoleWrite("! time=" & Int(TimerDiff($timer)) & "ms  since start, now wait for ArrayDisplay()..." & @CRLF)
$z = _ArrayDisplay($c)

Func Dec2Bin($D)
    Return (BitShift($D, 1) ? Dec2Bin(BitShift($D, 1)) : "") & BitAND($D, 1) ;
EndFunc                        ;==>Dec2Bin

 

[Melba23]

Hi,

I have been looking at how to generate the patterns directly rather then using brute-force - just for fun.  But although the required patterns seem to be fairly simple when examined:

8-bit pattern with 3 1s

          length of 0 runs before each 1
00000111  5 0 0

00001011  4 1 0
00001101  4 0 1

00011001  3 0 2
00010101  3 1 1
00010011  3 2 0

00100101  2 2 1

--------------------------------

8-bit pattern with 4 1s

          length of 0 runs before each 1
00001111  4 0 0 0

00010111  3 1 0 0
00011011  3 0 1 0
00011101  3 0 0 1


00100111  2 2 0 0
00110011  2 0 2 0

00101011  2 1 1 0
00101101  2 1 0 1
00110101  2 0 1 1


01010101  1 1 1 1

trying to get an algorithm to generate them is proving far more difficult - although I am sure one must exist.  The problem I am wresting with at the moment is how to realise that 2002 is equivalent to 2200 and not generate it automatically.

M23

[jchd]

I'm glad to see that my "back of enveloppe" note somehow contributed to make you guys think about the true nature of the problem.

I currently have very little free time to devote to digging further into this. Yet curiosity led me to ask OEIS about the sequence of number of results with increasing bitsize. Unsurprinsingly, this sequence is well-know: https://oeis.org/A000031

The references given there may shed some interesting light on how to tackle the problem in an opimal way. The numbering of this sequence (31) shows that it has been one of the first entered into OEIS when Sloane started his project. I really should have looked there first.

At the very least, this easily gives the exact number of entries that the resulting array will have. The fact that these numbers can also be defined by "number of binary irreducible polynomials whose degree divides n" leads to believe there could exist a fruitful theoretical approach to generating the results with a less computationally-intensive algorithm.

EDIT: the site may be off at times but the link given is correct " The OEIS may be off the air the weekends of August 13/14 and August 20/21 so that we can upgrade the server. There may be further interruptions later. "

Edited August 14, 2016 by jchd

[czardas]

This is far too important for the back of an envelope. Having said that, I worked 12 bits out manually about 10 years back. It took a while - ouch!  Mind you, each pattern needed analysis: to identify the variants which are relevant to my project, so it wasn't time spent in vain.

Edited August 14, 2016 by czardas

[jchd]

I was refering to my note in post

 

[czardas]

Yeah, I read it.

Edited August 14, 2016 by czardas

[Melba23]

Hi,

I went looking for an algorithm and I found one thanks to jchd's links to OEIS. It is blindingly fast - I get the 14-bit result in ~150ms on my machine. Anyway, here it is for completion:

expandcollapse popup

#include "Array.au3"

$nBegin = TimerInit()

; Set number of bits
$iMax = 14

; Create array to hold unique patterns
$iArraySizeFactor = 500
Global $aUnique[$iArraySizeFactor] =[0]

; Find factors for the bit value
$sFactors = "|1|"
For $i = Ceiling($iMax / 2) To 2 Step -1
    $nDiv = $iMax / $i
    If IsInt($nDiv) Then
        $sFactors &= $nDiv & "|"
    EndIf
Next
$sFactors &= $iMax & "|"
;ConsoleWrite($sFactors & @CRLF)

; Create initial pattern of all 1s
Local $aBits[$iMax + 1]
For $i = 1 To $iMax
    $aBits[$i] = 1
Next
_SavePattern($aBits)

; Start algorithm
While 1
    ; Find rightmost 1
    For $iIndex= $iMax To 1 Step -1
        If $aBits[$iIndex] = 1 Then ExitLoop
    Next

    ; Set found 1 to 0
    $aBits[$iIndex] = 0

    ; Fill rest of pattern with repeats of the pattern up to the found index
    $iFiller = 0
    For $i = $iIndex + 1 To $iMax
        $iFiller= Mod($iFiller, $iIndex) + 1
        $aBits[$i] = $aBits[$iFiller]
    Next

    ; If the found index is a factor of the bit value - valid pattern
    If StringInStr($sFactors, "|" & $iIndex & "|") Then
        _SavePattern($aBits)
    EndIf

    ; If leftmost 1 changed to 0 then pattern must be all 0s so end
    If $iIndex = 1 Then
        ExitLoop
    EndIf

WEnd

ReDim $aUnique[$aUnique[0] + 1]

ConsoleWrite(TimerDiff($nBegin) & @CRLF)

_ArrayDisplay($aUnique, "", "", 8)

Func _SavePattern($aArray)

    ; Convert pattern to string
    $sPattern = ""
    For $i = 1 to UBound($aArray) - 1
        $sPattern &= $aArray[$i]
    Next
    ; Resize array if required
    $aUnique[0] += 1
    If $aUnique[0] > UBound($aUnique) - 1 Then
        ReDim $aUnique[UBound($aUnique) + $iArraySizeFactor]
    EndIf
    ; Add pattern to array
    $aUnique[$aUnique[0]] = $sPattern

EndFunc

And please do not ask me to explain why it works - it took me long enough to work out how to get it to run!

M23

[jchd]

Good. I didn't look at it but maybe you can even squeeze a little bit out of it by allocating the exact final size of the resultset. Well, that's a bit cheating because you have to store known "magic" values of the series up to some reasonnable bitsize. But as those values are correct, published and not some copyrighted secret sauce recipe, why not benefit of the knowledge. All this of course provided it helps avoiding repetitive ReDims.