Squares

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

Re: Squares

Post by albert »

@Richard

My computer gets the bytes backwards , ushort ptr "01" = "10" instead of "01" ?
How do you correct for the big / little endian stuff??

Code: Select all


screen 19

dim as string l_r = ""
dim as string r_l = ""

print "left / right             right / left"
for a as longint = 0 to 3
    for b as longint = 0 to 3
        
        l_r = str(a) + str(b)
        r_l = str(b) + str(a)
        
        dim as ushort ptr usp_lr = cptr( ushort ptr , strptr( l_r ) )
        dim as ushort ptr usp_rl = cptr( ushort ptr , strptr( r_l ) )
        
        print "   " ; l_r ; " " ; *usp_lr - 12336  , ,   r_l ; " " ;  *usp_rl - 12336
        
    next
next

sleep
end

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

Re: Squares

Post by Richard »

You must reverse the order you convert the elements when you fill the array of Short variables.
Convert the string in one direction, the array in the other.
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

@Richard

I got my formulas working,, can you have a look-see , and see if you can make them simpler??

Code: Select all


screen 19

randomize

do

        randomize
        
        dim as string l_r = right( "0000" + str( int( rnd*10000 ) ) , 4 )
        dim as ulong ptr usp_lr = cptr( ulong ptr , strptr( l_r ) )
       
       
        print
        print l_r ,  *usp_lr - 808464432  , " " ;  *usp_lr ' 808464432 = *ulong ptr "0000" 
       
        *usp_lr-= 808464432
       
        'Albert's formula for solving ( ulong ptr ) endian
         'Returns the same value as MID( str , ? , 4 )
        dim as ulong mids = (((( *usp_lr mod 256 ) *10) + ( (*usp_lr mod 65536) \ 256)) * 100) + (((*usp_lr mod 16777216) \ 65536)*10) + (((*usp_lr mod 4294967296) \ 16777216))
        ' ; "         " , ; "  " ;
       
        'Albert's formula for solving ( ulong ptr ) endian
        'converts ( mids ) above back to a native endian ptr
        dim as ulong mids_back_to_ptr =   (((( mids mod 1000) \100 ) * 256) ) + (((mids \ 1000 mod 10 )  ) ) + ( (( mids mod 10) * (2^24)) + (((mids mod 100) \ 10 ) * (2^16)) )

        print mids , " " ; mids_back_to_ptr , mids_back_to_ptr + 808464432
       
       
        sleep

loop until inkey = chr(27)

end



I just fumbled around and kept altering them till i got them working...
It took me a week of fumbling,, taking baby steps , getting each digit till i got the full formula..

Can you correct them , to make them simpler and faster??
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

@Richard

I got my formulas working with 4 byte ULONG... I simplified the formulas, by myself..

Code: Select all


screen 19

randomize

do

        randomize
        
        dim as string l_r = right( "0000" + str( int( rnd*10000 ) ) , 4 )
        dim as ulong ptr usp_lr = cptr( ulong ptr , strptr( l_r ) )
       
       
        print
        print l_r ,  *usp_lr - 808464432  , " " ;  *usp_lr ' 808464432 = *ulong ptr "0000" 
       
        
        'Albert's formula for solving ( ulong ptr ) endian
         'Returns the same value as MID( str , ? , 4 )
        dim as ulong val1 = *usp_lr - 808464432
        dim as ulong mids = 0
        mids+= ( val1 mod 256 )
        mids*=10
        mids+= ((val1 mod 65536) \ 256)
        mids*=10
        mids+= ((val1 mod 16777216) \ 65536) 
        mids*=10
        mids+= ((val1 mod 4294967296) \ 16777216)
        
        'Albert's formula for solving ( ulong ptr ) endian
        'converts ( mids ) above back to a native endian ptr
        dim as ulong mids_back_to_ptr = 0
        mids_back_to_ptr+= ((mids mod 10000) \ 1000 )
        mids_back_to_ptr+= ((mids mod 1000  ) \ 100   ) * 256
        mids_back_to_ptr+= ((mids mod 100    )  \ 10    ) * 65536
        mids_back_to_ptr+= ((mids mod 10      )             ) * 16777216
        '
        print mids , " " ; mids_back_to_ptr , mids_back_to_ptr + 808464432
        
        sleep

loop until inkey = chr(27)

end

albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

I got my formulas working with ulongint , 8 bytes.

Code: Select all


screen 19

randomize

do

        randomize
        
        dim as string l_r = ""
        for a as longint = 1 to 8
            l_r+= str( int( rnd*10 ) )
        next
        
        dim as ulongint ptr ulp_lr = cptr( ulongint ptr , strptr( l_r ) )
              
        print
        print l_r ,  *ulp_lr - 3472328296227680304  , *ulp_lr
               
        'Albert's formula for solving ( ulongint ptr ) endian
         'Returns the same value as MID( str , ? , 8 )
        dim as ulongint val1 = *ulp_lr - 3472328296227680304
        dim as ulongint mids = 0
        mids+= ( val1 mod (2^7) )
        mids*=10
        mids+= ((val1 mod (2^15) ) \ (2^8) )
        mids*=10
        mids+= ((val1 mod (2^23) ) \ (2^16) )
        mids*=10
        mids+= ((val1 mod (2^31) ) \ (2^24) )
        mids*=10
        mids+= ((val1 mod (2^39) ) \ (2^32) )
        mids*=10
        mids+= ((val1 mod (2^47) ) \ (2^40) )
        mids*=10
        mids+= ((val1 mod (2^55) ) \ (2^48) )
        mids*=10
        mids+= ((val1 mod (2^63) ) \ (2^56) )
        
        'Albert's formula for solving ( ulongint ptr ) endian
        'converts ( mids ) above back to a native endian ptr
        dim as ulongint mids_back_to_ptr = 0
        mids_back_to_ptr+= ((mids mod 10               )                       ) * (2^56)
        mids_back_to_ptr+= ((mids mod 100             )  \ 10              ) * (2^48)
        mids_back_to_ptr+= ((mids mod 1000           )  \ 100            ) * (2^40)
        mids_back_to_ptr+= ((mids mod 10000         )  \ 1000          ) * (2^32)
        mids_back_to_ptr+= ((mids mod 100000       )  \ 10000        ) * (2^24)
        mids_back_to_ptr+= ((mids mod 1000000     )  \ 100000     ) * (2^16)
        mids_back_to_ptr+= ((mids mod 10000000   )  \ 1000000   ) * (2^8)
        mids_back_to_ptr+= ((mids mod 100000000 ) \ 10000000 )
        '
        print mids , mids_back_to_ptr ,  mids_back_to_ptr + 3472328296227680304
        
        sleep

loop until inkey = chr(27)

end

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

Re: Squares

Post by Richard »

@Albert.
2^56 is a double precision number, with only 52 bits of accuracy.
1ULL Shl 56 is the exact number, as a long integer with 64 bits.

Code: Select all

Print 2^56
Print "  "; 1ULL Shl 56
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

@Richard

Thanks Richard... For the end program i'm going to put in the actual value of the bits. No ( 2 ^ ?? )

1 = 256 = 8
2 = 65536 = 16
3 = 16777216 = 24
4 = 4294967296 = 32
5 = 1099511627776 = 40
6 = 281474976710656 = 48
7 = 72057594037927936 = 56

I was wondering , if you could alter the formulas , to be as fast as is possibly possible???
Richard
Posts: 3096
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

Post by Richard »

You DO NOT need to embed the actual number in the code to get speed, the compiler will work it out once at compile time. It comes down to the question; Which of the following five is the most obvious, and least likely to get wrong?
2^56
1uLL shl 56
Bitset( 0uLL, 56 )
&h0100000000000000uLL
72057594037927936uLL

I think it is Bitset( 0uLL, 56 )

Why should I speed up your code to spoil your fun.
It will probably behave differently on your platform anyhow.
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

@Richard

Setting the number to the actual value is the fastest... Here's each of your 5 formulas with 1,000,000 loops

Code: Select all


screen 19

dim as ulongint n1 = 0
dim as ulongint n2 = 0
dim as ulongint n3 = 0
dim as ulongint n4 = 0
dim as ulongint n5 = 0

dim as double t1 , t2
dim as double t3 , t4
dim as double t5 , t6
dim as double t7 , t8
dim as double t9 , t10

dim as double n1_low = 1
dim as double n2_low = 1
dim as double n3_low = 1
dim as double n4_low = 1
dim as double n5_low = 1


do
   
t1 = timer
for a as ulongint =  1 to 1000000
    n1 = 2^56
next
t2 = timer
if t2 - t1 < n1_low then n1_low = t2 - t1

t3 = timer
for a as ulongint =  1 to 1000000
    n2 = 1uLL shl 56
next
t4 = timer
if t4 - t3 < n2_low then n2_low = t4 - t3

t5 = timer
for a as ulongint =  1 to 1000000
    n3 = Bitset( 0uLL, 56 )
next
t6 = timer
if t6 - t5 < n3_low then n3_low = t6 - t5

t7 = timer
for a as ulongint =  1 to 1000000
    n4 = &h0100000000000000uLL
next
t8 = timer
if t8 - t7 < n4_low then n4_low = t8 - t7

t9 = timer
for a as ulongint =  1 to 1000000
    n5 = 72057594037927936uLL
next
t10 = timer
if t10 - t9 < n5_low then n5_low = t10 - t9

print
print "2^56              " ; "    " ; n1                       , t2-t1     , n1_low
print "1uLL shl 56       " ; "    " ; n2                  , t4-t3     , n2_low
print "Bitset( 0uLL, 56 )" ; "    " ; n3               , t6-t5     , n3_low 
print "&h0100000000000000uLL" ; " " ; n4 , t8-t7    , n4_low
print "72057594037927936uLL" ; "  " ; n5   , t10-t9 , n5_low

sleep

loop until inkey = chr(27)

end

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

Re: Squares

Post by Richard »

It might be fastest on your system but is not consistently faster on mine.
It is testing the speed of your cpu internal pipeline and cache for 64 bit data.
You need to examine the asm code actually generated by the compiler for each inner loop case.
Richard
Posts: 3096
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

Post by Richard »

@Albert. This makes it easy to understand and does not require acres of constants.

Code: Select all

'---------------------------------------------------------
' make working variables and constant at the same time
Dim As String num8 = "00000000", txt = num8
Dim As Ulongint Ptr p_num8 = Cast( Ulongint Ptr, Strptr( num8 ) )
Dim As Ulongint x, y, zbase = *p_num8, mask = &h0F
Print zbase 
Print 3472328296227680304uLL    ' Albert's magic number
Print
Randomize

'---------------------------------------------------------
' make a random string of 8 digits, called num8
For i As Integer = 0 To 7       ' direction irrelevant
    num8[ i ] = Asc( "0" ) + Int( Rnd*10 )
Next
Print " input "; num8

'---------------------------------------------------------
' convert 8 ascii bytes to uLL, called y
x = *p_num8 - zbase ' refer to ascii zero
y = 0
For i As Integer = 0 To 56 Step 8   ' reverse loop reverses endian
    y = y * 10 + ( ( x Shr i ) And mask )
Next i
Print  "  uLL  "; y

'---------------------------------------------------------
' convert a uLL back to an ascii string, called txt
For i As Integer = 7 To 0 Step -1   ' reverse loop to reverse endian
    txt[ i ] = y Mod 10 + Asc( "0" )
    y = y \ 10
Next i
If y Then Print " Input too big. "
Print "output "; txt

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

Re: Squares

Post by Richard »

One issue is that you are reading 8 bytes at the time from the string by using a UlongInt pointer. That produces 8 ascii digits, which then gets converted to binary, so it will fit easily in a 32 bit Ulong.
It is important that the string be a multiple of 8 digits long, or there will be a bounds error when you read the end of the string.

It is a pity we cannot compute y Div 10, and keep the y Mod 10 remainder for free, as happens in assembly code. Maybe if 10 was declared as a constant, a deep optimiser could recognise the case.

Here is an example with loops converted to straight code.

Code: Select all

'---------------------------------------------------------
' Conversions using Ulongint, pointer indexed from a string
' Start with 8 ascii digits in x, a UlongInt = 64 bit integer
' convert those 8 digits to y, a ULong = 32 bit integer
' then convert a Ulong y, back to z, as 8 ascii digits in Ulongint

'---------------------------------------------------------
' make state variables
Dim As Ulongint x, z
Dim As Ulong y

'---------------------------------------------------------
' make input and output uLL pointer indexed strings 
Dim As String num8 = "00000000", text = num8
Dim As Ulongint Ptr p_num8 = Cast( Ulongint Ptr, Strptr( num8 ) )   ' input
Dim As Ulongint Ptr p_text = Cast( Ulongint Ptr, Strptr( text ) )   ' output

'---------------------------------------------------------
Dim As Ulongint ascii_base = *p_num8
Print ascii_base
Print 3472328296227680304uLL    ' Albert's magic number
Print
Randomize

'---------------------------------------------------------
' make a random string of 8 digits
For i As Integer = 0 To 7       ' direction irrelevant
    num8[ i ] = Asc( "0" ) + Int( Rnd * 10 )
Next
x = *p_num8
Print " input "; num8

'---------------------------------------------------------
' convert 8 ascii bytes in Ulongint x to uLong y
x = *p_num8 - ascii_base ' refer to ascii zero
'y = 0
'For i As Integer = 0 To 56 Step 8   ' reverse loop reverses endian
'    y = ( ( x Shr i ) And &h0F ) + ( y * 10 )
'Next i
' expand above 4 lines
y = ( ( x Shr  0 ) And &h0F )
y = ( ( x Shr  8 ) And &h0F ) + y * 10
y = ( ( x Shr 16 ) And &h0F ) + y * 10
y = ( ( x Shr 24 ) And &h0F ) + y * 10
y = ( ( x Shr 32 ) And &h0F ) + y * 10
y = ( ( x Shr 40 ) And &h0F ) + y * 10
y = ( ( x Shr 48 ) And &h0F ) + y * 10
y = ( ( x Shr 56 ) And &h0F ) + y * 10
Print Using " uLong ########"; y

'---------------------------------------------------------
' convert a uLong y, back into Ulongint z, then to ascii string
'For i As Integer = 0 To 7     ' reverse loop to reverse endian
'    z = ( z Shl 8 ) + ( y Mod 10 ) : y = y \ 10
'Next i
' expand above 3 lines
z =               ( y Mod 10 ) : y \= 10
z = ( z Shl 8 ) + ( y Mod 10 ) : y \= 10
z = ( z Shl 8 ) + ( y Mod 10 ) : y \= 10
z = ( z Shl 8 ) + ( y Mod 10 ) : y \= 10
z = ( z Shl 8 ) + ( y Mod 10 ) : y \= 10
z = ( z Shl 8 ) + ( y Mod 10 ) : y \= 10
z = ( z Shl 8 ) + ( y Mod 10 ) : y \= 10
z = ( z Shl 8 ) + ( y Mod 10 )
*p_text = z + ascii_base
Print "output "; text

'---------------------------------------------------------
If num8 <> text Then
    Print " Error detected."
    Sleep
Else
    Print " Correct."
End If

Print
Sleep
'---------------------------------------------------------
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

@Richard

I'm working again , on my Vari_Cyph program , trying to speed it up.

It generates a binary string , maybe over a gigabyte..
I need to step through the string by 4 bits at a time , and convert the 4 bits , to decimal.

What' the fastest way to step through the string by 4's ( returning 0 to 15) ??
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

@Richard

I did a test comparing MID() to *ptr , on a string 1,000,000 bits..

Mid() comes out to about .33
*ptr comes out to about .0033 , hundred times faster... Can you do anything faster than .0033 ??

Code: Select all


screen 19

    dim as string n=""
    for a as longint = 1 to 1000000
        n+=str(int(rnd*2))
    next
        
    dim as string str1
    dim as longint dec1
    do
        str1 = str( len(n) / 4)
        dec1 = instr(1,str1,".")
        if dec1 <> 0 then n = "0" + n
    loop until dec1 = 0
    
    dim as string*16 sub_key = "ABCDEFGHIJKLMNOP"

    dim as double t1,t2,t3,t4
do 
    
    t1=timer
    dim as ubyte value_m = 0 
    dim as string mids_m = ""
    for a as ulongint = 1 to len(n) step 4
        value_m = val("&B"+mid(n,a,4))
        mids_m+= mid(sub_key,value_m+1,1)
    next
    t2=timer
    
    t3=timer
    dim as ulong ptr value_p = cptr(ulong ptr , strptr(n))
    dim as ubyte ptr s_k = cptr(ubyte ptr , strptr(sub_key))
    dim as string mids_p = string(len(n)\4,"0")
    dim as ubyte ptr place = cptr(ubyte ptr , strptr(mids_p))
    dim as ulong v1 , mids
    for a as ulongint = 1 to len(n) step 4
        v1 = *value_p - 808464432 : value_p+= 1
        mids = ( v1 mod (2^7) ) * 8
        mids+= ((v1 mod (2^15) ) \ 256) * 4
        mids+= ((v1 mod (2^23) ) \ 65536) * 2 
        mids+= ((v1 mod (2^31) ) \ 16777216)
        *place = *(s_k+mids) : place+=1
    next
    t4=timer
    
    print
    print left(mids_m,40) + " ~ " + right(mids_m,40)
    print left(mids_p,40) + " ~ " + right(mids_p,40)
    print
    print "time to step through 1,000,000 using MID() = " ; t2 - t1
    print "time to step through 1,000,000 using *ptr  = " ; t4 - t3
    
    sleep
    
loop until inkey = chr(27)

end

albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

@Richard

With Geany IDE fbc.exe -gen GCC -w all -O 3

I get .0014 for the pointers with 1,000,000 bits
Locked