Squares

General FreeBASIC programming questions.
Richard
Posts: 3011
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

Postby Richard » Dec 15, 2018 2:00

@Albert.
I cannot see how using byte pointers can speed things up. It will be slower by 1/(4x4) = 1/16th as fast as pointers to 32 bit integer multiplies.

The speed limit is determined by the maximum size of the partial product that can be produced. At the moment the widest accurate multiply available in FB is a 32 bit integer multiplication producing a 64 bit result.

The multiplication of 64 bit integers to produce 128 bit integer products is only available in two separate steps on some processors with the XOP multiply instructions. On standard processors with FB it takes 4 multiplies and several additions to do the same.

At most, 9 decimal digits can fit in a 32 bit integer.
1 digit stepping would do 1 partial product per step. Relative speed = 2.0%
2 digit stepping would do 4 partial product per step. Relative speed = 8.2%
3 digit stepping would do 9 partial product per step. Relative speed = 18.3%
4 digit stepping would do 16 partial product per step. Relative speed = 32.6%
5 digit stepping would do 25 partial product per step. Relative speed = 39.0%
6 digit stepping would do 36 partial product per step. Relative speed = 73.5%
7 digit stepping would do 49 partial products per step. Relative speed = 100.0%
8 digit stepping would do 64 partial products per step. Relative speed = 130.6%
9 digit stepping would do 81 partial products per step. Relative speed = 165.3%
albert
Posts: 5672
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Postby albert » Dec 15, 2018 3:45

@Richard

I asked if:
You build a number out of 18 digit pointers.. if you can mul them by single byte pointers??

n1 = 1e18
n2 = 1e18

num1 = *n1
num2 = *n2

Can you then do an asc( right(num1,1 ) ) * asc( right(num2,1) ) ???
Richard
Posts: 3011
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

Postby Richard » Dec 15, 2018 4:06

I do not understand what you mean by an “18 digit pointer”.
Is it pointing to a 64 bit integer that contains a number between 0 and (1e18)-1, or is it a byte pointer into a string of ascii which is the same as a string index?
dodicat
Posts: 6482
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Squares

Postby dodicat » Dec 15, 2018 9:12

Indeed Richard, I used the fb 64 bit compiler optimised -O3 for 22 seconds.
The 32 bit optimised -O3 gets the answer in about one minute.
I checked the results with gmp (only a few seconds), OK.

Now, I daresay the team at gmp would would use optimisations along the way as they keep trying to get speedier.
Of course the whole speed thing comes down to your own box, I mean, if I went up into the attic and dragged out my old Pentium Pro, fired it up and gave Albert's multiplier a run, what would transpire I wonder, bar cobwebs.
Anyway Albert, keeping trying out different Ideas and experimenting with this that and the other is great in my mind, and because you already have provided the fastest fb million digit multiplier so far, you are working from a solid background.
The seven stepper was fast because seven is a magic number, never mind about all those XOP's on the cpu. In fact I don't think that the Pentium Pro has any XOP's at all, so I might as well just leave it in the attic.
albert
Posts: 5672
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Postby albert » Dec 15, 2018 20:23

@Richard
@Dodicat

I'm fumbling around with pointer muls.... , I'm getting bad answers.

Can you guys see , where i'm screwing up??

Code: Select all


screen 19

do
   
        dim as ushort n1 = int(rnd*65536)
        dim as ushort n2 = int(rnd*65536)
       
        if n2 > n1 then swap n1 , n2
       
       
        dim as string *2  num1 = chr(0)+chr(0)
        dim as ushort ptr usp1 = cptr( ushort ptr , strptr(num1) ) : *usp1 = n1
       
        dim as string *2  num2 = chr(0)+chr(0)
        dim as ushort ptr usp2 = cptr( ushort ptr , strptr(num2) ) : *usp2 = n2
       
        dim as ulongint ans = ( ( asc( right(num1,1) ) * asc( right(num2,1) ) ) * 65536 ) + ( asc( left(num1,1) ) * 256 * asc( left(num2,1) ) )
       
        print
        print num1 , asc( left(num1,1) )  , asc( right(num1,1) )
        print num2 , asc( left(num2,1) )  , asc( right(num2,1) )
        print
        print "n1 = " ; n1
        print "   =" ; (asc( right(num1,1) ) * 256) + asc( left(num1,1) ) 
        print
        print "n2 = " ; n2
        print "   =" ; (asc( right(num2,1) ) * 256) + asc( left(num2,1) )
        print
        print "real answer =" ; n1*n2
        print "my answer   = " ; ans
       
        sleep
       
loop until inkey = chr(27)

sleep
end

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

Re: Squares

Postby Richard » Dec 15, 2018 22:01

Albert wrote:Can you guys see , where i'm screwing up??

Yes, it is clear and obvious. You are failing to document your brilliant code, so we cannot possibly know how you are trying to do it.

As it is, your code looks like it comes from a post-modernist phrase generator.

You should describe your plan or algorithm at the start of the source, then document the code as you write it, Then you and others would be able to work out what you need to do to realise your plan.
dodicat
Posts: 6482
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Squares

Postby dodicat » Dec 15, 2018 22:10

looks like you just have to multiply out (no easy shortcuts I can see)

Code: Select all

 


screen 19

do
   
        dim as ushort n1 = int(rnd*65536)
        dim as ushort n2 = int(rnd*65536)
       
        if n2 > n1 then swap n1 , n2
       
       
        dim as string *2  num1 = chr(0)+chr(0)
        dim as ushort ptr usp1 = cptr( ushort ptr , strptr(num1) ) : *usp1 = n1
       
        dim as string *2  num2 = chr(0)+chr(0)
        dim as ushort ptr usp2 = cptr( ushort ptr , strptr(num2) ) : *usp2 = n2
       
     
dim as ulongint ans=asc( right(num1,1) )*256*asc( right(num2,1) )*256 + asc( left(num1,1) )*asc( right(num2,1) )*256 +asc( right(num1,1) )*256*asc( left(num2,1) ) +  asc( left(num1,1) ) * asc( left(num2,1) )
       
        print
        print num1 , asc( left(num1,1) )  , asc( right(num1,1) )
        print num2 , asc( left(num2,1) )  , asc( right(num2,1) )
        print
        print "n1 = " ; n1
        print "   =" ; (asc( right(num1,1) ) * 256) + asc( left(num1,1) ) 
        print
        print "n2 = " ; n2
        print "   =" ; (asc( right(num2,1) ) * 256) + asc( left(num2,1) )
        print
        print "real answer =" ; n1*n2
        print "my answer   = " ; ans
       
        sleep
       
loop until inkey = chr(27)

sleep
end
 
albert
Posts: 5672
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Postby albert » Dec 16, 2018 1:28

@Dodicat

Thanks for fixing the code!!!!!

Code: Select all

 


screen 19

do
   
        dim as ushort n1 = int(rnd*65536)
        dim as ushort n2 = int(rnd*65536)
       
        if n2 > n1 then swap n1 , n2
       
       
        dim as string *2  num1 = chr(0)+chr(0)
        dim as ushort ptr usp1 = cptr( ushort ptr , strptr(num1) ) : *usp1 = n1
       
        dim as string *2  num2 = chr(0)+chr(0)
        dim as ushort ptr usp2 = cptr( ushort ptr , strptr(num2) ) : *usp2 = n2
     
        dim as ulongint ans = 0
                ans+= asc( right(num1,1) ) * asc( right(num2,1) ) * 65536
                ans+= asc(    left(num1,1) ) * asc( right(num2,1) ) * 256
                ans+= asc( right(num1,1) ) * asc(    left(num2,1) ) * 256
                ans+= asc(    left(num1,1) ) * asc(    left(num2,1) )
       
        print
        print num1 , asc( left(num1,1) )  , asc( right(num1,1) )
        print num2 , asc( left(num2,1) )  , asc( right(num2,1) )
        print
        print "n1 = " ; n1
        print "   =" ; (asc( right(num1,1) ) * 256) + asc( left(num1,1) )
        print
        print "n2 = " ; n2
        print "   =" ; (asc( right(num2,1) ) * 256) + asc( left(num2,1) )
        print
        print "real answer =" ; n1*n2
        print "my answer   = " ; ans
       
        sleep
       
loop until inkey = chr(27)

sleep
end

dodicat
Posts: 6482
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Squares

Postby dodicat » Dec 16, 2018 10:41

Hi Albert.
I have only multiplied out the returned two ushorts.
This is a simplified representation of the code.

Code: Select all

 


screen 19

do
   
        dim as ushort n1 = int(rnd*65536)
        dim as ushort n2 = int(rnd*65536)
       
        if n2 > n1 then swap n1 , n2
       
       
        dim as string   num1 = mkshort(n1)
       
       
        dim as string   num2 = mkshort(n2)
     
       
     
dim as ulongint ans=cushort(cvshort(num1))*cushort(cvshort(num2))'asc( right(num1,1) )*256*asc( right(num2,1) )*256 + asc( left(num1,1) )*asc( right(num2,1) )*256 +asc( right(num1,1) )*256*asc( left(num2,1) ) +  asc( left(num1,1) ) * asc( left(num2,1) )
       
        print
        print num1 , asc( left(num1,1) )  , asc( right(num1,1) )
        print num2 , asc( left(num2,1) )  , asc( right(num2,1) )
        print
        print "n1 = " ; n1
        print "   = " ;cushort(cvshort(num1))
        print
        print "n2 = " ; n2
        print "   = " ; cushort(cvshort(num2))
        print
        print "real answer =" ; n1*n2
        print "my answer   = " ; ans
       
        sleep
       
loop until inkey = chr(27)

sleep
end
   
albert
Posts: 5672
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Postby albert » Dec 17, 2018 0:41

@Dodicat

Thanks , i converted it to 1e9's

Code: Select all


screen 19

do
   
        dim as ulongint n1 = int( rnd * ( 1e9 ) )
        dim as ulongint n2 = int( rnd * ( 1e9 ) )
       
        if n2 > n1 then swap n1 , n2
       
        dim as string   num1 = mklongint(n1)
       
        dim as string   num2 = mklongint(n2)
     
dim as ulongint ans = clngint(cvlongint(num1)) * clngint(cvlongint(num2))
               
                'ans=0
                'ans+= asc( right(num1,1) ) * asc( right(num2,1) ) * 65536
                'ans+= asc(    left(num1,1) ) * asc( right(num2,1) ) * 256
                'ans+= asc( right(num1,1) ) * asc(    left(num2,1) ) * 256
                'ans+= asc(    left(num1,1) ) * asc(    left(num2,1) )

        print
        print num1 , asc( mid(num1,1,1) ) ; " " ; asc( mid(num1,2,1) ) ; " " ; asc( mid(num1,3,1) ) ; " " ; asc( mid(num1,4,1) )  ; " " ; asc( mid(num1,5,1) ) ; " " ; asc( mid(num1,6,1) ) ; " " ; asc( mid(num1,7,1) ) ; " " ; asc( mid(num1,8,1) )
        print num2 , asc( mid(num2,1,1) ) ; " " ; asc( mid(num2,2,1) ) ; " " ; asc( mid(num2,3,1) ) ; " " ; asc( mid(num2,4,1) )  ; " " ; asc( mid(num2,5,1) ) ; " " ; asc( mid(num2,6,1) ) ; " " ; asc( mid(num2,7,1) ) ; " " ; asc( mid(num2,8,1) )
        print
        print "n1 = " ; n1
        print "   =" ; clngint(cvlongint(num1))
        print
        print "n2 = " ; n2
        print "  = " ; clngint(cvlongint(num2))
        print
        print "real answer = " ; n1*n2 , len(str(n1*n2))
        print "my answer   = " ; ans    , len(str(ans))
       
        sleep
       
loop until inkey = chr(27)

sleep
end
   
dodicat
Posts: 6482
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Squares

Postby dodicat » Dec 17, 2018 2:05

For your information Albert
mklongint handles ulongint.
and
culngint(cvlongint(num1))
handles ulongint also
The string is 8 characters long

Code: Select all

 

do
   
dim as ulongint u=9223372036854775807+rnd*9223372036854775805 'a definite ulongint
print u
var num= mklongint(u)  'OK for ulongint
print num,len(num)
print culngint(cvlongint(num))  'must cast to ulongint for ulongint
print
sleep
loop until multikey(1) 'esc

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

Re: Squares

Postby albert » Dec 17, 2018 2:20

@Dodicat

Here's using n1 , n2 = int( rnd *( 2 ^ 24) ) , long = ( 4 bytes)

How should i handle the ans+= ??

I think i'm screwing up somewhere ???

Code: Select all


screen 19

do
   
        dim as long n1 = int(rnd*(2^24) )
        dim as long n2 = int(rnd*(2^24) )
       
        if n2 > n1 then swap n1 , n2
       
        dim as string *4  num1 = string( 4 , chr(0) )
        dim as long ptr usp1 = cptr( long ptr , strptr(num1) ) : *usp1 = n1
       
        dim as string *4  num2 = string( 4 , chr(0) )
        dim as long ptr usp2 = cptr( long ptr , strptr(num2) ) : *usp2 = n2
     
        dim as ulongint ans = 0
               
                ans+= asc( mid(num1,4,1) ) * asc( mid(num2,4,1) ) * (2^24)
                ans+= asc( mid(num1,4,1) ) * asc( mid(num2,3,1) ) * (2^16)
                ans+= asc( mid(num1,4,1) ) * asc( mid(num2,2,1) ) * (2^8)
                ans+= asc( mid(num1,4,1) ) * asc( mid(num2,1,1) )
               
                ans+= asc( mid(num1,3,1) ) * asc( mid(num2,4,1) ) * (2^24)
                ans+= asc( mid(num1,3,1) ) * asc( mid(num2,3,1) ) * (2^16)
                ans+= asc( mid(num1,3,1) ) * asc( mid(num2,2,1) ) * (2^8)
                ans+= asc( mid(num1,3,1) ) * asc( mid(num2,1,1) )
               
                ans+= asc( mid(num1,2,1) ) * asc( mid(num2,4,1) ) * (2^24)
                ans+= asc( mid(num1,2,1) ) * asc( mid(num2,3,1) ) * (2^16)
                ans+= asc( mid(num1,2,1) ) * asc( mid(num2,2,1) ) * (2^8)
                ans+= asc( mid(num1,2,1) ) * asc( mid(num2,1,1) )
               
                ans+= asc( mid(num1,1,1) ) * asc( mid(num2,4,1) ) * (2^24)
                ans+= asc( mid(num1,1,1) ) * asc( mid(num2,3,1) ) * (2^16)
                ans+= asc( mid(num1,1,1) ) * asc( mid(num2,2,1) ) * (2^8)
                ans+= asc( mid(num1,1,1) ) * asc( mid(num2,1,1) )
               
        print
        print num1 , asc( mid(num1,4,1) )  , asc( mid(num1,3,1) ) , asc( mid(num1,2,1) ) , asc( mid(num1,1,1) )
        print num2 , asc( mid(num2,4,1) )  , asc( mid(num2,3,1) ) , asc( mid(num2,2,1) ) , asc( mid(num2,1,1) )
        print
        print "n1 = " ; n1
        print "   = " ; (asc( mid(num1,4,1) ) *(2^24)) + (asc( mid(num1,3,1) )*(2^16)) + (asc( mid(num1,2,1) )*(2^8)) + asc( mid(num1,1,1) )
        print
        print "n2 = " ; n2
        print "   = " ; (asc( mid(num2,4,1) ) *(2^24)) + (asc( mid(num2,3,1) )*(2^16)) + (asc( mid(num2,2,1) )*(2^8)) + asc( mid(num2,1,1) )
        print
        print "real answer =" ; n1*n2 , len( str(n1*n2) )
        print "my answer   = " ; ans
       
        sleep
       
loop until inkey = chr(27)

sleep
end

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

Re: Squares

Postby albert » Dec 17, 2018 2:49

@Dodicat

I got it figured out !!!!!!!!!!!!!!!!!!!!!!!!!! (!!~~YAHOO~~!!)

Code: Select all


screen 19

do
   
        dim as long n1 = int(rnd*1e9)
        dim as long n2 = int(rnd*1e9)
       
        if n2 > n1 then swap n1 , n2
       
        dim as string *4  num1 = string( 4 , chr(0) )
        dim as long ptr usp1 = cptr( long ptr , strptr(num1) ) : *usp1 = n1
       
        dim as string *4  num2 = string( 4 , chr(0) )
        dim as long ptr usp2 = cptr( long ptr , strptr(num2) ) : *usp2 = n2
     
        dim as ulongint ans = 0
               
                ans+= asc( mid(num1,4,1) ) * asc( mid(num2,4,1) ) * (2^24)
                ans+= asc( mid(num1,4,1) ) * asc( mid(num2,3,1) ) * (2^16)
                ans+= asc( mid(num1,4,1) ) * asc( mid(num2,2,1) ) * (2^8)
                ans+= asc( mid(num1,4,1) ) * asc( mid(num2,1,1) )
               
                ans * = 256
               
                ans+= asc( mid(num1,3,1) ) * asc( mid(num2,4,1) ) * (2^24)
                ans+= asc( mid(num1,3,1) ) * asc( mid(num2,3,1) ) * (2^16)
                ans+= asc( mid(num1,3,1) ) * asc( mid(num2,2,1) ) * (2^8)
                ans+= asc( mid(num1,3,1) ) * asc( mid(num2,1,1) )
               
                ans * = 256
               
                ans+= asc( mid(num1,2,1) ) * asc( mid(num2,4,1) ) * (2^24)
                ans+= asc( mid(num1,2,1) ) * asc( mid(num2,3,1) ) * (2^16)
                ans+= asc( mid(num1,2,1) ) * asc( mid(num2,2,1) ) * (2^8)
                ans+= asc( mid(num1,2,1) ) * asc( mid(num2,1,1) )
               
                ans * = 256
               
                ans+= asc( mid(num1,1,1) ) * asc( mid(num2,4,1) ) * (2^24)
                ans+= asc( mid(num1,1,1) ) * asc( mid(num2,3,1) ) * (2^16)
                ans+= asc( mid(num1,1,1) ) * asc( mid(num2,2,1) ) * (2^8)
                ans+= asc( mid(num1,1,1) ) * asc( mid(num2,1,1) )
               
        print
        print num1 , asc( mid(num1,4,1) )  , asc( mid(num1,3,1) ) , asc( mid(num1,2,1) ) , asc( mid(num1,1,1) )
        print num2 , asc( mid(num2,4,1) )  , asc( mid(num2,3,1) ) , asc( mid(num2,2,1) ) , asc( mid(num2,1,1) )
        print
        print "n1 = " ; n1
        print "   = " ; (asc( mid(num1,4,1) ) *(2^24)) + (asc( mid(num1,3,1) )*(2^16)) + (asc( mid(num1,2,1) )*(2^8)) + asc( mid(num1,1,1) )
        print
        print "n2 = " ; n2
        print "   = " ; (asc( mid(num2,4,1) ) *(2^24)) + (asc( mid(num2,3,1) )*(2^16)) + (asc( mid(num2,2,1) )*(2^8)) + asc( mid(num2,1,1) )
        print
        print "real answer =" ; n1*n2 , len( str(n1*n2) )
        print "my answer   = " ; ans   , len( str(ans) )
       
        if n1 * n2 <. ans then sleep
       
        if inkey = " " then sleep
       
loop until inkey = chr(27)

sleep
end

dodicat
Posts: 6482
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Squares

Postby dodicat » Dec 17, 2018 3:16

That works Albert.
on 32 bit
print "real answer =" ; clngint(n1)*clngint(n2) , len( str(n1*n2) )
albert
Posts: 5672
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Postby albert » Dec 17, 2018 3:31

@Dodicat

I'm happy , i fumbled my way to the correct answer....

Got it Werkin like a Gerken!!!!

Now to do strings of 1e9's

Return to “General”

Who is online

Users browsing this forum: No registered users and 2 guests