## Squares

General FreeBASIC programming questions.
albert
Posts: 5631
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 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: 2998
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: 6360
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 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: 2998
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 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: 6360
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 = 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: 5631
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 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: 6360
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 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: 5631
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: 6360
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Squares

You get some tables in the fb help file.
Richard
Posts: 2998
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 = 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: 5631
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

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

Richard
Posts: 2998
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 = 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: 5631
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: 2998
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: 5631
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??