IncludePath #PB_Compiler_File + "\.." 
XIncludeFile "string.pbi" ; F:\Programming\PureBasicCode\Includes\
;XIncludeFile "F:\Programming\PureBasicCode\Includes\BigInt.pbi"

;=======================================================================

Structure Bytes 
    Byte.b[0] 
EndStructure

;=======================================================================

Declare.l IsBiggerInt(BiggerNum.s, SmallerNum.s )
Declare.s BigDivide(DivThis.s, byThis.s)
Declare.s BigMultiply(Num1.s,Num2.s)
Declare.s BigSubtract(Num1.s, Num2.s) ; Answer = Num1 - Num2 (negative output not handled yet)
Declare.s BigAdd(Num1.s, Num2.s)
Declare.s BigSquared(Num.s)
Declare.s BigPow(Num.s, pow.l)
Declare.s BigMod(DivThis.s, byThis.s)
Declare.l GetBiggestSqr(Num.s) ; returns largest 2^x that fits the number (eg 7 for a number over 128 under 512)
Declare.s BinBigNum(DecNum.s)  ;return binary
Declare.s bPow(x.s, n.s) ;a different pow function, can probably make N a quad fine, might be faster than bigpow()
Declare.s ModPow(bNum.s, bExp.s, bMod.s)

;=======================================================================


Procedure.s BigSquared(Num.s)

    carry.l = 0

    Num1Len = Len(num)
    Num2len = Num1Len
    
    AnswerLen = Num1len + Num2len ;+1
    
    Dim BCD1.l(Answerlen)
    Dim BCD2.l(Answerlen)
    Dim BCDA.l(Answerlen)
  
    ;Get Data out of string
    *BytePtr1.Bytes = @Num
    *BytePtr2.Bytes = @Num
    
    For i = 1 To Num1len 
        ;bcd1(i) = Val(Mid(Num1,Num1len - i +1 ,1))
        bcd1(i) = *BytePtr1\Byte[Num1len - i] -48
        bcd2(i) = bcd1(i)
    Next
    
    ;multiply
    For L1.l = 1 To Num1len    ;lower number
        carry = 0
        Digit.l = L1;1      
        For L2.l = 1 To Num2len  ;upper number
            BCDA(Digit) + (BCD1(L1) * BCD2(L2)) + carry
            carry = Int(BCDA(Digit) / 10)  ;int()
            BCDA(Digit) = BCDA(Digit) % 10
            Digit + 1    
        Next
                              
        If carry
            BCDA(Digit) = Carry
        EndIf                               
    Next
      
    ; set size
    Answer.s = ""

    For i = AnswerLen To 1 Step -1
        If i = answerlen And bcda(i) = 0
            ;skip trailing 0
        Else
            Answer = Answer + Str(BCDA(i))
        EndIf  
    Next

    ProcedureReturn Answer
    
EndProcedure

Procedure.s BigAdd(Num1.s, Num2.s)

    Carry.b = 0
    Num1Len = Len(num1)
    Num2Len = Len(num2)
    If Num1len > Num2Len
        AnswerLen = Num1len +1
    Else
        AnswerLen = Num2len + 1
    EndIf
    
    Dim BCD1.b(Answerlen)
    Dim BCD2.b(Answerlen)
    Dim BCDA.b(Answerlen)
    
    ;Get Data out of string
    
    For i = 1 To Num1len 
        bcd1(i) = Val(Mid(Num1,Num1len - i +1 ,1))
    Next

    For i = 1 To Num2len 
        bcd2(i) = Val(Mid(Num2,Num2len - i +1,1))
    Next    
       
    ;add
    For i = 1 To Answerlen   
        BCDA(i) = bcd1(i) + bcd2(i) + Carry
        If BCDA(i) > 9
            BCDA(i) - 10
            carry = 1
        Else
            carry = 0
        EndIf
    Next
    
    Answer.s = ""

    For i = AnswerLen To 1 Step -1
        If i = answerlen And bcda(i) = 0
            ;skip trailing 0
        Else
            Answer = Answer + Str(BCDA(i))
        EndIf
        
    Next
    
    ProcedureReturn Answer
    
EndProcedure

Procedure.s BigSubtract(Num1.s, Num2.s) ; Answer = Num1 - Num2 (negative output not handled yet)

    Carry.b = 0
    Num1Len = Len(num1)
    Num2Len = Len(num2)
    If Num1len > Num2Len
        AnswerLen = Num1len +1
    Else
        AnswerLen = Num2len + 1
    EndIf
    
    Dim BCD1.b(Answerlen)
    Dim BCD2.b(Answerlen)
    Dim BCDA.b(Answerlen)
    
    ;Get Data out of string
    
    For i = 1 To Num1len 
        bcd1(i) = Val(Mid(Num1,Num1len - i +1 ,1))
    Next

    For i = 1 To Num2len 
        bcd2(i) = Val(Mid(Num2,Num2len - i +1,1))
    Next   
       
    ;add
    For i = 1 To Answerlen   
        BCDA(i) = bcd1(i) - bcd2(i) - Carry
        If BCDA(i) < 0
            BCDA(i) + 10
            carry = 1
        Else
            carry = 0
        EndIf
    Next
    
    Answer.s = ""
    
    StringStart.l = #True

    For i = AnswerLen To 1 Step -1
        If StringStart = #True And bcda(i) = 0  ;If i = answerlen And bcda(i) = 0
            ;skip trailing 0
        Else
            Answer = Answer + Str(BCDA(i))
            StringStart = #False
        EndIf        
    Next    
   
    ProcedureReturn Answer

EndProcedure

Procedure.s BigMultiply(Num1.s,Num2.s)

    carry.l = 0

    Num1Len = Len(num1)
    Num2Len = Len(num2)
    
    AnswerLen = Num1len + Num2len ;+1
    
    Dim BCD1.b(Answerlen)
    Dim BCD2.b(Answerlen)
    Dim BCDA.c(Answerlen)
    
    ;Get Data out of string
    *BytePtr1.Bytes = @Num1
    *BytePtr2.Bytes = @Num2 
    
    For i = 1 To Num1len 
        bcd1(i) = *BytePtr1\Byte[Num1len - i] -48
    Next

    For i = 1 To Num2len 
        bcd2(i) = *BytePtr2\Byte[Num2len - i] -48
    Next

    ;multiply
    
    For L1.l = 1 To Num1len    ;lower number
        carry = 0
        Digit.l = L1;1      
        For L2.l = 1 To Num2len  ;upper number
            BCDA(Digit) + (BCD1(L1) * BCD2(L2)) + carry
            carry = BCDA(Digit) / 10  ;int()
            BCDA(Digit) = BCDA(Digit) % 10
            Digit + 1    
        Next
                              
        If carry
            BCDA(Digit) = Carry
        EndIf                               
    Next
      
    ; set size
   Answer.s = RSet(Chr(0), AnswerLen,Chr(0))

    *AnsPtr.Bytes = @Answer

    For i = AnswerLen To 1 Step -1
        *AnsPtr\byte[AnswerLen - i ] = BCDA(i) + 48
    Next
    
    If Left(Answer,1) = "0"
        Answer = Right(answer,AnswerLen-1)
    EndIf

    ProcedureReturn Answer
    
EndProcedure

Procedure.s BigPow(Num.s, pow.l)

    If pow = 1 ;
        ProcedureReturn num
    ElseIf pow = 2
        ProcedureReturn BigMultiply(Num,num)
    ElseIf pow = 3
        ProcedureReturn BigMultiply(Num, BigPow(Num,2))
    Else
        
        
        If pow % 2 = 0
            ProcedureReturn BigMultiply(BigPow(Num,pow / 2), BigPow(Num,pow / 2))  
        Else
            ProcedureReturn BigMultiply(BigMultiply(BigPow(Num,pow / 2), BigPow(Num,pow / 2)),num)  
        EndIf
    EndIf
    
EndProcedure

Procedure.l GetBiggestSqr(Num.s) ; returns largest 2^x that fits the number (eg 7 for a number over 128 under 512)

    Divizor.s = "2"
    Exponent.l = 1
    
    DivTotal.s = "1"
    
    While IsBiggerInt(Num,DivTotal)  Or  Num = DivTotal  
        DivTotal = BigPow(Divizor, Exponent)
        Exponent = Exponent + 1   
    Wend
    
    Exponent = Exponent - 2
    DivTotal = BigPow(Divizor, Exponent)    

    ProcedureReturn Exponent ;DivTotal
    
EndProcedure

Procedure.s BinBigNum(DecNum.s)  ;return binary
  
    If Len(DecNum) < 3
        ProcedureReturn Bin(Val(DecNum))
    EndIf
      
    BinStr.s = ""    
    BiggestSqr.l = GetBiggestSqr(DecNum)
     
    For i = BiggestSqr To 1 Step -1
    
        DivTotal.s = BigPow("2",i)
        ;Debug DivTotal
        ;Debug DecNum
        If IsBiggerInt(DivTotal,DecNum)
            BinStr = BinStr + "0"           
        Else
            BinStr = BinStr + "1"  
            DecNum = bigsubtract(DecNum,DivTotal)
        EndIf           
    Next

    ; catch last 0/1 as pow("2",0) fails (bug)
    If DecNum = "2" Or DecNum = "" Or DecNum = "0"
        BinStr = BinStr + "0"
    Else
        BinStr = BinStr + "1"
    EndIf
    
    ProcedureReturn BinStr

EndProcedure

Procedure.l IsBiggerInt(BiggerNum.s, SmallerNum.s ) ;returns true if first int is bigger

    Biglen.l = Len(BiggerNum)
    SmallLen.l = Len(SmallerNum)
    
    If Biglen > SmallLen
        ProcedureReturn #True
    ElseIf Biglen < SmallLen
        ProcedureReturn #False
    Else ;same len, string compare
        If BiggerNum > SmallerNum
            ProcedureReturn #True
        Else
            ProcedureReturn #False
        EndIf       
    EndIf 

EndProcedure

Procedure.s BigDivide(DivThis.s, byThis.s)  ; DivThis / byThis (First param should be bigger or result is zero)
   
    Define Result.s , divisorInc.l
    
    DivThislen.l = Len(DivThis)
    byThisLen.l = Len(byThis)
    
    NewDivisor.s = byThis
    NewDivLen.l = byThisLen
    
    If IsBiggerInt(byThis, DivThis)
        ProcedureReturn "0"
    EndIf
    
    DifLen = DivThislen - NewDivLen

    If diflen > 0 
    
        divisorInc = Val(Left(DivThis,1)) / Val(Left(byThis,1)) -1
        If divisorInc = < 1
            divisorInc = 1
        EndIf
                
        NewDivisor = BigMultiply(NewDivisor, Str(divisorInc) + string("0",DifLen-1))       
        NewDivLen = Len(NewDivisor)
        Result =  BigAdd(Result, Str(divisorInc) + string("0",DifLen-1))
        ; subtract calced piece
        DivThis = BigSubtract(DivThis, NewDivisor)
        DivThislen = Len(DivThis) 
        
        result = bigadd(result,BigDivide(DivThis.s, byThis.s)) 
    Else
    
        For i = 2 To 10 
            If IsBiggerInt(BigMultiply(Str(i),byThis),DivThis)
                result = Str(i-1)
                Break
            EndIf    
        Next
    
    EndIf
   
    ProcedureReturn(result)


EndProcedure

Procedure.s BigMod(DivThis.s, byThis.s)

    Divisor.s = BigDivide(DivThis, byThis)
    Multiplied.s = bigMultiply(byThis,Divisor)
    RetVal.s = bigSubtract(DivThis,Multiplied)
    
    If RetVal = "" 
        RetVal = "0"
    EndIf
    
    ProcedureReturn RetVal

EndProcedure

Procedure.s bPow(x.s, n.s) ;a different pow function, can probably make N a quad fine, might be faster than bigpow()

    i.s = n
    y.s = "1"
    z.s = x

    If n = "0"
        ProcedureReturn "1"
    Else   
        While i <> "0"
            
            If Val(Right(i,1)) % 2 = 1 ;is odd
                y = bigmultiply(y,z)
                i = bigsubtract(i , "1")
                
            EndIf
            z = bigMultiply(z,z)
            i = bigdivide(i,"2")
        Wend   
    EndIf
    
    ProcedureReturn y

EndProcedure

Procedure.s ModPow(bNum.s, bExp.s, bMod.s)

    ; returns big num of: bNum^bExp % bMod

    Result.s = "1"
    BinNum.s = BinBigNum(bExp)
    BitCount.l = 1
    TotalBits = Len(BinNum)
    
    For BitCount = 1 To TotalBits
    
        If Mid(BinNum,TotalBits - BitCount+1,1) = "1"
            Result = BigMod(BigMultiply(Result,bNum),bMod)
        EndIf
    
        bNum = BigMod(BigMultiply(bNum,bNum),bMod)
    
    Next
    
    ProcedureReturn Result   

EndProcedure
; IDE Options = PureBasic 4.20 (Windows - x86)
; CursorPosition = 24
; FirstLine = 11
; Folding = Ag-