Squares

[Richard]

@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]

@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]

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]

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]

@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]

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]

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]

@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]

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]

@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]

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]

@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]

@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]

That works Albert.
on 32 bit
print "real answer =" ; clngint(n1)*clngint(n2) , len( str(n1*n2) )

[albert]

@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