## Squares

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

### Re: Squares

@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

@Richard

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

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

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

@Richard
@Dodicat

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

Code: Select all

`screen 19do            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)sleepend`
Richard
Posts: 3011
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: Squares

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

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

Code: Select all

` screen 19do            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)sleepend `
albert
Posts: 5672
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Squares

@Dodicat

Thanks for fixing the code!!!!!

Code: Select all

` screen 19do           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)sleepend`
dodicat
Posts: 6482
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Squares

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

Code: Select all

` screen 19do            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)sleepend   `
albert
Posts: 5672
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Squares

@Dodicat

Thanks , i converted it to 1e9's

Code: Select all

`screen 19do           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)sleepend   `
dodicat
Posts: 6482
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Squares

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 ulongintprint uvar num= mklongint(u)  'OK for ulongintprint num,len(num)print culngint(cvlongint(num))  'must cast to ulongint for ulongintprintsleeploop until multikey(1) 'esc `
albert
Posts: 5672
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Squares

@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 19do           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)sleepend`
albert
Posts: 5672
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Squares

@Dodicat

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

Code: Select all

`screen 19do           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)sleepend`
dodicat
Posts: 6482
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Squares

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

@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