PureBasic Forums - English

Posted: **Thu Jan 03, 2008 8:53 am**

Here is something I wrote which can add subtract, multiply 2 integer numbers of any size (not restricted by the size of the longest register etc)
I wanted to make this into a generic calculator/math library which can be used for all sorts of computations, without running into floating point issues and rounding errors.

Right now it works with positive inputs, will be adding support for negative inputs as well as well as support for Mod and Division in a while,
Please feel free to let me know any tricks you may have to achieve the same

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


;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




num1$="00000000000005000"
num2$="000020"
OpenConsole()
PrintN ("num1$=" +num1$ + ";num2$=" + num2$)
;Compare (num1$,num2$)
;Result$= Add(n1$,n2$)
;PrintN ("Result::"+Str(result))
result$=Multiply(num1$,num2$)
PrintN ("Multiply::"+result$)
Input()
num2$=num1$
num1$=result$

num1=Len(num1$)
num2=Len(num2$)
;PrintN (num1$+"::"+num2$)
result$=Add(num1$,num2$)
PrintN ("addition::"+result$)
;PrintN (Str(Val("00100")))
;we compute 100! now
fact$="1"
For i=1 To 100
fact$=Multiply(fact$,Str(i))
Next i

Input()
CloseConsole()

Posted: **Thu Jan 03, 2008 11:14 am**

There's quite a bit of code around if you are interested.

Quite a few people were playing with http://projecteuler.net/index.php?section=problems earlier in the year and there's a thread in the coding section called Project Euler ( http://www.purebasic.fr/english/viewtopic.php?t=26985 ) where people were posting lots of functions to do things like this. There was a real need to optimise to get the problems out in the time limits. If you are interested in building a math lib there would be quite a bit of code there. If you are looking to give your functions a test drive you could try it out with some of those questions and see how it stacks up. Quite a bit of the code I'd used up till playing with those problems I ended up chucking as they just didn't cut it performance wise.... and it was a lot of fun

Posted: **Thu Jan 03, 2008 11:19 am**

well I ran some 70-100 digit additions, subtractions, multiplications and on my crummy little laptop the answers pop up fast enough.
It is not optimized code, I havent really touched assembler for a long time... I just wanted to see what a commercial grade CPU does with this kind of stuff and it seems fast enough,

heck if it can parse web pages and all the javascript in it, this is nothing

Right now I am just trying to get this working, if nothing else, I can dump it as a standalone machine somewhere which can keep doing nothing but this

thanks for your inputs though, euler seems interesting

Posted: **Thu Jan 03, 2008 11:32 am**

The algorithms are pretty simple

i just do everything digitwise, given 2 numbers a and b (a1a2..an) and (b1b2..bn) represent the digits

so addition is
a1 a2 a3 ..an
b1 b2 b3 ..bn
==========
sum(an+bn) carry goes forward
and so on

likewise for subtraction where the carry propogates backwards
likewise for multiplication, take eash digit from b and multiply it with digits of a and then keep adding the line totals per digit to the next digits results and so on, the way it is manually done

if nothing else, it is the infinite algo

, will probably slow down for very very very very large numbers but will always work for any input

Posted: **Thu Jan 03, 2008 1:06 pm**

For a format I went with a 1 byte version (as apposed to 4 bit version) of this http://en.wikipedia.org/wiki/Binary-coded_decimal

Dishing up some code from August...
I'm not sure if I supported or needed to support negative number then... can't remember but I'll post what I had anyway.

Code: Select all


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

    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 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) = Val(Mid(Num1,Num1len - i +1 ,1))
        bcd1(i) = *BytePtr1\Byte[Num1len - i] -48
    Next

    For i = 1 To Num2len 
        ;bcd2(i) = Val(Mid(Num2,Num2len - i +1,1))
        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
        ;If i = answerlen And bcda(i) = 0
        
            ;skip trailing 0
      ;  Else
            ;Answer = Answer + Str(BCDA(i))
            ;Debug BCDA(i); + 48
            
        ;EndIf  
    Next
    
    If Left(Answer,1) = "0"
        Answer = Right(answer,AnswerLen-1)
    EndIf

    ProcedureReturn Answer
    
EndProcedure

Posted: **Thu Jan 03, 2008 1:49 pm**

so what does BCDA do? is it a generic function? eitherways at BCD level too, though if it is a register/assembly instruction, it may be faster, it would do exactly something similar... add digit wise, or if there is an equivalent cpu op code, do it via multiple chips in exactly the same way.

Posted: **Thu Jan 03, 2008 2:01 pm**

BCD is just an array that holds a byte for each number.

so 50,001 would be an array BCD() with numbers 5,0,0,0,1 in it. The reason I found this idea useful is that it means that you can do most of the math part without any string conversions which is what slows everything down. So you do one conversion at the start to an array of numbers in binary-coded-decimal format (BCD) and do all your work then convert back at the end.

If rather than doing a few sums with big numbers you need to do lots of sums it might be better to change the functions so that they pass arrays arround so that there's even less string conversion.

BCDA() is the BCD array where I'm putting the Answer

I hope I'm not generalising but I notice that you are from India. I work with a lot of people here in tokyo who are from India who do development work and I've noticed that they have excellent arithmatic skills and all sorts of "tricks" (not the right word, maybe "shortcuts" is better) for doing sums in their heads quickly etc. The way I have multiplication is the same as how I do it on paper, I'd be very interested to know other ways to do this and see them in code

You are very welcome here

Posted: **Thu Jan 03, 2008 2:09 pm**

The reason I found this idea useful is that it means that you can do most of the math part without any string conversions which is what slows everything down

Well just like you case my input is a string too, and if purebasic is well written

Mid(string,start.len) should simply be a reference to a memory location at start, so it might be the same,

ideally we should by trying to extract the longest "longint" from the string at a time and using the same.. but I thought that would be too tedious too.. ofcourse, there maybe cases where BCDA could be an op code and in that case your way will be faster.

the rest does indeed seem very similar..
oh well im from india, but not the math freak kinds

I mean given todays computing power, frankly making a chipset which does the manual way on chips may not be such a bad deal too! (probably MMX guys will like it)

Posted: **Thu Jan 03, 2008 2:19 pm**

I did some speed tests, I think the strings stuff is slowing yours down. Also, I found mine is missing this structure that needs to be declared before it will work

Code: Select all


Structure Bytes 
    Byte.b[0] 
EndStructure

I think some of the areas I'd try and get rid of are lines like this:

Code: Select all

 temp_result$=Str(Val(Mid(myn1$,i,1))+Val(Mid(myn2$,i,1))+carry)

In the speed tests, I noticed you were calculating 100!, if I did 200! your took quite a while (maybe half a minute anyway). with BCD, mine did 500! in under a second

I think you'd love that Project Euler site, even if your not a math freak! (I'm certainly not one, I'm a school dropout

)

Posted: **Thu Jan 03, 2008 2:32 pm**

but if the size is like 50000 bytes you are actually defining an integer array of size 50000 right? and then adding/subtracting/multiplying each member?
So by your algo:
local_result$=Str(Val(Mid(myn2$,i,1))*Val(Mid(myn1$,j,1))+carry)
would become
local_result=Myn2(i)*Myn1(j)
yep so then i guess the Str(Val stuff is screwing things up, ill try it your way and see

Posted: **Thu Jan 03, 2008 2:43 pm**

"If the size is 50000 bytes" by that you mean the number is 50,000 digits long? It's one array element per digit.

It's no where near as efficient as binary of course but it's a memory trade off for speed.

Also, my bit math is not so good when it comes to multiplication that I could do it that way easily, otherwise I'd stick longs together and work at a bit level and bit shift and use OR and XOR etc and I guess it would be very fast and efficient. But I'm not really up to studying that much

Posted: **Thu Jan 03, 2008 2:45 pm**

yep and i guess using memory pointers is also making it more efficent,

I can do that in C, i have never used pointers in PB so no idea

Posted: **Thu Jan 03, 2008 2:57 pm**

1.3sec for calculating 2000! (7.8 from the IDE with debugger enabled etc)

(Actually, there were quite a few people working on tweaking these functions in the Euler thread so it's not like I did it all by my self, quite a few more on factors, primes and stuff too in there)

Code: Select all


Structure Bytes 
    Byte.b[0] 
EndStructure


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) = Val(Mid(Num1,Num1len - i +1 ,1))
        bcd1(i) = *BytePtr1\Byte[Num1len - i] -48
    Next

    For i = 1 To Num2len 
        ;bcd2(i) = Val(Mid(Num2,Num2len - i +1,1))
        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

OpenConsole()

    PrintN("Calculating 2000! Press any key to begin")
    PrintN("")
    Input()
    
    TheTime.l = ElapsedMilliseconds()
    fact$="1" 
    
    For i=1 To 2000 
        fact$=BigMultiply(fact$,Str(i)) 
    Next i
    
    PrintN(fact$)
    PrintN("")
    PrintN("Time Taken was " + Str(ElapsedMilliseconds() - TheTime) + " ms !")
    Input()

CloseConsole()

Answer

Code: Select all


33162750924506332411753933805763240382811172081057803945719354370603807790560082
24002732308597325922554023529412258341092580848174152937961313866335263436889056
34058556163940605117252571870647856393544045405243957467037674108722970434684158
34375243158087753364512748799543685924740803240894656150723325065279765575717967
15367186893590561128158716017172326571561100042140124204338425737127001758835477
96899921283528996665853405579854903657366350133386550401172012152635488038268152
15224692099520603156441856548067594649705155228820523489999572645081406553667896
95321014676226713320268315522051944944616182392752040265297226315025747520482960
64750927394165856283531779574482876314596450373991327334177263608852490093506621
61014445970941270782131373256383157230201994991495831647094277447387032798554967
42986088393763268241524788343874695958292577405745398375015858154681362942179499
72399813599481016556563876034227312912250384709872909626622461971076605931550201
89513558316535787149229091677904970224709461193760778516511068443225590564873626
65303773846503907880495246007125494026145660722541363027549136715834060978310749
45282217490781347709693241556111339828051358600690594619965257310741177081519922
56451677857145805660218565476095237746301667942248844448579834980154803262082989
09658573817518886193766928282798884535846398965942139529844652910920091037100461
49449915828588050761867924946385180879874512891408019340074625920057098729578599
64365065589561241023101869055606030878362911050560124590899838341079936790205207
68586691834779065585447001486926569246319333376124280974200671728463619392496986
28468719993450393889367270487127172734561700354867477509102955523953547941107421
91330135681954109194146276641754216158762526285808980122244389024867718205495941
57519917012717675717874958616196659318788551418357820926014820717773317353960343
04969082070589958701381980813035590160762908388574561288217698136182483576739218
30311841471913398689284234400077924669120976673165143349443747323563657204884447
83318549416930301245316762327453678793228474738244850922831399525097325059791270
31047683601481191102229253372697693823670057565612400290576043852852902937606479
53345817966612383960526254910718666386935476610845504619810208405063582767652658
94923932495196859541716724193295306836734955440045863598381610430594498266275306
05423580755894108278880427825951089880635410567917950974017780688782869810219010
90014835206168888372025031066592206860148364983053278208826353655804360568678128
41692171330471411763121758957771226375847531235172309905498292101346873042058980
14418063875382664169897704237759406280877253702265426530580862379301422675821187
14350291863763634030017325181826207603974736959520264263236414544685111342720215
04583838510101369413130348562219166316238926327658153550112763078250599691588245
33457435437863683173730673296589355199694458236873508830278657700879749889992343
55556624068283476378468518384497364887395247510322422211056120129582965719136810
86938254757641188868793467251912461921511447388362695916436724900716534282281526
61247800463922544945170363723627940757784542091048305461656190622174286981602973
32404652020199281385488268195100728286970107073750092766648750217477537274235150
87482467202741700315811228058961781221607474379475109506209385566745812525183766
82157712807861499255876132352950422346387878954850885764466136290394127665978044
20209228133798711590089626487894241321045492500356667063290944157937298674342147
05072135889320195807230647814984295225955890127548239717733257229103257609297907
33299545056388362640474650245080809469116072632087494143973000704111418595530278
82735765481918200244969776111134631819528276159096418979095811733862720608891043
29452449785351470141124421430554860896395783783473253235957632914389252883939862
56273242862775563140463830389168421633113445636309571965978466338551492316196335
67535513840342580416291983782226690952177015317533873028461084188655413832917195
13321178957285416620848236828179325129312375215419269702697032994776438233864830
08871530373405666383868294088487730721762268849023084934661194260180272613802108
00507821574100605484820134785957810277070778065551277254050167433239606625321641
50048087724030476119290322101543853531386855384864255707907953411765195711886837
39880683895792743749683498142923292196309777090143936843655333359307820181312993
45502420604456334057860696247196150560339489952332180043435996725662392719643540
28720554750120798543319706747973131268135236537440856622632067688375851327828962
52333284341812977624697079543436003492343159239674763638912115285406657783646213
91124744705125522634270123952701812704549164804593224810885867460095230679317596
77555810116799400052498063037631413444122690370349873557999160092592480750524855
41568266281760815446308305406677412630124441864204108373119093130001154470560277
77372437806718889977085105672727678124719883285769584421758889516046786820481001
00478164623582208385324881342708340798684866321627202088233087278190853788454691
31556021728873121907393965209260229101477527080930865364979858554010577450279289
81460368843182150863724621696787228216934737059928627711244769092090298832016683
01702734202597656717098633112163495021712644268271196502640542282317596308744753
01847194095524263411498469508073390080000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000

Posted: **Thu Jan 03, 2008 3:46 pm**

hrm wonder why the strings stuff is adding so many more layers to the code...
i guess ill just get the base framework going then work around optimizing it.. there is a call to add() in multiply which seems to be blocking a lot as per the debugger

what trick did u use to divide?
the one i have in mind is say it is a/b,
take some part of a till part(a) >b, multiply b from 1 to 9, find the number where b*n (n from 1 to 9) becomes > part (a) , n-1 is the digit to put in the quotient$ and calculate the remainder as part(a) - b.(n-1) and so on, like manual division
actually thats why i want a tight multiplication library, to get that division thing going

Posted: **Fri Jan 04, 2008 1:30 am**

I didn't need divide so I didn't get around to it.

Happy to help work on it though. (gotta remember how to do long division though

)

PB strings are quite slow, especially if they are getting long. Try to keep them out of tight loops or use memory raw as PB without strings is very fast! If you need more info on this let me know and I'll post some proof code

PureBasic Forums - English

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

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

thanks! performance is not the issue

algorithm

cool!

tricks

cool!