Dark Bit Factory & Gravity
PROGRAMMING => General coding questions => Topic started by: psygate on March 14, 2007
-
Hi again. I faced a real problem. I wanted to calculate a prime with about 300 digits, or in bits, 2048. But it's not possible with the normal compuiter arithmetics so could anyone refer me to a library (freebasic compatible) and give me a site where I can see how this thing with real big numbers works?
THX, Psy
-
Here is the code for doing the basic math functions in purebasic. If
you have any questions concerning the code i.e. purebasic functions
or keywords - just ask !
I guess converting those functions to freebasic wouldnt be that hard.
;BIGNUM Library for Purebasic
;-----------------------------------------------------------------------------
; (c) 2004-2005 Siegfried Rings
;
; This library is free software; you can redistribute it and/or
; modify it under the terms of the GNU Lesser General Public
; License as published by the Free Software Foundation; either
; version 2.1 of the License, Or (at your option) any later version.
;
; This library is distributed in the hope that it will be useful,
; but WITHOUT ANY WARRANTY; without even the implied warranty of
; MERCHANTABILITY Or FITNESS For A PARTICULAR PURPOSE. See the GNU
; Lesser General Public License For more details.
;-----------------------------------------------------------------------------
;#Limiter.s ="." ;You can also use "," Or something Else
;Proecure to check if it is a valid Number !
ProcedureDLL IsNum(Instring.s);Checks if the string is a Number
wert=FindString("1234567890+-"+".",Instring,1)
ProcedureReturn wert
EndProcedure
ProcedureDLL ValidNumber(Instring.s) ;Check If the string is a valid Number
L1=Len(Instring)
If L1=0:ProcedureReturn 1:EndIf
For I=1 To L1
If IsNum(Mid(Instring,I,1))=0
ProcedureReturn 0
EndIf
Next I
ProcedureReturn 1 ;Yes it's a Validnumber
EndProcedure
;Check If a number is greater than the other
Procedure GreaterThan(NR1.s,NR2.s)
NR1.s=Trim(NR1.s);Cut leading spaces
NR2.s=Trim(NR2.s);Cut leading space
L1=Len(NR1.s) ;Len of Number 1
L2=Len(NR2.s) ;Len of Number 2
P1=FindString(NR1.s,".",1)
P2=FindString(NR2.s,".",1)
If P1
NR11.s=Right(NR1.s,L1-P1)
NR1.s=Left(NR1.s,P1-1)
EndIf
If P2
NR21.s=Right(NR2.s,L2-P2)
NR2.s=Left(NR2.s,P2-1)
EndIf
L1=Len(NR1.s) ;Len of Number 1
L2=Len(NR2.s) ;Len of Number 2
If L1>0 And L2=0:ProcedureReturn 1:EndIf
If L1=0 And L2=0:ProcedureReturn 0:EndIf
If L1=0 And L2>0:ProcedureReturn 2:EndIf
If L1<>L2
If L1>L2
ProcedureReturn 1
EndIf
If L2>L1
ProcedureReturn 2
EndIf
Else
For L=1 To L1
If Val(Mid(NR1,L,1))>Val(Mid(NR2,L,1))
ProcedureReturn 1
EndIf
If Val(Mid(NR1,L,1))<Val(Mid(NR2,L,1))
ProcedureReturn 2
EndIf
Next L
If P1>0 And P2=0:ProcedureReturn 1:EndIf
If P2>0 And P1=0:ProcedureReturn 2:EndIf
Result=GreaterThan(NR11.s,NR21.s)
ProcedureReturn Result
EndIf
EndProcedure
ProcedureDLL IsGreaterThan(NR1.s,NR2.s);compare 2 StringNumbers
ProcedureReturn GreaterThan(NR1.s,NR2.s)
EndProcedure
;
ProcedureDLL.s GenerateString(Count,Character.s);fill a string with a given character
Sdummy.s=""
For I=1 To Count
Sdummy.s=Sdummy.s + Character.s
Next I
ProcedureReturn sDummy.s
EndProcedure
ProcedureDLL CheckFloat(NR1.s,NR2.s);Check if StringNumber is a float
Shared NF1.s
Shared NF2.s
L0=FindString(NR1.s,".",1)
R0=FindString(NR2.s,".",1) ;Is Float ?
If R0=0 And L0=0 ;No Floatingpoint
Point=0
Else
If L0=0:NR1.s=NR1.s+".":EndIf
If R0=0:NR2.s=NR2.s+".":EndIf
If L0>0: L01=Len(Right(NR1.s,Len(NR1.s)-L0)):EndIf
If R0>0: R01=Len(Right(NR2.s,Len(NR2.s)-R0)):EndIf
If L01>R01:NR2.s=NR2.s+GenerateString(L01-R01,"0"): EndIf
If R01>L01:NR1.s=NR1.s+GenerateString(R01-L01,"0") :EndIf
Point=Len(NR1.s)-FindString(NR1.s,".",1)
LL.s=Left(NR1.s,FindString(NR1.s,".",1)-1)
RR.s=Right(NR1.s,Len(NR1.s)-FindString(NR1.s,".",1) )
NR1.s=LL.s+RR.s
LL.s=Left(NR2.s,FindString(NR2.s,".",1)-1)
RR.s=Right(NR2.s,Len(NR2.s)-FindString(NR2.s,".",1) )
NR2.s=LL.s+RR.s
EndIf
NF1.s=NR1.s
NF2.s=NR2.s
ProcedureReturn Point
EndProcedure
ProcedureDLL.s BigNUMRemainderPart(Instring.s);Get Remainder Part of a StringNumber
I=FindString(Instring,".",0)
If I>0
ProcedureReturn Right(Instring,Len(Instring)-I)
EndIf
EndProcedure
ProcedureDLL.s BigNUMIntegerPart(Instring.s);Get Integer Part of a Stringnumber
I=FindString(Instring,".",0)
If I>0
ProcedureReturn Left(Instring,I-1)
Else
ProcedureReturn Instring
EndIf
EndProcedure
Procedure.s RemoveNULLs(Instring.s);Remove unneded Nulls
RMN1:
If Left(Instring,1)="0"
Instring=Right(Instring,Len(Instring)-1)
Goto RMN1
EndIf
If FindString(Instring,".",1)>0
RMN2:
If Right(Instring,1)="0"
Instring=Left(Instring,Len(Instring)-1)
Goto RMN2
EndIf
ProcedureReturn Instring
EndIf
ProcedureReturn Instring
EndProcedure
Procedure.s BIGNUMSUB1(NR1.s,NR2.s)
;First Check for valid Number
L2=Len(NR2.s) ;Len of Number 2
If L2=0:ProcedureReturn NR1.s:EndIf
If GreaterThan(NR1.s,NR2.s) =2: ProcedureReturn "-"+BIGNUMSUB1(NR2.s,NR1.s):EndIf
If GreaterThan(NR1.s,NR2.s) =0: ProcedureReturn "0":EndIf
Shared NF1.s
Shared NF2.s
Point=CheckFloat(NR1.s,NR2.s)
NR1.s=NF1.s
NR2.s=NF2.s
L1=Len(NR1.s) ;Len of Number 1
L2=Len(NR2.s) ;Len of Number 2
;Beginning from right to left like those old schooldays :)
Repeat
If P1<(L1)
V1=Val(Mid(NR1.s,L1-P1,1)) ;Number 1
Else
V1=0
EndIf
If P2<(L2)
V2=Val(Mid(NR2.s,L2-P2,1)) ;Number 2
Else
V2=0
EndIf
P1+1;Increment first counter
P2+1;Increment second counter
V3=V1-(V2+UB) ;Remember if there is a flag
; PrintN(NR1.s+" - "+NR2.s+" = V3:"+Str(V3)+" V1: "+Str(V1)+" V2:"+Str(V2)+" UB:"+Str(UB))
If V3<0 ;Bigger than 9 so Set Flag to 1
V3=(V1+10)-(V2+UB)
UB=1
Else
UB=0 ;Reset Flag
EndIf
NR0.s=Trim(Str(V3)) + NR0.s ;Add to new string
If P1>L1 And P2>L2 : P0=1 :EndIf;are we ready ?
Until P0=1
Repeat
If Left(NR0,1)="0" : NR0.s=Right(NR0.s,Len(NR0.s)-1):EndIf;Cut leading NULL
Until Left(NR0,1)<>"0"
If Point<>0
Anz=Len(NR0.s)-Point
NR0=Left(NR0.s,Anz)+"."+Right(NR0.s,Point)
EndIf
If NR0.s=""
NR0.s="0"
EndIf
ProcedureReturn NR0
EndProcedure
ProcedureDLL.s BIGNUMSUB(NR1.s,NR2.s);subtract Stringnumbers
ProcedureReturn BIGNUMSUB1(NR1.s,NR2.s)
EndProcedure
ProcedureDLL.s BIGNUMADD(NR1.s,NR2.s) ;add 2 Stringnumbers
NR1.s=Trim(NR1.s);Cut leading spaces
NR2.s=Trim(NR2.s);Cut leading space
N3.s=""
L1=Len(NR1.s) ;Len of Number 1
L2=Len(NR2.s) ;Len of Number 2
If Left(NR1.s,1)="+":NR1.s=Right(NR1.s,L1-1):L1-1:EndIf;Cut leading plussign
If Left(NR2.s,1)="+":NR2.s=Right(NR2.s,L1-1):L1-1:EndIf;Cut leading plussign
If Left(NR2.s,1)="-"
NR2.s=Right(NR2.s,L1-1)
NR3.s=BIGNUMSUB(NR1.s,NR2.s)
ProcedureReturn NR3.s
EndIf;
Shared NF1.s
Shared NF2.s
Point=CheckFloat(NR1.s,NR2.s)
NR1.s=NF1.s
NR2.s=NF2.s
L1=Len(NR1.s) ;Len of Number 1
L2=Len(NR2.s) ;Len of Number 2
;Beginning from right to left like those old schooldays :)
Repeat
If P1<(L1)
V1=Val(Mid(NR1.s,L1-P1,1)) ;Number 1
Else
V1=0
EndIf
If P2<(L2)
V2=Val(Mid(NR2.s,L2-P2,1)) ;Number 2
Else
V2=0
EndIf
P1+1;Increment first counter
P2+1;Increment second counter
V3=V1+V2+UB ;Remember if there is a flag
If V3>9;Bigger than 9 so Set Flag to 1
UB=1
V3=V3-10 ;and remove Flag from original
Else
UB=0 ;Reset Flag
EndIf
NR0.s=Trim(Str(V3)) + NR0.s ;Add to new string
If P1>L1 And P2>L2 : P0=1 :EndIf;are we ready ?
Until P0=1
If Left(NR0,1)="0" : NR0.s=Right(NR0.s,Len(NR0.s)-1):EndIf;Cut leading NULL
If Point<>0
Anz=Len(NR0.s)-Point
NR0=Left(NR0.s,Anz)+"."+Right(NR0.s,Point)
EndIf
ProcedureReturn NR0
EndProcedure
Procedure.s BIGNUMMULTI1(NR1.s,NR2.s)
; calulate multiple each number with each and add all those
If Left(NR1.s,1)="+":NR1.s=Right(NR1.s,L1-1):L1-1:EndIf;Cut leading plussign
If Left(NR2.s,1)="+":NR2.s=Right(NR2.s,L1-1):L1-1:EndIf;Cut leading plussign
If Left(NR1.s,1)="-" And Left(NR2.s,1)="-" ;-*- = +1
NR3.s=BIGNUMMULTI1(Right(NR1.s,Len(NR1.s)-1),Right(NR2.s,Len(NR2.s)-1))
ProcedureReturn NR3.s
EndIf;
If Left(NR1.s,1)="-" ;-*+ = -1
NR3.s="-"+BIGNUMMULTI1(Right(NR1.s,Len(NR1.s)-1),NR2.s)
ProcedureReturn NR3.s
EndIf;
If Left(NR2.s,1)="-" ;-*+ = -1
NR3.s="-"+BIGNUMMULTi1(NR1.s,Right(NR2.s,Len(NR2.s)-1))
ProcedureReturn NR3.s
EndIf;
L1=Len(NR1.s):L2=Len(NR2.s)
r0.s="0"
Shared NF1.s
Shared NF2.s
Point=CheckFloat(NR1.s,NR2.s)
NR1.s=NF1.s
NR2.s=NF2.s
L1=Len(NR1.s) ;Len of Number 1
L2=Len(NR2.s) ;Len of Number 2
For I=1 To L1
P1=Val(Mid(NR1.s,I,1))
For T= 1 To L2
P2=Val(Mid(NR2.s,T,1))
N1=L1-I
N2=L2-T
NR4.s=Str(P1*P2) + GenerateString(N1,"0") + GenerateString(N2,"0")
NR0.s=BIGNUMADD(NR0.s,NR4.s)
Next T
Next I
If Point<>0
Anz=Len(NR0.s)-(Point*2)
NR0=Left(NR0.s,Anz)+"."+Right(NR0.s,Point*2)
EndIf
NR0.s= RemoveNULLs(NR0.s)
ProcedureReturn NR0.s
EndProcedure
ProcedureDLL.s BIGNUMMULTI(NR1.s,NR2.s);Multiply 2 stringnumbers
ProcedureReturn BIGNUMMULTI1(NR1.s,NR2.s)
EndProcedure
ProcedureDLL.s BIGNUMMOD(Nr1.s,NR2.s)
Repeat
NR1.s=BigNumSub(Nr1.s,NR2.s)
If Greaterthan(NR1.s,NR2.s) =2
NR0.s=Nr1.s
P=0
Else
P=1
EndIf
Until P=0
ProcedureReturn NR0.s
EndProcedure
ProcedureDLL.s BIGNUMGDIV(Nr1.s,NR2.s); divide 2 Stringnumbers
NR0.s="0"
Repeat
NR1.s=BigNumSub(Nr1.s,NR2.s)
NR0.s=BIGNUMADD(NR0.s,"1")
If Greaterthan(NR1.s,NR2.s) =2
P=0
Else
P=1
EndIf
Until P=0
ProcedureReturn NR0.s
EndProcedure
ProcedureDLL.s BIGNUMPOW(NR1.s,NR2.s);POW with 2 Stringnumbers
NR0.s=NR1.s
Repeat
If NR2.s<>"1"
NR0.s=BigNumMulti(NR0.s,NR1.s)
EndIf
NR2.s=BigNumsub(NR2.s,"1")
Until NR2.s="0"
ProcedureReturn NR0.s
EndProcedure
ProcedureDLL.s BIGNUMDIV(NR1.s,NR2.s,Pres); Divide 2 Stringnumbers
If GreaterThan(NR1.s,NR2.s)=0
ProcedureReturn "1"
EndIf
NR0.s=NR1.s
Count.s="0"
Pres+1
Line=0
BGD1:
If GreaterThan(NR1.s,NR2.s)=1
If Left(NR2.s,1)="0" : NR2.s=Right(NR2.s,Len(NR2.s)-1):EndIf ;shorten
;Do the tricky part.If a Number is very greater than the other, use Multiply with 1? to cut down
; the very slow BigNumSub
L1=Len(BigNumIntegerPart(NR2.s))
L2=Len(BigNumIntegerPart(NR1.s))
If L1+2<L2
Count.s=BIGNUMADD(Count.s,"1"+GenerateString(L2-L1-1,"0"))
NR1.s=BIGNUMSUB(NR1.s,BigNumMulti(NR2.s,"1"+GenerateString(L2-L1-1,"0")))
Goto BGD1
EndIf
;Okay now try To subtract NR2.from NR1 as often as i can do
Count.s=BIGNUMADD(Count.s,"1")
;Debug Str(l1)+":" + Str(l2) + " " +NR1.s +"=" +NR2.s
NR1.s=BIGNUMSUB(NR1.s,NR2.s)
;Debug NR1.s
Goto BGD1
EndIf
If GreaterThan(NR1.s,NR2.s)=0
Count.s=BIGNUMADD(Count.s,"1")
Goto BGD2
EndIf
If GreaterThan(NR1.s,NR2.s)=2
If FindString(Count2.s,".",1)=0
Count2.s=Count.s+"."
Count="0"
Else
Count2.s=Count2.s+Count.s
Count.s="0"
EndIf
NR1.s=Nr1.s+"0"
;Shift the limiter right
P=FindString(NR1.s,".",1)
If P>0
If P>1
If P<Len(NR1.s)
Nr0.s=Left(NR1,P-1)+Mid(NR1,P+1,1)+"."+Right(NR1.s,Len(NR1.s)-P-1)
Else
Nr0.s=Left(NR1.s,Len(NR1.s)-1)
EndIf
Else
NR0.s=Mid(NR1.s,2,1)+"."+Right(NR1.s,Len(NR1.s)-2)
EndIf
NR1.s=NR0.s
EndIf
NR1.s= RemoveNULLs(NR1.s)
CPres+1
If CPres<Pres:Goto BGD1:EndIf
EndIf
BGD2:
If Count2.s<>""
Count.s=Count2.s+Count
EndIf
Count.s= RemoveNULLs(Count.s)
;now check For roundingmode ?
ProcedureReturn Count.s
EndProcedure
ProcedureDLL.s BIGNUMSQR(NR1.s,NR2.s,Pres);SQR on Stringnumbers
;Pres+1
i=1
Nr2.s="0"+"."+"5"
NR0.s=BigNumMulti(NR2.s,NR1.s)
Repeat
NR3.s=BigNumDiv(NR1.s,NR0.s,Pres)
NR4.s=BigNumAdd(NR0.s,NR3.s)
NR5.s=BigNumMulti(NR2.s,NR4.s)
NR0.s=Nr5.s
;Check for IntegerSQR ciz its faster and akurate
NR6.s=BigNumIntegerPart(NR0.s)
NR7.s=BigNumMulti(Nr6.s,NR6.s)
If Greaterthan(NR1.s,NR7.s)=0
ProcedureReturn NR6.s
EndIf
i+1
Until Pres<i
ProcedureReturn NR5.s
EndProcedure
ProcedureDLL.s BIGNUMSQX(NR1.s,NR2.s,Pres);experimental SQX on Stringnumbers
NR2.s=BIGNUMIntegerPart(NR2.s);Cut any given Remainder
NR0.s=BIGNUMDIV(NR1.s,NR2.s,Pres);First iteration
NR5.s=BIGNUMSUB(NR2.s,"1")
Repeat
Pro.s = NR0.s
NR4.s=BIGNUMSUB(NR2.s,"2")
While NR4.s <>""
NR4.s =Trim(RemoveNULLs(BIGNUMSUB(NR4.s ,"1")))
Pro.s = BigNumMulti(PRo,NR0.s);Pro * Näherung
Wend
NR8.s=BigNumMulti(NR5.s,NR0.s) ;(WW / Pro + (Nte - 1) * Näherung) / Nte
NR7.s=BigNumdiv(Nr1.s,PRo.s,Pres)
Nr6.s=BigNumAdd(Nr7.s,Nr8.s)
NR0.s=BigNumDiv(Nr6.s,NR2.s,Pres)
i+1
Until Pres<i
ProcedureReturn NR0.s
EndProcedure
The code works pretty well - though it is of course not so fast. For example :
BIGNUMADD("999999999999999999999999999999999999999999999999999999999", "6" )
returns
1000000000000000000000000000000000000000000000000000000005
-
You probably want the big_int lib which you can find in the inc/big_int folder of your FB installation.
You will want to include either big_int.bi or big_int_full.bi. The _full includes all the supporting functions.
-
No :D I'd like to learn thew maths behind the magic of working with real big numbers, but the purebasic bigintlibreary could help me understanding that thing!
Thx
PS: Don't stop postin ;D
-
The basic methods for simple bignum libraries are exactly like those you use for hundreds-tens-and-units that you did at school. Adding/subtracting by carrying/borrowing totals from one column, long division, and multiplication techniques too. Usually the only difference is instead of working in base10 then work in base2^32 to take advantage of the register operations on your CPU. It's quite informative to write your own big number adder using base 10. Have an array for each digit. Very useful for doing Fibonacci numbers http://en.wikipedia.org/wiki/Fibonacci_number (http://en.wikipedia.org/wiki/Fibonacci_number)
Jim