Operation: Billion Digits

[Gipe]

Originally Posted by Gipe

Reserving 3321929909....

Number now at 2^69, no factor yet....

[Aitsen]

M3321928699 no factor from 2^68 to 2^69.
M3321929053 no factor from 2^68 to 2^69.
M3321929059 no factor from 2^68 to 2^69.
M3321929113 no factor from 2^68 to 2^69.

I'll take M3321929173, M3321929179, M3321929197 and M3321929209 to 69 bits.

Andres

[MrHappy]

Originally Posted by Uncwilly

The other "most wanted updates" are:

3321928381 Starting @ 66 - HiddenWarrior
3321928417 Starting @ 66 - MrHappy
3321928483 Starting @ 66 - Nitro

Even no formal updates would be cool. A new progress graph coming on Friday and these all are the low points.

I currently have no spare processing time for OperationBillionDigits. The exponent is still at 66 bit and may be claimed by someone else.

[Uncwilly]

Here is the latest graph. The orange-brown line is the current. The blue line is the previous update, July 16 (~1 month).

I am willing to hear suggestions on if I should include 1, 2, or more previous graphs.

[Uncwilly]

I'll claim 3321928417 up to 69.

[Aitsen]

M3321929173 no factor from 2^68 to 2^69.
M3321929179 no factor from 2^68 to 2^69.
M3321929197 no factor from 2^68 to 2^69.
M3321929209 no factor from 2^68 to 2^69.

And I reserve M3321929411, M3321929519, M3321929563, M3321929573, M3321929579 and M3321929617. I'll factor these to 69 bits.

Also about the factor of M3321929461 I recently found. I let the program to search up to 68 bits. Shouldn't in the results table be then 68 rather than 67 bits of factored depth?

Cheers,
Andres

[wblipp]

Originally Posted by ET_ and wblipp

wblipp: What methods are you using to filter the k values before determining 2kp+1?

ET_: I'm checking factors mod 120 instead of 1 or 7 mod 8, and apply primality checking up to (around) 7000. Checking for higher factors would slow subsequent modulo operations on the Mersenne number even if it gets a higher number of K sieved out..

I've been thinking about the frequent suggestions we see on the boards about using the Graphical Processing Unit (GPU) in advanced graphics cards for mathematical distributed computing. People usually ask about Lucas-Lehmer tests or Proth tests, and the limited precision of GPUs makes these infeasible.

However, it might be possible to program a Miller-Rabin test for, say, numbers up to 128 bits. Then you could have the GPU perform a PRP test on future trial factors at the same time you were performing a trial factor in the CPU.

To get the best out of this you probably restructure your program to find the next 25 candidates or so. You assign the GPU the first candiate above level 10 that hasn't been PRP'd. If you get to level 15 you start asking the GPU to perform multiple PRP tests on each candidate.

I don't know enough to tell if this is feasible. If it is feasible, then to make it happen, somebody should probably code a GPU Miller-Rabin test and a C wrapper for the communications, then try to get the people that write the Siever and Trial Factor programs in various projects interested in using it.

William

[axn]

Originally Posted by wblipp

However, it might be possible to program a Miller-Rabin test for, say, numbers up to 128 bits. Then you could have the GPU perform a PRP test on future trial factors at the same time you were performing a trial factor in the CPU.

AFAIK, the computations involved in a single iteration of TF is much less than a PRP. So, you might as well do the actual TF using the GPU.

[wblipp]

Originally Posted by axn1

AFAIK, the computations involved in a single iteration of TF is much less than a PRP. So, you might as well do the actual TF using the GPU.

I guess that's right.

I was thinking that the trial divisors are small compared to the Billion Digit candidates, but that isn't the right comparison. If the trial divisor is t, the Miller-Rabin test required us to calculate 3^t mod t, while the trial division requires us to calculate 2^{3,321,928,171} mod t. Since t is much larger the 3,321,928,171, the trial division is faster.

It could still be used - the trial division program would send some tests to the CPU and some to the GPU. It doesn't generalize as well for cross-application to things like the SOB siever, though.

William

[wblipp]

Luigi,

I've been cutting the "d" value from factor3_2 and pasting it into Dario Alpern's Java factoring applet to see how often the d values are really prime. I was surprised to find one of the d values was divisible by 7; another was divisible by 29. Is this supposed to happen, or does it indicate a problem?

William

[wblipp]

Originally Posted by wblipp

Luigi,

I've been cutting the "d" value from factor3_2 and pasting it into Dario Alpern's Java factoring applet

I just realized - perhaps the shown value of "d" is NOT the value presently being tested. Perhaps it's a measure of the range of passed numbers. Is the one being tested always one more "k", or is it more complex than that?

William