PureBasic Forums - English

Posted: **Tue Jan 08, 2008 7:48 am**

one way i can think of is to break the input into sections of longint that the cpu can support and do it..
like input = x1x2x3..xn
break it into xi.xj.xk.xl.... where each is close to a sqrt(longint) so that you can multiply that chunk in 1 cycle and carry on...

Posted: **Tue Jan 08, 2008 8:50 am**

how is multiplication done in bit math using and/or/not/xor etc? it would be great if we could have an array of longs (to process on the 32bit boundary) but using bit math? not sure if this achieves anything or not. It would have a feel of not cheating though

Posted: **Tue Jan 08, 2008 8:52 am**

umm you plan to convert the whole string to binary?
mul is the same way as normal mul except it is 1 x 1 =10 (carry lookahead etc)

Posted: **Mon Jun 23, 2008 1:47 pm**

The BigDivide does not seem to work as well as the Divide and th Multiply not as well as the BigMultiply

Code: Select all

Global n2$="",n1$="" ;hold the absolute value without the sign, after padding zeros 
Global n1,n2; this holds the absolute length of the numbers after padding zeros, without the sign 
Global n1sign$,n2sign$ ; holds the + or - sign of n1 and n2 
;********do not ever access these values directly from the main program********** 
;these can be treated as global registers user by the all the to pass computed values 
; compare() function not only compares but also removes leading zeros, 
; seperates signs in the input from the abs value, and adds padding 
;these are used to pass across n1$ and n2$ and their associated properties 
;across all subroutines 
;so in other words while each procedure holds it's input as myn1$ and myn2$, 
;it can always use the global n1$ and n2$ to get back values from "compare" 


;compare returns 0 if n1>n2 , 1 if n2>n1 and -1 if n1=n2 
Procedure Compare (myn1$,myn2$) 
;1st we check for any leading 0s in myn1$ 
;PrintN("inside compare") 
;PrintN (myn1$) 
;PrintN (myn2$) 
;PrintN("=================") 
Protected flag=0 
Protected flag1=0;;keeps track if we have seen a non zero element 
Protected cnt=0;amount by which the string has to be trimmed 
Protected myn1sign$,myn2sign$ ;incase there is a sign 
Protected myn1,myn2 
Protected i 

If Mid(myn1$,1,1)="-" 
 myn1sign$="-" 
 myn1$=Right(myn1$,n1-1) 
EndIf 
myn1=Len(myn1$) 
;PrintN (Str(myn1)+"::"+Str(n1)) 
;PrintN (myn1$) 

For i=1 To myn1 
 If Mid(myn1$,i,1)="0" And (flag1=0) 
  cnt=cnt+1 
 Else 
 flag1=1 
 Break 
EndIf 
Next i 

myn1$=Right(myn1$,myn1-cnt) 
;myn1$=myn1sign$+myn1$ 
myn1=Len(myn1$) 

;PrintN (Str(myn1)+","+Str(cnt)) 
;PrintN (myn1$) 



;============================ 
;now we check for any leading 0s in myn2$ 
flag1=0 ;keeps track if we have seen a non zero element 
cnt=0;amount by which the string has to be trimmed 
myn2sign$="" ;incase there is a sign 

If Mid(myn2$,1,1)="-" 
 myn2sign$="-" 
 myn2$=Right(myn2$,myn2-1) 
EndIf 
myn2=Len(myn2$) 
;PrintN (Str(myn2)) 
;PrintN (myn2$) 

For i=1 To Len(myn2$) 
 If Mid(myn2$,i,1)="0" And (flag1=0) 
  cnt=cnt+1 
 Else 
 flag1=1 
 Break 
EndIf 
Next i 

myn2$=Right(myn2$,myn2-cnt) 
;myn2$=n2sign$+myn2$ 
myn2=Len(myn2$) 

;PrintN (Str(n2)+","+Str(cnt)) 
;PrintN (myn2$) 

;zero pads 
 If myn1>myn2 
  size=myn1 
  diff=myn1-myn2 
  For i=1 To diff 
  myn2$="0"+myn2$ 
  Next i 
 ElseIf myn2>myn1 
  size=myn2 
  diff=myn2-myn1 
  For i=1 To diff 
   myn1$="0"+myn1$ 
  Next i 
 EndIf 
;PrintN(myn1$+"::"+myn2$) 
;done with zero pads 
;PrintN("inside compare") 
;PrintN (myn1$) 
;PrintN (myn2$) 
flag=-1;the flag is 0 is abs(myn1$)>abs(myn2$) else is 1, if both are equal flag is -1 
; we now need to check which one is greater 
If myn1>myn2 
  flag=0 
ElseIf myn2>myn1 
  flag=1 
ElseIf (myn1=myn2) 
 For i = 1 To myn1 
 If Val(Mid(myn1$,i,1))>Val(Mid(myn2$,i,1)) 
 flag=0 
 Break 
 ElseIf Val(Mid(myn1$,i,1))<Val(Mid(myn2$,i,1)) 
 flag=1 
 Break 
 EndIf 
 Next i 
EndIf 
;flag stays -1 if both are equal 


;PrintN("inside compare") 
;PrintN (myn1$) 
;PrintN (myn2$) 
;PrintN (Str(flag)) 
;PrintN("=================") 

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 
If (flag=0) And (myn1sign$="")  And (myn2sign$="") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 0 

ElseIf (flag=0) And (myn1sign$="")  And (myn2sign$="-") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 0 

ElseIf (flag=0) And (myn1sign$="-")  And (myn2sign$="") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 1 

ElseIf (flag=0) And (myn1sign$="-")  And (myn2sign$="-") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 1 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 
ElseIf (flag=-1) And (myn1sign$="")  And (myn2sign$="") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn -1 

ElseIf (flag=-1) And (myn1sign$="")  And (myn2sign$="-") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 0 

ElseIf (flag=-1) And (myn1sign$="-")  And (myn2sign$="") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 1 

ElseIf (flag=-1) And (myn1sign$="-")  And (myn2sign$="-") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn -1 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 
ElseIf (flag=1) And (myn1sign$="")  And (myn2sign$="") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 1 

ElseIf (flag=1) And (myn1sign$="")  And (myn2sign$="-") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 0 

ElseIf (flag=1) And (myn1sign$="-")  And (myn2sign$="") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 1 

ElseIf (flag=1) And (myn1sign$="-")  And (myn2sign$="-") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 0 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 
EndIf 
 ;by this time myn1$ and myn2$ are of equal length in terms of string size (excluding the "-" sign) 
EndProcedure 
;============================================= 
Procedure.s Add (myn1$,myn2$) 
;PrintN ("==============================") 
;PrintN (myn1$) 
;PrintN (myn2$) 
;PrintN ("==============================") 
result=Compare (myn1$,myn2$) 
myn1$=n1$;we need to reassign these to the padded values 
myn2$=n2$ 
Protected result$="" 
Protected carry=0 
Protected size=Len(n1$) 
Protected temp_result$="" 
;PrintN ("==============================") 
;PrintN (myn1$) 
;PrintN (myn2$) 
;PrintN ("==============================") 
For i=size To 1 Step -1 
  
;PrintN(Mid(myn1$,size,1)) 
;PrintN(Mid(myn2$,size,1)) 
;PrintN("-----------------") 
 temp_result$=Str(Val(Mid(myn1$,i,1))+Val(Mid(myn2$,i,1))+carry) 
 ;PrintN(temp_result$) 
 ;PrintN("-----------------") 
 If Len(temp_result$)=2 And Not(i=1) ; if i=1 this is the 1st digit so the carry has to stick on front 
   carry=Val(Mid(temp_result$,1,1)) 
   temp_result$=Mid(temp_result$,2,1) 
 Else 
   carry=0 
 EndIf 
  
 result$=temp_result$+result$ 
  
Next i 

If result$="" 
result$="0" 
EndIf 


;PrintN ("Add:"+result$) 

ProcedureReturn result$ 

    

EndProcedure 
;============================================== 
Procedure.s Carry_propogation (myn1$,i,size) 
 ;PrintN ("myn1$:"+myn1$) 
temp_left$=Left(myn1$,i-1) 
temp_right$=Right(myn1$,size-i) 
this$="" 
 ;PrintN("temp left:"+temp_left$) 
 ;PrintN("temp right:"+temp_right$) 
If Val(Mid(myn1$,i,1))=0 ;if this zero, we have to borrow from previous and make this "9" 
 this$="9" 
 myn1$=temp_left$+this$+temp_right$ 
 ;PrintN ("myn1$:"+myn1$) 
 myn1$=Carry_propogation(myn1$,i-1,size) 
Else 
this$=Str(Val(Mid(myn1$,i,1))-1) 
myn1$=temp_left$+this$+temp_right$ 
;PrintN ("myn1$:"+myn1$) 
EndIf  
;PrintN ("myn1$:"+myn1$) 
ProcedureReturn myn1$ 

EndProcedure 
;============================================== 
Procedure.s Subtract (myn1$,myn2$) 
;PrintN ("inside subtract") 
;PrintN (myn1$) 
;PrintN (myn2$) 
;PrintN ("==============================") 
Protected carry 
Protected temp_result$ 
Protected toggle=0 ;if myn1$>=myn2$ we stay at 0 else we become 1 
Protected result=Compare(myn1$,myn2$) 
If (result=1) ; if n1$<n2$ result is 1 and so we swap myn1$ and myn2$ 
toggle=1 
myn2$=n1$ 
myn1$=n2$ 
ElseIf (result=0)Or(result=-1) 
toggle=0 
myn1$=n1$ 
myn2$=n2$ 
EndIf 

size=Len(n1$) 

result$="" 

;PrintN ("inside subtract") 
;PrintN (Str(result)) 
;PrintN (myn1$) 
;PrintN (myn2$) 
;PrintN ("==============================") 

For i=size To 1 Step -1 
carry=0 
If Val(Mid(myn1$,i,1))>=Val(Mid(myn2$,i,1)) 
 temp_result$=Str(Val(Mid(myn1$,i,1))-Val(Mid(myn2$,i,1))+carry) 
 result$=temp_result$+result$ 
 ;PrintN ("size="+Str(i)) 
 ;PrintN (result$) 
ElseIf Val(Mid(myn1$,i,1))<Val(Mid(myn2$,i,1)) 
   carry=10 
   myn1$=Carry_propogation(myn1$,i-1,size) ; carry reduction propogates from "i-1" 
   temp_result$=Str(Val(Mid(myn1$,i,1))-Val(Mid(myn2$,i,1))+carry) 
   result$=temp_result$+result$ 
   ;PrintN (result$) 
EndIf 
Next i 

;remove leading zeros 
For i=1 To Len(result$) 
 If Mid(result$,i,1)="0" And (flag=0) 
  cnt=cnt+1 
 Else 
 Break 
EndIf 
Next i 


result$=Right(result$,Len(result$)-cnt) 
;If toggle=1 
;result$="-"+result$ 
;EndIf 
If result$="" 
result$="0" 
EndIf 

;PrintN("Subtract:"+result$) 
ProcedureReturn result$ 
EndProcedure 
;=============================================== 
Procedure.s Multiply(Num1.s,Num2.s) 

Structure Bytes 
    Byte.b[0] 
EndStructure
    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
;===============================================

;compare function returns 0 if myn1>n2 and 1 if n2>n1 
;it pads the smaller number with leading 0s 
;it removes any leading 0s in the original input 
;the numbers obtained after a compare are suitable for any mathematical operation now

Procedure.s Divide (myn1$,myn2$) 
Protected sizemyn2=Len(myn2$) 

Protected result 
;this procedure divides myn1$ by myn2$ i.e myn1$/myn2$ and returns the quotient 
result=Compare (myn1$,myn2$) 
myn1$=n1$;we need to reassign these to the padded values 
myn2$=n2$ 
Protected result$="" 
;Protected carry=0 
Protected sizemyn1=Len(myn1$) 

Protected temp_divident$="" 
Protected temp_divisor_multiple$="" 
Protected quotient$="" 
Protected previous_remainder$=Left(myn1$,sizemyn2) 
Protected temp_result 
;PrintN ("myn2$:"+myn2$) 

For i= sizemyn2 To sizemyn1 
If i=sizemyn2 
temp_divident$=previous_remainder$ 
Else 
 ;we start with the part of myn1$ as long as myn2$ 
 temp_divident$=previous_remainder$+Mid(myn1$,i,1) 
EndIf 
 ;PrintN ("divident:"+temp_divident$) 
 temp_result=Compare(temp_divident$,myn2$) 
 If (temp_result=0)Or (temp_result=-1) ; if temp_divident$>=myn2$ 
  For m=1 To 9 
   temp_divisor_multiple$=Multiply (myn2$,Str(m)) 
   temp_result1=Compare(temp_divident$,temp_divisor_multiple$) 
   ;PrintN ("m="+Str(m)) 
   If temp_result1=1 
   m=m-1 
   ;PrintN ("breaking..") 
   Break 
   EndIf 
  Next m 
 Else 
 m=0 
 EndIf ; temp_result=0 or temp_result=-1 ends here 
  
 If m>9 
 m=9 
 EndIf 
  
 ;PrintN ("m="+Str(m)) 
 temp_divisor_multiple$=Multiply (myn2$,Str(m)) 
  
 quotient$=quotient$+Str(m) 
 previous_remainder$=Subtract(temp_divident$,temp_divisor_multiple$) 
 ;myn1$=LSet("",i,"0")+Right(myn1$,sizemyn1-i) 
 ;PrintN ("temp_divisor"+temp_divisor_multiple$) 
 ;PrintN("quotient$="+quotient$+";previous_remainder:"+previous_remainder$) 
  

 Next i 
n2$=previous_remainder$ 
result$=quotient$ 
;remove leading zeros 
For i=1 To Len(result$) 
 If Mid(result$,i,1)="0" And (flag=0) 
  cnt=cnt+1 
 Else 
 Break 
EndIf 
Next i 


result$=Right(result$,Len(result$)-cnt) 
ProcedureReturn result$ 
EndProcedure


; ============= Test code from here =========== 

DisableDebugger 

OpenConsole() 

  ;  Divide.s = "26098234092834075093854092383452340987340295703295702398573290457987043295783240957239032475320948799" 
   ; By.s     = "9309478523409785234085234095780329457987394752309870987" 

    ;PrintN("Divide   " + divide) 
    ;PrintN("By       " + by) 
    ;PrintN("") 
    ;PrintN(BigDivide(Divide, by )) 
    ;Input() 
num1$="1" 
For i=1 To 1500
num1$=Multiply(num1$,"244") 
;PrintN ("result:"+num1$)
Next i 
PrintN ("result:"+num1$)

num1$=Divide(num1$,"1001")
remainder$=n2$
PrintN ("result mod:"+n2$)
Input()
CloseConsole()

Posted: **Mon Jun 23, 2008 2:16 pm**

found this post on the net
Command line rulez:

read a; read e; read n; p=$[$a**$e]; echo "p=$p"; x=$[$p/$n]; m=$[$p-$n*$x];
echo $m

But you surely want to know a method for this. It's called 'square-and-
multiply', unfortunately google doesn't know much about it.
I'll try to explain.
Store e in binary representation. Store a as a start value s. Now iterate over
s the following way (along the bits of e):
If the bit is 0, just square s (s := s² % n).
If the bit is 1, also multiply it with a (s := (s² * a) % n).

Example:
a = 5, e = 9, n = 3
5^9 = 1953125, (5^9) % 3 = 2, because:
9 = (1001)bin, thus:
5(1) := 5 (= 2 % 3)
2(10) := 2² (= 1 % 3)
1(100) := 1² (= 1 % 3)
1(1001) := 1²*5 (= 2 % 3)

Posted: **Tue Aug 26, 2008 7:18 am**

added a quick mod module and modified the division a bit for faster results if the 1st parameter is less than the second or equal to the second

Code: Select all

Global n2$="",n1$="" ;hold the absolute value without the sign, after padding zeros 
Global n1,n2; this holds the absolute length of the numbers after padding zeros, without the sign 
Global n1sign$,n2sign$ ; holds the + or - sign of n1 and n2 
;********do not ever access these values directly from the main program********** 
;these can be treated as global registers user by the all the to pass computed values 
; compare() function not only compares but also removes leading zeros, 
; seperates signs in the input from the abs value, and adds padding 
;these are used to pass across n1$ and n2$ and their associated properties 
;across all subroutines 
;so in other words while each procedure holds it's input as myn1$ and myn2$, 
;it can always use the global n1$ and n2$ to get back values from "compare" 

Structure Bytes 
    Byte.b[0] 
EndStructure

;compare returns 0 if n1>n2 , 1 if n2>n1 and -1 if n1=n2 
Procedure Compare (myn1$,myn2$) 
;1st we check for any leading 0s in myn1$ 
;PrintN("inside compare") 
;PrintN (myn1$) 
;PrintN (myn2$) 
;PrintN("=================") 
Protected flag=0 
Protected flag1=0;;keeps track if we have seen a non zero element 
Protected cnt=0;amount by which the string has to be trimmed 
Protected myn1sign$,myn2sign$ ;incase there is a sign 
Protected myn1,myn2 
Protected i 

If Mid(myn1$,1,1)="-" 
 myn1sign$="-" 
 myn1$=Right(myn1$,n1-1) 
EndIf 
myn1=Len(myn1$) 
;PrintN (Str(myn1)+"::"+Str(n1)) 
;PrintN (myn1$) 

For i=1 To myn1 
 If Mid(myn1$,i,1)="0" And (flag1=0) 
  cnt=cnt+1 
 Else 
 flag1=1 
 Break 
EndIf 
Next i 

myn1$=Right(myn1$,myn1-cnt) 
;myn1$=myn1sign$+myn1$ 
myn1=Len(myn1$) 

;PrintN (Str(myn1)+","+Str(cnt)) 
;PrintN (myn1$) 



;============================ 
;now we check for any leading 0s in myn2$ 
flag1=0 ;keeps track if we have seen a non zero element 
cnt=0;amount by which the string has to be trimmed 
myn2sign$="" ;incase there is a sign 

If Mid(myn2$,1,1)="-" 
 myn2sign$="-" 
 myn2$=Right(myn2$,myn2-1) 
EndIf 
myn2=Len(myn2$) 
;PrintN (Str(myn2)) 
;PrintN (myn2$) 

For i=1 To Len(myn2$) 
 If Mid(myn2$,i,1)="0" And (flag1=0) 
  cnt=cnt+1 
 Else 
 flag1=1 
 Break 
EndIf 
Next i 

myn2$=Right(myn2$,myn2-cnt) 
;myn2$=n2sign$+myn2$ 
myn2=Len(myn2$) 

;PrintN (Str(n2)+","+Str(cnt)) 
;PrintN (myn2$) 

;zero pads 
 If myn1>myn2 
  size=myn1 
  diff=myn1-myn2 
  For i=1 To diff 
  myn2$="0"+myn2$ 
  Next i 
 ElseIf myn2>myn1 
  size=myn2 
  diff=myn2-myn1 
  For i=1 To diff 
   myn1$="0"+myn1$ 
  Next i 
 EndIf 
;PrintN(myn1$+"::"+myn2$) 
;done with zero pads 
;PrintN("inside compare") 
;PrintN (myn1$) 
;PrintN (myn2$) 
flag=-1;the flag is 0 is abs(myn1$)>abs(myn2$) else is 1, if both are equal flag is -1 
; we now need to check which one is greater 
If myn1>myn2 
  flag=0 
ElseIf myn2>myn1 
  flag=1 
ElseIf (myn1=myn2) 
 For i = 1 To myn1 
 If Val(Mid(myn1$,i,1))>Val(Mid(myn2$,i,1)) 
 flag=0 
 Break 
 ElseIf Val(Mid(myn1$,i,1))<Val(Mid(myn2$,i,1)) 
 flag=1 
 Break 
 EndIf 
 Next i 
EndIf 
;flag stays -1 if both are equal 


;PrintN("inside compare") 
;PrintN (myn1$) 
;PrintN (myn2$) 
;PrintN (Str(flag)) 
;PrintN("=================") 

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 
If (flag=0) And (myn1sign$="")  And (myn2sign$="") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 0 

ElseIf (flag=0) And (myn1sign$="")  And (myn2sign$="-") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 0 

ElseIf (flag=0) And (myn1sign$="-")  And (myn2sign$="") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 1 

ElseIf (flag=0) And (myn1sign$="-")  And (myn2sign$="-") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 1 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 
ElseIf (flag=-1) And (myn1sign$="")  And (myn2sign$="") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn -1 

ElseIf (flag=-1) And (myn1sign$="")  And (myn2sign$="-") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 0 

ElseIf (flag=-1) And (myn1sign$="-")  And (myn2sign$="") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 1 

ElseIf (flag=-1) And (myn1sign$="-")  And (myn2sign$="-") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn -1 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 
ElseIf (flag=1) And (myn1sign$="")  And (myn2sign$="") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 1 

ElseIf (flag=1) And (myn1sign$="")  And (myn2sign$="-") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 0 

ElseIf (flag=1) And (myn1sign$="-")  And (myn2sign$="") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 1 

ElseIf (flag=1) And (myn1sign$="-")  And (myn2sign$="-") 
n1$=myn1$ 
n2$=myn2$ 
n1=Len(myn1$) 
n2=Len(myn2$) 
n1sign$=myn1sign$ 
n2sign$=myn2sign$ 
ProcedureReturn 0 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 
EndIf 
 ;by this time myn1$ and myn2$ are of equal length in terms of string size (excluding the "-" sign) 
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 1 
    ElseIf Biglen < SmallLen 
        ProcedureReturn 0 
    Else ;same len, string compare 
        If BiggerNum > SmallerNum 
            ProcedureReturn 1 
        ElseIf BiggerNum = SmallerNum
            ProcedureReturn -1
        Else
            ProcedureReturn 0
        EndIf        
    EndIf 

EndProcedure 

Procedure.s Add (myn1$,myn2$) 
;PrintN ("==============================") 
;PrintN (myn1$) 
;PrintN (myn2$) 
;PrintN ("==============================") 
result=Compare (myn1$,myn2$) 
myn1$=n1$;we need to reassign these to the padded values 
myn2$=n2$ 
Protected result$="" 
Protected carry=0 
Protected size=Len(n1$) 
Protected temp_result$="" 
;PrintN ("==============================") 
;PrintN (myn1$) 
;PrintN (myn2$) 
;PrintN ("==============================") 
For i=size To 1 Step -1 
  
;PrintN(Mid(myn1$,size,1)) 
;PrintN(Mid(myn2$,size,1)) 
;PrintN("-----------------") 
 temp_result$=Str(Val(Mid(myn1$,i,1))+Val(Mid(myn2$,i,1))+carry) 
 ;PrintN(temp_result$) 
 ;PrintN("-----------------") 
 If Len(temp_result$)=2 And Not(i=1) ; if i=1 this is the 1st digit so the carry has to stick on front 
   carry=Val(Mid(temp_result$,1,1)) 
   temp_result$=Mid(temp_result$,2,1) 
 Else 
   carry=0 
 EndIf 
  
 result$=temp_result$+result$ 
  
Next i 

If result$="" 
result$="0" 
EndIf 


;PrintN ("Add:"+result$) 

ProcedureReturn result$ 

    

EndProcedure 
;============================================== 
Procedure.s Carry_propogation (myn1$,i,size) 
 ;PrintN ("myn1$:"+myn1$) 
temp_left$=Left(myn1$,i-1) 
temp_right$=Right(myn1$,size-i) 
this$="" 
 ;PrintN("temp left:"+temp_left$) 
 ;PrintN("temp right:"+temp_right$) 
If Val(Mid(myn1$,i,1))=0 ;if this zero, we have to borrow from previous and make this "9" 
 this$="9" 
 myn1$=temp_left$+this$+temp_right$ 
 ;PrintN ("myn1$:"+myn1$) 
 myn1$=Carry_propogation(myn1$,i-1,size) 
Else 
this$=Str(Val(Mid(myn1$,i,1))-1) 
myn1$=temp_left$+this$+temp_right$ 
;PrintN ("myn1$:"+myn1$) 
EndIf  
;PrintN ("myn1$:"+myn1$) 
ProcedureReturn myn1$ 

EndProcedure 
;============================================== 
Procedure.s Subtract (myn1$,myn2$) 
;PrintN ("inside subtract") 
;PrintN (myn1$) 
;PrintN (myn2$) 
;PrintN ("==============================") 
Protected carry 
Protected temp_result$ 
Protected toggle=0 ;if myn1$>=myn2$ we stay at 0 else we become 1 
Protected result=Compare(myn1$,myn2$) 
If (result=1) ; if n1$<n2$ result is 1 and so we swap myn1$ and myn2$ 
toggle=1 
myn2$=n1$ 
myn1$=n2$ 
ElseIf (result=0)Or(result=-1) 
toggle=0 
myn1$=n1$ 
myn2$=n2$ 
EndIf 

size=Len(n1$) 

result$="" 

;PrintN ("inside subtract") 
;PrintN (Str(result)) 
;PrintN (myn1$) 
;PrintN (myn2$) 
;PrintN ("==============================") 

For i=size To 1 Step -1 
carry=0 
If Val(Mid(myn1$,i,1))>=Val(Mid(myn2$,i,1)) 
 temp_result$=Str(Val(Mid(myn1$,i,1))-Val(Mid(myn2$,i,1))+carry) 
 result$=temp_result$+result$ 
 ;PrintN ("size="+Str(i)) 
 ;PrintN (result$) 
ElseIf Val(Mid(myn1$,i,1))<Val(Mid(myn2$,i,1)) 
   carry=10 
   myn1$=Carry_propogation(myn1$,i-1,size) ; carry reduction propogates from "i-1" 
   temp_result$=Str(Val(Mid(myn1$,i,1))-Val(Mid(myn2$,i,1))+carry) 
   result$=temp_result$+result$ 
   ;PrintN (result$) 
EndIf 
Next i 

;remove leading zeros 
For i=1 To Len(result$) 
 If Mid(result$,i,1)="0" And (flag=0) 
  cnt=cnt+1 
 Else 
 Break 
EndIf 
Next i 


result$=Right(result$,Len(result$)-cnt) 
;If toggle=1 
;result$="-"+result$ 
;EndIf 
If result$="" 
result$="0" 
EndIf 

;PrintN("Subtract:"+result$) 
ProcedureReturn result$ 
EndProcedure 
;=============================================== 
Procedure.s Multiply (myn1$,myn2$) 
result=Compare (myn1$,myn2$) 
myn1$=n1$;we need to reassign these to the padded values 
myn2$=n2$ 
Protected result$="" 
Protected carry=0 
Protected size=Len(n1$) 
Protected temp_result$="" 
Protected line_result$="0" 
For i=size To 1 Step -1; this goes across digits of myn2$ 
temp_result$="" 
  For j=size To 1 Step -1; this goes across digits of myn1$ 
   local_result$=Str(Val(Mid(myn2$,i,1))*Val(Mid(myn1$,j,1))+carry) 
    
   If Len(local_result$)=2 And Not(j=1) ; if j=1 this is the 1st digit so carry can stay as it is 
   carry=Val(Mid(local_result$,1,1)) 
   local_result$=Mid(local_result$,2,1) 
   Else 
   carry=0 
   EndIf 
    
    
   temp_result$=local_result$+temp_result$ 
    
  Next j 
  temp_result$=LSet(temp_result$,Len(temp_result$)+size-i,"0") 
  ;PrintN("temp_result$:"+temp_result$) 
  line_result$=Add(line_result$,temp_result$) 
  ;PrintN("line_result$:"+line_result$) 
Next i 

result$=line_result$ 
ProcedureReturn result$ 

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


;compare function returns 0 if myn1>n2 and 1 if n2>n1 
;it pads the smaller number with leading 0s 
;it removes any leading 0s in the original input 
;the numbers obtained after a compare are suitable for any mathematical operation now

Procedure.s Divide (myn1$,myn2$) 
Protected sizemyn2=Len(myn2$) 

Protected result 
;this procedure divides myn1$ by myn2$ i.e myn1$/myn2$ and returns the quotient 
result=Compare (myn1$,myn2$) 

If (result=0)

myn1$=n1$;we need to reassign these to the padded values 
myn2$=n2$ 
Protected result$="" 
;Protected carry=0 
Protected sizemyn1=Len(myn1$) 

Protected temp_divident$="" 
Protected temp_divisor_multiple$="" 
Protected quotient$="" 
Protected previous_remainder$=Left(myn1$,sizemyn2) 
Protected temp_result 
;PrintN ("myn2$:"+myn2$) 

For i= sizemyn2 To sizemyn1 
If i=sizemyn2 
temp_divident$=previous_remainder$ 
Else 
 ;we start with the part of myn1$ as long as myn2$ 
 temp_divident$=previous_remainder$+Mid(myn1$,i,1) 
EndIf 
 ;PrintN ("divident:"+temp_divident$) 
 temp_result=Compare(temp_divident$,myn2$) 
 If (temp_result=0)Or (temp_result=-1) ; if temp_divident$>=myn2$ 
  For m=1 To 9 
   temp_divisor_multiple$=BigMultiply (myn2$,Str(m)) 
   temp_result1=Compare(temp_divident$,temp_divisor_multiple$) 
   ;PrintN ("m="+Str(m)) 
   If temp_result1=1 
   m=m-1 
   ;PrintN ("breaking..") 
   Break 
   EndIf 
  Next m 
 Else 
 m=0 
 EndIf ; temp_result=0 or temp_result=-1 ends here 
  
 If m>9 
 m=9 
 EndIf 
  
 ;PrintN ("m="+Str(m)) 
 temp_divisor_multiple$=BigMultiply (myn2$,Str(m)) 
  
 quotient$=quotient$+Str(m) 
 previous_remainder$=Subtract(temp_divident$,temp_divisor_multiple$) 
 ;myn1$=LSet("",i,"0")+Right(myn1$,sizemyn1-i) 
 ;PrintN ("temp_divisor"+temp_divisor_multiple$) 
 ;PrintN("quotient$="+quotient$+";previous_remainder:"+previous_remainder$) 
  

 Next i 
n2$=previous_remainder$ 
result$=quotient$ 

ElseIf (result=1)
result$="0"
n2$=myn1$
;PrintN(n2$)

ElseIf (result=-1)
result$="1"
n2$="0"

EndIf

;remove leading zeros 
For i=1 To Len(result$) 
 If Mid(result$,i,1)="0" And (flag=0) 
  cnt=cnt+1 
 Else 
 Break 
EndIf 
Next i 


result$=Right(result$,Len(result$)-cnt) 
ProcedureReturn result$ 
EndProcedure

Procedure.s HextoDecimal(myn1$)
myn1$=LCase(myn1$)
myn1$=RemoveString(myn1$," ")
result$=""
Dim digit.s(1)

For i=1 To Len(myn1$) Step 2

For j=0 To 1 Step 1

digit(j)=Mid(myn1$,i+j,1)

Select digit(j)

Case "0","1","2","3","4","5","6","7","8","9"
result$=result$+"0"+digit(j)

Case "a"
result$=result$+"10"

Case "b"
result$=result$+"11"

Case "c"
result$=result$+"12"

Case "d"
result$=result$+"13"

Case "e"
result$=result$+"14"

Case "f"
result$=result$+"15"

EndSelect

Next j

Next i


ProcedureReturn(result$)
 

EndProcedure

Procedure.s Power(myn1$,myn2$)
result$="1"
For i=1 To Val(myn2$)
result$=BigMultiply(result$,myn1$)
Next i
ProcedureReturn (result$)
EndProcedure

Procedure.s FastMod(myn1$,e$,myn2$)
a$=myn1$
Divide(myn1$,myn2$)
temp$=n2$
myn1$=n2$
i$="1"
While Not(i$=e$)
Divide(BigMultiply(myn1$,temp$),myn2$)
myn1$=n2$
;PrintN (myn1$)
i$=BigAdd(i$,"1")
Wend
;Divide(BigMultiply(myn1$,myn1$),myn2$)
;myn1$=n2$
ProcedureReturn myn1$
EndProcedure

Procedure.s QuickMod(myn1$,e$,myn2$) ; takes only binary input
a$=myn1$
PrintN(Divide(myn1$,myn2$))
myn1$=n2$


For i = 2 To Len (e$)
PrintN(myn1$)
If Mid(e$,i,1)="0"
myn1$=Power(myn1$,"2")
Divide(myn1$,myn2$)
myn1$=n2$
EndIf

If Mid(e$,i,1)="1"
myn1$=Power(myn1$,"2")
myn1$=BigMultiply(myn1$,a$)
Divide(myn1$,myn2$)
myn1$=n2$
EndIf


Next i

ProcedureReturn myn1$
EndProcedure

; ============= Test code from here =========== 

;DisableDebugger 

OpenConsole() 

 
e$="01 00 01"
;
e$=HexToDecimal(e$)
;PrintN(e$)
;e$="10000"
e$=Bin(Val(e$))
PrintN(e$)


n$="ca 0a 7a 0c 99 3f 0c d2 f4 50 9a 30 de 7c b2 51 c4 10 ab db 70 91 a7 5f 34 2f 55 6c cb 19 91 c5 56 4d 59 3c 7c 5e bb 29 a6 8a bb f6 b9 4b de 5c 02 6f cc 70 4e db d9 ce 2f 64 9c b0 c1 bd 0c 97 4d 7f 2f ed c8 7d 7a 24 2f f1 91 db 32 da 91 60 0b 80 16 ed f3 93 d0 d5 7a c3 3d e4 e3 84 4f de 09 30 e1 3f f6 47 fd bb 6d f6 8e 7c 40 dd c4 74 aa ad 58 a3 59 fc bc 4d d0 04 45 de 0c a8 83 33 "
n$=HexToDecimal(n$)

PrintN(n$)


PrintN("starting mod")
;q$="1"


result$=QuickMod("2",e$,n$)

;result$=Power("2","2048");0001")

PrintN("mod:"+result$)

Result=compare(n$,result$)
PrintN(Str(result))

;Divide(result$,n$)

;result$=n2$


;result$="4473157005184325857835492268009548193145082438786232734567544032750179119598641102138300771551427574487234704319109129100696554963029380119134391912044900766149617830312388071048242746213680432110978862239317811429072338093199395413440726024222853675596956451853001350150417691539987086679483944672224256918743625155128106318786020832185799094893417724969799761379004008532889849326917058231715879188235077319156786150928234301694821299391869561323593240966093180064894399751508514283272474766853981740324"

;PrintN("divide:"+result$)

;result$=Power(result$,"10");00")

;PrintN("power:"+result$)

;Divide(result$,n$)

;e$=Subtract(e$,"1")

;PrintN(e$)

;Until e$="0"

;PrintN("divide:"+result$)
Input()
CloseConsole()





;Exponent (24 bits):
;01 00 01 "

Posted: **Tue Oct 21, 2008 7:50 am**

the difference in the 2 multiply libraries is nice:
1. if one has 1245*21
what I do is:
1245*1 = 1245--a
1245*2=2490(0) the zero comes from the carry--b
total(a+b)=26145

i only propogate the carry to the same line
Paul does it differently
paul gets
1245*1
1245
then kind of does:
1245+
(1245*2)10
hence we get digit wise
1245+100(which is 5x2(0)=10(0)) , 1345+800(which is 4*20(0)), and so on...2145+4000,6145+20000=26145

the result does come faster Paul's way

Posted: **Tue Jul 07, 2009 10:01 am**

the multiply slows down because it tries to pad zeros... need to fix that bit...

PureBasic Forums - English

generic module to add , subtract, mul 2 numbers of any size

final code working for me

nice one for mod

implemented quick mod

interesting

fyi