Squares

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

Re: Squares

@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 19dim 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            nextnextsleepend`
Richard
Posts: 2976
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

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: 5419
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

@Richard

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

Code: Select all

`screen 19randomizedo        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                      sleeploop 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: 5419
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

@Richard

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

Code: Select all

`screen 19randomizedo        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                sleeploop until inkey = chr(27)end`
albert
Posts: 5419
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

I got my formulas working with ulongint , 8 bytes.

Code: Select all

`screen 19randomizedo        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                sleeploop until inkey = chr(27)end`
Richard
Posts: 2976
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

@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^56Print "  "; 1ULL Shl 56`
albert
Posts: 5419
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

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

Re: Squares

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: 5419
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

@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 19dim as ulongint n1 = 0dim as ulongint n2 = 0dim as ulongint n3 = 0dim as ulongint n4 = 0dim as ulongint n5 = 0dim as double t1 , t2dim as double t3 , t4dim as double t5 , t6dim as double t7 , t8dim as double t9 , t10dim as double n1_low = 1dim as double n2_low = 1dim as double n3_low = 1dim as double n4_low = 1dim as double n5_low = 1do   t1 = timerfor a as ulongint =  1 to 1000000    n1 = 2^56nextt2 = timerif t2 - t1 < n1_low then n1_low = t2 - t1t3 = timerfor a as ulongint =  1 to 1000000    n2 = 1uLL shl 56nextt4 = timerif t4 - t3 < n2_low then n2_low = t4 - t3t5 = timerfor a as ulongint =  1 to 1000000    n3 = Bitset( 0uLL, 56 )nextt6 = timerif t6 - t5 < n3_low then n3_low = t6 - t5t7 = timerfor a as ulongint =  1 to 1000000    n4 = &h0100000000000000uLLnextt8 = timerif t8 - t7 < n4_low then n4_low = t8 - t7t9 = timerfor a as ulongint =  1 to 1000000    n5 = 72057594037927936uLLnextt10 = timerif t10 - t9 < n5_low then n5_low = t10 - t9printprint "2^56              " ; "    " ; n1                       , t2-t1     , n1_lowprint "1uLL shl 56       " ; "    " ; n2                  , t4-t3     , n2_lowprint "Bitset( 0uLL, 56 )" ; "    " ; n3               , t6-t5     , n3_low print "&h0100000000000000uLL" ; " " ; n4 , t8-t7    , n4_lowprint "72057594037927936uLL" ; "  " ; n5   , t10-t9 , n5_lowsleeploop until inkey = chr(27)end`
Richard
Posts: 2976
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

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

Re: Squares

@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 timeDim As String num8 = "00000000", txt = num8Dim As Ulongint Ptr p_num8 = Cast( Ulongint Ptr, Strptr( num8 ) )Dim As Ulongint x, y, zbase = *p_num8, mask = &h0FPrint zbase Print 3472328296227680304uLL    ' Albert's magic numberPrintRandomize'---------------------------------------------------------' make a random string of 8 digits, called num8For i As Integer = 0 To 7       ' direction irrelevant    num8[ i ] = Asc( "0" ) + Int( Rnd*10 )NextPrint " input "; num8'---------------------------------------------------------' convert 8 ascii bytes to uLL, called yx = *p_num8 - zbase ' refer to ascii zeroy = 0For i As Integer = 0 To 56 Step 8   ' reverse loop reverses endian    y = y * 10 + ( ( x Shr i ) And mask )Next iPrint  "  uLL  "; y'---------------------------------------------------------' convert a uLL back to an ascii string, called txtFor i As Integer = 7 To 0 Step -1   ' reverse loop to reverse endian    txt[ i ] = y Mod 10 + Asc( "0" )    y = y \ 10Next iIf y Then Print " Input too big. "Print "output "; txt'---------------------------------------------------------Sleep'---------------------------------------------------------`
Richard
Posts: 2976
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

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 variablesDim As Ulongint x, zDim As Ulong y'---------------------------------------------------------' make input and output uLL pointer indexed strings Dim As String num8 = "00000000", text = num8Dim As Ulongint Ptr p_num8 = Cast( Ulongint Ptr, Strptr( num8 ) )   ' inputDim As Ulongint Ptr p_text = Cast( Ulongint Ptr, Strptr( text ) )   ' output'---------------------------------------------------------Dim As Ulongint ascii_base = *p_num8Print ascii_basePrint 3472328296227680304uLL    ' Albert's magic numberPrintRandomize'---------------------------------------------------------' make a random string of 8 digitsFor i As Integer = 0 To 7       ' direction irrelevant    num8[ i ] = Asc( "0" ) + Int( Rnd * 10 )Nextx = *p_num8Print " input "; num8'---------------------------------------------------------' convert 8 ascii bytes in Ulongint x to uLong yx = *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 linesy = ( ( x Shr  0 ) And &h0F )y = ( ( x Shr  8 ) And &h0F ) + y * 10y = ( ( x Shr 16 ) And &h0F ) + y * 10y = ( ( x Shr 24 ) And &h0F ) + y * 10y = ( ( x Shr 32 ) And &h0F ) + y * 10y = ( ( x Shr 40 ) And &h0F ) + y * 10y = ( ( x Shr 48 ) And &h0F ) + y * 10y = ( ( x Shr 56 ) And &h0F ) + y * 10Print 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 linesz =               ( y Mod 10 ) : y \= 10z = ( z Shl 8 ) + ( y Mod 10 ) : y \= 10z = ( z Shl 8 ) + ( y Mod 10 ) : y \= 10z = ( z Shl 8 ) + ( y Mod 10 ) : y \= 10z = ( z Shl 8 ) + ( y Mod 10 ) : y \= 10z = ( z Shl 8 ) + ( y Mod 10 ) : y \= 10z = ( z Shl 8 ) + ( y Mod 10 ) : y \= 10z = ( z Shl 8 ) + ( y Mod 10 )*p_text = z + ascii_basePrint "output "; text'---------------------------------------------------------If num8 <> text Then    Print " Error detected."    SleepElse    Print " Correct."End IfPrintSleep'---------------------------------------------------------`
albert
Posts: 5419
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

@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: 5419
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

@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,t4do         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: 5419
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

@Richard

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

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

Return to “General”

Who is online

Users browsing this forum: Google [Bot] and 1 guest