## 1 Billion digit prime

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

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.

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

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 )

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

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.

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

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.

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

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

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.

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

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

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

@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 ??

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

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

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.

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

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

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

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.

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.

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.

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

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

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

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

### Re: 1 Billion digit prime

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

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

Return to “Community Discussion”

### Who is online

Users browsing this forum: No registered users and 9 guests