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.
1 Billion digit prime
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
The beauty of primes is that they cannot be easily predicted.Albert wrote:Isn't there some type of math formula to figure primes??
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
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
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
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
EndRe: 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
I have checked the result against the result of my first program (by means of good old FC) they where identical.owen wrote:Did u get the same results ie what are the first and last 10 digits of the number.
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.