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

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

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

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

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

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

@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

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

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 needsdim 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 testdim as ulongint countprint "  unique 1's    unique 2's     unique 3's     unique 5's     unique 7's"    one   = 1*lowtwo   = 2*lowthree = 3*lowfive  = 5*lowseven = 7*lowcount = lowfor 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 + 1next'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)    nextclose #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)    nextclose #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)    nextclose #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)    nextclose #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)    nextclose #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)    nextclose #1'==============================================================================='==============================================================================='==============================================================================='===============================================================================printprint "!!!~~finished~~!!!"printprint "printed data to:"print ".\Uniques\*.txt"printprint "open file with 'wordpad' to preserve the number spacing."printprint "press a key to end..."SLEEPEND`

@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

@ 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

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 positiondim as ulongint high = 256  'change here to set finish positiondim as string base2dim as string base4dim as string base8dim as string base16dim as string testdim as ulongint placedim as ulongint primedim as ulongint countdim as string divisorsdim as string str1 = ""dim as ulongint decprime = lowdo      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<>""SLEEPEND`
frisian
Posts: 249
Joined: Oct 08, 2009 17:25

### Re: 1 Billion digit prime

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)#EndMacroinitbig(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,t2Dim As UByte ff = FreeFileDim As String partialDim text As ZString Ptrtext = 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 resultMpz_set_ui(mul_1,10)Mpz_pow_ui(mul_1, mul_1, limit)' read first input file and chop it up in smaller filesPrint "reading "+in_file+"1"+ext, TimeOpen in_file+"1"+ext For Input As #ffLine Input #ff,*textClose #ffMpz_set_str(big_answer,*text,10)Print "converting into smaller files",timeDo 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)Looptotal = indexDo   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 += 1Loop Until next_file > 5t2 = Timer' free memoryMpz_clear (mul_1)Mpz_clear (mul_2)Mpz_clear (big_answer)Mpz_clear (q)Mpz_clear (r)DeAllocate(text)PrintPrint "start making big number",timePrintOpen out_file+Str(total)+ext For Input As #ffDim As UByte f_out = FreeFileOpen "all.txt" For Output As #f_outLine Input #ff,partialClose #ffPrint #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 yPrint #f_out,Close #f_outPrintPrint "all done",TimePrintPrint Using "               time for multiplying = ######.## sec.";t2-t1Print Using "time for construction of big number = ######.## sec.";Timer-t2PrintPrint "finished  -= hit any key to stop =-"SleepEnd`

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 sumEnd Function'=====================================================================Const ext As String = ".txt"Const in_file As String = "200M-"Dim As String partDim As UByte tmp, ff = FreeFileDim As Integer M(5), x, yDim As LongInt sumFor 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 xPrintPrint "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)Printsum = 0Open "all"+ext For Binary Access Read As #ffPrint "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"PrintPrint "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 llClose #ffprint "finished ";timePrint "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"PrintPrint "finished  -= hit any key to exit program =-"SleepEnd`

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

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

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)#EndMacroinitbig(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 = 50000500Dim As Double t1 = Timer, t2Dim As UByte ff = FreeFileDim text As ZString Ptrtext = Allocate(200002000)  ' must be big enough to hold a 200M digit number' if it's to small it will truncate the input/resultMpz_set_ui(mul_1,10)Mpz_pow_ui(div, mul_1, limit)' read first input file and chop it up in smaller filesPrint "reading "+in_file+"1"+ext, TimeOpen in_file+"1"+ext For Input As #ffLine Input #ff, *textClose #ffMpz_set_str(big_answer,*text,10)Print "converting into smaller files",TimeDo 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)Looptotal = indexDo  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 += 1Loop Until next_file > 5t2 = Timer' free memoryMpz_clear (mul_1)Mpz_clear (mul_2)Mpz_clear (div)Mpz_clear (q)Mpz_clear (r)PrintPrint "start makeing bignumber",TimePrintOpen out_file+Str(total)+ext For Input As #ffDim As UByte f_out = FreeFileOpen "all.txt" For Output As #f_outLine Input #ff, *textClose #ffMpz_set_str(big_answer, *text, 16) ' read hex string in and convert to decimalGmp_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 yPrint #f_out,Close #f_outMpz_clear (big_answer)DeAllocate(text)PrintPrint "all done",TimePrintPrint Using "               time for multiplying = ######.## sec.";t2-t1Print Using "time for construction of big number = ######.## sec.";Timer-t2PrintPrint "finished  -= hit any key to stop =-"SleepEnd`
owen
Posts: 555
Joined: Apr 19, 2006 10:55
Location: Kissimmee, FL
Contact:

### Re: 1 Billion digit prime

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

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.