Squares

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

Re: Squares

Post by albert »

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 b
end 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 b
end 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 b
end function
'====================================================
'====================================================
'test functions
'====================================================
'====================================================
randomize

do
   
        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: 3096
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

Post by Richard »

@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: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Squares

Post by dodicat »

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 generator

type Rand
   a as ulongint
   b as ulongint
   c as ulongint
   d as ulongint
end type

function 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.d
end 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)
        next
end sub

'=========
dim shared as rand z
init(z)
'========


function range(f as ulongint,l as ulongint) as ulongint
    return (ranulong(z) mod ((l-f)+1)) + f
end function


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 b
end function


function 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 s1
end function


randomize

do
    
        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: 3096
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

Post by Richard »

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

Code: Select all

'a ulongint generator

Type Rand
    a As Ulongint
    b As Ulongint
    c As Ulongint
    d As Ulongint
End Type

Function 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.d
End Function

Sub 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 )
    Next
End Sub

'=========
Dim Shared As rand z
init( z )
'========

Function range( Byval f As Ulongint, Byval l As Ulongint ) As Ulongint
    Return ( ranulong( z ) Mod ( ( l - f ) + 1 ) ) + f
End 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 b
End 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 s1
End 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 s1
End Function

'---------------------------------------------------------------------------
Randomize

Do
    
    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: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Squares

Post by dodicat »

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

Code: Select all


n1 = 17507795416264255861
n2 = 14945250268739933205

14008483112229797909         0.138441122835502          albert
14008483112229797909         0.09201234485954046        dodicat
14008483112229797909         0.1212029235903174         richard

n1 = 15745121398853196173
n2 = 16103048213999544446

15708977747966183436         0.1349346947390586         albert
15708977747966183436         0.09259509551338852        dodicat
15708977747966183436         0.1163557921536267         richard

n1 = 18316301485387743194
n2 = 11256583403861619992

11254497805315257624         0.148491948377341          albert
11254497805315257624         0.09239388746209443        dodicat
11254497805315257624         0.1189567837864161         richard

n1 = 11148471744494959139
n2 = 16331900129679159417

9414230350445981729          0.1348371701315045         albert
9414230350445981729          0.09196854452602565        dodicat
9414230350445981729          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: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

@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 r
end 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 r
end 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 r
end function
'====================================================
'====================================================
'test functions
'====================================================
'====================================================
randomize
do
    
    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: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Squares

Post by dodicat »

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 Ulongint
End Type

Function 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.d
End Function

Sub 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 )
    Next
End Sub

'=========
Dim Shared As rand z
init( z )
'========

Function range( Byval f As longint, Byval l As longint ) As Ulongint
    Return ( ranulong( z ) Mod ( ( l - f ) + 1 ) ) + f
End Function

function 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 a
end function

Randomize
sleep 100
Do
    
    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: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

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: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Squares

Post by dodicat »

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

Re: Squares

Post by Richard »

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

Code: Select all

n1 = 15745121398853196173
n2 = 16103048213999544446

15708977747966183436         0.1671305693962495         albert
15708977747966183436         0.12494262704422           dodicat
15708977747966183436         0.09886247960093897        richard

n1 = 18316301485387743194
n2 = 11256583403861619992

11254497805315257624         0.1661665231149527         albert
11254497805315257624         0.1249372059755842         dodicat
11254497805315257624         0.09877333317854209        richard
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

@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


   1234
x 1234
----------
1522756

steps : mul number sets    : answer      : carry

1       = 4*4                              = 16  = 6  carry 1
2       = 3*4  ,  4*3                   = 24  = 5  carry 2
3       = 2*4  ,  3*3 , 4*2          = 25  = 7  carry 2
4       = 1*4 ,  2*3 , 3*2 , 4*1  = 20  = 2  carry 2
5       = 1*3 ,  2*2 , 3*1           = 10  = 2  carry 1
6       = 1*2 ,  2*1                    =  4   = 5  carry 0
7       = 1*1                              =  1   = 1  carry 0

Answer = 1522756

Richard
Posts: 3096
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

Post by Richard »

@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 = 8
Const As Integer ymax = 5
Dim As Integer x, y, count
Screen 20
Window (-.5, -.5)-(Iif(xmax < 10, 10, xmax + 1), Iif(ymax < 8, 8, ymax + 1))
Locate 1, 1
Print " x range 0 to"; xmax; "    y range 0 to"; ymax
Pset (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 = 0
End Sub

'============================================================
Color 14
y = 0
For x = 0 To xmax
    If x < ymax Then count = x + 1 Else count = ymax + 1
    inner(x, y, count)
Next x    

'------------------------------------------------------------
Color 13
x = xmax
For 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: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

@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: 3096
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

Post by Richard »

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.
https://freebasic.net/forum/viewtopic.p ... 00#p250800
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

@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??
Locked