Squares

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

Re: Squares

Postby dodicat » Jul 24, 2017 0:05

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

Re: Squares

Postby albert » Jul 24, 2017 1:19

@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 string
DECLARE Function minus(NUM1 As String,NUM2 As String) As String
Declare FUNCTION   SET_STR1( byref n1 as string , byref n2 as string ) as string
Declare Function       plus( NUMber1 As String  ,  NUMber2 As String ) As String

screen 19

do
   
    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)

sleep
end


'===============================================================================
'===============================================================================
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 outtext

end function
'===============================================================================
'===============================================================================



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

Re: Squares

Postby albert » Jul 28, 2017 22:45

@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 string
DECLARE Function minus(NUM1 As String,NUM2 As String) As String

Declare FUNCTION   SET_STR1( byref n1 as string , byref n2 as string ) as string'
Declare Function       plus( NUMber1 As String  ,  NUMber2 As String ) As String

screen 19

do
   
    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)

sleep
end


'===============================================================================
'===============================================================================
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 outtext

end function
'===============================================================================
'===============================================================================

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

add_mult

Postby albert » Jul 30, 2017 2:37

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

DECLARE Function minus(NUM1 As String,NUM2 As String) As String
Declare Function       plus( NUMber1 As String  ,  NUMber2 As String ) As String

screen 19

do
   
    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)

sleep
end

'===============================================================================
'===============================================================================
'===============================================================================
'===============================================================================
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 outtext

end function
'===============================================================================
'===============================================================================

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

Re: Squares

Postby Richard » Jul 30, 2017 6:42

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

Re: Squares

Postby albert » Jul 30, 2017 15:46

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

Re: Squares

Postby albert » Aug 01, 2017 0:17

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

DECLARE Function minus(NUM1 As String,NUM2 As String) As String
Declare Function       plus( NUMber1 As String  ,  NUMber2 As String ) As String

screen 19

do
   
    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)

sleep
end

'===============================================================================
'===============================================================================
'===============================================================================
'===============================================================================
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 outtext

end function
'===============================================================================
'===============================================================================

Tourist Trap
Posts: 2197
Joined: Jun 02, 2015 16:24

Re: Squares

Postby Tourist Trap » Aug 06, 2017 16:00

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 upperbound

var mult    => 4
var i   => 1234567
var 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 digits
dim 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 += 1
wend

'show matching entries
if 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 index
end if

? "end"
'(eof)
Richard
Posts: 2753
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

Postby Richard » Aug 07, 2017 2:47

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

Re: Squares

Postby Richard » Aug 07, 2017 13:41

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: 2197
Joined: Jun 02, 2015 16:24

Re: Squares

Postby Tourist Trap » Aug 07, 2017 16:46

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: 2197
Joined: Jun 02, 2015 16:24

Re: Squares

Postby Tourist Trap » Aug 07, 2017 20:19

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  => 6
const as uInteger   mult_min  => 1  ''0 would never trigger any digit size overflow
const as uInteger   mult_max  => 12 ''greater than 9 is useless
width 100, 100

'loop over digit size
var digit_size => 0
do
    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


[edit]
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: 2753
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

Postby Richard » Aug 08, 2017 6:56

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: 2197
Joined: Jun 02, 2015 16:24

Re: Squares

Postby Tourist Trap » Aug 08, 2017 20:31

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

Re: Squares

Postby Richard » Aug 08, 2017 23:53

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.

Return to “General”

Who is online

Users browsing this forum: No registered users and 3 guests