Comparisons in mathematical simulations

Just starting out? Need help? Post your questions and find answers here.
fvillanova
User
User
Posts: 70
Joined: Wed May 02, 2012 2:17 am
Location: Brazil

Comparisons in mathematical simulations

Post by fvillanova »

I'm developing a program that uses binary numbers that represent positive or negative results for 62 different types of infections in mathematical simulations.

1 to 62 types can be detected, see example with the processing of 23 possible types:

00000000010100000100101

In the representation above, types 1,3,6,12 and 14 were positive (1)

The first digit one (1) on the right refers to type 1
The second zero (0) digit on the right to type 2
.... up to the last zero (0) digit referring to type 23

then we can say the following:

This result with 23 different types of infections can be represented by a number:

Result(x)=%00000000010100000100101 = 10277 (decimal)

Everything is working perfectly in the system, I need to increase the processing speed of the following command that counts how many types were positive in the simulation, see how it is currently programmed:

n=CountString(Bin(Result(x)),"1") in this case n=5

Here we have another result with 23 processed types:

Result(y)=%10000000000100000000100 = 4196356 (decimal)

n2=CountString(Bin(Result(y)),"1") in this case n2=3

See that using this methodology I can see how many equal types occurred in the two samples:

match=CountString(Bin(Result(x) & Result(y)),"1") in this case match=2

Processings can have from 1 to 62 binary digits:

from %1 to %1111111111.....111111 ( 62 numbers 1 = 4611686018427387903 )

How can I increase the speed of the below routine:

Code: Select all

DisableDebugger
input1.q=%00000000010100000100101
input2.q=%10000000000100000000100
t1 = ElapsedMilliseconds()
For i = 1 To 100000000
  Result = CountString(Bin(input1 & input2),"1")
Next
t2 = ElapsedMilliseconds()
MessageRequester("End",Str(Int((t2-t1)/1000))+" seconds", #PB_MessageRequester_Ok) 
The processing I'm doing involves trillions of simulation comparisons, that's why I need to speed up this comparison between two simulations.
Any help will be welcome.
thanks
User avatar
jacdelad
Addict
Addict
Posts: 1431
Joined: Wed Feb 03, 2021 12:46 pm
Location: Planet Riesa
Contact:

Re: Comparisons in mathematical simulations

Post by jacdelad »

Hi fvillanova,
I hope I'm not wasting your time and that my method works. I created a lookup table for bytes (256) entries and simply use the predefined values:

Code: Select all

DisableDebugger
input1.q=%00000000010100000100101
input2.q=%10000000000100000000100
t1 = ElapsedMilliseconds()
Define intermediate.q,help.a
For i = 1 To 100000000
  ;create the desired pattern
  intermediate=input1 & input2
  ;reset result
  Result=0
  ;go through all bytes of the quad
  For help=0 To 7
    ;search the predefined result and add it to Result
    Result+PeekA(?LookupTable+PeekA(@intermediate+help))
  Next
  ;Result = CountString(Bin(input1 & input2),"1")
Next
t2 = ElapsedMilliseconds()
MessageRequester("End",StrF((t2-t1)/1000,3)+" seconds", #PB_MessageRequester_Ok) 

DataSection
  ;Precalculated Lookup-Table
  LookupTable:
  Data.q 216737935419048192,289078108257124865,289078108257124865,361418281095201538,289078108257124865,361418281095201538,361418281095201538,433758453933278211,289078108257124865,361418281095201538,361418281095201538,433758453933278211,361418281095201538,433758453933278211,433758453933278211,506098626771354884,289078108257124865,361418281095201538,361418281095201538,433758453933278211,361418281095201538,433758453933278211,433758453933278211,506098626771354884,361418281095201538,433758453933278211,433758453933278211,506098626771354884,433758453933278211,506098626771354884,506098626771354884,578438799609431557
EndDataSection
I am not sure if this code works (it worked on my tests), I guess you can check better. If it works, it reduced the time on my machine from 8.7 to 2.5 seconds. You can extend the lookup table to words, which makes the program slightly bigger, but should speed it up more too.
PureBasic 6.04/XProfan X4a/Embarcadero RAD Studio 11/Perl 5.2/Python 3.10
Windows 11/Ryzen 5800X/32GB RAM/Radeon 7770 OC/3TB SSD/11TB HDD
Synology DS1821+/36GB RAM/130TB
Synology DS920+/20GB RAM/54TB
Synology DS916+ii/8GB RAM/12TB
User avatar
jacdelad
Addict
Addict
Posts: 1431
Joined: Wed Feb 03, 2021 12:46 pm
Location: Planet Riesa
Contact:

Re: Comparisons in mathematical simulations

Post by jacdelad »

This code should work with words (1.2 seconds in my test):

Code: Select all

DisableDebugger
input1.q=%00000000010100000100101
input2.q=%10000000000100000000100
t1 = ElapsedMilliseconds()
Define intermediate.q,help.a
For i = 1 To 100000000
  ;create the desired pattern
  intermediate=input1 & input2
  ;reset result
  Result=0
  ;go through all bytes of the quad
  For help=0 To 3
    ;search the predefined result and add it to Result
    Result+PeekW(?LookupTable16+PeekW(@intermediate+help))
  Next
  ;Result = CountString(Bin(input1 & input2),"1")
Next
t2 = ElapsedMilliseconds()
MessageRequester("End",StrF((t2-t1)/1000,3)+" seconds", #PB_MessageRequester_Ok) 

DataSection
    LookupTable16:
    ;You lookup table here!
EndDataSection
But you need to generate your own lookup table...

Code: Select all

Define a.l,b.a,med.q,output$
For a=0 To 65535
  PokeW(@med+b,a)
  b+2
  If b>3
    b=0
    output$+",$"+Hex(med)
    If Len(output$)>150
      Debug "Data.q "+Right(output$,Len(output$)-1)
      output$=""
    EndIf
  EndIf
Next
If output$<>""
  Debug "Data.q "+Right(output$,Len(output$)-1)
EndIf
...and put the debug output into the lookup table (first code).
PureBasic 6.04/XProfan X4a/Embarcadero RAD Studio 11/Perl 5.2/Python 3.10
Windows 11/Ryzen 5800X/32GB RAM/Radeon 7770 OC/3TB SSD/11TB HDD
Synology DS1821+/36GB RAM/130TB
Synology DS920+/20GB RAM/54TB
Synology DS916+ii/8GB RAM/12TB
User avatar
jacdelad
Addict
Addict
Posts: 1431
Joined: Wed Feb 03, 2021 12:46 pm
Location: Planet Riesa
Contact:

Re: Comparisons in mathematical simulations

Post by jacdelad »

BTW, if this works you could also use the code and create the lookup table "on the fly". And don't try it with longs...or you have a super computer with lots, lots, LOTS of memory!
PureBasic 6.04/XProfan X4a/Embarcadero RAD Studio 11/Perl 5.2/Python 3.10
Windows 11/Ryzen 5800X/32GB RAM/Radeon 7770 OC/3TB SSD/11TB HDD
Synology DS1821+/36GB RAM/130TB
Synology DS920+/20GB RAM/54TB
Synology DS916+ii/8GB RAM/12TB
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: Comparisons in mathematical simulations

Post by idle »

This can be greatly speed up with SSE4.2 popcount
this is for x64 Asm and C backend
countstring 5205 ms: Popcnt SSE 162ms

Code: Select all

;DisableDebugger

Prototype protPopCount(x.i) 
Global PopCount.protPopCount  

CompilerIf #PB_Compiler_Backend = #PB_Backend_C 
  
  Procedure.i Popcount64(x.i)
    x - (x >> 1) &  $5555555555555555           
    x = (x & $3333333333333333) + ((x >> 2) & $3333333333333333)
    x = (x + (x >> 4)) & $0f0f0f0f0f0f0f0f
    x * $0101010101010101
    x >> 56
    ProcedureReturn x   
  EndProcedure 
  
  PopCount = @Popcount64()
  
CompilerElse   
    
  Procedure Popcount64(x.i)
    ;x - (x >> 1) &  $5555555555555555           
    !mov rax, [p.v_x]
    !mov rdx, rax
    !shr rdx, 1
    !mov r15, 0x5555555555555555
    !and rdx, r15
    !sub rax,rdx 
    ;x = (x & $3333333333333333) + ((x >> 2) & $3333333333333333)
    !mov rdx, rax       ;x 
    !mov r15, 0x3333333333333333 
    !and rax, r15  
    !shr rdx, 2 
    !and rdx, r15
    !add rax,rdx
    ;x = (x + (x >> 4)) & $0f0f0f0f0f0f0f0f
    !mov rdx, rax 
    !shr rdx, 4 
    !add rax,rdx 
    !mov r15, 0x0f0f0f0f0f0f0f0f
    !and rax, r15 
    ;x * 0101010101010101 >> 56
    !mov r15, 0x0101010101010101
    !imul rax, r15
    !shr rax, 56 
    ProcedureReturn  
  EndProcedure 
  
  Procedure PopCountSSE(inp.i)
    !POPCNT rax,[p.v_inp]  
    ProcedureReturn  
  EndProcedure  
  
  Global gIsSSE42
  
  !mov rax, 1
  !cpuid
  !shr rcx, 23
  !and rcx, 1
  !mov [v_gIsSSE42],rcx 
  
  If gIsSSE42 
    PopCount = @PopcountSSE() 
  Else 
    PopCount = @Popcount64()
 EndIf    
  
CompilerEndIf 

input1.q=%00000000010100000100101
input2.q=%10000000000100000000100

Debug  PopCount64(input1 & input2) 
Debug  PopCount(input1 & input2) 

t1 = ElapsedMilliseconds()
For i = 1 To 100000000
  Result = CountString(Bin(input1 & input2),"1")
Next
t2 = ElapsedMilliseconds()
For i = 1 To 100000000
  Result = PopCount(input1 & input2) 
Next
t3 = ElapsedMilliseconds()

If gIsSSE42  
  out.s = "countstring " + Str(Int((t2-t1)))+" ms: Popcnt SSE " + Str(Int((t3-t2))) + "ms "
Else 
  out.s = "countstring " + Str(Int((t2-t1)))+" ms: Popcnt 64 " + Str(Int((t3-t2))) + "ms "
EndIf   

SetClipboardText(out) 
MessageRequester("End",out, #PB_MessageRequester_Ok) 

if you need want to do bigger bitarrays you can use bitmodule
viewtopic.php?t=57409

also this bloomfilter might be useful too (it was made for doing kmer counts in the 100's)
viewtopic.php?p=573334#p573334
User avatar
jacdelad
Addict
Addict
Posts: 1431
Joined: Wed Feb 03, 2021 12:46 pm
Location: Planet Riesa
Contact:

Re: Comparisons in mathematical simulations

Post by jacdelad »

Dangit...I was so proud on my code...
PureBasic 6.04/XProfan X4a/Embarcadero RAD Studio 11/Perl 5.2/Python 3.10
Windows 11/Ryzen 5800X/32GB RAM/Radeon 7770 OC/3TB SSD/11TB HDD
Synology DS1821+/36GB RAM/130TB
Synology DS920+/20GB RAM/54TB
Synology DS916+ii/8GB RAM/12TB
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: Comparisons in mathematical simulations

Post by idle »

jacdelad wrote: Sat Apr 29, 2023 2:56 am Dangit...I was so proud on my code...
you should be, it's almost 5 times quicker, that's a good improvement and besides I'm just being a parrot.
SSE4.2 made it easy otherwise you'd use the swar parallel method https://graphics.stanford.edu/~seander/bithacks.htm
User avatar
jacdelad
Addict
Addict
Posts: 1431
Joined: Wed Feb 03, 2021 12:46 pm
Location: Planet Riesa
Contact:

Re: Comparisons in mathematical simulations

Post by jacdelad »

There's nothing wrong with spreading wisdom gained somewhere else. Your code did the job in 0.25 seconds (after turning off the debugger). That's simply amazing. I guess fvillanova will be happy!
PureBasic 6.04/XProfan X4a/Embarcadero RAD Studio 11/Perl 5.2/Python 3.10
Windows 11/Ryzen 5800X/32GB RAM/Radeon 7770 OC/3TB SSD/11TB HDD
Synology DS1821+/36GB RAM/130TB
Synology DS920+/20GB RAM/54TB
Synology DS916+ii/8GB RAM/12TB
fvillanova
User
User
Posts: 70
Joined: Wed May 02, 2012 2:17 am
Location: Brazil

Re: Comparisons in mathematical simulations

Post by fvillanova »

jacdelad wrote: Sat Apr 29, 2023 1:29 am This code should work with words (1.2 seconds in my test):

Code: Select all

DisableDebugger
input1.q=%00000000010100000100101
input2.q=%10000000000100000000100
t1 = ElapsedMilliseconds()
Define intermediate.q,help.a
For i = 1 To 100000000
  ;create the desired pattern
  intermediate=input1 & input2
  ;reset result
  Result=0
  ;go through all bytes of the quad
  For help=0 To 3
    ;search the predefined result and add it to Result
    Result+PeekW(?LookupTable16+PeekW(@intermediate+help))
  Next
  ;Result = CountString(Bin(input1 & input2),"1")
Next
t2 = ElapsedMilliseconds()
MessageRequester("End",StrF((t2-t1)/1000,3)+" seconds", #PB_MessageRequester_Ok) 

DataSection
    LookupTable16:
    ;You lookup table here!
EndDataSection
But you need to generate your own lookup table...

Code: Select all

Define a.l,b.a,med.q,output$
For a=0 To 65535
  PokeW(@med+b,a)
  b+2
  If b>3
    b=0
    output$+",$"+Hex(med)
    If Len(output$)>150
      Debug "Data.q "+Right(output$,Len(output$)-1)
      output$=""
    EndIf
  EndIf
Next
If output$<>""
  Debug "Data.q "+Right(output$,Len(output$)-1)
EndIf
...and put the debug output into the lookup table (first code).
Hi Jacdelad,
Thanks a lot for your quick help.
My example routine above takes 5.018 sec
yours is faster and does it in 0.912 seconds !!!
Much better than mine.
I still don't understand "Lookup-Table" exactly but the problem of
increasing encoding is not a problem.
I'll run some tests and let you know later.
Thank you very much
User avatar
jacdelad
Addict
Addict
Posts: 1431
Joined: Wed Feb 03, 2021 12:46 pm
Location: Planet Riesa
Contact:

Re: Comparisons in mathematical simulations

Post by jacdelad »

Nah, take idles approach. That's the maximum of optimization (though I suspect it only works for the 64 bit compiler and only ASM, not C; at least without some changes).
Last edited by jacdelad on Sat Apr 29, 2023 3:54 am, edited 1 time in total.
PureBasic 6.04/XProfan X4a/Embarcadero RAD Studio 11/Perl 5.2/Python 3.10
Windows 11/Ryzen 5800X/32GB RAM/Radeon 7770 OC/3TB SSD/11TB HDD
Synology DS1821+/36GB RAM/130TB
Synology DS920+/20GB RAM/54TB
Synology DS916+ii/8GB RAM/12TB
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: Comparisons in mathematical simulations

Post by idle »

I just added the c support, but it's x64 only
If on x86 the bitmodule will work quite well

Code: Select all


DisableDebugger

Prototype protPopCount(x.i) 
Global PopCount.protPopCount  

CompilerIf #PB_Compiler_Backend = #PB_Backend_C 
  
  Procedure.i Popcount64(x.i)
    x - (x >> 1) &  $5555555555555555           
    x = (x & $3333333333333333) + ((x >> 2) & $3333333333333333)
    x = (x + (x >> 4)) & $0f0f0f0f0f0f0f0f
    x * $0101010101010101
    x >> 56
    ProcedureReturn x   
  EndProcedure 
  
  PopCount = @Popcount64()
  
CompilerElse   
    
  Procedure Popcount64(x.i)
    ;x - (x >> 1) &  $5555555555555555           
    !mov rax, [p.v_x]
    !mov rdx, rax
    !shr rdx, 1
    !mov r15, 0x5555555555555555
    !and rdx, r15
    !sub rax,rdx 
    ;x = (x & $3333333333333333) + ((x >> 2) & $3333333333333333)
    !mov rdx, rax       ;x 
    !mov r15, 0x3333333333333333 
    !and rax, r15  
    !shr rdx, 2 
    !and rdx, r15
    !add rax,rdx
    ;x = (x + (x >> 4)) & $0f0f0f0f0f0f0f0f
    !mov rdx, rax 
    !shr rdx, 4 
    !add rax,rdx 
    !mov r15, 0x0f0f0f0f0f0f0f0f
    !and rax, r15 
    ;x * 0101010101010101 >> 56
    !mov r15, 0x0101010101010101
    !imul rax, r15
    !shr rax, 56 
    ProcedureReturn  
  EndProcedure 
  
  Procedure PopCountSSE(inp.i)
    !POPCNT rax,[p.v_inp]  
    ProcedureReturn  
  EndProcedure  
  
  Global gIsSSE42
  
  !mov rax, 1
  !cpuid
  !shr rcx, 23
  !and rcx, 1
  !mov [v_gIsSSE42],rcx 
  
  If gIsSSE42 
    PopCount = @PopcountSSE() 
  Else 
    PopCount = @Popcount64()
 EndIf    
  
CompilerEndIf 

input1.q=%00000000010100000100101
input2.q=%10000000000100000000100

Debug  PopCount64(input1 & input2) 
Debug  PopCount(input1 & input2) 

t1 = ElapsedMilliseconds()
For i = 1 To 100000000
  Result = CountString(Bin(input1 & input2),"1")
Next
t2 = ElapsedMilliseconds()
For i = 1 To 100000000
  Result = PopCount(input1 & input2) 
Next
t3 = ElapsedMilliseconds()

If gIsSSE42  
  out.s = "countstring " + Str(Int((t2-t1)))+" ms: Popcnt SSE " + Str(Int((t3-t2))) + "ms "
Else 
  out.s = "countstring " + Str(Int((t2-t1)))+" ms: Popcnt 64 " + Str(Int((t3-t2))) + "ms "
EndIf   

SetClipboardText(out) 
MessageRequester("End",out, #PB_MessageRequester_Ok) 
fvillanova
User
User
Posts: 70
Joined: Wed May 02, 2012 2:17 am
Location: Brazil

Re: Comparisons in mathematical simulations

Post by fvillanova »

idle wrote: Sat Apr 29, 2023 2:31 am This can be greatly speed up with SSE4.2 popcount
this is for x64 Asm and C backend
countstring 5205 ms: Popcnt SSE 162ms

Code: Select all

;DisableDebugger

Prototype protPopCount(x.i) 
Global PopCount.protPopCount  

CompilerIf #PB_Compiler_Backend = #PB_Backend_C 
  
  Procedure.i Popcount64(x.i)
    x - (x >> 1) &  $5555555555555555           
    x = (x & $3333333333333333) + ((x >> 2) & $3333333333333333)
    x = (x + (x >> 4)) & $0f0f0f0f0f0f0f0f
    x * $0101010101010101
    x >> 56
    ProcedureReturn x   
  EndProcedure 
  
  PopCount = @Popcount64()
  
CompilerElse   
    
  Procedure Popcount64(x.i)
    ;x - (x >> 1) &  $5555555555555555           
    !mov rax, [p.v_x]
    !mov rdx, rax
    !shr rdx, 1
    !mov r15, 0x5555555555555555
    !and rdx, r15
    !sub rax,rdx 
    ;x = (x & $3333333333333333) + ((x >> 2) & $3333333333333333)
    !mov rdx, rax       ;x 
    !mov r15, 0x3333333333333333 
    !and rax, r15  
    !shr rdx, 2 
    !and rdx, r15
    !add rax,rdx
    ;x = (x + (x >> 4)) & $0f0f0f0f0f0f0f0f
    !mov rdx, rax 
    !shr rdx, 4 
    !add rax,rdx 
    !mov r15, 0x0f0f0f0f0f0f0f0f
    !and rax, r15 
    ;x * 0101010101010101 >> 56
    !mov r15, 0x0101010101010101
    !imul rax, r15
    !shr rax, 56 
    ProcedureReturn  
  EndProcedure 
  
  Procedure PopCountSSE(inp.i)
    !POPCNT rax,[p.v_inp]  
    ProcedureReturn  
  EndProcedure  
  
  Global gIsSSE42
  
  !mov rax, 1
  !cpuid
  !shr rcx, 23
  !and rcx, 1
  !mov [v_gIsSSE42],rcx 
  
  If gIsSSE42 
    PopCount = @PopcountSSE() 
  Else 
    PopCount = @Popcount64()
 EndIf    
  
CompilerEndIf 

input1.q=%00000000010100000100101
input2.q=%10000000000100000000100

Debug  PopCount64(input1 & input2) 
Debug  PopCount(input1 & input2) 

t1 = ElapsedMilliseconds()
For i = 1 To 100000000
  Result = CountString(Bin(input1 & input2),"1")
Next
t2 = ElapsedMilliseconds()
For i = 1 To 100000000
  Result = PopCount(input1 & input2) 
Next
t3 = ElapsedMilliseconds()

If gIsSSE42  
  out.s = "countstring " + Str(Int((t2-t1)))+" ms: Popcnt SSE " + Str(Int((t3-t2))) + "ms "
Else 
  out.s = "countstring " + Str(Int((t2-t1)))+" ms: Popcnt 64 " + Str(Int((t3-t2))) + "ms "
EndIf   

SetClipboardText(out) 
MessageRequester("End",out, #PB_MessageRequester_Ok) 

if you need want to do bigger bitarrays you can use bitmodule
viewtopic.php?t=57409

also this bloomfilter might be useful too (it was made for doing kmer counts in the 100's)
viewtopic.php?p=573334#p573334
wow!!! unbelievable!
I will test your idea.
here was 0.194 seconds with my computer
thank you very much
fvillanova
User
User
Posts: 70
Joined: Wed May 02, 2012 2:17 am
Location: Brazil

Re: Comparisons in mathematical simulations

Post by fvillanova »

I need to thank Jacdelad and Idle for the help that speeded up my processing, thanks for the ideas.
I have another small routine that converts the results obtained (01 to 62) into a binary string that will later be compared and analyzed within their simulation groups.
It will also be possible to accelerate:

Code: Select all

DisableDebugger
Global Dim Types_.s(62)
For i = 1 To 62: If i<10: Types_(i)="0"+Str(i): Else: Types_(i)=Str(i): EndIf: Next 

 Procedure.s CreateB(String1.s,lim.i)
  Protected.i i
  Protected.s aux="%"
  For i=lim To 1 Step -1
    If FindString(String1,Types_(i))
      aux+"1"
    Else
      aux+"0"
    EndIf  
  Next
  ProcedureReturn aux
EndProcedure

input1.s="03 07 11 13 17 18 19 21 23 25 28 31 33 37 43 45 49 51 55 60 62" ; With results in sequence
input2.s="51 43 11 27 29 33 18 01 02 05 19"                               ; With results out of sequence

t1 = ElapsedMilliseconds()
For i = 1 To 200000
  Result1$ = CreateB(input1,62)  ; Result1$ = %10100001000101000101000001000101001001010101110001010001000100  
  Result2$ = CreateB(input2,53)  ; Result2$ = %00100000001000000000100010100000001100000010000010011
Next
t2 = ElapsedMilliseconds()
MessageRequester("End",StrF((t2-t1)/1000,3)+" seconds", #PB_MessageRequester_Ok) 
Here this processing takes 4.543 seconds
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: Comparisons in mathematical simulations

Post by idle »

This assumes your input strings are exactly in format as they appear and rather than returning a sting it returns the binary number, if you need to print it as a string you can call Bin()
16ms vs 4210 ms

Code: Select all

Procedure.i CreateB(*input)
  Protected *inp.Unicode = *input 
  Protected n.u 
  Protected aux.i
  Repeat  
    n = (*inp\u-48) * 10  
    *inp+2 
    n + *inp\u-48 
    *inp+4
    aux | (1 << (n)) 
  Until *inp\u = 0 
  ProcedureReturn aux>>1
EndProcedure

input1.s="03 07 11 13 17 18 19 21 23 25 28 31 33 37 43 45 49 51 55 60 62" ; With results in sequence
input2.s="51 43 11 27 29 33 18 01 02 05 19"                               ; With results out of sequence

CompilerIf #PB_Compiler_Debugger 
Result1 = CreateB(@input1)  ; Result1$ = %10100001000101000101000001000101001001010101110001010001000100  
Result2 = CreateB(@input2)  ; Result2$ = %00100000001000000000100010100000001100000010000010011
Debug Bin(result1,#PB_Quad) 
Debug Bin(result2,#PB_Quad)  
CompilerEndIf 

t1 = ElapsedMilliseconds()
For i = 1 To 200000
  Result1 = CreateB(@input1)  ; Result1$ = %10100001000101000101000001000101001001010101110001010001000100  
  Result2 = CreateB(@input2)  ; Result2$ = %00100000001000000000100010100000001100000010000010011
Next
t2= ElapsedMilliseconds()
out.s = Str(t2-t1) + " ms"
SetClipboardText(out) 
MessageRequester("End",out, #PB_MessageRequester_Ok) 

and combined codes

Code: Select all

Prototype protPopCount(x.i) 
Global PopCount.protPopCount  

CompilerIf #PB_Compiler_Backend = #PB_Backend_C 
  
  Procedure.i Popcount64(x.i)
    x - (x >> 1) &  $5555555555555555           
    x = (x & $3333333333333333) + ((x >> 2) & $3333333333333333)
    x = (x + (x >> 4)) & $0f0f0f0f0f0f0f0f
    x * $0101010101010101
    x >> 56
    ProcedureReturn x   
  EndProcedure 
  
  PopCount = @Popcount64()
  
CompilerElse   
    
  Procedure Popcount64(x.i)
    ;x - (x >> 1) &  $5555555555555555           
    !mov rax, [p.v_x]
    !mov rdx, rax
    !shr rdx, 1
    !mov r15, 0x5555555555555555
    !and rdx, r15
    !sub rax,rdx 
    ;x = (x & $3333333333333333) + ((x >> 2) & $3333333333333333)
    !mov rdx, rax       ;x 
    !mov r15, 0x3333333333333333 
    !and rax, r15  
    !shr rdx, 2 
    !and rdx, r15
    !add rax,rdx
    ;x = (x + (x >> 4)) & $0f0f0f0f0f0f0f0f
    !mov rdx, rax 
    !shr rdx, 4 
    !add rax,rdx 
    !mov r15, 0x0f0f0f0f0f0f0f0f
    !and rax, r15 
    ;x * 0101010101010101 >> 56
    !mov r15, 0x0101010101010101
    !imul rax, r15
    !shr rax, 56 
    ProcedureReturn  
  EndProcedure 
  
  Procedure PopCountSSE(inp.i)
    !POPCNT rax,[p.v_inp]  
    ProcedureReturn  
  EndProcedure  
  
  Global gIsSSE42
  
  !mov rax, 1
  !cpuid
  !shr rcx, 23
  !and rcx, 1
  !mov [v_gIsSSE42],rcx 
  
  If gIsSSE42 
    PopCount = @PopcountSSE() 
  Else 
    PopCount = @Popcount64()
 EndIf    
  
CompilerEndIf 

Procedure.i CreateB(*input)
  Protected *inp.Unicode = *input 
  Protected n.u 
  Protected aux.i
  Repeat  
    n = (*inp\u-48) * 10  
    *inp+2 
    n + *inp\u-48 
    *inp+4
    aux | (1 << (n)) 
  Until *inp\u = 0 
  ProcedureReturn aux>>1
EndProcedure

input1.s="03 07 11 13 17 18 19 21 23 25 28 31 33 37 43 45 49 51 55 60 62" ; With results in sequence
input2.s="51 43 11 27 29 33 18 01 02 05 19"                               ; With results out of sequence

inputq1.q = CreateB(@input1)
inputq2.q = CreateB(@input2) 

Debug RSet(Bin(inputq1,#PB_Quad),64,"0") 
Debug RSet(Bin(inputq2,#PB_Quad),64,"0") 
Debug RSet(Bin(inputq1 & inputq2),64,"0") 

Debug PopCount(inputq1 & inputq2) 

fvillanova
User
User
Posts: 70
Joined: Wed May 02, 2012 2:17 am
Location: Brazil

Re: Comparisons in mathematical simulations

Post by fvillanova »

Code: Select all

DisableDebugger
Procedure.i CreateB(*input)
  Protected *inp.Unicode = *input 
  Protected n.u 
  Protected aux.i
  Repeat  
    n = (*inp\u-48) * 10  
    *inp+2 
    n + *inp\u-48 
    *inp+4
    aux | (1 << (n)) 
  Until *inp\u = 0 
  ProcedureReturn aux>>1
EndProcedure

input1.s="03 07 11 13 17 18 19 21 23 25 28 31 33 37 43 45 49 51 55 60 62" ; With results in sequence
input2.s="51 43 11 27 29 33 18 01 02 05 19"                               ; With results out of sequence

t1 = ElapsedMilliseconds()
For i = 1 To 200000
  Result1 = CreateB(@input1)  ; Result1 = 10100001000101000101000001000101001001010101110001010001000100  
  Result2 = CreateB(@input2)  ; Result2 = 100000001000000000100010100000001100000010000010011
Next
t2= ElapsedMilliseconds()
out.s = Str(t2-t1) + " ms"
SetClipboardText(out) 
MessageRequester("End",out, #PB_MessageRequester_Ok) 
Hi Idle,
your procedure worked perfectly here.
This test above takes 15 milliseconds on my computer
Now I will be able to process much larger amounts of simulations in a shorter period of time.
thank you so much again!
Post Reply