1 Billion digit prime

For other topics related to the FreeBASIC project or its community.
owen
Posts: 555
Joined: Apr 19, 2006 10:55
Location: Kissimmee, FL
Contact:

Re: 1 Billion digit prime

Postby owen » Feb 29, 2012 9:40

smart attack... statistical proof... and all this effort just to identify a possible candidate to test.
this is what i'm thinking
smart attack:
testing prime: trial division of a billion digit number up to its square root by primes only is optimal however impractical.
my idea of a smart attack is to reduce the number of composites used for trial division.

the simplest way to describe this is the idea of skipping numbers or using a pattern of exclusion.
ie. list numbers starting after 2 that are not multiples of 2. (3,5,7,9,11,13,15,17...)
the pattern here is 2 (3+2=5+2=7+2=9+2=11+2....)

list number starting after 3 that are not multiples of 2 or 3 (5,7,11,13,17,19,23,25,29...)
the pattern here is 2,4 (5+2=7+4=11+2=13+4=17+2=19+4....)
Notice (2x3=2+4)

What's the pattern for the exclusion of 2,3,5?
the pattern is 4,2,4,2,4,6,2,6
The product of 2x3x5 equals the sum of the numbers in the pattern (30)

the pattern of 2,3,5,7 is a series of 48 numbers starting with 2 4 2 4 6 2 6 4 2 4 6 6 2 6 4
the pattern of 2,3,5,7,11 is a series of 480 numbers
and the pattern for 2,3,5,7,11,13 has 5760 numbers

One thing to note about these patterns is that the LAST 3 numbers will always be x,2,x where x is next prime minus 1
ie the last 3 numbers for the pattern 2,3,5,7,11,13,17,19 will be 22,2,22
Second thing to note is that the pattern is mirrored and always has a 4 in the middle which means that the quantity of numbers needed in the pattern are: (N-3-1)/2 where N is the quantity of numbers in the pattern.
Knowing this (mirror) info is useful cuz you can know that last digits by knowing the first digits.
Basically this is saying I can begin to list numbers to investigate near the 1 billion digit number.that are not multiples of any prime number up to and including 2302630117 however they may be numbers that are multiples of primes higher then 2302630117...
The thing is that I think i would not have to list the numbers themselves (where each number is a one gig file) but simply refer to them as +N where N is a number in the pattern.

Ok, So now about the idea of statistical proof... well ... let's just say it this way... i figure i'll need about 46 terabytes of storage to hold the suspect numbers (the N's) and the processes of elimination begins from there.
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

Re: 1 Billion digit prime

Postby TESLACOIL » Feb 29, 2012 16:06

if the prize was a million bucks id be tempted


but you would be lucky to break even , even if you did scoop the current prize

the billion number prime is a low calorie carrot, lol , a few sniffers, but few attempts to take it




lots more tempting challenges out there me thinks , though chasing primes is simple and relatively straight forward , the challenge is there all-right, but the reward is a bit dry.....of course history will remember the first man to find a billion digit prime

Id rather be remembered for something a bit more sexy, lol , if i had access to a supercomputer i would give the prime a whirl, its way beyond the capability of my network ( kinda thought it would be )
Richard
Posts: 3047
Joined: Jan 15, 2007 20:44
Location: Australia

Re: 1 Billion digit prime

Postby Richard » Feb 29, 2012 22:05

There are two parts to this problem.
1. Make a minimum size list of possible primes.
2. Test the primality of members in that list, starting with the easiest factorisation attack.
Note that any linear search over 10^(half billion) possible factors will take forever, it is impossible.
albert
Posts: 5927
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: 1 Billion digit prime

Postby albert » Apr 07, 2012 3:16

Isn't there some type of math formula to figure primes??

It seems that all primes are ODD numbers
and a two digit
ODD,ODD = EVEN
so maybe
EVEN,ODD or ODD,EVEN = PRIME

You might be able to figure a formula of chaining certain EVENS and certain ODDS to create HUGE-PRIMES..

it might end up like 2'nd even followed by 3'rd odd followed by 3'rd even followed by 4'th odd , etc...??

The Russians would ony give up RSA if they had developed a way to crack it quickly..

On side 1 you got 1,3,5,7
On side 2 you got 2,4,6,8
9 is the oddity or the first product of 6,3 EVEN,ODD ; so you might have to use a base 9 (0 to 8) number system to figure a formula.
Richard
Posts: 3047
Joined: Jan 15, 2007 20:44
Location: Australia

Re: 1 Billion digit prime

Postby Richard » Apr 07, 2012 9:29

Albert wrote:Isn't there some type of math formula to figure primes??

The beauty of primes is that they cannot be easily predicted.
Primes must be proposed, then verified by testing.
Primes are all that is left after the composite numbers have been removed.
albert
Posts: 5927
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: 1 Billion digit prime

Postby albert » Apr 07, 2012 17:28

@Richard

What is a Marsene Prime number ? if a Prime is only divisible by 1 and itself, What do they call a Marsene ?

I'll play around with it today and see if i can create a formula.
I like analyzing long lists of numbers for patterns.
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

Re: 1 Billion digit prime

Postby TESLACOIL » Apr 07, 2012 19:21

i strongly suspect that primes have a deep fundamental link with the laws of the universe

that is to say i think that the 'harmonics of divisibility and indivisibility' allow for some things (aka laws) to be stable and hang around over time while other less harmonious constructs dissipate or never arise in the first place.


There is a mathematical & musical like tune to the universe at anyrate , we perhaps cant see the wood for the trees because the maths that describes the universe looks pretty at higher dimensions while our minds are atuned to just 3. Time and indeed creation itself may be just be the intrinsic inability of certain mathematically constructs to cancel themselves out.

Perhaps some things are forbidden to arise, some arise and cancel/evaporate in an instant, other facets may linger before they finally decay and others by their nature cannot cancel each other out and thus must endure for all eternity. Perhaps one day our understanding of mathematics may advance to the point that at least some of if not all of these themes are understood.

just my 2 cents ...or should i say mathematical philosophy
albert
Posts: 5927
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: 1 Billion digit prime

Postby albert » Apr 07, 2012 19:33

Heres a program i did a while back in Circles or maybe in Squares ??

It picks out all the numbers in a range that are absolutely unique (only divisible by ) 1,2,3,5,7 the ones column are the primes.

Code: Select all

'a program to:
'pick out all numbers that are unique multiples of 1,2,3,5,7
'only those multiples of a number that are not multiples of another number.
'===============================================================================
dim as ulongint  low =     0   ' adjust here to suit your needs
dim as ulongint high = 10000   ' adjust here to suit your needs , loop goes low to high
'===============================================================================
dim as ulongint   one ,   ones(low to high)
dim as ulongint   two ,   twos(low to high)
dim as ulongint three , threes(low to high)
dim as ulongint  five ,  fives(low to high)
dim as ulongint seven , sevens(low to high)

dim as string test
dim as ulongint count

print "  unique 1's    unique 2's     unique 3's     unique 5's     unique 7's"   

one   = 1*low
two   = 2*low
three = 3*low
five  = 5*low
seven = 7*low

count = low
for a as ulongint = low to high step 1

      ones(count) = one
      twos(count) = two
    threes(count) = three
     fives(count) = five
    sevens(count) = seven
   
    test = str(ones(count)/2) : if instr(1,test,".") = 0 then ones(count) = 0
    test = str(ones(count)/3) : if instr(1,test,".") = 0 then ones(count) = 0
    test = str(ones(count)/5) : if instr(1,test,".") = 0 then ones(count) = 0
    test = str(ones(count)/7) : if instr(1,test,".") = 0 then ones(count) = 0

    'if ones(count) > 1  then
    '    test = str(twos(count)/ones(count)) : if instr(1,test,".") = 0 then twos(count) = 0
    'end if   
    test = str(twos(count)/3) : if instr(1,test,".") = 0 then twos(count) = 0
    test = str(twos(count)/5) : if instr(1,test,".") = 0 then twos(count) = 0
    test = str(twos(count)/7) : if instr(1,test,".") = 0 then twos(count) = 0

    'if ones(count) > 1  then
    '    test = str(threes(count)/ones(count)) : if instr(1,test,".") = 0 then threes(count) = 0
    'end if   
    test = str(threes(count)/2) : if instr(1,test,".") = 0 then threes(count) = 0
    test = str(threes(count)/5) : if instr(1,test,".") = 0 then threes(count) = 0
    test = str(threes(count)/7) : if instr(1,test,".") = 0 then threes(count) = 0
   
    'if ones(count) > 1  then
    '    test = str(fives(count)/ones(count)) : if instr(1,test,".") = 0 then fives(count) = 0
    'end if   
    test = str(fives(count)/2) : if instr(1,test,".") = 0 then fives(count) = 0
    test = str(fives(count)/3) : if instr(1,test,".") = 0 then fives(count) = 0
    test = str(fives(count)/7) : if instr(1,test,".") = 0 then fives(count) = 0

    'if ones(count) > 1  then
    '    test = str(sevens(count)/ones(count)) : if instr(1,test,".") = 0 then sevens(count) = 0
    'end if   
    test = str(sevens(count)/2) : if instr(1,test,".") = 0 then sevens(count) = 0
    test = str(sevens(count)/3) : if instr(1,test,".") = 0 then sevens(count) = 0
    test = str(sevens(count)/5) : if instr(1,test,".") = 0 then sevens(count) = 0
   
    print using "############# #############  #############  #############  #############"; _
                  ones(count),  twos(count),  threes(count),  fives(count),  sevens(count)

    one   = one   + 1
    two   = two   + 2
    three = three + 3
    five  = five  + 5
    seven = seven + 7

    count = count + 1

next
'SLEEP
'END
'===============================================================================
'===============================================================================
'===============================================================================
'===============================================================================
'print arrays out to files
'===============================================================================
'===============================================================================
'===============================================================================
'===============================================================================
mkdir(".\Uniques")
' change path to your user directory...
open ".\Uniques\ones.txt" for output as #1
    for count = 1 to ubound(ones(0))
        if ones(count)<>0 then print #1,ones(count)
    next
close #1
'===============================================================================
'===============================================================================
' change path to your user directory...
open ".\Uniques\twos.txt" for output as #1
    for count = 1 to ubound(twos(0))
        if twos(count)<>0 then print #1,twos(count)
    next
close #1
'===============================================================================
'===============================================================================
' change path to your user directory...
open ".\Uniques\threes.txt" for output as #1
    for count = 1 to ubound(threes(0))
        if threes(count)<>0 then print #1,threes(count)
    next
close #1
'===============================================================================
'===============================================================================
' change path to your user directory...
open ".\Uniques\fives.txt" for output as #1
    for count = 1 to ubound(fives(0))
        if fives(count)<>0 then print #1,fives(count)
    next
close #1
'===============================================================================
'===============================================================================
' change path to your user directory...
open ".\Uniques\sevens.txt" for output as #1
    for count = 1 to ubound(sevens(0))
        if sevens(count)<>0 then print #1,sevens(count)
    next
close #1
'===============================================================================
'===============================================================================
'===============================================================================
'===============================================================================
' change path to your user directory...
open ".\Uniques\Uniques.txt" for output as #1
    for count = 1 to ubound(sevens(0))
        print #1, ones(count) , twos(count) , threes(count) , fives(count) , sevens(count)
    next
close #1
'===============================================================================
'===============================================================================
'===============================================================================
'===============================================================================
print
print "!!!~~finished~~!!!"
print
print "printed data to:"
print ".\Uniques\*.txt"
print
print "open file with 'wordpad' to preserve the number spacing."
print
print "press a key to end..."

SLEEP
END



@Richard :
I got a thought about maybe using a different number base to solve for the primes.
How would you convert a base 10 into a base 3 ??
Richard
Posts: 3047
Joined: Jan 15, 2007 20:44
Location: Australia

Re: 1 Billion digit prime

Postby Richard » Apr 07, 2012 22:06

@ Albert. I mentioned earlier in this thread;
If you write a number in base b and it ends in 0 then that number is divisible by b.
Consider writting your integer p in base q, where q ranged from 3 to Sqr(p) in steps of 2.
Changing the base from b to b+2 may be quite a fast process compared to a division.
I think it may be done in linear time, not time squared.
Your challenge is to write that code, I wrote it back in the early 1980s but have lost it and forgotten exactly how I did it.
albert
Posts: 5927
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: 1 Billion digit prime

Postby albert » Apr 07, 2012 22:31

I did a base expansion of , 2 , 4, 8 , 16
I used an "_" for zero and "A" for 1

There doesn't seem to be much more of a pattern than with decimal.
How do you convert decimal to base3 , base5 , base7 ???? Some pattern might show up with different bases???

Code: Select all


dim as ulongint low  =   0  'change here to set low position
dim as ulongint high = 256  'change here to set finish position

dim as string base2
dim as string base4
dim as string base8
dim as string base16

dim as string test
dim as ulongint place

dim as ulongint prime
dim as ulongint count

dim as string divisors
dim as string str1 = ""
dim as ulongint dec

prime = low
do 
    divisors = right( string(len(str(high))," ") + str(prime) , len(str(high)) ) + ": "
    count=0
    for a as ulongint = 1 to prime
        str1 = str(prime/a)
        dec  = instr(1,str1,".")
        if dec=0 then count+=1
        if dec=0 and count>=1 then divisors+= str1+" "
    next
   
    if count=2 then
       
        base2 = right(string(16,"0") +  bin(prime) ,16 )
       
        'convert binary to base 4
        base4 = string(16,"_")
        place = 16
        for a as integer = len(base2) to 1 step -2
            test = mid(base2,a-1,2)
            select case test
                case "00" : mid(base4,place,1)="_"
                case "01" : mid(base4,place,1)="A"
                case "10" : mid(base4,place,1)="B"
                case "11" : mid(base4,place,1)="C"
            end select
            place-=1
        next
       
        'convert binary to base 8
        base8 = string(16,"_")
        place = 16
        for a as integer = len(base2) to 1 step -3
            test = mid(base2,a-2,3)
            select case test
                case "000" : mid(base8,place,1)="_"
                case "001" : mid(base8,place,1)="A"
                case "010" : mid(base8,place,1)="B"
                case "011" : mid(base8,place,1)="C"
                case "100" : mid(base8,place,1)="D"
                case "101" : mid(base8,place,1)="E"
                case "110" : mid(base8,place,1)="F"
                case "111" : mid(base8,place,1)="G"
            end select
            place-=1
        next
       
        'convert binary to base 16
        base16 = string(16,"_")
        place = 16
        for a as integer = len(base2) to 1 step -4
            test = mid(base2,a-3,4)
            select case test
                case "0000" : mid(base16,place,1)="_"
                case "0001" : mid(base16,place,1)="A"
                case "0010" : mid(base16,place,1)="B"
                case "0011" : mid(base16,place,1)="C"
                case "0100" : mid(base16,place,1)="D"
                case "0101" : mid(base16,place,1)="E"
                case "0110" : mid(base16,place,1)="F"
                case "0111" : mid(base16,place,1)="G"
                case "1000" : mid(base16,place,1)="H"
                case "1001" : mid(base16,place,1)="I"
                case "1010" : mid(base16,place,1)="J"
                case "1011" : mid(base16,place,1)="K"
                case "1100" : mid(base16,place,1)="L"
                case "1101" : mid(base16,place,1)="M"
                case "1110" : mid(base16,place,1)="N"
                case "1111" : mid(base16,place,1)="O"
            end select
            place-=1
        next
       
        for a as integer = 1 to len(base2)
            if mid(base2,a,1)="0" then mid(base2,a,1)="_"
            if mid(base2,a,1)="1" then mid(base2,a,1)="A"
        next
       
        print
        print divisors
        print base2
        print base4
        print base8
        print base16
       
        'sleep 1000
       
    end if
   
    prime+=1
   
loop until prime>high or inkey<>""

SLEEP
END

frisian
Posts: 249
Joined: Oct 08, 2009 17:25

Re: 1 Billion digit prime

Postby frisian » May 06, 2012 11:03

First let me tell about why I wrote this program.

I have a AMD quad 3.1 Ghz processor, window7 64bit and 4 Gb memory and i like to try out things that are sometimes silly or plain stupid.
And I compile GMP and MPIR with the help of MSYS. Most of the time I use MPIR because it somewhat faster then GMP.

I stopped all programs that weren’t needed, stopped some non essential processes, to free up memory.

I started FBedit, loaded mymultgmp.bas , replaced gmp.bi with mpir.bi (mpir.bi is a copy of gmp.bi, it only point to the mpir library), compile and run.

It read the 200M-1.txt file very fast (about 1 sec.), converting it into a integer took about 2 min.
It read the 200M-2.txt file and converted it and multiplied it and it read the 200M-3.txt file and converted it and multiplied it.
It read the 200M-4.txt file and then it crashed, trying to convert the string into the integer, MPIR

needed more memory than there was available.
GMP/MPIR need real memory, they will not work with virtual memory.

Would it be possible to multiply two 200M digits numbers and save the result.
It crashed trying to convert the integer into a string, it seems that a lot of memory is needed for this conversion.

In order to multiply those big numbers I needed a different approach using disk files and the numbers should be to big.
With some looking around on internet and thinking I came up with the following program.
It could do with some improvements like comments and better naming of variables but it does the job.


Code: Select all

#Include Once "mpir.bi"
'#Include Once "gmp.bi"  ' is slower

#Macro initbig ( big_int)
Dim As Mpz_ptr big_int = Allocate( Len( __mpz_struct))
Mpz_init(big_int)
#EndMacro

initbig(mul_1)
initbig(mul_2)
initbig(big_answer)
initbig(q)
initbig(r)

Const ext As String = ".txt"
Const in_file As String = "200M-"
Const out_file As String = "part#"

Dim As Integer total, index, next_file=2, y, limit = 50000000
Dim As Double t1=Timer,t2
Dim As UByte ff = FreeFile
Dim As String partial
Dim text As ZString Ptr
text = Allocate(200002000+limit)  ' must be big enough to hold the product of a 200M digit * 50M digit

number
                                  ' if it's to small it will truncate the result
Mpz_set_ui(mul_1,10)
Mpz_pow_ui(mul_1, mul_1, limit)

' read first input file and chop it up in smaller files

Print "reading "+in_file+"1"+ext, Time
Open in_file+"1"+ext For Input As #ff
Line Input #ff,*text
Close #ff
Mpz_set_str(big_answer,*text,10)
Print "converting into smaller files",time
Do While (Mpz_cmp_ui(big_answer, 0) > 0)
   index += 1
   Mpz_tdiv_qr(q, r, big_answer, mul_1)
   Gmp_sprintf (text,"%Zd", r)
   Open out_file+Str(index)+ext For Output As #ff
   Print #ff,*text
   Close #ff
   Mpz_swap(big_answer, q)
Loop

total = index

Do
   index = 1
   Print"-------------------------------------------"
   Print "read "+in_file;Str(next_file);",assign to mul_2", Time
   Open in_file+Str(next_file)+ext For Input As #ff
   Line Input #ff,*text
   Close #ff
   Mpz_set_str(mul_2,*text,10)
   Mpz_set_ui(q,0)
   For y = 1 To total
      Open out_file+Str(y)+ext For Input As #ff
      Line Input #ff,*text
      Close #ff
      Print "multiplying file "+out_file;Str(y), Time
      Mpz_set_str(mul_1, *text, 10)
      Mpz_mul(big_answer, mul_2, mul_1)
      Mpz_add(big_answer, big_answer, q)
      Mpz_set_ui(mul_1,10)
      Mpz_pow_ui(mul_1, mul_1, limit)
      Mpz_tdiv_qr(q, r, big_answer, mul_1)
      Gmp_sprintf (text,"%Zd", r)
      Print "writing file "+out_file;Str(index), Time
      Open out_file+Str(y)+ext For Output As #ff
      Print #ff,*text
      Close #ff
      index += 1
   Next y

   Do While (Mpz_cmp_ui(q, 0) > 0)
      Mpz_swap(big_answer, q)
      Mpz_tdiv_qr(q, r, big_answer, mul_1)
      Gmp_sprintf (text,"%Zd", r)
      Print "writing file "+out_file;str(index), Time
      Open out_file+Str(index)+ext For Output As #ff
      Print #ff,*text
      Close #ff
      index += 1
   Loop

   total = index - 1
   next_file += 1

Loop Until next_file > 5

t2 = Timer

' free memory
Mpz_clear (mul_1)
Mpz_clear (mul_2)
Mpz_clear (big_answer)
Mpz_clear (q)
Mpz_clear (r)
DeAllocate(text)

Print
Print "start making big number",time
Print

Open out_file+Str(total)+ext For Input As #ff

Dim As UByte f_out = FreeFile
Open "all.txt" For Output As #f_out

Line Input #ff,partial
Close #ff
Print #f_out,partial;

For y = total-1 To 1 Step -1
   Print "adding "+out_file;Str(y)
   Open out_file+Str(y)+ext For Input As #ff
   Line Input #ff,partial
   Close #ff
   If (Len(partial) < limit) Then
      partial = String( limit-Len(partial),"0")+partial
   EndIf
   Print #f_out,partial;
   partial = ""
Next y

Print #f_out,

Close #f_out

Print
Print "all done",Time
Print
Print Using "               time for multiplying = ######.## sec.";t2-t1
Print Using "time for construction of big number = ######.## sec.";Timer-t2

Print
Print "finished  -= hit any key to stop =-"
Sleep
End


It start by chopping up 200M-1.txt in smaller pieces and save them on a disk, I took 50M digits pieces, (if needed you can make them bigger or smaller).
Then it reads 200M-2.txt and convert it into a big integer, it then read the first of the smaller pieces from the disk and also converts it into a big integer.
It multiplies those two integers and splits the answer into a quotient and a remainder that has the same size of the file.
The remainder is converted to a string and written to the file, the quotient is the carry and will be added after the next multiplication.
This process is repeated until a files are used, the quotient is then split op in smaller pieces and written to the disk.
The whole process is then repeated with the next 200M- file until all 200M- files are used.

The files have to be combined to form the answer, first try was to create a big string to be written to the disk, but this failed when the two last files needed to be added.
Now the files a read into a string and then the string is printed to a result file blocking a newline with ;.

And after 1 hour and 47 minutes I have a file with a file size of 1000004484 containing a number of 1000004482 digits.
It start with 3899296143281541443869942584513190028750... and it ends with
...5643439441859458231147165606894306438790
Can't do anything with it, it will not load in notepad and notepad++ (notepad++ has even problems with a 50M digit file).

Only one question remains is the result correct, the only way to check the result is to use the sum of digits method (the only way I know off).
So I made a program to check the result. You have to look for yourself to see of the result is correct.

Code: Select all

Function sod(number As LongInt) As Integer

   Dim As Integer x, sum
   Dim As String str1 = Str(number)

   For x = 0 To Len(str1)-1
      sum += str1[x]-48
   Next

   If sum > 9 Then sum = sod(sum)
   If sum = 0 Then sum += 9

   Return sum

End Function
'=====================================================================

Const ext As String = ".txt"
Const in_file As String = "200M-"

Dim As String part
Dim As UByte tmp, ff = FreeFile
Dim As Integer M(5), x, y
Dim As LongInt sum

For x = 1 To 5

   Print in_file+Str(x)+ext,
   Open in_file+Str(x)+ext For Input As #ff
   Line Input #ff,part
   Close #ff

   Print "file length =";Len(part),
   sum = 0

   For y = 0 To Len(part)-1
      sum += part[y]-48
   Next y

   M(x) = sod(sum)
   Print "sum of digits =";M(x)
Next x

Print
Print "multiply the sum of the 5 files"
Print M(1);" *";M(2);" *";M(3);" *";M(4);" *";M(5);" =";
sum = M(1)*M(2)*M(3)*M(4)*M(5)
Print sum;", the sum of the digits =";sod(sum)
Print

sum = 0

Open "all"+ext For Binary Access Read As #ff

Print "calculate sum of the digits of all.txt"
Print "file is over 1 000 000 000 digits."
Print "this will take a while, about 45 min. on a AMD quad 3.1 Ghz. with -gen gcc -O max"
Print "can't read the file into memory, not enough memory"
Print
Print "starting time = ";time

' need to subtract 2 for the length of the file (newline "\r\n")
For ll As LongInt = 1 To Lof(ff)-2
   Get #ff, ll, tmp
   sum += (tmp - 48)
Next ll
Close #ff
print "finished ";time
Print "sum of digits for all.txt =";sod(sum)

Print "if both numbers a equal then its look if all.txt contains the correct answer"
Print "but method used is very simple so there is no 100% guarantee"

Print
Print "finished  -= hit any key to exit program =-"

Sleep
End


It will take a about 25 min. to calculate the sum of digits for the 1G digit file.
The sum for the five 200M is 3 and the sum for the 1G digit file is 3, they are equal so the result is correct.
Happy no, when the smaller files are in a wrong way assembled then the sum would still be 3 (123 gives the same result as 321 or 213 etc.)
If someone knows a better way let me know.

owen

After seeing the speed of my program works and the things I tried I guess is that your program could do it in less then 2 hours, the only unknown factor would be the conversion from big integer into string.

Regard


P.S I think that I stick to things like calculating PI with 10 million digits or something in that order.

Forgot to mentions that the version of GMP I had crashed (right in the beginning, had no idea why).
I downloaded GMP version 5.0.4 that worked without problems. I don't know if earlier versions of GMP will work with my program.
owen
Posts: 555
Joined: Apr 19, 2006 10:55
Location: Kissimmee, FL
Contact:

Re: 1 Billion digit prime

Postby owen » May 06, 2012 22:06

frisian thank you for being the first person to address my request.
if possible please keep hold of that number.
i hope to compare my results with yours in the near future.
i was unaware of MPIR so i'll be checking that out right away.
www.mpir.org

i wonder if i can utilize mpir's memory management function (if any) in order to crunch the multiple on my older win xp system. win xp unlike win 7 has limitation of 3 gig ram i think and win 7 might be 8 gig. new mac os supposedly will handle 16 gig ram.

might be some time before i can produce the product an get back to you.

thanks again.

owen
frisian
Posts: 249
Joined: Oct 08, 2009 17:25

Re: 1 Billion digit prime

Postby frisian » Apr 07, 2014 18:03

Faster version.
This one avoids the conversion from binary to decimal and from decimal to binary by save as hexadecimals.
One byte is two hexadecimal, byte to decimal takes a lot of calculations.
The only time the parts are converted to to decimal is when the final answer is constructed.
Timing: 2612.8 sec. for the multiplying and 1010.2 sec. for constructing the answer.
In total 3623 sec. in other words 1 hour and 23 sec. a great improvement over the original 1 hour and 47 minutes.

Code: Select all

#Include Once "mpir.bi"  ' or "gmp.bi"

#Macro initbig ( big_int)
Dim As Mpz_ptr big_int = Allocate( Len( __mpz_struct))
Mpz_init(big_int)
#EndMacro

initbig(mul_1)
initbig(mul_2)
initbig(big_answer)
initbig(div)
initbig(q)
initbig(r)

Const ext As String = ".txt"
Const in_file As String = "200M-"
Const out_file As String = "part#"

Dim As Integer total, index, next_file=2, y, limit = 50000500
Dim As Double t1 = Timer, t2
Dim As UByte ff = FreeFile
Dim text As ZString Ptr
text = Allocate(200002000)  ' must be big enough to hold a 200M digit number
' if it's to small it will truncate the input/result
Mpz_set_ui(mul_1,10)
Mpz_pow_ui(div, mul_1, limit)

' read first input file and chop it up in smaller files

Print "reading "+in_file+"1"+ext, Time
Open in_file+"1"+ext For Input As #ff
Line Input #ff, *text
Close #ff
Mpz_set_str(big_answer,*text,10)
Print "converting into smaller files",Time
Do While (Mpz_cmp_ui(big_answer, 0) > 0)
  index += 1
  Mpz_tdiv_qr(q, r, big_answer, div)
  Gmp_sprintf (text,"%ZX", r) ' save as hexadecimal number
  Open out_file+Str(index)+ext For Output As #ff
  Print #ff,*text
  Close #ff
  Mpz_swap(big_answer, q)
Loop

total = index

Do
  index = 1
  Print"-------------------------------------------"
  Print "read "+in_file;Str(next_file);",assign to mul_2", Time
  Open in_file+Str(next_file)+ext For Input As #ff
  Line Input #ff,*text
  Close #ff
  Mpz_set_str(mul_2, *text, 10)
  Mpz_set_ui(q,0)
  For y = 1 To total
    Open out_file+Str(y)+ext For Input As #ff
    Line Input #ff,*text
    Close #ff
    Print "multiplying file "+out_file;Str(y), Time
    Mpz_set_str(mul_1, *text, 16)  ' string is hexadecimal
    Mpz_mul(big_answer, mul_2, mul_1)
    Mpz_add(big_answer, big_answer, q)
    Mpz_tdiv_qr(q, r, big_answer, div)
    Gmp_sprintf (text,"%ZX", r) ' save as hexadecimal number
    Print "writing file "+out_file;Str(index), Time
    Open out_file+Str(y)+ext For Output As #ff
    Print #ff, *text
    Close #ff
    index += 1
  Next y

  Do While (Mpz_cmp_ui(q, 0) > 0)
    Mpz_swap(big_answer, q)
    Mpz_tdiv_qr(q, r, big_answer, div)
    Gmp_sprintf (text,"%ZX", r)
    Print "writing file "+out_file;Str(index), Time
    Open out_file+Str(index)+ext For Output As #ff
    Print #ff,*text
    Close #ff
    index += 1
  Loop

  total = index - 1
  next_file += 1

Loop Until next_file > 5

t2 = Timer

' free memory
Mpz_clear (mul_1)
Mpz_clear (mul_2)
Mpz_clear (div)
Mpz_clear (q)
Mpz_clear (r)

Print
Print "start makeing bignumber",Time
Print

Open out_file+Str(total)+ext For Input As #ff
Dim As UByte f_out = FreeFile
Open "all.txt" For Output As #f_out


Line Input #ff, *text
Close #ff
Mpz_set_str(big_answer, *text, 16) ' read hex string in and convert to decimal
Gmp_sprintf (text,"%Zd", big_answer)
Print #f_out, *text;

For y = total-1 To 1 Step -1
  Print "adding "+out_file;Str(y)
  Open out_file+Str(y)+ext For Input As #ff
  Line Input #ff, *text
  Close #ff
  Mpz_set_str(big_answer, *text, 16) ' read hex string in and convert to decimal
  Gmp_sprintf (text,"%Zd", big_answer)
  If (Len(*text) < limit) Then
    *text = String( limit - Len(*text), "0") + *text
  EndIf
  Print #f_out, *text;
  *text = ""
Next y

Print #f_out,

Close #f_out

Mpz_clear (big_answer)
DeAllocate(text)

Print
Print "all done",Time
Print
Print Using "               time for multiplying = ######.## sec.";t2-t1
Print Using "time for construction of big number = ######.## sec.";Timer-t2

Print
Print "finished  -= hit any key to stop =-"
Sleep
End
owen
Posts: 555
Joined: Apr 19, 2006 10:55
Location: Kissimmee, FL
Contact:

Re: 1 Billion digit prime

Postby owen » Apr 07, 2014 18:32

Did u get the same results ie what are the first and last 10 digits of the number.
frisian
Posts: 249
Joined: Oct 08, 2009 17:25

Re: 1 Billion digit prime

Postby frisian » Apr 07, 2014 19:23

owen wrote:Did u get the same results ie what are the first and last 10 digits of the number.


I have checked the result against the result of my first program (by means of good old FC) they where identical.
I also run my control program and the results where also identical. If the numbers in 200M*.txt are correct then my conclusion is that the result given must be correct.

The resulting number will not load into a word processor it is simply to big.

Return to “Community Discussion”

Who is online

Users browsing this forum: No registered users and 9 guests