[QUOTE=VBCurtis;474725]Try 10,000 digits. Then try 100,000. Then consider how much
longer the second case takes, extrapolate. [/QUOTE]This is wise. Also, you should test your machine to ensure that it is stable. Doing some double checks is useful. Also testing known primes and known composites with your software is a useful check.

@OP:
Your best computer can do one iteration in ~16ms, according with the benchmark you posted. To test a number with 100 million digits with the known best algorithm and program (that is LL test, and P95) you will need to do about 350 million iterations. Because your exponent is in the range of 350 million. That is, it will take [U]that particular[/U] computer, 350 000 000 * 0.016 = 5 600 000 million seconds. Or, about 1600 hours. Or, about 65 days.

To test a billion digits number, your exponent is 10 times larger, that is in the range of 3.4 gigs. Your number has [U]ten times[/U] a hundred million digits. A single iteration for such a monster would take more than 20 times longer, but say for the sake of the calculus that you can improve the algorithm, and get a faster computer, such that the iteration time grows only ten times. That is 160 milliseconds per iteration. In that case, you will need to do ~3.4 billion iterations, and that makes 3 400 000 000 * 0.16 = 544 million seconds, or about 156 thousand hours, or about 6300 days, or about 17 years.

If my calculus is right, that is the time you will need with a computer much faster than you have (but still in reasonable limits to buy in a specialized shop) to test a billion digit number with current known math.

Mind that the 160ms per iteration is exaggeratedly optimistic. That is because multiplication algorithm is not linear. Think about like that: with the school grade algorithm, when you double the number of digits, you need to do four times more multiplications. To multiply 3 time 5 you do a single multiplication, but to multiply 37 * 54 you do four multiplications (4*7, 4*3, 5*7, 5*3) and then add the stuff shifted respectively. Now, if you have 10 times more digits, you will have to do (school grade) 100 times more multiplications. Now, well, we do not make school grade multiplications here, that would be so slow that we would not be able to test even numbers with a single million digits. We do some tricks called Fast Fourier Transformation (FFT) to speed up the multiplications. But yet, when your numbers grows 10 times in size (like from 10 digits to 100 digits), the speed goes more than 10 times slower. Not 100 times slower, like it would be with school-grade (try to do a 100 digits multiplication by hand!), but yet, more than 10 times slower. Depending on the size of the numbers, it can be anything between 20 and 50 times slower.

Therefore, my calculus with 160 ms per iteration is extremely optimistic, you can better count on something like 30 years, instead of 17.

And that is for a single test. You don't need PhD in physics and math to make all this calculus.

Therefore, don't get upset if people here start making fun of you. We are kinda tough community here, and what you claim is really funny. :razz:

[QUOTE=evanh;474708]I think there is a miscommunication I am [b]not[/b] referring to [b]a billion digit exponent[/b]....[/QUOTE][QUOTE=evanh;474650]... a [b]1Billion digit exponent[/b]...[/QUOTE]Hence the confusion.

[QUOTE=LaurV;474771]@OP:
Your best computer can do one iteration in ~16ms, according with the benchmark you posted. To test a number with 100 million digits with the known best algorithm and program (that is LL test, and P95) you will need to do about 350 million iterations. Because your exponent is in the range of 350 million. That is, it will take [U]that particular[/U] computer, 350 000 000 * 0.016 = 5 600 000 million seconds. Or, about 1600 hours. Or, about 65 days.

To test a billion digits number, your exponent is 10 times larger, that is in the range of 3.4 gigs. Your number has [U]ten times[/U] a hundred million digits. A single iteration for such a monster would take more than 20 times longer, but say for the sake of the calculus that you can improve the algorithm, and get a faster computer, such that the iteration time grows only ten times. That is 160 milliseconds per iteration. In that case, you will need to do ~3.4 billion iterations, and that makes 3 400 000 000 * 0.16 = 544 million seconds, or about 156 thousand hours, or about 6300 days, or about 17 years.

If my calculus is right, that is the time you will need with a computer much faster than you have (but still in reasonable limits to buy in a specialized shop) to test a billion digit number with current known math.

Mind that the 160ms per iteration is exaggeratedly optimistic. That is because multiplication algorithm is not linear. Think about like that: with the school grade algorithm, when you double the number of digits, you need to do four times more multiplications. To multiply 3 time 5 you do a single multiplication, but to multiply 37 * 54 you do four multiplications (4*7, 4*3, 5*7, 5*3) and then add the stuff shifted respectively. Now, if you have 10 times more digits, you will have to do (school grade) 100 times more multiplications. Now, well, we do not make school grade multiplications here, that would be so slow that we would not be able to test even numbers with a single million digits. We do some tricks called Fast Fourier Transformation (FFT) to speed up the multiplications. But yet, when your numbers grows 10 times in size (like from 10 digits to 100 digits), the speed goes more than 10 times slower. Not 100 times slower, like it would be with school-grade (try to do a 100 digits multiplication by hand!), but yet, more than 10 times slower. Depending on the size of the numbers, it can be anything between 20 and 50 times slower.

Therefore, my calculus with 160 ms per iteration is extremely optimistic, you can better count on something like 30 years, instead of 17.

And that is for a single test. You don't need PhD in physics and math to make all this calculus.

Therefore, don't get upset if people here start making fun of you. We are kinda tough community here, and what you claim is really funny. :razz:[/QUOTE]

Also consider that what Laurv just wrote is valid using prime95 on a candidate of the form 2^p - 1. If, as you just said, your number is not of that form (2^p - C, C != 1), your timings would grow another 30% (if using a LLR test).

Luigi

[QUOTE=retina;474772]Hence the confusion.[/QUOTE]


I see, that is my fault, I apologize.

I think I may have confused myself during that post. I was looking for an exponent that would produce a billion digit number and I think I was finding that it would take an exponent over 1 billion, probably around 3 billion... as an exponent.. I was using Maple to find such an exponent that would produce a billion digit number but I could only find 999,xxx,xxx digits... I guess thats where Maple stops because when I increased the exponent every so slightly it stops giving me an answer there.

Thank you for pointing out my miscommunication, I appreciate it.

[QUOTE=Uncwilly;474735]This is wise. Also, you should test your machine to ensure that it is stable. Doing some double checks is useful. Also testing known primes and known composites with your software is a useful check.[/QUOTE]

So far my iMac has a Verified M45305383, Unverified M81540187, and a Mismatch M48025451 as result types. Not sure what Mismatch is I haven't been able to find any literature on it yet.

Is there a link that anyone can provide that explains what the "residue", "shift", "type", and "results" all mean on the "primenet exponent status" page?


When using my software for my personal prime search I have been checking against known primes and not-primes(composites?) before attempting to locate a prime. I really wish there was a way to save the progress and see a completion date in the Maple software... While Prime95 seems to be CPU heavy, Maple seems to be RAM heavy and spares the CPU, even when I ran Maple in terminal mode.

[QUOTE=LaurV;474771]@OP:
Your best computer can do one iteration in ~16ms, according with the benchmark you posted. To test a number with 100 million digits with the known best algorithm and program (that is LL test, and P95) you will need to do about 350 million iterations. Because your exponent is in the range of 350 million. That is, it will take [U]that particular[/U] computer, 350 000 000 * 0.016 = 5 600 000 million seconds. Or, about 1600 hours. Or, about 65 days.

To test a billion digits number, your exponent is 10 times larger, that is in the range of 3.4 gigs. Your number has [U]ten times[/U] a hundred million digits. A single iteration for such a monster would take more than 20 times longer, but say for the sake of the calculus that you can improve the algorithm, and get a faster computer, such that the iteration time grows only ten times. That is 160 milliseconds per iteration. In that case, you will need to do ~3.4 billion iterations, and that makes 3 400 000 000 * 0.16 = 544 million seconds, or about 156 thousand hours, or about 6300 days, or about 17 years.

If my calculus is right, that is the time you will need with a computer much faster than you have (but still in reasonable limits to buy in a specialized shop) to test a billion digit number with current known math.

Mind that the 160ms per iteration is exaggeratedly optimistic. That is because multiplication algorithm is not linear. Think about like that: with the school grade algorithm, when you double the number of digits, you need to do four times more multiplications. To multiply 3 time 5 you do a single multiplication, but to multiply 37 * 54 you do four multiplications (4*7, 4*3, 5*7, 5*3) and then add the stuff shifted respectively. Now, if you have 10 times more digits, you will have to do (school grade) 100 times more multiplications. Now, well, we do not make school grade multiplications here, that would be so slow that we would not be able to test even numbers with a single million digits. We do some tricks called Fast Fourier Transformation (FFT) to speed up the multiplications. But yet, when your numbers grows 10 times in size (like from 10 digits to 100 digits), the speed goes more than 10 times slower. Not 100 times slower, like it would be with school-grade (try to do a 100 digits multiplication by hand!), but yet, more than 10 times slower. Depending on the size of the numbers, it can be anything between 20 and 50 times slower.

Therefore, my calculus with 160 ms per iteration is extremely optimistic, you can better count on something like 30 years, instead of 17.

And that is for a single test. You don't need PhD in physics and math to make all this calculus.

Therefore, don't get upset if people here start making fun of you. We are kinda tough community here, and what you claim is really funny. :razz:[/QUOTE]

First of all, thank you for taking the time to type all of this up I really do appreciate it. I have read through it, and I am now going to drink my coffee while I read through it again making sure I completely understand each sentence.. :coffee:

I don't mind if people make fun of me.. I grew up with "[I]sticks and stones may break my bones but words shall never hurt me[/I]". I only ask that if people are going to make fun at least couple it with some constructive criticism so that I may learn something in the process:smile:

Again thank you for the write up.. I am going to take some notes on it and I'll get back to you.

[QUOTE=ET_;474778]Also consider that what Laurv just wrote is valid using prime95 on a candidate of the form 2^p - 1. If, as you just said, your number is not of that form (2^p - C, C != 1), your timings would grow another 30% (if using a LLR test).

Luigi[/QUOTE]

I understand.

You all have been very insightful. I am glad that you all have taken time out of your day to help me better understand.

My iMac is currently running M332xxxxxx on Prime95 as well as a 300M+ exponent in Maple. I did start the Maple calculation a few days after the Prime95 calculation but we'll see how it goes. I know there are a lot of variables that go into comparing the two computations, I just figured since Prime95 is CPU heavy and Maple is RAM heavy why not take advantage of the two programs since they don't hinder each other.

[QUOTE=a1call;474712]Evan,
Have you looked into Pari-Gp.
It's isprime function is deterministic and one of the fastest off the shelf functions for primality testing. For general form primes you can use primo it has limited (but large) parallel processing capability. It can only run on 64 bit Linux machine and will require a few lifetimes to come up with certificates for very large numbers.
IMHO your best chance of proving your 1G dd integer prime is writing your own code using Lucas primally test and not LL test. You will have to write your own code make your own hardware (a PC won't do) and find all the prime factors of n-1 where n is your prime candidate. This could be trivial and virtually instantaneous (relatively speaking) if the C in your formula can be -1.
If you see a discussion about the number of atoms in the universe, you can just ignore them[/QUOTE]

Thank you a1call. I am looking into your suggestions now.

I am new to code but better late than never. It seems like the general theme is a billion digit number will require either a supercomputer or a search to be passed down from generation to generation lol!

Thanks for the input, I will respond again when/if I have questions about Pari-GP

[QUOTE=LaurV;474771]@OP:
Your best computer can do one iteration in ~16ms, according with the benchmark you posted. [/QUOTE]That time is for 4M FFT only. For the required 1Gdigit check the FFT iteration time would be a lot more. Since P95 can't do tests that large the times will have to come from another application. Is there any program currently existing that [i]can[/i] handle numbers of 1Gdigit? A single iteration could take a few minutes. Multiply that by 1G iterations and you need to have the lifetime of a few Methuselahs to see it finish.

[QUOTE=evanh;474793]I understand.

You all have been very insightful. I am glad that you all have taken time out of your day to help me better understand.

My iMac is currently running M332xxxxxx on Prime95 as well as a 300M+ exponent in Maple. I did start the Maple calculation a few days after the Prime95 calculation but we'll see how it goes. I know there are a lot of variables that go into comparing the two computations, I just figured since Prime95 is CPU heavy and Maple is RAM heavy why not take advantage of the two programs since they don't hinder each other.[/QUOTE]

Let me add that

IF (prime-proving requires high-level CPU calculations)
AND (prime95 is CPU heavy)
THEN (prime95 will reach its result much faster than Maple)

and

IF (prime95 proves numbers of the form 2^p - 1)
AND (your number is not of the form 2^p - 1)
THEN (you cannot use prime95 to prove your numbers: the result will be wrong)

I beg your pardon if such syllogisms are already clear to you: having to do daily with students who do not know how computers work, I felt the urge to elaborate. :smile:

Luigi