## Squares

General FreeBASIC programming questions.
dodicat
Posts: 4633
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Squares

Hi srvaldez
If Albert converts his method to pointers it'll probably optimise itself out much further.
Remember, he achieved the million X million digits multiply in well under one minute a while back.
albert
Posts: 4082
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Squares

@Dodicat

This way is about twice as fast as your last posted code..

Code: Select all

`DECLARE FUNCTION multiplier_7(byref num1 as string, byref num2 as string) as stringDECLARE Function minus(NUM1 As String,NUM2 As String) As StringDeclare FUNCTION   SET_STR1( byref n1 as string , byref n2 as string ) as stringDeclare Function       plus( NUMber1 As String  ,  NUMber2 As String ) As Stringscreen 19do         dim as string num1    dim as string num2    for a as longint = 1 to 100 step 1        num1+=str(int(rnd*10))    next    for a as longint = 1 to 100 step 1        num2+=str(int(rnd*10))    next    if len(num2) < len(num1)  then swap num1 , num2            print    print num1    print num2        dim as double t1 , t2 , t3 , t4        t1 = timer        dim as string short_mul(0 to 9)    dim as longint length = 0    for a as byte = 9 to 0 step -1        short_mul(a) = Set_Str1( num1 , str(a) )       length = len(short_mul(9))       short_mul(a) = string( len(short_mul(9)) - len(short_mul(a)) ,"0" ) + short_mul(a)   next       dim as string answer = ""    dim as longint value = 0     dim as ubyte vals = 0    dim as longint hold = 0    dim as longint locat = 0    dim as string carry = ""    dim as longint high1 = len(num2)-1    dim as longint high2 = len(short_mul(0))-1    do        carry=""        for a as longint = hold to 0 step -1            if high1 - locat >=0 and high1 - locat <= high1 and a >= 0 and a <= high2 then                     'vals = val( mid( num2 , len(num2) - locat , 1 ) )                    vals = num2[ high1 - locat ] - 48                    'value+= val( mid( short_mul( vals ) , len( short_mul(0) ) - a  , 1 ) )                     value+= short_mul( vals )[ high2 - a ] -48            end if            locat+= 1        next        locat=0        hold+= 1        dim as string check = right( string( 16,"0") + str(value) , 16)        dim as string rght = right( check , 1 )        carry = left( check , 15 )        value = valulng(carry)        answer= rght + answer    loop until len(answer) = len(num1) + len(num2)        answer = ltrim(answer,"0")        t2 = timer        t3 = timer        dim as string real_answer = multiplier_7( num1 , num2 )        real_answer = rtrim( real_answer,".")    t4 = timer            dim as string difference = minus( answer , real_answer )        print answer    print real_answer    print "Difference = " ; difference    print "Time = " ; t2 - t1    print "Time = " ; t4 - t3            sleep    loop until inkey=chr(27)sleepend'==============================================================================='===============================================================================FUNCTION SET_STR1( byref n1 as string , byref n2 as string ) as string        dim as string s1 ="0"    dim as ubyte iteration = val(left(n2,1))        'basically multipling ( n1 * leftmost digit of n2)    'but using addition instead of multiply        for a as ubyte = 1 to  iteration        if iteration mod 2 = 0 then            s1 = plus(s1,n1)        else            s1 = plus(s1,n1)        end if    next        return s1    end function'==============================================================================='==============================================================================='Dodicats plus & Minus functions'==============================================================================='===============================================================================    Function plus(_num1 As String,_num2 As String) As String        Dim  ADDQmod(0 To 19) As Ubyte        Dim  ADDbool(0 To 19) As Ubyte        For z As Integer=0 To 19            ADDQmod(z)=(z Mod 10+48)            ADDbool(z)=(-(10<=z))        Next z        Var _flag=0,n_=0        Dim As Ubyte addup=Any,addcarry=Any        #macro finish()        answer=Ltrim(answer,"0")        If _flag=1 Then Swap _num2,_num1        Return answer        #endmacro        If Len(_num2)>Len(_num1) Then             Swap _num2,_num1            _flag=1        End If        Var diff=Len(_num1)-Len(_num2)        Var answer="0"+_num1        addcarry=0        For n_=Len(_num1)-1 To diff Step -1             addup=_num2[n_-diff]+_num1[n_]-96            answer[n_+1]=ADDQmod(addup+addcarry)            addcarry=ADDbool(addup+addcarry)        Next n_         If addcarry=0 Then             finish()        End If        If n_=-1 Then             answer[0]=addcarry+48            finish()            Endif            For n_=n_ To 0 Step -1                 addup=_num1[n_]-48                answer[n_+1]=ADDQmod(addup+addcarry)                addcarry=ADDbool(addup+addcarry)                If addcarry=0 Then Exit For            Next n_            answer[0]=addcarry+48            finish()        End Function'==============================================================================='===============================================================================Function minus(NUM1 As String,NUM2 As String) As String     'Dim As String copyfirstnum=mul_num_1,copysecondnum=mul_num_2    Dim As Byte swapflag                Dim As Long lenf,lens    Dim sign As String * 1    'Dim As String part1,part2    Dim bigger As Byte     'set up tables    Dim As Ubyte Qmod(0 To 19)    Dim bool(0 To 19) As Ubyte    For z As Integer=0 To 19        Qmod(z)=cubyte(z Mod 10+48)        bool(z)=cubyte(-(10>z))    Next z    lenf=Len(NUM1)    lens=Len(NUM2)    #macro compare(numbers)        If Lens>lenf Then bigger= -1:Goto fin        If Lens<lenf Then bigger =0:Goto fin        If NUM2>NUM1 Then             bigger=-1        Else            bigger= 0        End If        fin:    #endmacro    compare(numbers)    If bigger Then         sign="-"        Swap NUM2,NUM1        Swap lens,lenf        swapflag=1    Endif    'lenf=Len(NUM1)    'lens=Len(NUM2)    Dim diff As Long=lenf-lens-Sgn(lenf-lens)    Dim As String one,two,three    three=NUM1    two=String(lenf-lens,"0")+NUM2    one=NUM1    Dim As Long n2    Dim As Ubyte takeaway,subtractcarry    Dim As Ubyte ten=10    'Dim z As Long    subtractcarry=0    Do         For n2=lenf-1 To diff Step -1            takeaway= one[n2]-two[n2]+ten-subtractcarry           three[n2]=Qmod(takeaway)            subtractcarry=bool(takeaway)        Next n2         If subtractcarry=0 Then Exit Do        If n2=-1 Then Exit Do        For n2=n2 To 0 Step -1             takeaway= one[n2]-two[n2]+ten-subtractcarry            three[n2]=Qmod(takeaway)            subtractcarry=bool(takeaway)            Next n2        Exit Do    Loop        three=Ltrim(three,"0")    If three="" Then Return "0"    If swapflag=1 Then Swap NUM1,NUM2       Return sign+three    End Function'==============================================================================='===============================================================================function multiplier_7(byref num1 as string, byref num2 as string) as string        dim as string number1,number2    dim as string answer,outtext        dim as string int1,frac1,int2,frac2    dim as ulongint dec,dec1,len1,len2    dim as string str1    dim as string sign1,sign2,outsign        number1 = num1    number2 = num2        sign1 = left(number1,1)    if sign1 = "+" or sign1 = "-" then number1 = mid(number1,2) else sign1 = ""        sign2 = left(number2,1)    if sign2 = "+" or sign2 = "-" then number2 = mid(number2,2) else sign2 = ""        if (sign1 = sign2) then outsign = ""    if (sign1 <> sign2) then outsign = "-"        dec = instr(1,number1,".")    if dec > 0 then         int1 = left(number1,dec-1)        frac1 = mid(number1,dec+1)    else        int1 = number1        frac1 = ""    end if        dec = instr(1,number2,".")    if dec > 0 then         int2 = left(number2,dec-1)        frac2 = mid(number2,dec+1)    else        int2 = number2        frac2 = ""    end if    dec = len(frac1)+len(frac2)    number1 = int1+frac1    number2 = int2+frac2    'swap numbers so that bigger number is number1 and smaller is number2    if len(number2) > len(number1) then swap number1,number2    if len(number1) = len(number2) then         if val(left(number2,1)) > val(left(number1,1)) then swap number1,number2    end if    'make numbers equal multiple of 7 bytes    do        str1 = str(len(number1)/7)        dec1 = instr(1,str1,".")        if dec1 <> 0 then number1 = "0" + number1    loop until dec1 = 0    do        str1 = str(len(number2)/7)        dec1 = instr(1,str1,".")        if dec1 <> 0 then number2 = "0" + number2    loop until dec1 = 0        'convert the numeric strings to use pointers    'convert number1    dim as string n1 = string(len(number1)*8,chr(0))    dim as ulongint ptr ulp1     ulp1 = cptr(ulongint ptr,strptr(n1))    dim as longint val1    dim as longint len_1 = 0    dim as uinteger a    for a = 0 to len(number1)-1 step 7        val1 = (number1[a+0]-48)*1000000ull        val1+= (number1[a+1]-48)*100000ull        val1+= (number1[a+2]-48)*10000ull        val1+= (number1[a+3]-48)*1000ull        val1+= (number1[a+4]-48)*100ull        val1+= (number1[a+5]-48)*10ull        val1+= (number1[a+6]-48)*1ull        *ulp1 = val1        ulp1+=1        len_1+=8    next    number1 = left(n1,len_1)    n1=""        'convert the numeric strings to use pointers    'convert number2    dim as string n2 = string(len(number2)*8,chr(0))    dim as ulongint ptr ulp2    ulp2 = cptr(ulongint ptr,strptr(n2))    dim as longint val2    dim as longint len_2 = 0    for a = 0 to len(number2)-1 step 7        val2 = (number2[a+0]-48)*1000000ull        val2+= (number2[a+1]-48)*100000ull        val2+= (number2[a+2]-48)*10000ull        val2+= (number2[a+3]-48)*1000ull        val2+= (number2[a+4]-48)*100ull        val2+= (number2[a+5]-48)*10ull        val2+= (number2[a+6]-48)*1ull        *ulp2 = val2        ulp2+=1        len_2+=8    next    number2 = left(n2,len_2)    n2=""        'create accumulator    answer = string( len(number1) + len(number2) + 8 , chr(0) )     'dimension vars for the mul    dim as longint ptr start1,stop1,start2,stop2 'use longint because the pointers go negative    dim as longint ptr chk_1 , chk_2    dim as longint ptr inc1,inc2    dim as longint ptr outplace    dim as ulongint carry    dim as ulongint total    dim as ulongint blocknumber1 = len(number1)/8    dim as ulongint blocknumber2 = len(number2)/8    dim as ulongint outblocks = len(answer)/8        'set initial accumulator place    outplace = cptr(longint ptr , strptr(answer)) + (outblocks - 1)    'set initial pointers into number1     start1 = cptr(longint ptr , strptr(number1))+(blocknumber1-1)    stop1 =  cptr(longint ptr , strptr(number1))+(blocknumber1-1)    'set initial pointers into number2    start2 = cptr(longint ptr , strptr(number2))+(blocknumber2-1)    stop2 =  cptr(longint ptr , strptr(number2))+(blocknumber2-1)    'set comparison to beg of numbers    chk_1 = cptr( longint ptr , strptr(number1))    chk_2 = cptr( longint ptr , strptr(number2))        'zero the carry    carry = 0        'begin looping thru strings multiplying    do        'set total to zero        total = 0        'we are going to be incrementing thru number2 while decrementing thru number1        'working in opposite directions from start1 to stop1 and start2 to stop2        'inc1 works from right to left in the top number1 string        'inc2 works from start2 to stop 2, in the bottom number2 string, decrementing each loop.        inc1 = start1        inc2 = start2        do            total += *inc1 * *inc2            inc1-= 1            inc2+= 1        loop until inc2 = stop2+1            total = total + carry        carry = total \ 1e7        *outplace = total mod 1e7        '*outplace = imod(total , 1e7)                outplace -= 1                'each loop we need to decrement stop1        'if stop1 goes negative we reset it to zero and decrement stop2        stop1 -= 1        if stop1 < chk_1 then            stop1 += 1            stop2 -=1            if stop2 < chk_2 then stop2+= 1        end if        'each loop we decrement start2 to the left        start2 -= 1        'if start2 goes negative we reset it to zero and decrement start1        'start1 is the rightmost digit of number1 we need to multiply        if start2 < chk_2 then            start2 += 1            start1 -= 1            if start1 < chk_1 then start1+=1        end if        loop until outplace = cptr(ulongint ptr,strptr(answer))+1        'put in the carry at the end    if carry > 0  then *outplace = carry else *outplace = 0        'convert answer back to ascii    for a as ulongint = 1 to outblocks-1 step 1        val1 = *outplace        outplace +=1        outtext = outtext + right("0000000" + str(val1),7)    next        'put in the decimal point    outtext = left(outtext,len(outtext)-dec) + "." +  mid(outtext,(len(outtext)-dec)+1)    'trim leading zeros    outtext = trim(outtext,"0") 'if multiplying by 1, we have a zero in front.    outtext = outsign + outtext    return outtextend function'==============================================================================='===============================================================================`

I got to get it doing steps of 10 or more digits, to make it as fast as my "multiplier_7"
albert
Posts: 4082
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Squares

@Dodicat

I got it converted to ubyte pointers.

At 10 x 10 digits its twice as fast as my multiplier_7.

Now i got to convert it to step more than a ubyte at a time . maybe step by 7's

Code: Select all

`DECLARE FUNCTION multiplier_7(byref num1 as string, byref num2 as string) as stringDECLARE Function minus(NUM1 As String,NUM2 As String) As StringDeclare FUNCTION   SET_STR1( byref n1 as string , byref n2 as string ) as string'Declare Function       plus( NUMber1 As String  ,  NUMber2 As String ) As Stringscreen 19do         dim as string num1    dim as string num2    for a as longint = 1 to 10 step 1        num1+=str(int(rnd*10))    next    for a as longint = 1 to 10 step 1        num2+=str(int(rnd*10))    next    if len(num2) < len(num1)  then swap num1 , num2            print    print num1    print num2        dim as double t1 , t2 , t3 , t4        t1 = timer        dim as string answer = ""    dim as longint value = 0     dim as ubyte vals = 0    dim as longint hold = 0    dim as longint locat = 0    dim as longint carry = 0    dim as longint high1 = len(num1)-1    dim as longint high2 = len(num2)-1    dim as ubyte ptr num1_ptr = cptr( ubyte ptr , strptr(num1) ) + high1    dim as ubyte ptr num2_ptr = cptr( ubyte ptr , strptr(num2) ) + high2    do        for a as longint = hold to 0 step -1            if high1 - locat >= 0 and a <= high1 then                 'vals = num2[ high1 - a ] - 48                vals = *(num2_ptr-a) - 48                'value+= (num1[ high2 - locat ] -48) * vals                value+= (*(num1_ptr-locat)-48) * vals             end if            locat+= 1        next        locat = 0        hold+= 1        carry = value \ 1e1        answer = str( value mod 1e1) + answer        value = carry    loop until hold>= len(num1) + len(num2)        answer = ltrim(answer,"0")        t2 = timer        t3 = timer        dim as string real_answer = multiplier_7( num1 , num2 )        real_answer = rtrim( real_answer,".")    t4 = timer            dim as string difference = minus( answer , real_answer )        print answer    print real_answer    print "Difference = " ; difference    print "Time = " ; t2 - t1    print "Time = " ; t4 - t3            sleep    loop until inkey=chr(27)sleepend'==============================================================================='===============================================================================FUNCTION SET_STR1( byref n1 as string , byref n2 as string ) as string        dim as string s1 ="0"    dim as ubyte iteration = val(left(n2,1))        'basically multipling ( n1 * leftmost digit of n2)    'but using addition instead of multiply        for a as ubyte = 1 to  iteration        if iteration mod 2 = 0 then            s1 = plus(s1,n1)        else            s1 = plus(s1,n1)        end if    next        return s1    end function'==============================================================================='==============================================================================='Dodicats plus & Minus functions'==============================================================================='===============================================================================    Function plus(_num1 As String,_num2 As String) As String        Dim  ADDQmod(0 To 19) As Ubyte        Dim  ADDbool(0 To 19) As Ubyte        For z As Integer=0 To 19            ADDQmod(z)=(z Mod 10+48)            ADDbool(z)=(-(10<=z))        Next z        Var _flag=0,n_=0        Dim As Ubyte addup=Any,addcarry=Any        #macro finish()        answer=Ltrim(answer,"0")        If _flag=1 Then Swap _num2,_num1        Return answer        #endmacro        If Len(_num2)>Len(_num1) Then             Swap _num2,_num1            _flag=1        End If        Var diff=Len(_num1)-Len(_num2)        Var answer="0"+_num1        addcarry=0        For n_=Len(_num1)-1 To diff Step -1             addup=_num2[n_-diff]+_num1[n_]-96            answer[n_+1]=ADDQmod(addup+addcarry)            addcarry=ADDbool(addup+addcarry)        Next n_         If addcarry=0 Then             finish()        End If        If n_=-1 Then             answer[0]=addcarry+48            finish()            Endif            For n_=n_ To 0 Step -1                 addup=_num1[n_]-48                answer[n_+1]=ADDQmod(addup+addcarry)                addcarry=ADDbool(addup+addcarry)                If addcarry=0 Then Exit For            Next n_            answer[0]=addcarry+48            finish()        End Function'==============================================================================='===============================================================================Function minus(NUM1 As String,NUM2 As String) As String     'Dim As String copyfirstnum=mul_num_1,copysecondnum=mul_num_2    Dim As Byte swapflag                Dim As Long lenf,lens    Dim sign As String * 1    'Dim As String part1,part2    Dim bigger As Byte     'set up tables    Dim As Ubyte Qmod(0 To 19)    Dim bool(0 To 19) As Ubyte    For z As Integer=0 To 19        Qmod(z)=cubyte(z Mod 10+48)        bool(z)=cubyte(-(10>z))    Next z    lenf=Len(NUM1)    lens=Len(NUM2)    #macro compare(numbers)        If Lens>lenf Then bigger= -1:Goto fin        If Lens<lenf Then bigger =0:Goto fin        If NUM2>NUM1 Then             bigger=-1        Else            bigger= 0        End If        fin:    #endmacro    compare(numbers)    If bigger Then         sign="-"        Swap NUM2,NUM1        Swap lens,lenf        swapflag=1    Endif    'lenf=Len(NUM1)    'lens=Len(NUM2)    Dim diff As Long=lenf-lens-Sgn(lenf-lens)    Dim As String one,two,three    three=NUM1    two=String(lenf-lens,"0")+NUM2    one=NUM1    Dim As Long n2    Dim As Ubyte takeaway,subtractcarry    Dim As Ubyte ten=10    'Dim z As Long    subtractcarry=0    Do         For n2=lenf-1 To diff Step -1            takeaway= one[n2]-two[n2]+ten-subtractcarry           three[n2]=Qmod(takeaway)            subtractcarry=bool(takeaway)        Next n2         If subtractcarry=0 Then Exit Do        If n2=-1 Then Exit Do        For n2=n2 To 0 Step -1             takeaway= one[n2]-two[n2]+ten-subtractcarry            three[n2]=Qmod(takeaway)            subtractcarry=bool(takeaway)            Next n2        Exit Do    Loop        three=Ltrim(three,"0")    If three="" Then Return "0"    If swapflag=1 Then Swap NUM1,NUM2       Return sign+three    End Function'==============================================================================='===============================================================================function multiplier_7(byref num1 as string, byref num2 as string) as string        dim as string number1,number2    dim as string answer,outtext        dim as string int1,frac1,int2,frac2    dim as ulongint dec,dec1,len1,len2    dim as string str1    dim as string sign1,sign2,outsign        number1 = num1    number2 = num2        sign1 = left(number1,1)    if sign1 = "+" or sign1 = "-" then number1 = mid(number1,2) else sign1 = ""        sign2 = left(number2,1)    if sign2 = "+" or sign2 = "-" then number2 = mid(number2,2) else sign2 = ""        if (sign1 = sign2) then outsign = ""    if (sign1 <> sign2) then outsign = "-"        dec = instr(1,number1,".")    if dec > 0 then         int1 = left(number1,dec-1)        frac1 = mid(number1,dec+1)    else        int1 = number1        frac1 = ""    end if        dec = instr(1,number2,".")    if dec > 0 then         int2 = left(number2,dec-1)        frac2 = mid(number2,dec+1)    else        int2 = number2        frac2 = ""    end if    dec = len(frac1)+len(frac2)    number1 = int1+frac1    number2 = int2+frac2    'swap numbers so that bigger number is number1 and smaller is number2    if len(number2) > len(number1) then swap number1,number2    if len(number1) = len(number2) then         if val(left(number2,1)) > val(left(number1,1)) then swap number1,number2    end if    'make numbers equal multiple of 7 bytes    do        str1 = str(len(number1)/7)        dec1 = instr(1,str1,".")        if dec1 <> 0 then number1 = "0" + number1    loop until dec1 = 0    do        str1 = str(len(number2)/7)        dec1 = instr(1,str1,".")        if dec1 <> 0 then number2 = "0" + number2    loop until dec1 = 0        'convert the numeric strings to use pointers    'convert number1    dim as string n1 = string(len(number1)*8,chr(0))    dim as ulongint ptr ulp1     ulp1 = cptr(ulongint ptr,strptr(n1))    dim as longint val1    dim as longint len_1 = 0    dim as uinteger a    for a = 0 to len(number1)-1 step 7        val1 = (number1[a+0]-48)*1000000ull        val1+= (number1[a+1]-48)*100000ull        val1+= (number1[a+2]-48)*10000ull        val1+= (number1[a+3]-48)*1000ull        val1+= (number1[a+4]-48)*100ull        val1+= (number1[a+5]-48)*10ull        val1+= (number1[a+6]-48)*1ull        *ulp1 = val1        ulp1+=1        len_1+=8    next    number1 = left(n1,len_1)    n1=""        'convert the numeric strings to use pointers    'convert number2    dim as string n2 = string(len(number2)*8,chr(0))    dim as ulongint ptr ulp2    ulp2 = cptr(ulongint ptr,strptr(n2))    dim as longint val2    dim as longint len_2 = 0    for a = 0 to len(number2)-1 step 7        val2 = (number2[a+0]-48)*1000000ull        val2+= (number2[a+1]-48)*100000ull        val2+= (number2[a+2]-48)*10000ull        val2+= (number2[a+3]-48)*1000ull        val2+= (number2[a+4]-48)*100ull        val2+= (number2[a+5]-48)*10ull        val2+= (number2[a+6]-48)*1ull        *ulp2 = val2        ulp2+=1        len_2+=8    next    number2 = left(n2,len_2)    n2=""        'create accumulator    answer = string( len(number1) + len(number2) + 8 , chr(0) )     'dimension vars for the mul    dim as longint ptr start1,stop1,start2,stop2 'use longint because the pointers go negative    dim as longint ptr chk_1 , chk_2    dim as longint ptr inc1,inc2    dim as longint ptr outplace    dim as ulongint carry    dim as ulongint total    dim as ulongint blocknumber1 = len(number1)/8    dim as ulongint blocknumber2 = len(number2)/8    dim as ulongint outblocks = len(answer)/8        'set initial accumulator place    outplace = cptr(longint ptr , strptr(answer)) + (outblocks - 1)    'set initial pointers into number1     start1 = cptr(longint ptr , strptr(number1))+(blocknumber1-1)    stop1 =  cptr(longint ptr , strptr(number1))+(blocknumber1-1)    'set initial pointers into number2    start2 = cptr(longint ptr , strptr(number2))+(blocknumber2-1)    stop2 =  cptr(longint ptr , strptr(number2))+(blocknumber2-1)    'set comparison to beg of numbers    chk_1 = cptr( longint ptr , strptr(number1))    chk_2 = cptr( longint ptr , strptr(number2))        'zero the carry    carry = 0        'begin looping thru strings multiplying    do        'set total to zero        total = 0        'we are going to be incrementing thru number2 while decrementing thru number1        'working in opposite directions from start1 to stop1 and start2 to stop2        'inc1 works from right to left in the top number1 string        'inc2 works from start2 to stop 2, in the bottom number2 string, decrementing each loop.        inc1 = start1        inc2 = start2        do            total += *inc1 * *inc2            inc1-= 1            inc2+= 1        loop until inc2 = stop2+1            total = total + carry        carry = total \ 1e7        *outplace = total mod 1e7        '*outplace = imod(total , 1e7)                outplace -= 1                'each loop we need to decrement stop1        'if stop1 goes negative we reset it to zero and decrement stop2        stop1 -= 1        if stop1 < chk_1 then            stop1 += 1            stop2 -=1            if stop2 < chk_2 then stop2+= 1        end if        'each loop we decrement start2 to the left        start2 -= 1        'if start2 goes negative we reset it to zero and decrement start1        'start1 is the rightmost digit of number1 we need to multiply        if start2 < chk_2 then            start2 += 1            start1 -= 1            if start1 < chk_1 then start1+=1        end if        loop until outplace = cptr(ulongint ptr,strptr(answer))+1        'put in the carry at the end    if carry > 0  then *outplace = carry else *outplace = 0        'convert answer back to ascii    for a as ulongint = 1 to outblocks-1 step 1        val1 = *outplace        outplace +=1        outtext = outtext + right("0000000" + str(val1),7)    next        'put in the decimal point    outtext = left(outtext,len(outtext)-dec) + "." +  mid(outtext,(len(outtext)-dec)+1)    'trim leading zeros    outtext = trim(outtext,"0") 'if multiplying by 1, we have a zero in front.    outtext = outsign + outtext    return outtextend function'==============================================================================='===============================================================================`
albert
Posts: 4082
Joined: Sep 28, 2006 2:41
Location: California, USA

@Dodicat
@Richard

I got it converted to ulongint pointers..
At 10,000 x 10,000 digits its 4 times slower than my multiplier_7.

@Richard , could you convert it to 64 bit assembly language??

Code: Select all

`Declare Function add_mult( num1 as string , num2 as string ) as string DECLARE FUNCTION multiplier_7(byref num1 as string, byref num2 as string) as stringDECLARE Function minus(NUM1 As String,NUM2 As String) As StringDeclare Function       plus( NUMber1 As String  ,  NUMber2 As String ) As Stringscreen 19do         dim as string num1    dim as string num2    for a as longint = 1 to 10000 step 1        num1+=str(int(rnd*10))    next    for a as longint = 1 to 10000 step 1        num2+=str(int(rnd*10))    next    if len(num2) < len(num1)  then swap num1 , num2            print    print num1    print num2        dim as double t1 , t2 , t3 , t4        t1 = timer        dim as string answer = add_mult( num1,num2 )    t2 = timer        t3 = timer        dim as string real_answer = multiplier_7( num1 , num2 )        real_answer = rtrim( real_answer,".")    t4 = timer            dim as string difference = minus( answer , real_answer )        print answer    print real_answer    print "Difference = " ; difference    print "Time = " ; t2 - t1    print "Time = " ; t4 - t3            sleep    loop until inkey=chr(27)sleepend'==============================================================================='==============================================================================='==============================================================================='===============================================================================function add_mult( num1 as string , num2 as string ) as string         dim as string number1 = num1    dim as string number2 = num2        'make numbers equal multiple of 7 bytes    dim as string str1    dim as longint dec1    do        str1 = str(len(number1)/7)        dec1 = instr(1,str1,".")        if dec1 <> 0 then number1 = "0" + number1    loop until dec1 = 0    do        str1 = str(len(number2)/7)        dec1 = instr(1,str1,".")        if dec1 <> 0 then number2 = "0" + number2    loop until dec1 = 0            'convert the numeric strings to use pointers    'convert number1    dim as string n1 = string(len(number1)*8,chr(0))    dim as ulongint ptr ulp1 = cptr(ulongint ptr,strptr(n1))    dim as longint valu1    dim as longint len_1 = 0    for a as longint = 0 to len(number1)-1 step 7        valu1  = (number1[a+0]-48)*1e6        valu1+= (number1[a+1]-48)*1e5        valu1+= (number1[a+2]-48)*1e4        valu1+= (number1[a+3]-48)*1e3        valu1+= (number1[a+4]-48)*1e2        valu1+= (number1[a+5]-48)*1e1        valu1+= (number1[a+6]-48)*1        *ulp1 = valu1        ulp1+=1        len_1+=8    next    number1 = left(n1,len_1)    n1=""        'convert the numeric strings to use pointers    'convert number2    dim as string n2 = string(len(number2)*8,chr(0))    dim as ulongint ptr ulp2 = cptr(ulongint ptr,strptr(n2))    dim as longint valu2    dim as longint len_2 = 0    for a as longint = 0 to len(number2)-1 step 7        valu2 =  (number2[a+0]-48)*1e6        valu2+= (number2[a+1]-48)*1e5        valu2+= (number2[a+2]-48)*1e4        valu2+= (number2[a+3]-48)*1e3        valu2+= (number2[a+4]-48)*1e2        valu2+= (number2[a+5]-48)*1e1        valu2+= (number2[a+6]-48)*1        *ulp2 = valu2        ulp2+=1        len_2+=8    next    number2 = left(n2,len_2)    n2=""        'create accumulator    dim as string answer = string( len(number1) + len(number2) , chr(0) )     dim as ulongint outblocks = len(answer) / 8    dim as ulongint ptr outplace = cptr(ulongint ptr , strptr(answer)) + (outblocks - 1)    dim as ulongint stops = (len(number1)\8) + (len(number2)\8)    dim as ulongint value = 0     dim as ulongint vals = 0    dim as ulongint hold = 0    dim as ulongint locat = 0    dim as ulongint carry = 0    dim as ulongint high1 = ( len(number1)  \ 8 ) - 1    dim as ulongint high2 = ( len(number2)  \ 8 ) - 1    dim as ulongint ptr num1_ptr = cptr( ulongint ptr , strptr(number1) ) + high1    dim as ulongint ptr num2_ptr = cptr( ulongint ptr , strptr(number2) ) + high2    for hold = 0 to stops step 1        for a as longint = hold to 0 step -1            if (high1 - locat) <= high1 and (a <= high2) then                vals = *( num2_ptr - a )                value+= *( num1_ptr - locat ) * vals             end if            locat+=1        next        locat = 0        carry = value \ 1e7        *outplace = value mod 1e7         outplace-= 1         value = carry    next        'convert answer back to ascii   dim as string outtext=""   outplace = cptr( ulongint ptr , strptr(answer) )   for a as ulongint = 1 to outblocks step 1       value = *outplace       outplace+=1       outtext+= right("0000000" + str(value),7)    next           outtext = ltrim(outtext,"0")       return outtext    end function'==============================================================================='==============================================================================='Dodicats plus & Minus functions'==============================================================================='===============================================================================    Function plus(_num1 As String,_num2 As String) As String        Dim  ADDQmod(0 To 19) As Ubyte        Dim  ADDbool(0 To 19) As Ubyte        For z As Integer=0 To 19            ADDQmod(z)=(z Mod 10+48)            ADDbool(z)=(-(10<=z))        Next z        Var _flag=0,n_=0        Dim As Ubyte addup=Any,addcarry=Any        #macro finish()        answer=Ltrim(answer,"0")        If _flag=1 Then Swap _num2,_num1        Return answer        #endmacro        If Len(_num2)>Len(_num1) Then             Swap _num2,_num1            _flag=1        End If        Var diff=Len(_num1)-Len(_num2)        Var answer="0"+_num1        addcarry=0        For n_=Len(_num1)-1 To diff Step -1             addup=_num2[n_-diff]+_num1[n_]-96            answer[n_+1]=ADDQmod(addup+addcarry)            addcarry=ADDbool(addup+addcarry)        Next n_         If addcarry=0 Then             finish()        End If        If n_=-1 Then             answer[0]=addcarry+48            finish()            Endif            For n_=n_ To 0 Step -1                 addup=_num1[n_]-48                answer[n_+1]=ADDQmod(addup+addcarry)                addcarry=ADDbool(addup+addcarry)                If addcarry=0 Then Exit For            Next n_            answer[0]=addcarry+48            finish()        End Function'==============================================================================='===============================================================================Function minus(NUM1 As String,NUM2 As String) As String     'Dim As String copyfirstnum=mul_num_1,copysecondnum=mul_num_2    Dim As Byte swapflag                Dim As Long lenf,lens    Dim sign As String * 1    'Dim As String part1,part2    Dim bigger As Byte     'set up tables    Dim As Ubyte Qmod(0 To 19)    Dim bool(0 To 19) As Ubyte    For z As Integer=0 To 19        Qmod(z)=cubyte(z Mod 10+48)        bool(z)=cubyte(-(10>z))    Next z    lenf=Len(NUM1)    lens=Len(NUM2)    #macro compare(numbers)        If Lens>lenf Then bigger= -1:Goto fin        If Lens<lenf Then bigger =0:Goto fin        If NUM2>NUM1 Then             bigger=-1        Else            bigger= 0        End If        fin:    #endmacro    compare(numbers)    If bigger Then         sign="-"        Swap NUM2,NUM1        Swap lens,lenf        swapflag=1    Endif    'lenf=Len(NUM1)    'lens=Len(NUM2)    Dim diff As Long=lenf-lens-Sgn(lenf-lens)    Dim As String one,two,three    three=NUM1    two=String(lenf-lens,"0")+NUM2    one=NUM1    Dim As Long n2    Dim As Ubyte takeaway,subtractcarry    Dim As Ubyte ten=10    'Dim z As Long    subtractcarry=0    Do         For n2=lenf-1 To diff Step -1            takeaway= one[n2]-two[n2]+ten-subtractcarry           three[n2]=Qmod(takeaway)            subtractcarry=bool(takeaway)        Next n2         If subtractcarry=0 Then Exit Do        If n2=-1 Then Exit Do        For n2=n2 To 0 Step -1             takeaway= one[n2]-two[n2]+ten-subtractcarry            three[n2]=Qmod(takeaway)            subtractcarry=bool(takeaway)            Next n2        Exit Do    Loop        three=Ltrim(three,"0")    If three="" Then Return "0"    If swapflag=1 Then Swap NUM1,NUM2       Return sign+three    End Function'==============================================================================='===============================================================================function multiplier_7(byref num1 as string, byref num2 as string) as string        dim as string number1,number2    dim as string answer,outtext        dim as string int1,frac1,int2,frac2    dim as ulongint dec,dec1,len1,len2    dim as string str1    dim as string sign1,sign2,outsign        number1 = num1    number2 = num2        sign1 = left(number1,1)    if sign1 = "+" or sign1 = "-" then number1 = mid(number1,2) else sign1 = ""        sign2 = left(number2,1)    if sign2 = "+" or sign2 = "-" then number2 = mid(number2,2) else sign2 = ""        if (sign1 = sign2) then outsign = ""    if (sign1 <> sign2) then outsign = "-"        dec = instr(1,number1,".")    if dec > 0 then         int1 = left(number1,dec-1)        frac1 = mid(number1,dec+1)    else        int1 = number1        frac1 = ""    end if        dec = instr(1,number2,".")    if dec > 0 then         int2 = left(number2,dec-1)        frac2 = mid(number2,dec+1)    else        int2 = number2        frac2 = ""    end if    dec = len(frac1)+len(frac2)    number1 = int1+frac1    number2 = int2+frac2    'swap numbers so that bigger number is number1 and smaller is number2    if len(number2) > len(number1) then swap number1,number2    if len(number1) = len(number2) then         if val(left(number2,1)) > val(left(number1,1)) then swap number1,number2    end if    'make numbers equal multiple of 7 bytes    do        str1 = str(len(number1)/7)        dec1 = instr(1,str1,".")        if dec1 <> 0 then number1 = "0" + number1    loop until dec1 = 0    do        str1 = str(len(number2)/7)        dec1 = instr(1,str1,".")        if dec1 <> 0 then number2 = "0" + number2    loop until dec1 = 0        'convert the numeric strings to use pointers    'convert number1    dim as string n1 = string(len(number1)*8,chr(0))    dim as ulongint ptr ulp1     ulp1 = cptr(ulongint ptr,strptr(n1))    dim as longint val1    dim as longint len_1 = 0    dim as uinteger a    for a = 0 to len(number1)-1 step 7        val1 = (number1[a+0]-48)*1000000ull        val1+= (number1[a+1]-48)*100000ull        val1+= (number1[a+2]-48)*10000ull        val1+= (number1[a+3]-48)*1000ull        val1+= (number1[a+4]-48)*100ull        val1+= (number1[a+5]-48)*10ull        val1+= (number1[a+6]-48)*1ull        *ulp1 = val1        ulp1+=1        len_1+=8    next    number1 = left(n1,len_1)    n1=""        'convert the numeric strings to use pointers    'convert number2    dim as string n2 = string(len(number2)*8,chr(0))    dim as ulongint ptr ulp2    ulp2 = cptr(ulongint ptr,strptr(n2))    dim as longint val2    dim as longint len_2 = 0    for a = 0 to len(number2)-1 step 7        val2 = (number2[a+0]-48)*1000000ull        val2+= (number2[a+1]-48)*100000ull        val2+= (number2[a+2]-48)*10000ull        val2+= (number2[a+3]-48)*1000ull        val2+= (number2[a+4]-48)*100ull        val2+= (number2[a+5]-48)*10ull        val2+= (number2[a+6]-48)*1ull        *ulp2 = val2        ulp2+=1        len_2+=8    next    number2 = left(n2,len_2)    n2=""        'create accumulator    answer = string( len(number1) + len(number2) + 8 , chr(0) )     'dimension vars for the mul    dim as longint ptr start1,stop1,start2,stop2 'use longint because the pointers go negative    dim as longint ptr chk_1 , chk_2    dim as longint ptr inc1,inc2    dim as longint ptr outplace    dim as ulongint carry    dim as ulongint total    dim as ulongint blocknumber1 = len(number1)/8    dim as ulongint blocknumber2 = len(number2)/8    dim as ulongint outblocks = len(answer)/8        'set initial accumulator place    outplace = cptr(longint ptr , strptr(answer)) + (outblocks - 1)    'set initial pointers into number1     start1 = cptr(longint ptr , strptr(number1))+(blocknumber1-1)    stop1 =  cptr(longint ptr , strptr(number1))+(blocknumber1-1)    'set initial pointers into number2    start2 = cptr(longint ptr , strptr(number2))+(blocknumber2-1)    stop2 =  cptr(longint ptr , strptr(number2))+(blocknumber2-1)    'set comparison to beg of numbers    chk_1 = cptr( longint ptr , strptr(number1))    chk_2 = cptr( longint ptr , strptr(number2))        'zero the carry    carry = 0        'begin looping thru strings multiplying    do        'set total to zero        total = 0        'we are going to be incrementing thru number2 while decrementing thru number1        'working in opposite directions from start1 to stop1 and start2 to stop2        'inc1 works from right to left in the top number1 string        'inc2 works from start2 to stop 2, in the bottom number2 string, decrementing each loop.        inc1 = start1        inc2 = start2        do            total += *inc1 * *inc2            inc1-= 1            inc2+= 1        loop until inc2 = stop2+1            total = total + carry        carry = total \ 1e7        *outplace = total mod 1e7        '*outplace = imod(total , 1e7)                outplace -= 1                'each loop we need to decrement stop1        'if stop1 goes negative we reset it to zero and decrement stop2        stop1 -= 1        if stop1 < chk_1 then            stop1 += 1            stop2 -=1            if stop2 < chk_2 then stop2+= 1        end if        'each loop we decrement start2 to the left        start2 -= 1        'if start2 goes negative we reset it to zero and decrement start1        'start1 is the rightmost digit of number1 we need to multiply        if start2 < chk_2 then            start2 += 1            start1 -= 1            if start1 < chk_1 then start1+=1        end if        loop until outplace = cptr(ulongint ptr,strptr(answer))+1        'put in the carry at the end    if carry > 0  then *outplace = carry else *outplace = 0        'convert answer back to ascii    for a as ulongint = 1 to outblocks-1 step 1        val1 = *outplace        outplace +=1        outtext = outtext + right("0000000" + str(val1),7)    next        'put in the decimal point    outtext = left(outtext,len(outtext)-dec) + "." +  mid(outtext,(len(outtext)-dec)+1)    'trim leading zeros    outtext = trim(outtext,"0") 'if multiplying by 1, we have a zero in front.    outtext = outsign + outtext    return outtextend function'==============================================================================='===============================================================================`
Richard
Posts: 2766
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: Squares

Albert wrote:@Richard , could you convert it to 64 bit assembly language??

I could but I wouldn't. I would only translate a routine that was mature and that was being heavily used.

Your stepping by 7s or 8s is slower than by 9s. That is why I used Base1e9. Stepping by 10 or greater is not possible unless you have a fast multiply instruction that is bigger than a 32 bit x 32 bit = 64 bit result.

You might consider Karatsuba Multiplication, or some way to more efficiently use the CLMUL instructions.
albert
Posts: 4082
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Squares

@Richard

I think after it gets to the max length, it needs to step backwards..??
I'll keep playing with it till its faster than multiplier_7..
albert
Posts: 4082
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Squares

@Dodicat

I need to somehow set up the stepping to follow the output shown here..

Code: Select all

`Declare Function add_mult( num1 as string , num2 as string ) as string DECLARE FUNCTION multiplier_7(byref num1 as string, byref num2 as string) as stringDECLARE Function minus(NUM1 As String,NUM2 As String) As StringDeclare Function       plus( NUMber1 As String  ,  NUMber2 As String ) As Stringscreen 19do         dim as string num1    dim as string num2    for a as longint = 1 to 24 step 1        num1+=str(int(rnd*10))    next    for a as longint = 1 to 24 step 1        num2+=str(int(rnd*10))    next    if len(num2) < len(num1)  then swap num1 , num2            print    print num1    print num2        dim as double t1 , t2 , t3 , t4        t1 = timer        dim as string answer = add_mult( num1,num2 )    t2 = timer        t3 = timer        dim as string real_answer = multiplier_7( num1 , num2 )        real_answer = rtrim( real_answer,".")    t4 = timer            dim as string difference = minus( answer , real_answer )        print answer    print real_answer    print "Difference = " ; difference    print "Time = " ; t2 - t1    print "Time = " ; t4 - t3            sleep    loop until inkey=chr(27)sleepend'==============================================================================='==============================================================================='==============================================================================='===============================================================================function add_mult( num1 as string , num2 as string ) as string         dim as string number1 = num1    dim as string number2 = num2        'make numbers equal multiple of 7 bytes    dim as string str1    dim as longint dec1    do        str1 = str(len(number1)/7)        dec1 = instr(1,str1,".")        if dec1 <> 0 then number1 = "0" + number1    loop until dec1 = 0    do        str1 = str(len(number2)/7)        dec1 = instr(1,str1,".")        if dec1 <> 0 then number2 = "0" + number2    loop until dec1 = 0            'convert the numeric strings to use pointers    'convert number1    dim as string n1 = string(len(number1)*8,chr(0))    dim as ulongint ptr ulp1 = cptr(ulongint ptr,strptr(n1))    dim as longint valu1    dim as longint len_1 = 0    for a as longint = 0 to len(number1)-1 step 7        valu1  = (number1[a+0]-48)*1e6        valu1+= (number1[a+1]-48)*1e5        valu1+= (number1[a+2]-48)*1e4        valu1+= (number1[a+3]-48)*1e3        valu1+= (number1[a+4]-48)*1e2        valu1+= (number1[a+5]-48)*1e1        valu1+= (number1[a+6]-48)*1        *ulp1 = valu1        ulp1+=1        len_1+=8    next    number1 = left(n1,len_1)    n1=""        'convert the numeric strings to use pointers    'convert number2    dim as string n2 = string(len(number2)*8,chr(0))    dim as ulongint ptr ulp2 = cptr(ulongint ptr,strptr(n2))    dim as longint valu2    dim as longint len_2 = 0    for a as longint = 0 to len(number2)-1 step 7        valu2 =  (number2[a+0]-48)*1e6        valu2+= (number2[a+1]-48)*1e5        valu2+= (number2[a+2]-48)*1e4        valu2+= (number2[a+3]-48)*1e3        valu2+= (number2[a+4]-48)*1e2        valu2+= (number2[a+5]-48)*1e1        valu2+= (number2[a+6]-48)*1        *ulp2 = valu2        ulp2+=1        len_2+=8    next    number2 = left(n2,len_2)    n2=""        'create accumulator    dim as string answer = string( len(number1) + len(number2) , chr(0) )     dim as ulongint outblocks = ( len(answer) \ 8 )    dim as ulongint ptr outplace = cptr(ulongint ptr , strptr(answer)) + (outblocks - 1)    dim as ulongint stops = (len(number1)\8) + (len(number2)\8)    dim as ulongint value = 0     dim as ulongint vals = 0    dim as longint locat = 0    dim as ulongint carry = 0    dim as ulongint high1 = ( len(number1)  \ 8 ) - 1    dim as ulongint high2 = ( len(number2)  \ 8 ) - 1    dim as ulongint ptr num1_ptr = cptr( ulongint ptr , strptr(number1) ) + high1    dim as ulongint ptr num2_ptr = cptr( ulongint ptr , strptr(number2) ) + high2    print "hold" , "a" , "locat" , "vals" , "value"    for hold as longint = 0 to stops step 1        locat = 0        for a as longint = hold to 0 step -1            if locat <= high1 and a <= high2 then                vals = *( num2_ptr - a )                value+= *( num1_ptr - locat ) * vals                print hold , a , locat , vals , value           end if           locat+=1        next        carry = value \ 1e7        *outplace = value mod 1e7         outplace-= 1         value = carry    next        'convert answer back to ascii   dim as string outtext=""   outplace = cptr( ulongint ptr , strptr(answer) )   for a as ulongint = 1 to outblocks step 1       value = *outplace       outplace+=1       outtext+= right("0000000" + str(value),7)    next           outtext = ltrim(outtext,"0")       return outtext    end function'==============================================================================='==============================================================================='Dodicats plus & Minus functions'==============================================================================='===============================================================================    Function plus(_num1 As String,_num2 As String) As String        Dim  ADDQmod(0 To 19) As Ubyte        Dim  ADDbool(0 To 19) As Ubyte        For z As Integer=0 To 19            ADDQmod(z)=(z Mod 10+48)            ADDbool(z)=(-(10<=z))        Next z        Var _flag=0,n_=0        Dim As Ubyte addup=Any,addcarry=Any        #macro finish()        answer=Ltrim(answer,"0")        If _flag=1 Then Swap _num2,_num1        Return answer        #endmacro        If Len(_num2)>Len(_num1) Then             Swap _num2,_num1            _flag=1        End If        Var diff=Len(_num1)-Len(_num2)        Var answer="0"+_num1        addcarry=0        For n_=Len(_num1)-1 To diff Step -1             addup=_num2[n_-diff]+_num1[n_]-96            answer[n_+1]=ADDQmod(addup+addcarry)            addcarry=ADDbool(addup+addcarry)        Next n_         If addcarry=0 Then             finish()        End If        If n_=-1 Then             answer[0]=addcarry+48            finish()            Endif            For n_=n_ To 0 Step -1                 addup=_num1[n_]-48                answer[n_+1]=ADDQmod(addup+addcarry)                addcarry=ADDbool(addup+addcarry)                If addcarry=0 Then Exit For            Next n_            answer[0]=addcarry+48            finish()        End Function'==============================================================================='===============================================================================Function minus(NUM1 As String,NUM2 As String) As String     'Dim As String copyfirstnum=mul_num_1,copysecondnum=mul_num_2    Dim As Byte swapflag                Dim As Long lenf,lens    Dim sign As String * 1    'Dim As String part1,part2    Dim bigger As Byte     'set up tables    Dim As Ubyte Qmod(0 To 19)    Dim bool(0 To 19) As Ubyte    For z As Integer=0 To 19        Qmod(z)=cubyte(z Mod 10+48)        bool(z)=cubyte(-(10>z))    Next z    lenf=Len(NUM1)    lens=Len(NUM2)    #macro compare(numbers)        If Lens>lenf Then bigger= -1:Goto fin        If Lens<lenf Then bigger =0:Goto fin        If NUM2>NUM1 Then             bigger=-1        Else            bigger= 0        End If        fin:    #endmacro    compare(numbers)    If bigger Then         sign="-"        Swap NUM2,NUM1        Swap lens,lenf        swapflag=1    Endif    'lenf=Len(NUM1)    'lens=Len(NUM2)    Dim diff As Long=lenf-lens-Sgn(lenf-lens)    Dim As String one,two,three    three=NUM1    two=String(lenf-lens,"0")+NUM2    one=NUM1    Dim As Long n2    Dim As Ubyte takeaway,subtractcarry    Dim As Ubyte ten=10    'Dim z As Long    subtractcarry=0    Do         For n2=lenf-1 To diff Step -1            takeaway= one[n2]-two[n2]+ten-subtractcarry           three[n2]=Qmod(takeaway)            subtractcarry=bool(takeaway)        Next n2         If subtractcarry=0 Then Exit Do        If n2=-1 Then Exit Do        For n2=n2 To 0 Step -1             takeaway= one[n2]-two[n2]+ten-subtractcarry            three[n2]=Qmod(takeaway)            subtractcarry=bool(takeaway)            Next n2        Exit Do    Loop        three=Ltrim(three,"0")    If three="" Then Return "0"    If swapflag=1 Then Swap NUM1,NUM2       Return sign+three    End Function'==============================================================================='===============================================================================function multiplier_7(byref num1 as string, byref num2 as string) as string        dim as string number1,number2    dim as string answer,outtext        dim as string int1,frac1,int2,frac2    dim as ulongint dec,dec1,len1,len2    dim as string str1    dim as string sign1,sign2,outsign        number1 = num1    number2 = num2        sign1 = left(number1,1)    if sign1 = "+" or sign1 = "-" then number1 = mid(number1,2) else sign1 = ""        sign2 = left(number2,1)    if sign2 = "+" or sign2 = "-" then number2 = mid(number2,2) else sign2 = ""        if (sign1 = sign2) then outsign = ""    if (sign1 <> sign2) then outsign = "-"        dec = instr(1,number1,".")    if dec > 0 then         int1 = left(number1,dec-1)        frac1 = mid(number1,dec+1)    else        int1 = number1        frac1 = ""    end if        dec = instr(1,number2,".")    if dec > 0 then         int2 = left(number2,dec-1)        frac2 = mid(number2,dec+1)    else        int2 = number2        frac2 = ""    end if    dec = len(frac1)+len(frac2)    number1 = int1+frac1    number2 = int2+frac2    'swap numbers so that bigger number is number1 and smaller is number2    if len(number2) > len(number1) then swap number1,number2    if len(number1) = len(number2) then         if val(left(number2,1)) > val(left(number1,1)) then swap number1,number2    end if    'make numbers equal multiple of 7 bytes    do        str1 = str(len(number1)/7)        dec1 = instr(1,str1,".")        if dec1 <> 0 then number1 = "0" + number1    loop until dec1 = 0    do        str1 = str(len(number2)/7)        dec1 = instr(1,str1,".")        if dec1 <> 0 then number2 = "0" + number2    loop until dec1 = 0        'convert the numeric strings to use pointers    'convert number1    dim as string n1 = string(len(number1)*8,chr(0))    dim as ulongint ptr ulp1     ulp1 = cptr(ulongint ptr,strptr(n1))    dim as longint val1    dim as longint len_1 = 0    dim as uinteger a    for a = 0 to len(number1)-1 step 7        val1 = (number1[a+0]-48)*1000000ull        val1+= (number1[a+1]-48)*100000ull        val1+= (number1[a+2]-48)*10000ull        val1+= (number1[a+3]-48)*1000ull        val1+= (number1[a+4]-48)*100ull        val1+= (number1[a+5]-48)*10ull        val1+= (number1[a+6]-48)*1ull        *ulp1 = val1        ulp1+=1        len_1+=8    next    number1 = left(n1,len_1)    n1=""        'convert the numeric strings to use pointers    'convert number2    dim as string n2 = string(len(number2)*8,chr(0))    dim as ulongint ptr ulp2    ulp2 = cptr(ulongint ptr,strptr(n2))    dim as longint val2    dim as longint len_2 = 0    for a = 0 to len(number2)-1 step 7        val2 = (number2[a+0]-48)*1000000ull        val2+= (number2[a+1]-48)*100000ull        val2+= (number2[a+2]-48)*10000ull        val2+= (number2[a+3]-48)*1000ull        val2+= (number2[a+4]-48)*100ull        val2+= (number2[a+5]-48)*10ull        val2+= (number2[a+6]-48)*1ull        *ulp2 = val2        ulp2+=1        len_2+=8    next    number2 = left(n2,len_2)    n2=""        'create accumulator    answer = string( len(number1) + len(number2) + 8 , chr(0) )     'dimension vars for the mul    dim as longint ptr start1,stop1,start2,stop2 'use longint because the pointers go negative    dim as longint ptr chk_1 , chk_2    dim as longint ptr inc1,inc2    dim as longint ptr outplace    dim as ulongint carry    dim as ulongint total    dim as ulongint blocknumber1 = len(number1)/8    dim as ulongint blocknumber2 = len(number2)/8    dim as ulongint outblocks = len(answer)/8        'set initial accumulator place    outplace = cptr(longint ptr , strptr(answer)) + (outblocks - 1)    'set initial pointers into number1     start1 = cptr(longint ptr , strptr(number1))+(blocknumber1-1)    stop1 =  cptr(longint ptr , strptr(number1))+(blocknumber1-1)    'set initial pointers into number2    start2 = cptr(longint ptr , strptr(number2))+(blocknumber2-1)    stop2 =  cptr(longint ptr , strptr(number2))+(blocknumber2-1)    'set comparison to beg of numbers    chk_1 = cptr( longint ptr , strptr(number1))    chk_2 = cptr( longint ptr , strptr(number2))        'zero the carry    carry = 0        'begin looping thru strings multiplying    do        'set total to zero        total = 0        'we are going to be incrementing thru number2 while decrementing thru number1        'working in opposite directions from start1 to stop1 and start2 to stop2        'inc1 works from right to left in the top number1 string        'inc2 works from start2 to stop 2, in the bottom number2 string, decrementing each loop.        inc1 = start1        inc2 = start2        do            total += *inc1 * *inc2            inc1-= 1            inc2+= 1        loop until inc2 = stop2+1            total = total + carry        carry = total \ 1e7        *outplace = total mod 1e7        '*outplace = imod(total , 1e7)                outplace -= 1                'each loop we need to decrement stop1        'if stop1 goes negative we reset it to zero and decrement stop2        stop1 -= 1        if stop1 < chk_1 then            stop1 += 1            stop2 -=1            if stop2 < chk_2 then stop2+= 1        end if        'each loop we decrement start2 to the left        start2 -= 1        'if start2 goes negative we reset it to zero and decrement start1        'start1 is the rightmost digit of number1 we need to multiply        if start2 < chk_2 then            start2 += 1            start1 -= 1            if start1 < chk_1 then start1+=1        end if        loop until outplace = cptr(ulongint ptr,strptr(answer))+1        'put in the carry at the end    if carry > 0  then *outplace = carry else *outplace = 0        'convert answer back to ascii    for a as ulongint = 1 to outblocks-1 step 1        val1 = *outplace        outplace +=1        outtext = outtext + right("0000000" + str(val1),7)    next        'put in the decimal point    outtext = left(outtext,len(outtext)-dec) + "." +  mid(outtext,(len(outtext)-dec)+1)    'trim leading zeros    outtext = trim(outtext,"0") 'if multiplying by 1, we have a zero in front.    outtext = outsign + outtext    return outtextend function'==============================================================================='===============================================================================`
Tourist Trap
Posts: 2244
Joined: Jun 02, 2015 16:24

### Re: Squares

Hi all,
hi Albert the multiplier (this one can be of some interest for you maybe),

I've not been very around those weeks! I've been being moving and so on in real life so no really time left for my favourite programming language and board. However I've been hunting this strange multiplication problem today and tried to solve it by some coding.
It's about finding the reverse of a number after this number is multiplied by one other. Ok, not sure if it is clear, but what I found surprising is that there is something found only for a multiplier=4 and then, only for a number greater than a 4 digits number, and even then, I can't find more than one matching result each time.

Here is it:

Code: Select all

`'goal:'typically find abcd such that dcba==abcd*mult, digitwise'known restrictions of the code:'   i can not be a negative number'   i must be integer'   the length of i has some upperboundvar mult    => 4var i   => 1234567var n   => len(str(i))redim as typeOf(i)  digit_tab(1 to n)redim as typeOf(i)  num_tab(1 to n)'loop over n-digits num such that num*mult is still n digitsdim as typeOf(i)    loopVariable    => val(1 & string(n - 1, asc("0")))redim as typeOf(i)  reverse_tab(0)? "searching..."while (len(str(loopVariable*mult))=n)    for index as integer = 1 to n        digit_tab(index)    = val(mid(str(    _                                             int(loopVariable*10^(1 - index)) _                                             ), _                                         n - index + 1, _                                          1 ))        num_tab(index) = val(   str(digit_tab(index)) & _                                 string(index - 1, asc("0")) )        '? num_tab(index), iif(index=n,"=","+"), "(digit="; digit_tab(index); ")"    next index        '? loopVariable, "*mult="; loopVariable*mult    '?        var digit_tab_str   => ""    for index as integer = lBound(digit_tab) to uBound(digit_tab)        digit_tab_str   &= str(digit_tab(index))    next index        var reverse => val(digit_tab_str)        if loopVariable*mult=reverse then        ? "found one matching entry at", loopVariable        redim reverse_tab(uBound(reverse_tab) + 1)        reverse_tab(uBound(reverse_tab)) = loopVariable    end if        loopVariable += 1wend'show matching entriesif uBound(reverse_tab)=0 then    ? "no matching entry found"else    ? "found "; uBound(reverse_tab); " matching entries at:"    for index as integer = 1 to uBound(reverse_tab)        ? reverse_tab(index)    next indexend if? "end"'(eof)`
Richard
Posts: 2766
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: Squares

@ Tourist Trap
8712 = 2178 x 4
87912 = 21978 x 4
879912 = 219978 x 4
8799912 = 2199978 x 4 (as you found.)
ditto

9801 = 1089 x 9
98901 = 10989 x 9
989901 = 109989 x 9
98999901 = 10999989 x 9
ditto

There are very many trivial cases if 0 is allowed as a digit
Richard
Posts: 2766
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: Squares

Further to the above …
We have forbidden end digits from being zero. We have forbidden the multiplier m from being 1, and m = 0 is not possible. So for base 10 the multiplier cannot be greater than 9 or the number of digits would increase. Where m is the integer multiplier, and x is the radix = 10 for decimal, we must solve a diophantine equation of the form;
ax² + bx + c = m * ( cx² + bx + a ), for values of the digits a, b and c, having specified x and guessed m.
The solution requires square roots of integers. But with the exception of the perfect squares, the square roots of integers are irrational and their continued fractions are recurring. The only perfect squares below 10 are 0, 1, 4 and 9, we have ruled out 0 and 1, so the only possible multipliers must be m = 4 or m = 9.

Now it is clear that the numbers are composed of three parts, a head, a body and a tail.
The head and tail switch places during the multiply, they are in effect reflected.
During the multiply, the head and tail are connected by the propagation of carry along lines of 9's in the body, or are prevented from propagating carry by lines of zeros in the body. The number of 9s or 0s in the body is then unimportant.

Once a small seed number has been found, it leads to all body lengths of either 0s or 9s.
Also, any repetition of the numbers generate larger numbers that still give a correct reversal.
For example 2178 can become; 21978, 219978, 2199978, 21999978 …
It also generates; 21782178, 217821782178, 2178217821782178 …
Then there are repetitions with various bodies; 21978, 2197821978, etc.

Code: Select all

`'---------------------------------------------------------'' group 4, "2178"''                8712 = 2178 x 4'             87·9·12 = 21978 x 4'            87·99·12 = 219978 x 4'           87·999·12 = 2199978 x 4'          87·9999·12 = 21999978 x 4'         87·99999·12 = 219999978 x 4'        87·999999·12 = 2199999978 x 4 '        '           8712·8712 = 21782178 x 4'         8712·0·8712 = 217802178 x 4'        8712·00·8712 = 2178002178 x 4 ''      8712·8712·8712 = 217821782178 x 4'        '         87912·87912 = 2197821978 x 4 '       87912·0·87912 = 21978021978 x 4'      87912·00·87912 = 219780021978 x 4'        '   87912·87912·87912 = 219782197821978 x 4''---------------------------------------------------------'' group 9, "1089"''                9801 = 1089 x 9'             98·9·01 = 10989 x 9'            98·99·01 = 109989 x 9'           98·999·01 = 1099989 x 9'          98·9999·01 = 10999989 x 9'         98·99999·01 = 109999989 x 9'        98·999999·01 = 1099999989 x 9'       98·9999999·01 = 10999999989 x 9'        '           9801·9801 = 10891089 x 9'         9801·0·9801 = 108901089 x 9'        9801·00·9801 = 1089001089 x 9'       9801·000·9801 = 10890001089 x 9  '        '         98901·98901 = 1098910989 x 9'       98901·0·98901 = 10989010989 x 9'      98901·00·98901 = 109890010989 x 9''---------------------------------------------------------`
Tourist Trap
Posts: 2244
Joined: Jun 02, 2015 16:24

### Re: Squares

Richard wrote: 8712 = 2178 x 4
9801 = 1089 x 9

Hi Richard,

a big thank for the rigorous proof so we have this item solved. This is quite interesting as subset of the greater problem dealing with number reversal. I mean, we have solved (you did... to be more exact), another interesting issue:
• find a function, call it REV(x), that operates on a number (natural integer for now) and which matches a simple scalar multiplication
So we have found some candidates for REV, with the restriction of using only the convenient mult operator.
REV == *4 is clearly such a thing (this with a subset of whole integers to feed the engine, but with *4 we have such a subset as seen above).

Why can it be useful despite the restriction? In my opinion it allows us to generate a great amount of function-wise generated reverses at a rather low cost. It's a fact to be able to generate reverses with some algorithm (like something crude operating on the string of digit), and it's another to get the same thing done using a function. I'm quite happy with this first subset, maybe the job could be extended... to squares for instance (which is our favourite around here ;) )

Ok, now I would have a second question left without answer. It seems to me that greater the base in which the string of digit is expressed, lesser the chances to make multwise reversals. I may be wrong, but my reasoning lies on the observing that for 1-digit numbers, the by-mult reversal is impossible. And extending the base, has for effect to also expand the 1-digit numbers of the whole integer list.

I can be wrong on this reasonning of course. But if I'm not mistaking to much in this intuition, I then wonder what is the optimal base for the multwise reversal operation. What base allows more matching multiplier, and more candidates to reversion in the whole?

Not sure if it's an easy thing. I think I'll try some coding around this later :)
Tourist Trap
Posts: 2244
Joined: Jun 02, 2015 16:24

### Re: Squares

Little utility related to the above stuff (note that this starts being very slow when num_size>6 digits):

Code: Select all

`'-'given a multiplier and a number 'num' of a fixed digit size, 'what is the maximum argument for mult before the initial digit size is incremented for the mult result'-const as uInteger   digit_size_max  => 6const as uInteger   mult_min  => 1  ''0 would never trigger any digit size overflowconst as uInteger   mult_max  => 12 ''greater than 9 is uselesswidth 100, 100'loop over digit sizevar digit_size => 0do    digit_size += 1    var num => 0    ? "---------- digit size = "; digit_size    ? "---------- multipliers searching interval = ["; mult_min; ";"; mult_max; "]"    ? "---------- numbers searching interval = ["; _                                                 10^(digit_size - 1); _                                                 ";"; _                                                 10^(digit_size) - 1; _                                                 "]"    '    'loop over multipliers    for mult as integer = mult_min to mult_max step +1        'loop over numbers        num = 10^(digit_size - 1)        do            'test for digit size overflow            var resultSize  => len(str(cUint(num*mult)))            if resultSize=digit_size then                if len(str(cUint((num + 1)*mult)))=digit_size then                    num += 1                else                    ? "mult="; mult,                     ? "size overflow after num = "; num                    exit do                end if            else                ? "mult="; mult,                 ? "size overflow after num = "; num                exit do            end if        loop    next mult    'loop until digit_size=digit_size_max? : ? "end"'(eof)`

---------- digit size = 1
---------- multipliers searching interval = [1;12]
---------- numbers searching interval = [ 1; 9]
mult= 1 size overflow after num = 9
mult= 2 size overflow after num = 4
mult= 3 size overflow after num = 3
mult= 4 size overflow after num = 2
mult= 5 size overflow after num = 1
mult= 6 size overflow after num = 1
mult= 7 size overflow after num = 1
mult= 8 size overflow after num = 1
mult= 9 size overflow after num = 1
mult= 10 size overflow after num = 1
mult= 11 size overflow after num = 1
mult= 12 size overflow after num = 1
---------- digit size = 2
---------- multipliers searching interval = [1;12]
---------- numbers searching interval = [ 10; 99]
mult= 1 size overflow after num = 99
mult= 2 size overflow after num = 49
mult= 3 size overflow after num = 33
mult= 4 size overflow after num = 24
mult= 5 size overflow after num = 19
mult= 6 size overflow after num = 16
mult= 7 size overflow after num = 14
mult= 8 size overflow after num = 12
mult= 9 size overflow after num = 11
mult= 10 size overflow after num = 10
mult= 11 size overflow after num = 10
mult= 12 size overflow after num = 10
---------- digit size = 3
---------- multipliers searching interval = [1;12]
---------- numbers searching interval = [ 100; 999]
mult= 1 size overflow after num = 999
mult= 2 size overflow after num = 499
mult= 3 size overflow after num = 333
mult= 4 size overflow after num = 249
mult= 5 size overflow after num = 199
mult= 6 size overflow after num = 166
mult= 7 size overflow after num = 142
mult= 8 size overflow after num = 124
mult= 9 size overflow after num = 111
mult= 10 size overflow after num = 100
mult= 11 size overflow after num = 100
mult= 12 size overflow after num = 100
---------- digit size = 4
---------- multipliers searching interval = [1;12]
---------- numbers searching interval = [ 1000; 9999]
mult= 1 size overflow after num = 9999
mult= 2 size overflow after num = 4999
mult= 3 size overflow after num = 3333
mult= 4 size overflow after num = 2499
mult= 5 size overflow after num = 1999
mult= 6 size overflow after num = 1666
mult= 7 size overflow after num = 1428
mult= 8 size overflow after num = 1249
mult= 9 size overflow after num = 1111
mult= 10 size overflow after num = 1000
mult= 11 size overflow after num = 1000
mult= 12 size overflow after num = 1000
---------- digit size = 5
---------- multipliers searching interval = [1;12]
---------- numbers searching interval = [ 10000; 99999]
mult= 1 size overflow after num = 99999
mult= 2 size overflow after num = 49999
mult= 3 size overflow after num = 33333
mult= 4 size overflow after num = 24999
mult= 5 size overflow after num = 19999
mult= 6 size overflow after num = 16666
mult= 7 size overflow after num = 14285
mult= 8 size overflow after num = 12499
mult= 9 size overflow after num = 11111
mult= 10 size overflow after num = 10000
mult= 11 size overflow after num = 10000
mult= 12 size overflow after num = 10000
---------- digit size = 6
---------- multipliers searching interval = [1;12]
---------- numbers searching interval = [ 100000; 999999]
mult= 1 size overflow after num = 999999
mult= 2 size overflow after num = 499999
mult= 3 size overflow after num = 333333
mult= 4 size overflow after num = 249999
mult= 5 size overflow after num = 199999
mult= 6 size overflow after num = 166666
mult= 7 size overflow after num = 142857
mult= 8 size overflow after num = 124999
mult= 9 size overflow after num = 111111
mult= 10 size overflow after num = 100000
mult= 11 size overflow after num = 100000
mult= 12 size overflow after num = 100000

And maybe some other way (I may be mistaken in anything, just let me know whoever) to see what multipliers we are forced to use:
Let's write our numbers in the (tedious) form: Sum(0, N, ai*10^i).

If we take now for what seems to be the simplest example, the case where N=3, we see that we want to solve for k the equation:
k*Sum(0, 3, ai*10^i) == Sum(0, 3, ai*10^(n - 1))
That expands as:
k*a0*10^0 + k*a1*10^1 + k*a2*10^2 + k*a3*10^3 == a3*10^0 + a2*10^1 + a1*10^2 + a0*10^3

At this point we just have to try every possible entry. For instance if k = 4 we must have k*a0<10 so a0=1 or a0=2.
If a0=1 then a3=k*a0=4*1=4. But then k*a3=a0 doesn't match. 4*4<>1!
If a0=2, a3=2, which is what is wanted.

And we should go on testing every possible cases. Far more tedious than the Richard's way but rather straightforward if the identification is legit (what I'm not sure here). Moreover the way to induce the general solution from here then is another story...

And yes the carry propagation has to be taken into account, definitely tedious.
Richard
Posts: 2766
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: Squares

Tourist Trap wrote:At this point we just have to try every possible entry.
These problems are like that of finding prime factors. There are slow brute force solutions, but that does not preclude the discovery of faster solutions. Continued fraction approximations and Euclid's algorithm make these diophantine equations tractable.
Tourist Trap
Posts: 2244
Joined: Jun 02, 2015 16:24

### Re: Squares

Richard wrote:Continued fraction approximations and Euclid's algorithm make these diophantine equations tractable.

Unfortunately those things are never taught out of pure math curriculum.

I still haven't gone further with reverse obtained by multiplication when the base varies. But in order to clarify this topic, here is some of the paradox:

In base 10:
4*219978 = 879912 , reversal is success

In base 16, same values just expressed in the new base:
4*35B4A = D6D28 , reversal is failure

The reversal seems to be broken as we change the base, despite the fact it worked in the initial base.How to express the rule of this, it is puzzling. By what should we replace "4" in order to find the reverse of 35B4A in hexadecimal. Unless everything is broken, and we have other multipliers, with other values, unrelated as far as we are in another base.
Richard
Posts: 2766
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: Squares

Some people find patterns in numbers and believe those patterns are of fundamental physical significant. But when those numbers are written in a different base, the pattern disappears, it was a delusion. One example is Bruce Cathie. His harmonics 33, 695, 288 and 371244 made sense to him in base 10, but not in any other base. We know that they are not of physical significance because they are base dependent patterns.
https://en.wikipedia.org/wiki/Bruce_Cathie

It is important to recognise when a change of base will change the game. Physics and measurement are dependent on standards. It does not matter what base we use for a computation, the physics still works. Three-toed Sloths and five fingered humans all obey the same laws of physics.

Consider; n = a₀·x⁰ + a₁·x¹ + a₂·x² + a₃·x³ ; the indices are there for a very important purpose.
When I write a number as n = dx³ + cx² + bx¹ + ax⁰ ; it makes it obvious that the base x can be variable. When you change the position of the exponents relative to their coefficients you are tearing the number system apart. For example, if you want things to keep working arithmetically the c needs to remain associated with the x².

Number theory allows us to understand what is happening when the indices are scrambled, but scrambling the indices does not seem to help us in the real world. Maybe Number Theory is the Queen of Mathematics because she is high enough to not be sullied by the world we live in.

It is interesting to note that we are not restricted to integer values of base. Pi and √2 are irrational, but if we express Pi in the base Pi, we get Pi = 10. Likewise √2 can be a rational 10 when expressed in base √2.