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...
generic module to add , subtract, mul 2 numbers of any size
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 
Paul Dwyer
“In nature, it’s not the strongest nor the most intelligent who survives. It’s the most adaptable to change” - Charles Darwin
“If you can't explain it to a six-year old you really don't understand it yourself.” - Albert Einstein
“In nature, it’s not the strongest nor the most intelligent who survives. It’s the most adaptable to change” - Charles Darwin
“If you can't explain it to a six-year old you really don't understand it yourself.” - Albert Einstein
final code working for me
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()
nice one for mod
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)
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)
implemented quick mod
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 "
Last edited by alokdube on Fri Oct 09, 2009 8:51 am, edited 1 time in total.
interesting
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
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
fyi
the multiply slows down because it tries to pad zeros... need to fix that bit...