## Squares

General FreeBASIC programming questions.
albert
Posts: 5701
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Squares

Here's my latest "LOGIC FUNCTIONS"

Works as long as both strings are the same length...

Code: Select all

`screen 19'===================================================='====================================================function Redditt_and( a as string , b as string ) as string    dim as longint x = len(b) - 1    do        b[x]+= a[x]        if b[x] = 98 then b[x] = 49 else b[x] = 48        x-=1    loop until x = -1    return bend function'===================================================='====================================================function Redditt_or( a as string , b as string ) as string    dim as longint x = len(b) - 1    do        b[x]+= a[x]        if b[x] = 96 then b[x] = 48 else b[x] = 49        x-=1    loop until x = -1    return bend function'===================================================='====================================================function Redditt_xor( a as string , b as string ) as string    dim as longint x = len(b) - 1    do        b[x]+= a[x]        if b[x] = 97 then b[x] = 49 else b[x] = 48        x-=1    loop until x = -1    return bend function'===================================================='===================================================='test functions'===================================================='====================================================randomizedo           dim as ulongint a = int( rnd*1e10 )        dim as ulongint b = int( rnd*1e10 )        if b > a then swap a , b                dim as double time1 , time2                dim as double b_and_time        dim as double r_and_time                dim as double b_or_time        dim as double r_or_time                dim as double b_xor_time        dim as double r_xor_time                dim as ulongint b_and        dim as ulongint b_or        dim as ulongint b_xor                dim as ulongint r_and        dim as ulongint r_or        dim as ulongint r_xor'======================================            'builtin AND            time1 = timer                'for x as longint = 1 to 1e6                    b_and = ( a and b)                'next            time2 = timer           b_and_time = time2 - time1                      'Redditt_AND                dim as string and_ans = ""                dim as string and_1 = right( string(64,"0") + bin(a) , 64 )                dim as string and_2 = right( string(64,"0") + bin(b) , 64 )            time1 = timer                'for x as longint = 1 to 1e6                    and_ans = Redditt_and( and_1 , and_2 )                'next                r_and = valulng("&B" + and_ans)            time2 = timer            r_and_time = time2 - time1'======================================'======================================            'builtin OR            time1 = timer                'for x as longint = 1 to 1e6                    b_or = ( a or b)                'next            time2 = timer           b_or_time = time2 - time1                      'Redditt_OR                dim as string or_ans = ""                dim as string or_1 = right( string(64,"0") + bin(a) , 64 )                dim as string or_2 = right( string(64,"0") + bin(b) , 64 )            time1 = timer                'for x as longint = 1 to 1e6                    or_ans = Redditt_or( or_1 , or_2 )                'next                r_or = valulng("&B" + or_ans)            time2 = timer            r_or_time = time2 - time1'======================================            'builtin XOR            time1 = timer                'for x as longint = 1 to 1e6                    b_xor = ( a xor b)                'next            time2 = timer           b_xor_time = time2 - time1                      'Redditt_XOR                dim as string xor_ans = ""                dim as string xor_1 = right( string(64,"0") + bin(a) , 64 )                dim as string xor_2 = right( string(64,"0") + bin(b) , 64 )            time1 = timer                'for x as longint = 1 to 1e6                    xor_ans = Redditt_xor( xor_1 , xor_2 )                'next                r_xor = valulng("&B" + xor_ans)            time2 = timer            r_xor_time = time2 - time1'======================================                        dim as longint and_diff = b_and - r_and             dim as longint    or_diff = b_or    - r_or            dim as longint   xor_diff = b_xor    - r_xor                        cls            print            print "n1 = " ; a            print "n2 = " ; b            print            print "Builtin AND  = "   ; b_and , "time = " ;  b_and_time            print "Redditt AND  = "  ; r_and  , "time = " ;  r_and_time            print            print "Builtin OR  = "   ; b_or , "time = " ;  b_or_time            print "Redditt OR  = "  ; r_or  , "time = " ;  r_or_time            print            print "Builtin XOR  = "   ; b_xor , "time = " ;  b_xor_time            print "Redditt XOR  = "  ; r_xor  , "time = " ;  r_xor_time                                    print "AND diff = "; and_diff            print "OR  diff = "; or_diff            print "XOR diff = "; xor_diff            print            print "Press a key to advance" , "press esc to exit"            sleep                       if inkey = chr(27) then end           loop until inkey = chr(27)end`
Richard
Posts: 3023
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: Squares

@Albert.
When you use strings to perform the AND operation on ULongInt data you should be doing the Bin() conversions every time inside your function. You should not be arbitrarily swapping the input numbers based on size, but should find and control the length of the strings inside your AND function each time.
That is what would have to happen if you were processing real data, and not just threshing the same cached two numbers over and over again a million times.
dodicat
Posts: 6545
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Squares

Hi Albert.
I tried running along the string from left to right,
In with two bins, use one of the parameters. and a bin out, same as yours.
I use a little ulongint generator to get the numbers.

Code: Select all

`'a ulongint generatortype Rand   a as ulongint   b as ulongint   c as ulongint   d as ulongintend typefunction ranulong(x as rand) as ulongint   dim e as ulongint = x.a - ((x.b shl 7) or (x.b shr (64 - 7)))   x.a = x.b xor ((x.c shl 13) or (x.c shr (64 - 13)))   x.b = x.c + ((x.d shl 37) or (x.d shr (64 - 37)))   x.c = x.d + e   x.d = e + x.a   return x.dend function sub init(x as rand, byval seed as ulongint=100)   dim i as ulongint    x=type(4058668781,seed,seed,seed)    for i as ulongint=1 to 20        ranulong(x)        nextend sub'=========dim shared as rand zinit(z)'========function range(f as ulongint,l as ulongint) as ulongint    return (ranulong(z) mod ((l-f)+1)) + fend functionfunction Redditt_and( a as string , b as string ) as string    dim as longint x = len(b) - 1    do        b[x]+= a[x]        if b[x] = 98 then b[x] = 49 else b[x] = 48        x-=1    loop until x = -1    return bend functionfunction dodi_and(s1 as string , s2 as string ) as string    for n as long=0 to 63       s1[n]=(s1[n]-48)*(s2[n]-48)+48    next    return s1end functionrandomizedo            dim as ulongint a = range(9223372036854775807,18446744073709551614)'int( rnd*1e10 )        dim as ulongint b = range(9223372036854775807,18446744073709551614)'int( rnd*1e10 )                dim as double time1 , time2 , time3 , time4        dim as ulongint b_and , a_and         dim as string ans            time1 = timer                for x as longint = 1 to 1e5                     ans = redditt_and( bin(a,64),bin(b,64))                next                b_and=valulng("&b"+ans)            time2 = timer                        time3 = timer                for x as longint = 1 to 1e5                      ans = dodi_and(bin(a,64),bin(b,64) )                next                a_and = valulng("&b"+ans)            time4 = timer                        'cls            print            print "n1 = " ; a            print "n2 = " ; b            print            print b_and , time2 - time1,"albert"            print a_and , time4 - time3,"dodicat"            sleep            loop until inkey = chr(27)  `
Richard
Posts: 3023
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: Squares

@dodicat. Why spend all that time in the For Next loop.

Code: Select all

`'a ulongint generatorType Rand    a As Ulongint    b As Ulongint    c As Ulongint    d As UlongintEnd TypeFunction ranulong( Byref x As rand ) As Ulongint    Dim e As Ulongint = x.a - ( ( x.b Shl 7 ) Or ( x.b Shr ( 64 - 7 ) ) )    x.a = x.b xor ( ( x.c Shl 13 ) Or ( x.c Shr ( 64 - 13 ) ) )    x.b = x.c + ( ( x.d Shl 37 ) Or ( x.d Shr ( 64 - 37 ) ) )    x.c = x.d + e    x.d = e + x.a    Return x.dEnd FunctionSub init( Byref x As rand, Byval seed As Ulongint = 100 )    Dim i As Ulongint    x = Type( 4058668781, seed, seed, seed )    For i As Ulongint = 1 To 20        ranulong( x )    NextEnd Sub'=========Dim Shared As rand zinit( z )'========Function range( Byval f As Ulongint, Byval l As Ulongint ) As Ulongint    Return ( ranulong( z ) Mod ( ( l - f ) + 1 ) ) + fEnd Function'---------------------------------------------------------------------------Function Redditt_and( Byref a As String , Byref b As String ) As String    Dim As Longint x = Len( b ) - 1    Do        b[ x ] += a[ x ]        If b[ x ] = 98 Then b[ x ] = 49 Else b[ x ] = 48        x -= 1    Loop Until x = - 1    Return bEnd Function'---------------------------------------------------------------------------Function dodi_and( Byref s1 As String, Byref s2 As String ) As String    For n As Long = 0 To 63        s1[ n ] = ( s1[ n ] - 48 ) * ( s2[ n ] - 48 ) + 48    Next    Return s1End Function'---------------------------------------------------------------------------Function Rich_and( Byref s1 As String, Byref s2 As String ) As String    Dim As Integer n = 64    Do        n -= 1        If s2[ n ] = Asc( "0" ) Then s1[ n ] = Asc( "0" )    Loop While n    Return s1End Function'---------------------------------------------------------------------------RandomizeDo        Dim As Ulongint a = range( 9223372036854775807, 18446744073709551614 ) 'int( rnd*1e10 )    Dim As Ulongint b = range( 9223372036854775807, 18446744073709551614 ) 'int( rnd*1e10 )        Dim As Double time1, time2, time3, time4, time5, time6    Dim As Ulongint b_and, a_and, c_and    Dim As String ans        '-------------------------------------------    time1 = Timer    For x As Longint = 1 To 1e5        ans = redditt_and( Bin( a, 64 ), Bin( b, 64 ) )    Next    b_and = Valulng( "&b" + ans )    time2 = Timer        '-------------------------------------------    time3 = Timer    For x As Longint = 1 To 1e5        ans = dodi_and( Bin( a, 64 ), Bin( b, 64 ) )    Next    a_and = Valulng( "&b" + ans )    time4 = Timer        '-------------------------------------------    time5 = Timer    For x As Longint = 1 To 1e5        ans = rich_and( Bin( a, 64 ), Bin( b, 64 ) )    Next    c_and = Valulng( "&b" + ans )    time6 = Timer        '-------------------------------------------    Print    Print "n1 = " ; a    Print "n2 = " ; b    Print    Print b_and , time2 - time1, "albert"    Print a_and , time4 - time3, "dodicat"    Print c_and , time6 - time5, "richard"        Sleep    Loop Until Inkey = Chr( 27 )`
dodicat
Posts: 6545
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Squares

You method looks faster Richard, but is a little slower. (here)

Code: Select all

`n1 = 17507795416264255861n2 = 1494525026873993320514008483112229797909         0.138441122835502          albert14008483112229797909         0.09201234485954046        dodicat14008483112229797909         0.1212029235903174         richardn1 = 15745121398853196173n2 = 1610304821399954444615708977747966183436         0.1349346947390586         albert15708977747966183436         0.09259509551338852        dodicat15708977747966183436         0.1163557921536267         richardn1 = 18316301485387743194n2 = 1125658340386161999211254497805315257624         0.148491948377341          albert11254497805315257624         0.09239388746209443        dodicat11254497805315257624         0.1189567837864161         richardn1 = 11148471744494959139n2 = 163319001296791594179414230350445981729          0.1348371701315045         albert9414230350445981729          0.09196854452602565        dodicat9414230350445981729          0.1186022742185742         richard `

win 10
64 bit (with no optimisations).
But with optimisation I get the same kind of speed ratios.
This computer always seems to have timings contrary to yours and Alberts.
(I put sleep 1000 before do to let the cpu settle into the program)
albert
Posts: 5701
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Squares

@Richard
@Dodicat

My LOGIC FUNCTIONS work on any length of binary strings.. not just 64 bit. ,
Only ; both strings need to be the same length.. So you have to pad with zeros to make equal lengths...

I designed them to work with a big num "binary" math system..That's why i put bin(a,b) code , outside the timers.

I'm stuck on big num "NOT" ??? how to return (-x) - 1 ??

Here's my revised functs with 80 char length binary strings...
The original functs were destroying (b) , so i added an r string to the functs.

Code: Select all

`screen 19'===================================================='====================================================function Redditt_and( a as string , b as string ) as string    dim as string r = b    dim as longint x = len(b) - 1    do        r[x]+= a[x]        if r[x] = 98 then r[x] = 49 else r[x] = 48        x-=1    loop until x = -1    return rend function'===================================================='====================================================function Redditt_or( a as string , b as string ) as string    dim as string r = b     dim as longint x = len(b) - 1    do        r[x]+= a[x]        if r[x] = 96 then r[x] = 48 else r[x] = 49        x-=1    loop until x = -1    return rend function'===================================================='====================================================function Redditt_xor( a as string , b as string ) as string    dim as string r = b    dim as longint x = len(b) - 1    do        r[x]+= a[x]        if r[x] = 97 then r[x] = 49 else r[x] = 48        x-=1    loop until x = -1    return rend function'===================================================='===================================================='test functions'===================================================='====================================================randomizedo        dim as string n1=""    for x as longint = 1 to 80        n1+=str( int( rnd*2 ) )    next        dim as string n2=""    for x as longint = 1 to 80        n2+=str( int( rnd*2 ) )    next        dim as string r_and = Redditt_and( n1 , n2 )    dim as string r_or    = Redditt_or( n1 , n2 )    dim as string r_xor  = Redditt_xor( n1 , n2 )        print    print "n1          = " ;  n1    print "n2          = " ; n2    print    print "Redditt AND = "; r_and    print "Redditt OR  = " ; r_or    print "Redditt XOR = " ; r_xor        sleep    loop until inkey = chr(27)end`
dodicat
Posts: 6545
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Squares

You will have a use for Richard's dec to bin and bin to dec now for these operations.
For not you could just run along the string again picking off what needs picked off.
I use longint here to get some negative values to test.

Code: Select all

`Type Rand    a As Ulongint    b As Ulongint    c As Ulongint    d As UlongintEnd TypeFunction ranulong( Byref x As rand ) As Ulongint    Dim e As Ulongint = x.a - ( ( x.b Shl 7 ) Or ( x.b Shr ( 64 - 7 ) ) )    x.a = x.b xor ( ( x.c Shl 13 ) Or ( x.c Shr ( 64 - 13 ) ) )    x.b = x.c + ( ( x.d Shl 37 ) Or ( x.d Shr ( 64 - 37 ) ) )    x.c = x.d + e    x.d = e + x.a    Return x.dEnd FunctionSub init( Byref x As rand, Byval seed As Ulongint = 100 )    Dim i As Ulongint    x = Type( 4058668781, seed, seed, seed )    For i As Ulongint = 1 To 20        ranulong( x )    NextEnd Sub'=========Dim Shared As rand zinit( z )'========Function range( Byval f As longint, Byval l As longint ) As Ulongint    Return ( ranulong( z ) Mod ( ( l - f ) + 1 ) ) + fEnd Functionfunction dnot(byval a as string ) as string    for n as long=0 to len(a)-1        if a[n]=asc("1") then a[n]=asc("0") else a[n]=asc("1")    next    return aend functionRandomizesleep 100Do        Dim As longint a = range(-9223372036854775807, 9223372036854775807)', 18446744073709551614 ) 'int( rnd*1e10 )          Dim As Double time1, time2, time3, time4, time5, time6    Dim As longint b_and, a_and, c_and    Dim As String ans        '-------------------------------------------    time1 = Timer    For x As Longint = 1 To 1e5        ans = dnot( Bin( a, 64 ))    Next    b_and = Vallng( "&b" + ans )    time2 = Timer        '-------------------------------------------    time3 = Timer    For x As Longint = 1 To 1e5        ans = str(not a)    Next    a_and = Vallng( ans )    time4 = Timer           '-------------------------------------------    Print    Print "n1 = " ; a      Print    Print b_and , time2 - time1, "string"    Print a_and , time4 - time3, "fb"           Sleep    Loop Until Inkey = Chr( 27 )  `
albert
Posts: 5701
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Squares

Now to write a binary mul and div..

I'm gonna play around , and do all the other logic functs , nor , xnor , nand , etc..
Just to search the internet for the logic truth tables..
dodicat
Posts: 6545
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Squares

You get some tables in the fb help file.
Richard
Posts: 3023
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: Squares

@dodicat. Your computer does run differently.
Maybe there is some advantage in 32 bits for string processing.

Code: Select all

`n1 = 15745121398853196173n2 = 1610304821399954444615708977747966183436         0.1671305693962495         albert15708977747966183436         0.12494262704422           dodicat15708977747966183436         0.09886247960093897        richardn1 = 18316301485387743194n2 = 1125658340386161999211254497805315257624         0.1661665231149527         albert11254497805315257624         0.1249372059755842         dodicat11254497805315257624         0.09877333317854209        richard`
albert
Posts: 5701
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Squares

@Richard
@Dodicat

Here's the low down on my multiplier method..
The reason it's faster , it only needs to access the output string position once.. So you don't have to add the output , over and over..

You have to copy and paste it , into FBIDE to get the formatting right..

Code: Select all

`   1234x 1234----------1522756steps : mul number sets    : answer      : carry1       = 4*4                              = 16  = 6  carry 12       = 3*4  ,  4*3                   = 24  = 5  carry 23       = 2*4  ,  3*3 , 4*2          = 25  = 7  carry 24       = 1*4 ,  2*3 , 3*2 , 4*1  = 20  = 2  carry 25       = 1*3 ,  2*2 , 3*1           = 10  = 2  carry 16       = 1*2 ,  2*1                    =  4   = 5  carry 07       = 1*1                              =  1   = 1  carry 0Answer = 1522756`
Richard
Posts: 3023
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: Squares

@Albert.
Just like my diagonal multiply avoided multiple output references, to minimise the number of times Mod 1e9 and DIV 1e9 were called.
You will find that for numbers with different lengths you will need a more complex control structure with two multiply kernels.
Here is the anotated picture of the process needed.

Code: Select all

`'================================================================' order of evaluation of partial products for diagonal multiply '================================================================Const As Integer xmax = 8Const As Integer ymax = 5Dim As Integer x, y, countScreen 20Window (-.5, -.5)-(Iif(xmax < 10, 10, xmax + 1), Iif(ymax < 8, 8, ymax + 1))Locate 1, 1Print " x range 0 to"; xmax; "    y range 0 to"; ymaxPset (0, 0), 0'============================================================Sub inner(Byval x As Integer, Byval y As Integer, Byval count As Integer)    Line -(x, y), 7    Dim As Integer i    Do        ' evaluate and accumulate partial product        Line -(x, y), Color        Draw String (x, y), Str(x) + "x" + Str(y)        x -= 1        y += 1        count -= 1    Loop Until count = 0End Sub'============================================================Color 14y = 0For x = 0 To xmax    If x < ymax Then count = x + 1 Else count = ymax + 1    inner(x, y, count)Next x    '------------------------------------------------------------Color 13x = xmaxFor y = 1 To ymax    If (ymax - y) < xmax Then count = (ymax - y) + 1 Else count = xmax + 1    inner(x, y, count)Next y'============================================================Sleep'============================================================`
albert
Posts: 5701
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Squares

@Richard

With mul binary....and my mul method..
At the height of 1 million digits , you would have maybe 1,000,000 output..
How would you proceed with bin( 1,000,000) ???
Richard
Posts: 3023
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: Squares

I'm not sure I understand the question.

A 1 million x 1 million digit multiply will have at most 1 million partial products to accumulate, so you will need at least 20 more bits in your accumulator register. 2^20 = 1 million, so I would accumulate in a 64 bit ULongInt passing carry to a 32 bit extension.

If you want conversions between decimal and binary ascii strings you could go back to my post of 18 Aug 2018.
viewtopic.php?p=250800#p250800
albert
Posts: 5701
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Squares

@Richard
@Dodicat

n1 = 01010100
n2 = 01010100
ans = 0001101110010000
me = 0001020302010000 ' How to convert to binary??

n1 = 10100100
n2 = 10100111
ans = 0110101011111100
me = 0102012131111100 ' How to convert to binary??